Category Archives: Network Notebook

Semi-structured notes on my Ph.D. thesis work on network science. For an intro, see http://youtu.be/KKrM2c-ww_k

The dampened contagion: spreading memes in an economy of attention

I really enjoyed a recent paper by Nathan Hodas and Kristina Lerman called The Simple Rules of Social Contagion. It resonates strikingly with my own work. They start by asking themselves why is it that “social contagion” (the spreading of memes) does not behave like contagion proper as described by SIR models – in the sense that, for a given network of interactions, social contagion spreads slower than and not as far as actual epidemics. The way they answer this question is really nice, as are they results.

Their results is the following: social contagion effects can be broken down into two components. One is indeed a simple SIR-style epidemic model; the other is a dampening factors that takes into account the cognitive limits of highly connected individuals. The idea here is that catching the flu does not require any expenditure of energy, whereas resharing something on the web does: you had to devote some attention to it before you could make the decision it was worth resharing. The critical point here is this: highly connected individuals (network hubs) are exposed to more information than less connected ones, because their richer web of relationships entails more exposure. Therefore, they end up with a higher attention threshold. So, in contagion proper wherever the infection hits a network hub diffusion skyrockets: hubs unambiguously help the infection spread. In social contagion on hitting a hub diffusion can still skyrocket if the meme makes it past the hub’s attention threshold, but it can also decrease if it does not. Hubs are both enhancers (via connectivity) and dampeners (via attention deficit) of contagion. This way of looking at things resonates with economists: their models work well only where there is a scarce resource (attention).

Their method is also sweet. They consider two social networks, Twitter and Digg. For each they build an exposure response function, which maps the probability of users exposed to a certain URL to retweet it (Twitter) or vote it (Digg). This function is in turn broken into two components: the visibility of incoming messages (exposures) and a social enhancement factor – if you know that your friends are spreading a certain content, you might be more likely to spread it yourself. So, the paper tracks down the visibility of each exposure through a time response function (probability that a user retweets or votes a URL as a function of the time elapsed since exposure and their number of friends). At the highest level, this is modeled as a multiplication: the probability of becoming infected by the meme for a in individual with $n_f$ friends after $n_e$ exposures is the product of the social enhancement factor times the probability of finding $n$ of the $n_e$ exposure occurring during the time interval considered.

At this point, the authors do something neat: they model the precise form of the user response function based on the specific characteristics of the user interfaces of, respectively, Twitter and Digg. For example, in Twitter, they reason, the user is going to scan the screen top to bottom. Her probability of becoming infected by one tweet can be reasonably assumed to be independent of her probability of becoming infected by any other tweet. Suppose the same URL is exposed twice in the user’s feed (which would mean two of the people she follows have retweeted the same URL): then, the overall probability of the user not to become infected is given by the probability of not becoming infected by the first of the tweets times that of not becoming infected by the second tweet. For Digg, they model explicitly the social signal given by “a badge next to the URL that shows the number of friends who voted for the URL”. So, they are accounting for design choices in social software to model how information spreads across it – something I have myself been going on about for a few years now.

This kind of research can be elusive: for example, Twitter is at core a set of APIs that can be queried in a zillion different ways. Accounting for the user interfaces of the different apps people use to look at the Twitter stream can be challenging: the paper itself at some point mentions that “the Twitter user interface offered no explicit social feedback”, and that is not quite the way I perceive it. But never mind that: the route is traced. If you can quantify the effects of user interfaces on the spreading of information in networks, you can also design for the desired effects in a rigorous way. The implication for those of us who care about collective intelligence are straightforward: important conversations should be moved online, where stewardship is easy(-ier) and cheap (-er).

Noted: there are some brackets missing from equation (2).

Explaining diffusion in finite time: “diffusion centrality”

Leave a reply

Many applied mathematicians like to put together their own indicators. In this paper, Banerjee and co-authors made a simple and interesting move that I want to make a note of.

They are interested in the diffusion of participation to microfinance in 43 Indian villages. In each of this case, a microfinance institution would move into the village and identify a person likely to drive participation in that village (they call this person “leader”): the local schoolteacher, or some other respected person. Before the bank moved in, they mapped out social networks in the village. The question they were interested in was: does the centrality of the person the bank talks to first influence the outcome in terms of participation? (Notice how this question brushes aside textbook economics, in that it assumes that participation in the microfinance program spreads across the social network rather than resulting from utility-maximizing decisions made in isolation in response to price signals. We are already in the future of economics.)

To test this hypothesis, you have to pick one measure of centrality. The authors do one better, and make up their own. They imagine a process in which one person is initially informed about the microfinance program. This person than tells her contacts about it with a certain probability p. This is iterated over time periods: in the first period only a fraction p of the initial person’s neighbors learn about the microfinance program, in the second period the information reaches a fraction of those guys neighbors etc. This results in a measure of centrality they call diffusion centrality:

$DC (p, T)=\sum_{t=1}^{T}{p\mathbf{g}^t}$

