Cascading Behavior in Networks: Algorithmic and Economic Issues

# Cascading Behavior in Networks: Algorithmic and Economic Issues [toc] ## 24.1 Introduction The process of new ideas spreading through a population is called the *diffusion of inovation* - begin with some small *early adopters* ## 24.2 A First Model: Networked Coordination Games Let $G=(V,E)$ be the *social network*, $V$ is countably infinite, $v\in V$ has finite neighbors - $A$ be the old behavior - $B$ be the new behavior - a fixed amount $0<q<1$, for $(v,w)\in E$ - if both choose $A$, both receive payoff $q$ - if both choose $B$, both receive payoff $q$ - otherwise, both receive $0$ and the payoff of $v$ is the sum of payoff in the games with $v$'s neighbors. Let $d_v$ be the degree of $v$, $d_v^A$ of $d_v$ choose $A$, $d_v^B$ of $d_v$ choose $B$, then $v$ prefers $B$ if $$ qd_v^A\leq (1-q)d_v^B,\\q\leq\frac{d_v^B}{d_v^A+d_v^B}=\frac{d_v^B}{d_v} $$ where $q$ is called the *threshold*. ### Cascading Behavior Assume nodes change behavior at time $t=1,2,\ldots$. Let finite set $S$ be the initial adopters of $B$, $h^k_q(S)$ be the nodes of $B$ after $k$ successions. We define - $v$ is *converted* by $S$ if $$\exists\,k\in\mathbb{N},\forall\,j\geq k, w\in h_q^j(S)$$ - $S$ is *contagious* with respect to $h_q$ if all nodes are converted by $S$ - the *contagion threshold* of $G$ is $$\sup\{q\mid\exists\,S\mbox{ is contagious with respect to }h_q\}$$ ### Example Let $G=(\mathbb Z,\{\{k,k+1\}\mid k\in\mathbb Z\})$, then $\frac{1}{2}$ is the contagion threshold. ### Progressive Processes Assume nodes of $B$ won't change to $A$ anymore, and define the new process $\overline{h}_q^k$. :::info **Theorem.** For any graph $G$, fix $q$ $$ \exists\,\mbox{a finite contagious set with respect to }h_q\Leftrightarrow\exists\,\mbox{one with respect to }\overline h_q $$ thus $G$ has the same contagion threshold with respect to $h_q$ and $\overline h_q$. **Proof.** The right arrow is trivial. For the other side, assume $S$ is contagious with respect to $\overline h_q$. Since $S$ is contagious, there exists $l\in\mathbb N$ such that $$ N(S)\cup S\subseteq \overline h_q^l(S). $$ Let $T=\overline h_q^l(S)$, and $S_j=\overline h_q^j(S)$, with the fact that $$ \forall\,\mbox{ finite }S,S_j=S\cup h_q(S_{j-1}) $$ that one can prove by induction. Now for $j>l$, $$ S_j=S\cup h_q(S_{j-1})=h_q(S_{j-1}) $$ thus by induction, $$ h_q^{j-l}(T)=h_q^{j-l}(S_l)=S_j\to V\mbox{ as }j\to\infty $$ hence $T$ is contagious. ::: ### Contagion Threshold :::info **Theroem.** For any graph $G$, the contagion threshold of $G$ is at most $\frac{1}{2}$. **Proof.** Let $q>\frac{1}{2}$ and $S$ be finite set of $G=(V,E)$. With the theorem above, $S$ proceeds with respect to $\overline h_q$. Define $$ \delta(X)=\{\{u,v\}\in E\mid u\in X,v\not\in X\},\quad d(X)=|\delta(X)|. $$ Now, claim for $j>0$, $$ S_{j-1}\subsetneq S_j\Rightarrow d(S_j)<d(S_{j-1}). $$ For $v\in S_j\setminus S_{j-1}$, divided $v$'s neighbors into $A_v=\{w\mid w\in S_{j-1}\}$ and $B_v=\{w\mid w\in V\setminus S_j\}$. Since $q>\frac{1}{2}$, we have $|A_v|>|B_v|$. Thus $$ d(S_j)-d(S_{j-1})=\sum_{v\in S_j\setminus S_{j-1}}|B_v|-|A_v|<0. $$ Finally, since $d(S_j)$ is strictly decreases to $0$, $\exists\,k\in\mathbb N$ such that $d(S_k)=0$, thus $S$ is not contigious. ::: ## 24.3 More General Models of Social Contagion - Consider... - directed graphs - contagion processes that are progressive ### A Linear Threshold Models - term - $w$ is a *neighbor* of $v$ if there is an edge $(w, v)$. - $w$ is an *out-neighbor* of $v$ if there is an edge $(v, w)$. - Two ingredients - Nodes weigh the inﬂuences of their neighbors differently. - We have a weight $b_{vw} \ge 0$ on each edge $(w, v)$ - $\sum_{w∈N(v)} b_{vw} ≤ 1$, where $N(v)$ denotes the set of nodes with edges to $v$. - Each node $v$ choose a threshold $θ_v$ uniformly at random from $[0, 1]$ - Now, the progressive dynamics of the behavior operates - Set $S$ starts out adopting $B$. all other nodes start out adopting $A$. - A node is *active* if it is following $B$. - Any inactive node $v$ becomes active if $\sum_{active\space w∈N(v)} b_{vw} ≥ θ_v$. ### A General Threshold Model - Each node $v$ has an arbitrary function $g_v(·)$ - Deﬁned on any set $X ⊆ N(v)$ - $0 \le g_v(X)\le 1$ - Assume that $g_v(·)$ is *monotone*: If $X ⊆ Y$, then $g_v(X) ≤ g_v(Y)$. - Dynamics of adoption proceed - $g_v(·)$ playing the role of the weighed sum. Each $v$ becomes active if its set of active neighbors $X$ satisﬁes $g_v(X) ≥ θ_v$. - The assumption that the threshold is selected uniformly at random is without loss of generality, since other distributions can be represented by modifying $g_v$. ### A Cascade Model - Idea - There is a edge $(u,v)$ s.t. $u$ is active and $v$ is not. - $u$ is given one chance to activate $v$ - probability depends on a set of nodes that have already tried and failed to activate $v$. - In place of a function $g_v$, each node $v$ has an incremental function $p_v(u, X)$, where $u$ is a neighbor of $v$ and $X$ is **a** set of neighbors of $v$ not containing $u$. - $p_v(u, X)$ is the probability that $u$ activates $v$, given that the set $X$ of neighbors has tried and failed. - Only consider $p_v$ that are *order-independent*. :::info One can translate from a set of $p_v$ to a set of $g_v$, and vice versa. **Proof.** ***(i)*** From $g_v$ to $p_v$ Let $X$ be a set that has already tried and failed to activate $v$. $θ_v \in (g_v(X), 1]$. Let $u$ be a node that succeed. $θ_v ≤ g_v(X ∪ \{u\})$. Hence we can deﬁne $p_v(u, X) = \frac{g_v(X ∪ \{u\}) − g_v(X)}{1 − g_v(X)}.$ ![](https://i.imgur.com/MIYzGys.png) ***(ii)*** From $p_v$ to $g_v$ Suppose we have incremental functions $p_v$. Then the probability $v$ is not activated by a set of neighbors $X = \{u_1, u_2, . . . , u_k\}$ is $\prod_{i=1}^k(1 − p_v(u_i, X_{i−1})$, where $X_{i−1} = \{u_1, . . . , u_{i−1}\}$. (Note that *order-independence*) Hence we can deﬁne a threshold function $g_v$ by setting $g_v(X) = 1 −\prod_{i=1}^k(1 − p_v(u_i, X_{i−1})$ ::: ### Progressive vs. Non-progressive processes - Encoding non-progressive processes by a reduction to the progressive case - Given a graph $G$ on which we have a non-progressive process that may run for up to $T$ steps. - Create a graph $G^′$ built from $T$ copies of $G$, labeled $G_1, G_2, . . . , G_T$. - Let $v^{}$ be the copy of node $v$ in $G_i$ - Construct edges $(u^{<i-1>},v^{})$ for each neighbor $u$ of $v$. - As a result, the neighbors of $v^{}$ in $G^′$ are just the copies of $v$’s neighbors that “live” in the previous time-step. - ![](https://i.imgur.com/QN6O2al.png) ## 24.4 Finding Influential Sets of Nodes We now try to find the initial adopters to maximize the number of influenced individuals ### The most influential set of nodes :::info **Definition.** For any Cascade Models, there is a natural *influence function* $f(\cdot)$ defined as follow: * For a set $S$ of nodes, $f(S)$ is the expected number of active nodes at the end of the process * The graphs are finite, so that the number of processes is bounded by number of nodes $n$ ::: Now we try to choose a set $S$ of $k$ initial adopters to maximize $f(S)$ But it's NP-hard to find optimal set $S$ and even to approximate optimal set $S$ for some instances. So we focus on subclasses of models that good approximation results can be obtained ### Submodularity as a route to good approximations We say that a function $f$ is *submodular* if adding an element to a set $Y$ causes a smaller marginal improvement than adding the same element to a subset of $Y$ Express it in mathmatical way, $f$ is submodular if $\forall X \subseteq Y$ and $v \notin Y$ $$ f(X \cup \{v\}) - f(X) \geq f(Y \cup \{v\}) - f(Y) $$ :::info **Theorem.** Let 1. $f$ be a *monotone submodular* function 2. $S^*$ be the $k$-element set achieving maximum value of $f$ 3. $S$ be a $k$-element set obtained by $k$ iterations, each iteration including the element producing the largest increase in $f$ (Can think of $S$ as the result of [**hill-climbing algorithm**](http://snap.stanford.edu/class/cs224w-2015/handouts/influence_maximization-handout.pdf)) Then $f(S) \geq (1-{1 \over e})f(S^*)$ ::: We now proceed with Cascade Model which the influence function $f$ is submodular ### Diminishing returns and submodularity :::success **Diminishing returns.** A incremental function $p_v$ exhibits diminishing returns if $p_v(u,X) \geq p_v(u,Y)$ whenever $X \subseteq Y$ i.e. Node $v$ is harder to be activated by $u$ if more node has tried and failed to activate it ::: Does diminishing returns imply influence function $f$ is submodular ? :::info **Theorem.** For any instance of the Cascade Model in which all the incremental functions $p_v$ exhibit diminishing returns, the resulting influence function $f$ is submodular ::: The proof of this theorem is intricate, so instead we describe the proof of a special case of this theorem. :::success **Independent Cascade Model.** Increment function $p_v$ is independent of nodes that has tried and failed: $p_v(u,X)=p_{uv}$ for some parameter $p_{uv}$ that depends only on $u$ and $v$ Since $p_v(u,X) = p_{uv} = p_v(u,Y)$ whenever $X \subseteq Y$, independent cascade model is a special case that exhibits diminishing returns ::: :::info **Theorem.** For any instance of the *Independent Cascade Model*, the resulting influence function $f$ is submodular **Proof.** 1. Consider a alternate way of viewing the Independent Cascade Process | Standard View | Alternate view | |:---------------------------------------------------------------------------------------------------- |:--------------------------------------------------------------------------------------------------------------------------- | | When node $u$ becomes active, flip a coin of bias $p_{uv}$ to determine whether activating $v$ | for each edge $(u,v)$, flip a coin of bias $p_{uv}$ in advance, only consult the outcome when $u$ becomes active | 2. If there are $m$ edges, then there are $2^m$ possible outcomes of the coin flips 3. Let $\alpha$ denote one of these $2^m$ outcomes 4. For a node $s$, let $R_s^{\langle \alpha \rangle}$ denote the set of nodes that can be activate by $s$ under the outcome $\alpha$ 5. Let $f_\alpha(S)$ denote the eventual number of activated nodes under the outcome $\alpha$ 6. Then * $f_\alpha(S) = | \underset{s \in S}{\bigcup} R_s^{\langle \alpha \rangle} |$ * $f(S) = \underset{\alpha}{\sum}\text{Prob}[\alpha] \cdot f_\alpha(S)$ 7. Thus * $f_\alpha$ is clearly submodular * <details><summary> Why? </summary> 1. Let $S$ be a arbitrary set, $\Delta{S_v} = f_\alpha(S \cup \{v\}) - f_\alpha(S) = | \underset{s \in S} {\bigcup} R_s^{\langle \alpha \rangle}| + | R_v^{\langle \alpha \rangle} \setminus \underset{s \in S} {\bigcup} R_s^{\langle \alpha \rangle} | - | \underset{s \in S}{\bigcup} R_s^{\langle \alpha \rangle} | = | R_v^{\langle \alpha \rangle} \setminus \underset{s \in S} {\bigcup} R_s^{\langle \alpha \rangle} |$ 2. Suppose $X \subseteq Y$, then $\underset{s \in X} {\bigcup} R_s^{\langle \alpha \rangle} \subseteq \underset{s \in Y} {\bigcup} R_s^{\langle \alpha \rangle}$ and hence $\Delta X_v - \Delta Y_v = |R_v^{\langle \alpha \rangle} \setminus \underset{s \in X} {\bigcup} R_s^{\langle \alpha \rangle} | - |R_v^{\langle \alpha \rangle} \setminus \underset{s \in Y} {\bigcup} R_s^{\langle \alpha \rangle} | \geq 0$ 3. Thus $\Delta X_v \geq \Delta Y_v$, and hence $f_\alpha$ is submodular </details> * $f$ is submodular since it is the linear combination of $f_\alpha$ :::  ## 24.5 Empirical Studies of Cascades in Online Data ### A study performed on LiveJournal _LiveJournal_ is an online blogging and social networking site, which has several members and user-defined communities. - **Purpose:** - Observe the relationship between the lists of users' friends in the system and the communities which they belong to - **Settings:** 1. Convert the lists of friends to a social network, with an edge $(v,w)$ if $v$ lists $w$ as a friend. 2. At two times $t_1$ and $t_2$, snapshots are taken of the social network. 3. For each integer $k\geq0$, $U_k$ represents the set of all pairs $(u,C)$ such that: - At time $t_1$, user $u$ did not belong to community $C$, but had $k$ friends in $C$ 4. $P(k)$ denote the fraction of pairs $(u, C)$ in the set $U_k$ for which $u$ had joined $C$ by time $t_2$ 5. $P(k)$ is also the probability of joining $C$ at $t_2$, given that $u$ had $k$ friends in $C$ at $t_1$ - So the purpose is the same as **investigating $P(k)$ as a function of $k$** - **Results:** ![](https://i.imgur.com/cDDnfcJ.jpg) 1. $P(k)$ continues increasing even as $k$ becomes fairly large, but it grows less quickly as $k$ increases - We say the dependence on $k$ is dominated by a **diminishing returns** effect 2. There is a significant **deviation** from diminishing returns for $k=0, 1, 2$ ![](https://i.imgur.com/w14AWnd.jpg) - This gives a sense that having a **second friend** in a community gives a **significant boost** to the probability of joining ### Challenges of relating the empirical and theoretical models 1. We know very little about what the links between the online users really mean - _**e.g.** A user may have a link to a close friend, or to someone he has barely met_ 2. The LiveJournal model gives the clean logarithmic form of the resulting curve, but it is still in need of deeper explanation In conclusion, we are not able to get enough information about underlying factors from the empirical model: ||Theoretical model|Empirical model| |---|---|---| |Difference|Each node follows a fixed probabilistic rule to incorporate information from its neighbors over time.|We just observe the snapshot of the network, but not understand anything about any particular individual’s response to their friends’ behaviors.| ## 24.6 Notes and Further Reading - [Maximizing the spread of inﬂuence in a social network](https://dl-acm-org.ezproxy.lib.nctu.edu.tw/doi/abs/10.1145/956750.956769?casa_token=3cGrpRAVPvsAAAAA:eVfY7Isb1tYDch7rthwfyFdmRjpWN7zmmp7bFDZvrbx46vcyhEdd0W63wokp9PpDqLgouaSv-ASnuQ) - How to choose the set of nodes initially adopting the new behavior? - [A Time-Dependent SIR Model for COVID-19 With Undetectable Infected Persons](https://ieeexplore-ieee-org.ezproxy.lib.nctu.edu.tw/abstract/document/9200529?casa_token=aePjKmvtAHwAAAAA:N1k67eImhTrFQlyfs4rJHm12WwZFT9PArx17aPYxmlofUWxibmsnaAOa0ZMZfBMsBAdJMaxN2Q) - Propose a time-dependent SIR model - analyze the impact of the undetectable infections - [Epidemic Spreading in Scale-Free Networks](https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.86.3200) - [link(pdf)](http://www.ffn.ub.es/albert/complex_networks/romu.prl.pdf) - Analyzing real data from **computer virus**. - Defining a dynamical model for the spreading of infections on *scale-free networks*. - ![](https://i.imgur.com/RKuqV7q.png) - cited - [A mathematical model reveals the influence of population heterogeneity on herd immunity to SARS-CoV-2](https://science-sciencemag-org.ezproxy.lib.nctu.edu.tw/content/369/6505/846.abstract) - Heterogeneity affects herd immunity a lot. - [A Simulation of a COVID-19 Epidemic Based on a Deterministic SEIR Model](https://www.frontiersin.org/articles/10.3389/fpubh.2020.00230/full) - Implement an SEIR model to compute the infected population and the number of casualties of this epidemic.(Italy) - [Universal Behavior in a Generalized Model of Contagion](https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.92.218701) - [Coevolution spreading in complex networks](https://www-sciencedirect-com.ezproxy.lib.nctu.edu.tw/science/article/pii/S0370157319302583?casa_token=rn1HqZiS7ekAAAAA:Df8AwhOsmvOQVGhPUbugqi1bibR6qqqA_zqC7oWC86ShcP7dWDqn_cr7oXx0NALTnl8kf-gnXg8) - The propagations of diseases, behaviors and information are rarely independent of each other, but they are coevolving with strong interactions. - We introduce recent progress in the study of coevolution spreading dynamics. - Introdue the theoretical methods, effects of network topology,... for some types of coevolution spreading mechanisms --- - [EpiModel: An R Package for Mathematical Modeling of Infectious Disease over Networks](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5931789/) 1. Deterministic compartmental models(DCM): based on systems of differential equations 2. Stochastic individual contact models(ICM): Similar with Indepedent Cascade Model 3. Network models: generalization of the ICM ![](https://i.imgur.com/U4lnloT.jpg) - [MODELLING INFECTIOUS DISEASE IN DYNAMIC NETWORKS CONSIDERING VACCINE.](https://www.sysrevpharm.org/articles/modelling-infectious-disease-in-dynamic-networks-considering-vaccine.pdf) 1. In addition to *SIR*, *V* compartment which represent vaccinated is added. ![](https://i.imgur.com/tgbogvm.png) - [Heterogeneity matters: Contact structure and individual variation shape epidemic dynamics](https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0250050) 1. Stochastic COVID-19 Simulation ![](https://i.imgur.com/wLTsmaZ.gif) 2. Analyze modeling COVID-19 under DCM and ICM ![](https://i.imgur.com/it5UXvB.png) --- - [_Group Formation in Large Social Networks: Membership, Growth, and Evolution_](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.370.9788&rep=rep1&type=pdf) - the main source of section 24.5 - [_Dynamic-Sensitive centrality of nodes in temporal networks_](https://www.nature.com/articles/srep41454) - Measuring the **centrality** of nodes is an essential part of analysing networked systems - Classic works looked at analysing static networks but rarely highlighted the **dynamics** - TDC (temporal Dynamic-Sensitive centrality) is more accurate than static versions of centrality - [_Theories for Influencer Identification in Complex Networks_](https://link.springer.com/chapter/10.1007/978-3-319-77332-2_8) - The successful identification of **influencers** should have profound implications in various real-world spreading dynamics - Summarizing the centrality-based approach in finding single influencers - Locating multiple influencers from a collective point of view - [_Superspreaders and superblockers based community evolution tracking in dynamic social networks_](https://www.sciencedirect.com/science/article/pii/S0950705119306264?casa_token=rLcZQYT-00YAAAAA:PxSX7iFz12xHH9HgGvxzvtPvdSNPjlk2iUILDMtzRd2Vz6auzAjJVFO30W8gm7zXiE10uOEocg) - Propose a two-stage method to increase the accuracy of tracking the community evolution: 1. Error accumulation sensitive **(EAS)** incremental community detection 2. Superspreaders and superblockers **(SAS)** based community evolution tracking ---- *[Hethcote HW (2000). "The mathematics of infectious diseases". Society for Industrial and Applied Mathematics. 42: 599–653](https://epubs.siam.org/doi/abs/10.1137/s0036144500371907?casa_token=CCF_qc2t66YAAAAA:V95boIjGcv5xwyPuwHEpGuCdJKRDYlxPybX-pBAVtY5xHcJcy--ZwIKH4RVJMoMuOad9MMUGZTff)* - SIR model - MSEIR model - differential equation *[J Kleinberg (2007). "Cascading Behavior in Networks: Algorithmic and Economic Issues"](http://perso.ens-lyon.fr/christophe.crespelle/enseignements/GGT/inutilise/cascades.pdf)* - the source of this chapter *[IZ Kiss, JC Miller, PL Simon (2017) "Mathematics of epidemics on networks"](https://link.springer.com/content/pdf/10.1007/978-3-319-50806-1.pdf)* - covering a wide range of SIR and SIS model networks *[MEJ Newman (2002) "Spread of epidemic disease on networks"](https://journals.aps.org/pre/abstract/10.1103/PhysRevE.66.016128)* - detailed discussion of SIR model network ----