Network Effects And Cascading Behaviour
The phenomenon of spreading through networks and cascading behaviors is prevalent in a wide range of real networks. Examples include contagion of diseases, cascading failure of technologies, diffusion of fake news, and viral marketing. Formally, an “infection” event can spread contagion through main players (active/infected nodes) which constitute a propagation tree, known as a cascade. We will examine two model classes of diffusion:
- Decision-based: each node decides whether to activate based on its neighbors’ decisions. Deterministic rule, nodes are active players, and suited for modeling adoption
- Probabilistic: infected nodes “push” contagion to uninfected nodes with some probability. Can involve randomness, nodes are passive, and suited for modeling epidemic spreading
Decision Based Diffusion
Game Theoretic Model of Cascades: single behavior adoption
The key intuition behind the game theoretic model is that a node will gain more payoff if its neighbors adopt the same behavior as it. An example is competing technological products: if your friends have the same type DVD players and discs (e.g. Blu-ray vs. HD DVD), then you can enjoy sharing DVDs with them.
Every node independently decides whether to adopt the contagion depending upon its neighbors. The decision is modelled as a two-player game between a node and a given neighbor. Hence a node with degree plays such games to evaluate its payoff and correspondingly its behavior. The total payoff is the sum of node payoffs over all games.
If there are two behavior and in the network and each node can adopt a single behavior, the payoff matrix for the two-player game is as follows:
A | B | |
---|---|---|
A | a | 0 |
B | 0 | b |
where rows correspond to node ’s behavior, columns correspond to node ’s behavior, and entries represent each node’s payoff.
Let’s analyze a node with neighbors, and let be the fraction of nodes which have adopted . The payoff for choosing is and the payoff for choosing is . Hence the node adopts behavior if the following is met:
We define to be the threshold fraction of a node’s neighbors required for the node to choose i.e. requires .
Example:
Scenario:
- Graph where all nodes start with
- Small set of early adopters of . Hardwire this set such that these nodes will persistently use regardless of payoff -Set and for a small constant . Interpretation: I adopt if more than 50% of my neighbors adopt .
Case Study: Modelling Protest Recruitment on social networks
Undirected network of Twitter users. 70 identified hashtags associated with 2011 Spain anti-austerity protests. For each user (node):
- User activation time = moment when user starts tweeting protest messages
- = total number of neighbors at user activation time
- = number of activate neighbors at user activation time
- Activation threshold = fraction of neighbors that are active at user activation time
Key Insights:
- The distribution of activation threshold had two local peaks: i) at , indicating many self-active users who join with without social pressure ii) at indicating many users join once half their neighbors have. Remainder of distribution mostly uniform.
- A “burst” of neighbors joining the movement has greater impact on users with high threshold and lesser impact on users with low threshold
- Most cascades were small
- Larger cascades were started by users with higher -core number i.e. more central. The -core is defined as the largest connected subgraph where every node has at least degree and can be evaluated by iteratively removing nodes with degree less than .
Extending Game Theoretic Model: multi-behavior adoption
A node can adopt both behaviors and become by paying a cost . The resulting payoff matrix (without cost applied) is as follows:
A | B | AB | |
---|---|---|---|
A | a | 0 | a |
B | 0 | b | b |
AB | a | b | max(a,b) |
Example: Infinite path graph
Let us examine an infinite path graph where everyone begins with behavior/product except for three nodes of the following cases. Let us also set .
Case 1:A-w-B
Payoffs for : , ,
Case 2: AB-w-B
Payoffs for : , ,
The graphs show how different regions of values impact the decision-based diffusion:
- B->A (Direct Conquest): If and are both high, then the cost of being compatible to both products is not worth it and conversion to is direct
- B->AB->A (Infiltration): If is high and is lower, users first transition to before fully committing to