CS224W Course Notes
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

93 lines
5.8 KiB

  1. ---
  2. layout: post
  3. title: Network Effects And Cascading Behaviour
  4. header-includes:
  5. - \usepackage{amsmath}
  6. ---
  7. 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:
  8. - Decision-based: each node decides whether to activate based on its neighbors' decisions. Deterministic rule, nodes are active players, and suited for modeling adoption
  9. - Probabilistic: infected nodes "push" contagion to uninfected nodes with some probability. Can involve randomness, nodes are passive, and suited for modeling epidemic spreading
  10. # Decision Based Diffusion
  11. ## Game Theoretic Model of Cascades: single behavior adoption
  12. 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.
  13. 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 $$k$$ plays $$k$$ such games to evaluate its payoff and correspondingly its behavior. The total payoff is the sum of node payoffs over all games.
  14. If there are two behavior $$A$$ and $$B$$ in the network and each node can adopt a single behavior, the payoff matrix for the two-player game is as follows:
  15. | | A | B |
  16. |---|---|---|
  17. | A | a | 0 |
  18. | B | 0 | b |
  19. where rows correspond to node $$v$$'s behavior, columns correspond to node $$w$$'s behavior, and entries represent each node's payoff.
  20. Let's analyze a node with $$d$$ neighbors, and let $$p$$ be the fraction of nodes which have adopted $$A$$. The payoff for choosing $$A$$ is $$apd$$ and the payoff for choosing $$B$$ is $$b(1-p)d$$. Hence the node adopts behavior $$A$$ if the following is met:
  21. $$apd > b(1-p)d \implies p > \frac{b}{a+b}$$
  22. We define $$q = \frac{b}{a+b}$$ to be the **threshold** fraction of a node's neighbors required for the node to choose $$A$$ i.e. requires $$p > q$$.
  23. ### Example:
  24. Scenario:
  25. - Graph where all nodes start with $$B$$
  26. - Small set $$S$$ of early adopters of $$A$$. Hardwire this set such that these nodes will persistently use $$A$$ regardless of payoff
  27. -Set $$a=b-\epsilon$$ and $$q = 0.5$$ for a small constant $$\epsilon>0$$. Interpretation: I adopt $$A$$ if more than 50% of my neighbors adopt $$A$$.
  28. ![Example of decision-based diffusion](../assets/gif/decision_based_network_spreading_example.gif)
  29. ### Case Study: [Modelling Protest Recruitment on social networks](https://arxiv.org/abs/1111.5595)
  30. Undirected network of Twitter users. 70 identified hashtags associated with 2011 Spain anti-austerity protests.
  31. For each user (node):
  32. - User activation time = moment when user starts tweeting protest messages
  33. - $$k_{in}$$ = total number of neighbors at user activation time
  34. - $$k_{a}$$ = number of activate neighbors at user activation time
  35. - Activation threshold $$\frac{k_{a}}{k_{in}}$$ = fraction of neighbors that are active at user activation time
  36. Key Insights:
  37. - The distribution of activation threshold had two local peaks: i) at $$\frac{k_{a}}{k_{in}} \approx 0$$, indicating many self-active users who join with without social pressure ii) at $$\frac{k_{a}}{k_{in}} \approx 0.5$$ indicating many users join once half their neighbors have. Remainder of distribution mostly uniform.
  38. ![Activation threshold distribution](../assets/img/activation_threshold_distribution.jpg)
  39. - A "burst" of neighbors joining the movement has greater impact on users with high threshold and lesser impact on users with low threshold
  40. - Most cascades were small
  41. - Larger cascades were started by users with higher $$k$$-core number i.e. more central. The $$k$$-core is defined as the largest connected subgraph where every node has at least degree $$k$$ and can be evaluated by iteratively removing nodes with degree less than $$k$$.
  42. ![k-core decomposition](../assets/img/k-core.jpg)
  43. ## Extending Game Theoretic Model: multi-behavior adoption
  44. A node can adopt both behaviors and become $$AB$$ by paying a cost $$c$$. The resulting payoff matrix (without cost $$c$$ applied) is as follows:
  45. | | A | B | AB |
  46. |---|---|---|----|
  47. | A | a | 0 | a |
  48. | B | 0 | b | b |
  49. | AB| a | b | max(a,b)|
  50. ### Example: Infinite path graph
  51. Let us examine an infinite path graph where everyone begins with behavior/product $$B$$ except for three nodes of the following cases. Let us also set $$b=1$$.
  52. **Case 1**:**A-w-B**
  53. ![decision_case_1](../assets/img/decision_model_1.png?style=centerme)
  54. Payoffs for $$w$$: $$A: a$$, $$B: 1$$, $$AB: a+1-c$$
  55. ![decision_case_2](../assets/img/decision_model_2.png?style=centerme)
  56. **Case 2**: **AB-w-B**
  57. ![decision_case_3](../assets/img/decision_model_3.png?style=centerme)
  58. Payoffs for $$w$$: $$A: a$$, $$B: 1$$, $$AB: max(a, 1) + 1 -c$$
  59. ![decision_case_4](../assets/img/adoption_graph_general.jpg)
  60. The graphs show how different regions of $$(a,c)$$ values impact the decision-based diffusion:
  61. - B->A (Direct Conquest): If $$a$$ and $$c$$ are both high, then the cost of being compatible to both products is not worth it and conversion to $$A$$ is direct
  62. - B->AB->A (Infiltration): If $$a$$ is high and $$c$$ is lower, users first transition to $$AB$$ before fully committing to $$A$$
  63. # Probabilistic Diffusion
  64. ## Epidemic Model based on Random Trees
  65. ## Basic Reproductive Number $$R_0$$
  66. ## S+E+I+R Models
  67. ### SIR
  68. ### SIS
  69. ### SEIZ
  70. ### Example: rumor spreading
  71. ## Independent Cascade Model
  72. ## Exposure Curves