Where g is the adjacency matrix. My gut reaction to this was: “this is supposed to capture the notion of being connected to central nodes – you are central if you are connected to people who are central, and so on, recursively – so why don’t they just use eigenvector centrality?” Indeed, for T large and p large, this measure converges to eigenvector centrality. But the way diffusion centrality is construed encodes the idea that this all happens in finite time, so that the initial information might not really reach every corner of the network. This makes plenty of sense, because we live in finite time and so do real-world diffusion processes. Statistical tests on the data, indeed, show that diffusion centrality is a better predictor of microfinance participation in villages than eigenvector centrality. The other centrality measures are not even contenders.

What I like about this is that it injects some dynamics in eigenvector centrality, which is essentially a topological (hence static) measure. Moreover, it does so with minimum computational fuss. Well done!

I learned this in yet another MOOC on networks I am taking, this one.

Thinking in networks: what it means for policy makers

Leave a reply

Elegant, influential theories have a way to rewire your brain. In my formative years, it was not uncommon to joke that Marxist intellectuals could and would explain absolutely anything in terms of Marxist dialectics. For all our joking, exactly the same thing happened to me, as I dug deep into neoclassical economic theory. I did have access to non-neoclassical theories, but in the end it is the math that makes the difference. Mathematics gives you a grip on the model: by manipulating it, you can stretch it, adapt it, critique it, own it in a way that you can’t really any other way. In the end, the mathematical tools you use to think about the world become a default way to parse empirical data: when your only tool is a hammer, you see every problem as a nail and all that.

The hammer of neoclassical economics is functions. Not just any old function: convex, continuous, differentiable ones – designer functions with smooth hypersurfaces. If everything is a function of this kind, everything (say, your country’s economy) must have a maximum, because (bounded) continuous, convex and differentiable functions have exactly one max. This means there is a perfect (“optimal”) state of the world. You find it by calculus. You can then hack your way around the system with taxes, subsidies and interest rates until you push the economy to that maximum. If you are a consumer, or a worker, you also will be looking at a function, representing your well-being. Again, you can find its max, fine-tuning savings and consumptions, work and leisure into your personal sweet spot. There’s no such thing as unemployed: hey, the function is not discrete! What you are seeing is people that choose to allocate zero hours to work, given the existing wage rate (I exaggerate, but not much).

I spent the past five years learning how to use a new mathematical tool: networks. Going deep into the intuition of the math (as opposed to memorizing the equations) means, in the long run, a rewiring of your brain. What used to look like a nail suddenly makes much more sense as a screw. A good thing, since you are now the proud owner of a screwdriver! What I am seeing now as I consider public policies is this: I think of them as signals that the policy maker sends out. The interesting question is what carries the signal.

Traditional policy signals are broadcast: every agent in the economy receives the same message. Price signals (hence taxes and subsidies, too) are broadcast. So, in general, is regulation. Broadcast makes a lot of sense in an undifferentiated mean: if you want to reach a large number of recipients and they are all disconnected from each other, it’s a good technique. Just push that signal out in all directions, as loud as you can.

Once you really take networks on board, though, you start seeing them everywhere. And when you have all sorts of networks that could carry the signal for you, broadcast seems a blunt way to do things. Consider AIDS prevention policies. Broadcast policy sees that, as a category young people are more likely than old-timers to engage in unsafe sex, so it puts posters up in high schools. Since you can’t really be too graphic about it for political reasons, such posters tend to be quite bland, and immediately drowned by far stronger broadcasting signals that glorify sexual prowess and availability, those of commercial markets. Even if your average teen does become more careful, the epidemics still spreads through the very promiscuous few, who are unlikely to be impressed by a bland poster. All in all, near-zero impact is a good guess.

On the other hand, research has shown that networks of sexual partnerships are scale-free: a small number of individuals (not categories) have a very large number of sexual partners. These people are the main vector for the virus to spread. So here’s the networked version of AIDS prevention policy: go talk to the hubs. Dispatch researchers to identify them (it does not matter where you start, with scale-free networks it will take a small number of hops before you get to one); have one-on-one conversations with them. Spend time with them, they are important. Show them the data. Hire them, even. Should be cheap: it’s only a handful of people, who can have a disproportionate amount of impact on the epidemics by switching behavior. See the difference in approach?

In my talk at Policy Making 2.0 last week I tried to explore what it means, for policy makers, to think in terms of networks. I proposed that the gains from doing so are:

impact: more bang for your taxpayer buck.
reduced iatrogenics: policy becomes more surgical, so it causes less unintended damage.
robustness to “too big to know”. Very simple network models exhibit sophisticated behavior. You can model several real-world phenomena without losing your grip on the intuition of the model, and therefore make more accountable decision.
compassion. Networks owe their uncanny efficiency in carrying signals to large inequalities in the connectedness of nodes. Further, it is easy to build very simple models that produce inequalities even with identical nodes. This, at least for me, gets rid of the “underserving poor” rhetoric and fosters simpathy towards the smart and hard-working people out there that found themselves on the wrong side of system dynamics.
measurability. Social interactions that happen online are now cheap to keep records of; you can use those record to build networks of interactions run quantitative analysis on them.

If you want to know more, you might find my (annotated) slides interesting. I am indebted, as ever, to the INSITE project and to all participants in Masters of Networks.