Graphs can be useful tools in understanding social phenomena. You're probably familiar with some trend or fad that has swept through your social life from music, games, slang, or clothes. Frequently such fads start out with a few early adopters whose friends or acquaintances then adopt the fad, and from there it snowballs. We might also want to think in terms of innovation instead of fads; in this context we can imagine that our early adopters are using some new technology, and over time others in their social network adopt this technology. In either case there is often a communication issue between those who have adopted and those who haven't. It is reasonable to assume this is what fuels fads: if your friend starts using new slang or Facebook 2.0 it will probably help your friendship if you do the same.
To model this we will color vertices in our graph red (R) and blue (B), with red signifying people who have adopted the trend. The initial red vertices will be called early adopters. Each edge (v, u) represents a friendship and comes with a payoff function p(v, u). The payoff function can be thought of as measuring the quality of the friendship or interaction represented by the edge, with 0 being poor and 1 being high. The strength of the trend is given by a parameter t between 0 and 1. The payoff function is defined by:
Call pnet(v, X) = Σp(v,u) the net payoff of vertex v with choice X where X is either R or B. The sum is taken over the neighbors of v. We have the trend spread in discrete steps. At each step v picks its color depending on which net payoff function is larger. In case the two net payoff functions are tied v choses to become red. You should be aware that this setup makes even very strong trends likely to die out if there are few early adopters or if the early adopters are far apart. Below is an example of a trend with strength t = 0.75 spreading (read it left to right). You should think about what might happen if the example started with the early adopter in a different location.
Also test this using two neighboring vertices as early adopters. What changes?
The last activity demonstrates that there is a critical phenomenon at work in this model when the graph is infinite. For small values of t the trend won't spread at all, while for large values of t the trend will spread throughout the entire graph. This change in behavior happens all of a sudden at a specific value of t called the contagion threshold. This name comes from envisioning a virus spreading rather than a trend. At or above the contagion threshold an epidemic ensues. As the activity showed, varying the number of early adopters doesn't change this behavior.
After some thought you might be led to the conclusion that the contagion threshold is at least 1/2. Intuitively, this makes sense as the new trend should be at least as good as the old in order to spread, and on a per-edge basis t ≥ 1/2 is when this happens. It is in fact true that on any infinite graph the contagion threshold is at least 1/2.
To approach this problem we first assume that once a vertex adopts the trend it cannot change back. This doesn't affect the contagion threshold as nothing stranger than oscillations similar to the one in the second activity occur. Next we assume t < 1/2. We let S0 be the early adopters and Si be all the red vertices at the "i"th step. Also, let B(Si) denote the edges with one end in Si and the other end not in Si.
Since we have forbidden the set of red vertices from shrinking we know that once Si = Si-1 for some i the set of red vertices remains unchanged thereafter. This means that for the trend to spread to the entire graph we must have that Si is larger than Si-1 for all i.
Assume this is true. Then for any vertex v in Si-Si-1 we know that v has to have more neighbors in Si than outside Si because having t < 1/2 forces the red neighbors of a vertex to outnumber the blue neighbors in order to adopt the trend. Looking at this over all such v, we can see that B(Si) must be smaller than B(Si-1). If we look at the sequence of numbers { |B(S1)|, |B(S2)|, |B(S3)|, ... }, we know that they are a strictly decreasing sequence of natural numbers. Since there is a smallest natural number, namely 0, this isn't possible! This means that our assumption that Si is always larger than Si-1 must be false, and therefore the set of red vertices must stop growing at some point.
One can also look at the influence model on directed graphs or weighted graphs (or weighted directed graphs). These are very natural assumptions to add. Directed edges help represent one-way interactions like how you might decide to listen to a band based on a review posted on DJ Soandso's website while DJ Soandso doesn't even know you exist. Weights represent strengths of interactions. For instance, one of your friends may have better taste in music than the rest, and so you are more likely to listen to their recommendations. Contagion thresholds don't have the same universal behavior on directed or weighted graphs. In fact given a trend of any strength it is isn't hard to construct directed/weighted graphs for which the trend will spread to all vertices. The last activity explores this a little bit.
For a directed graph the net payoff of a vertex only counts edges going into that vertex. Find a weighted graph (along with a location for the early adopter(s)) for which a trend of any strength t will take over.
For a weighted graph we multiply the payoff associated with an edge by the weight of the edge. For any strength t find a weight w such that the trend will spread throughout the graph below:
