Network Cascades

We can think of networks as a medium where certain information or contagion spreads. You can look at it from different point of views. Cascading behaviour, Diffusion of innovations or failures, network effects or epidemics.

We want to understand and formalise this behaviour and get some insights into this, as its more relevant than ever because of not just pandemics, but because of how important things like viral marketing, fake news, and etc are in the social media era.

Contagion is something that spreads over the edges of the network. It creates a propagation tree or a cascade.

Terminology:

• What spreads: contagion.
• Infection event: adoption, infection, activation
• Main players: infected/active nodes, adopters.

We want to be able to model this diffusion behaviour. There are two kinds of diffusion models. Decision based models and probabilistic models.

In decision based models we allow the nodes to make a decision. A node observes its neighbours behaviour and make its own decision. Things like technology adoption or protest demonstrations come under this.

In probabilistic models, an infected node tries to push the contagion to the uninfected node. Which is more relevant in case of pandemics.

Decision Based Diffusion Models

Let's look at this with a game theoretic approach. Based on 2 player coordination game. A player can only adopt one behaviour from A or B. The key intuition is that you gain more payoff if your friends have adopted the same behaviour as you. We allow each player to play their own game and maximize his payoff.

Examples: vhs vs betamax, blue ray vs hddvd

Let's consider the below payoff matrix for two nodes' behaviours, and we will extend this for a bigger graph.

• if both v and w adopt behavior A, they each get payoff a > 0
• if v and w adopt behavior B, they each get payoff b > 0
• if v and w adopt the opposite behaviours, they each get 0

In a larger network, each node is playing a copy of this game with each of its neighbours, and the payoff will be sum of all node payoffs over all games.

Consider a node in a larger network with d neighbours and p fraction of v's neighbours adopt A and the rest adopt B. The total payoff for v

${\text{payoff}}_v=\{\begin{array}{ll}a.p.d& \text{if v chooses A}\\ b.(1-p).d& \text{if v chooses B}\end{array}$

Hence v chooses A if $p>\frac{b}{a+b}=q$ where p is v's fraction of neighbours with A and q payoff threshold.

Modeling protest recruitment on social networks

From the paper The Dynamics of Protest Recruitment through an Online Network

Tries to model twitter hashtag activism during the Anti-austerity protests. Twitter was used to organize and mobilize users to participate in the protest. The researchers manually selected 70 hashtags that were by the protestors and their timeline. And crawled 581,750 tweets and 90k users related to these hashtags.

They created two networks. Full network: directed twitter follow links, and Symmetric network with only nodes and edges that are symmetric, edge only when both users follow each other. This network represents strong connections only.

We needed the following stats:

• User activation time: moment the user starts tweeting protest message hashtags
• $k_{in}: the total number of neighbors in our network when a user became active
• $k_a$: number of active neighbours when a user became active
• Activation threshold: $k_a/k_{in}$ the fraction of active neighbours when the user becomes active.

Intuitively, a user with less activation threshold he doesn't need much push for him to become active, he posted with no social pressure, and if he started becoming active with activation threshold 0, he's one of the protest organizer or patient zero in case of pandemics .Users with very high activation threshold implies they started becoming active when most of their neighbours are active and high social pressure.

Allow people to Adopt both A and B

Below are the payoffs when you allow a node to adopt both A and B at the same time. But we will introduce a cost c for people to be wanting to adopt both at the same time. A given node can receive 1 from one neighbour and b from another by playing AB, which is why it could be worth the cost c.

With the following payoff matrix when two neighbouring nodes have these adoption strategies

• AB-A: gets a
• AB-B: gets b
• AB-AB: gets max(a, b) and a cost c for the effort of maintaining both strategies.

Each node selects a behaviour that will optimize payoff given what its neighbors did in at a time.

Assume a long chain of nodes, with default adoption of B, then a finite set initially adopts A. we want to know if the A behaviour cascades for various values of a, b and c.

With values $a=3,b=2,c=1$ the cascading stops as shown in the picture after 1 time step.

With values $a=5,b=3,c=1$ the cascading never stops as shown in the picture and eventually every node adopts A.

General Case

Let the payoff matrix for a node w be: A: a, B: 1, AB: a+1-c. With nodes of different adoptions on either side of w. We want to know based on values a and c what will w do.

TODO: Boooringgg

Chapters

1. Introduction, Structure of Graphs
2. Properties of Networks and Random Graph Models
3. Motifs and Structural Roles in Networks
4. Community Structure in Networks
5. Spectral Clustering
6. Message Passing and Node Classification
7. Graph Representation Learning
8. Graph Neural Networks
9. Graph Neural Networks - Pytorch Geometric
10. Deep Generative Models for Graphs
11. Link Analysis: PageRank
12. Network Effects and Cascading Behaviour
13. Probabilistic Contagion and Models of Influence
14. Influence Maximization in Networks
15. Outbreak Detection in Networks
16. Network Evolution
17. Reasoning over Knowledge Graphs
18. Limitations of Graph Neural Networks
19. Applications of Graph Neural Networks