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 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:

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):

Key Insights:

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 decision_case_1

Payoffs for : , ,

decision_case_2

Case 2: AB-w-B decision_case_3

Payoffs for : , ,

decision_case_4

The graphs show how different regions of values impact the decision-based diffusion:

Probabilistic Diffusion

Epidemic Model based on Random Trees

Basic Reproductive Number

S+E+I+R Models

SIR

SIS

SEIZ

Example: rumor spreading

Independent Cascade Model

Exposure Curves