## “Threshold Conditions for Arbitrary Cascade Models on Arbitrary Networks,” B.A. Prakash et al (2011)

No need to separate economics from the rest of the social sciences, and no need to separate social science from the rest of science: we often learn quite a bit from our compatriot fields. Here’s a great example. Consider any epidemic diffusion, where a population (of nodes) is connected to each other (along, in this case, unweighted edges, equal to 1 if and only if there is a link between the nodes). Consider the case where nodes can become “infected” – in economics, we may think of nodes as people or cities adopting a new technology, or purchasing a new product. Does a given seeding on the network lead to an “infection” that spreads across the network, or is the network fairly impervious to infections?

This seems like it must be a tricky question, for nodes can be connected to other nodes in an arbitrary fashion. Let’s make it even more challenging for the analyst: allow there to be m “susceptible” states, an “exposed” state, an “infected” state, and N “vaccinated” states, who cannot be infected. Only exposed or infected agents can propagate an infection, and do so to each of their neighbors in any given period according to probabilities a and b, independently across neighbors. Parameters tell me the probability each agent transitions from susceptible or vaccinated states to other such states.

You may know the simple SIR model – susceptible, infected, recovered. In these models, all agents begin as susceptible pr infected. If my neighbor is infected and I am susceptible, he gives me the disease with probability a. If I am infected, I recover with probability c. This system spreads across the population if the first eigenvalue of the adjacency matrix (which equals 1 if two people are connected, and 0 otherwise) is greater than a/c. (Incredibly, I believe this proof dates back to Kermack and McKendrick in 1927). That is, the only way the network topology matters is in a single-valued summary statistic, the first eigenvalue. Pretty incredible.

The authors of the present paper show that this is a general property. For any epidemic model in which disease spreads over a network such that, first, transmissions are independent across neighbors, and second, one can only enter the exposed or infected state from an exposed or infected neighbor, the general property is the same: the disease spreads through the population if the first eigenvalue of the adjacency matrix is larger than a constant which depends only on model parameters and not on the topology of the network (and, in fact, these parameters are easy to characterize). It is a particularly nice proof. First we compute the probabilities of transitioning from each state to any other. This gives us a discrete-time nonlinear dynamic system. Such systems are asymptotically stable if all real eigenvalues of the nonlinear dynamic are less than one in absolute value. If there are no infections at all, the steady state is just the steady state of a Markov chain: only infected or exposed people can infect me, so the graph structure doesn’t matter if we assume no infections, and transition between the susceptible and vaccinated states are just Markov by assumption. We then note that the Jacobian has a nice block structure which limits the eigenvalues to being one of two types, show that the first type of eigenvalues are always less than one in absolute value, then show that the second types are less than one if and only if a property depending on model parameters only are satisfied; this property has nothing to do with the network topology.

The result tells you some interesting things as well. For example, say you wish to stop the spread of an epidemic. Should you immunize people with many friends? No – you should immunize the person who lowers the first eigenvalue of the adjacency matrix the most. This result is independent of the actual network topology or the properties of the disease (how long it incubates, how fast it transmits, how long people stay sick, how likely they are to develop natural immunity, etc.). Likewise, in the opposite problem, if you wish an innovation to diffuse through a society, how should you organize conferences or otherwise create a network? Create links between people or locations such that the first eigenvalue of the adjacency matrix increases by the highest amount. Again, this is independent of the current network topology or the properties of the particular invention you wish to diffuse. Nice.

Final conference paper from ICDM2011. (No IDEAS version).