Source-linked AI summary
Diffusion and Cascading Behavior in Random Networks
Marc Lelarge
TL;DR
The paper asks when strategic adoption spreads through a random network, where choices depend on neighbors rather than on transmission alone. It analyzes deterministic best-response play in a binary coordination game and finds that contagion is possible only over a range of global connectivity, with sparse and dense networks limiting it for different reasons.
Problem
The paper examines how deterministic best-response coordination behaves on complex networks, where network structure and initial choices can affect whether an innovation becomes widespread.
Source: §1 · pp. 2–3Method
The authors analyze a binary coordination game under deterministic best-response dynamics on sparse random networks with given vertex degrees.
Source: §1 · p. 3Results
Contagion is possible only over a range of global connectivity: sparse networks limit spread through low connectivity, while dense networks limit it through stable high-degree nodes.
Source: §7 · p. 33Takeaways & Limitations
When pivotal players are rare, contagion can still occur with a sufficiently large initial adopter set, and connectivity affects spread differently in low- and high-connectivity cases.
Source: §7 · pp. 33–34The local mean-field approximation is difficult to make rigorous because its recursive distributional equation can have multiple solutions.
Source: §2.5 · p. 18
Abstract
from arXiv · showhide
The spread of new ideas, behaviors or technologies has been extensively studied using epidemic models. Here we consider a model of diffusion where the individuals' behavior is the result of a strategic choice. We study a simple coordination game with binary choice and give a condition for a new action to become widespread in a random network. We also analyze the possible equilibria of this game and identify conditions for the coexistence of both strategies in large connected sets. Finally we look at how can firms use social networks to promote their goals with limited information. Our results differ strongly from the one derived with epidemic models and show that connectivity plays an ambiguous role: while it allows the diffusion to spread, when the network is highly connected, the diffusion is also limited by high-degree nodes which are very stable.
1 Introduction
The paper studies strategic adoption, where a person's choice depends on neighbors' behavior, rather than epidemic transmission independent of local conditions. It develops an analysis of deterministic best responses on random networks and examines when cascades, coexistence, and advertising-driven diffusion occur.
1 Introduction
- The paper models diffusion as deterministic best-response play in a binary coordination game on a network, with payoffs depending on neighbors' actions.Each node chooses A or B, and matching neighbors receive the payoff associated with their shared action.Source: §1 · pp. 2–3
- An agent switches to B only when the number of B-playing neighbors exceeds q times its degree; ties favor A.The model's local incentives make adoption depend on the fraction of neighbors already choosing B.Source: §1 · p. 3
- A contagion threshold determines whether a finite seed can spread B throughout the network; it is at most 1/2, so B must be risk-dominant, but that condition alone is insufficient.Low contagion thresholds are also associated with equilibria in which both actions are played.Source: §1 · p. 3
- The paper analyzes large-population limits on random graphs with given degree sequences, addressing the limits of node-by-node local-graph results for heterogeneous networks.The authors describe random graphs as a first approximation for sparse interaction networks when the problem has no known geometry.Source: §1 · p. 3
- Connectivity has an ambiguous role: it can enable diffusion, while high-degree nodes in highly connected networks are stable and can limit it.The paper also presents a general diffusion model with varying and potentially random initial activation and thresholds.Source: §1 · pp. 3–4
- For sparse random networks, the paper studies contagion thresholds, phase transitions, coexistence of large connected groups, and the minimum uninformed seed needed to trigger a cascade.It also relates these results to pivotal players and considers advertising strategies when the firm lacks graph-specific information.Source: §1 · p. 4
2 Analysis of a simple model of cascades
The section analyzes cascades on random networks with prescribed degree distributions, characterizing widespread adoption and the coexistence of strategies in equilibria. It also estimates adoption under degree-targeted advertising and word of mouth using a local branching-process approximation, and examines how connectivity can impede cascade initiation while helping spread once triggered.
2.1 Graphs: the configuration model
- The network model uniformly matches degree-sequence half-edges, conditioning on simplicity to obtain uniformly distributed simple graphs; limiting degree frequencies have finite mean and second moment.Source: §2.1 · p. 5
2.2 Contagion threshold for random networks
- Below q_c, a uniformly random initial adopter has a positive probability of triggering a cascade affecting a positive population fraction; above q_c, cascades are sublinear.Below the threshold, the cascade fraction and the probability of a large cascade are bounded away from zero; above it, the cascade size is o(n).Source: §2.2 · p. 7
- For Erdős–Rényi networks, q_c≤1/4, while the considered scale-free networks have q_c≤1/9; widespread diffusion requires sufficiently low adoption thresholds among many nodes.In the scale-free example, nodes with no more than nine neighbors must adopt with one adopting neighbor; in the Erdős–Rényi case, the corresponding bound is four neighbors.Source: §2.2 · p. 8
- For fixed low q, global cascades occur only between lower and upper average-degree thresholds: sparse networks fail to branch, while dense networks are stopped by locally stable high-degree nodes.The pivotal-player fraction is positive only between these thresholds, with continuous transitions at both ends; cascade size is discontinuous at the upper threshold, where cascades become rarer but larger before disappearing.Source: §2.2 · pp. 8–10
2.3 Equilibria of the game and coexistence
- When q<q_c, switching two neighboring pivotal players from all-A yields an equilibrium with more than s(q,p)n players playing B.There are Ω_p(n) pivotal players, so sampling neighboring players eventually triggers this equilibrium after a finite number of trials not increasing with n.Source: §2.3 · p. 11
- In the Erdős–Rényi pivotal equilibrium, λ∈(λ_i(q),λ_c(q)) supports giant connected components of both strategies; for λ>λ_c(q), A has no giant component.Source: §2.3 · p. 12
- For Erdős–Rényi graphs, above λc(q), a positive fraction still plays A, but A players occupy only small disconnected components; λc(q) is close to λi(q).For general degree distributions, Proposition 7 identifies conditions for giant components of both A and B players to coexist in the pivotal equilibrium.Source: §2.3 · pp. 12–13
2.4 Advertising with word of mouth communication
- A firm with degree-distribution information can choose advertising rates by degree, while buyers adopt after direct advertising or enough influential neighbors buy.The model allows random degree-dependent thresholds and influence probability π; it includes the contact process when K(d) = 0 and the Morris threshold model when π = 1 and K(d) = qd.Source: §2.4 · p. 13
- The final buyer count is (1 − h1(ẑ, α, p, π))n + op(n) when ẑ = 0 or the stated root and sign conditions hold.The result estimates the marketing strategy’s expected payoff from the advertising vector and degree distribution.Source: §2.4 · pp. 13–14
- For q < 1/4, the critical seed fraction αc is zero on [λi(q), λs(q)] and positive above λs(q); for q > 1/4, it is positive for every λ.Below αc, diffusion remains small; above it, diffusion becomes large. When q > 1/4, a single uniformly sampled adopter cannot trigger a global cascade.Source: §2.4 · p. 15, Figure 7 · p. 15
2.5 Local Mean Field approximation
- The local mean-field approximation uses a Galton–Watson tree to derive recursive activation probabilities and recover the functions h, g, and h1.The recursion yields a fixed-point equation, but can have multiple solutions; this difficulty prevents the approximation from directly providing the rigorous proof.Source: §2.5 · pp. 16–18
3 General model and main results
The section sets out a threshold-based diffusion model on random networks, with both degree-based and single-node activation. It gives conditions and asymptotic statements for diffusion, including a cascade condition for single activation.
3.1 Diffusion: percolated threshold model
- The symmetric threshold model activates an inactive node when its active-neighbor count exceeds its degree-dependent threshold K_i(d_i).Thresholds are independent across nodes and their distribution may depend on degree.Source: §3.1 · p. 19
- In the percolated threshold model, edges are independently deleted with probability 1 − π before the threshold update, while thresholds depend on original degree.The model is therefore not equivalent to applying the symmetric threshold model to the percolated graph.Source: §3.1 · pp. 19–20
3.2 Diffusion with degree based activation
- For degree-based activation, the theorem's asymptotic statements require zhat = 0 or a positive root with g negative immediately to its left.The selected root is the largest z in [0, 1] satisfying g(z; p, t, α, π) = 0.Source: §3.2 · pp. 20–21
3.3 Diffusion with a single activation
- The single-activation analysis defines the cascade condition as πE[D(D − 1)11(K(D) = 0)] > E[D], and calls vertices in P pivotal.Every u in P satisfies P ⊂ C(u).Source: §3.3 · p. 21
- For any j = o(n), the final active set C(1, . . . , j) has size o_p(n).This is the stated result for a seed of the first j nodes.Source: §3.3 · p. 22
4 Proof of Theorem 10
The proof couples diffusion to the construction of a random multigraph and uses death processes to track its evolution. A deletion process then links the stopping state to the inactive subgraph.
4.1 Sketch of the proof
- The proof couples graph construction with diffusion dynamics, adding independent thresholds to vertices; the single-seed case also requires handling the fact that C(u) need not equal C(v) for v in C(u).The argument is developed on the configuration-model multigraph, with results transferred by conditioning on simplicity.Source: §4.1 · p. 23
4.2 A Lemma for death processes
- The auxiliary lemma tracks bins with independent rate-1 death processes, coloring a ball green with probability 1 − π when it dies and otherwise removing it.Bins carry initial degree and threshold information.Source: §4.2 · pp. 23–24
4.3 Proof of the diffusion spread
- In the diffusion deletion process, white balls are removed at rate 1 and a white B-ball is recolored red; at stopping, the remaining white A-balls are the inactive subgraph's half-edges.Thus the inactive subgraph has 1/2 A(τ) edges and A1(τ) vertices.Source: §4.3 · p. 25
5 Proof of Theorem 11
The proof tracks an exploration process with exceptions to establish when a large cascade occurs and how pivotal players relate to the final active set. It also uses coupling and a modified threshold model to bound active-set size.
5 Proof of Theorem 11
- An exception near time τ triggers a large cascade: the exception times concentrate near 0 and τ, and the intervening removed subgraph is large.The proof also shows the next exception after τ occurs near τ, with only o(n) vertices removed between those two later exceptions.Source: §5 · pp. 30–31
- When ξ = 0, no exception occurs after a last exception at time tending to 0, and the ensuing removed subgraph is the whole graph up to o(n) vertices.For ξ > 0 under the stated negativity condition near ξ, the proof locates exceptions around τ = −ln ξ.Source: §5 · pp. 29–30
- The pivotal set P is contained in the subgraph removed between the exceptions near τ, linking pivotal players to a large cascade.The proof establishes this inclusion by ruling out a small intervening subgraph if P were disjoint from that removed subgraph.Source: §5 · p. 31
- For parameters where the root condition does not directly yield the bound, coupling with a smaller π′ model gives a lower bound on the active fraction.As π′ approaches π, the lower bound approaches 1 − h1(ξ). A modified threshold process also represents P as the largest component explored under bond and site percolation.Source: §5 · pp. 31–32
6 Proof of Propositions 6 and 7
The proof relates giant inactive components in the pivotal equilibrium to a condition on the degree-distribution quantities. In the specified range of λ, that condition is characterized by a single intersection.
6 Proof of Propositions 6 and 7
- Under the cascade condition, the active vertices contain the pivotal vertices and have a giant component; the inactive set is taken in the pivotal equilibrium.The proof denotes the induced inactive subgraph by I and tracks its vertices by degree.Source: §6 · p. 32
- The interval endpoints λ_i(q) and λ_s(q) are defined using where ψ(λ) is below or above 1, on opposite sides of λ∗.The passage states that ψ increases through λ∗ and then decreases, with ψ(λ∗) > 1.Source: §6 · p. 33
- A giant component of inactive vertices exists when ζ(λ) < ξ(λ), and these functions intersect only once on (λ_i(q), λ_s(q)).Both functions are non-increasing on that interval.Source: §6 · p. 33
7 Conclusions
The paper studies strategic diffusion on sparse random networks, finding that connectivity can constrain cascades at both low and high levels. It identifies pivotal players and examines coexistence equilibria and diffusion with larger initial seeds.
7 Conclusions
- Cascades are limited by low connectivity in sufficiently sparse networks and by high-degree-node stability in sufficiently dense networks, so they occur only within a range of global connectivity.The analysis uses deterministic best-response dynamics in a local binary interaction game on a sparse random graph.Source: §7 · p. 33
- Cascades occur only when pivotal players form a positive population fraction, and any cascade is triggered by such a player.In the high-connectivity case, pivotal players are rare but can trigger very large cascades, making global contagions hard to anticipate.Source: §7 · p. 33
- With a sufficiently large initial adopter set, contagion can remain possible when pivotal players are negligible; higher connectivity helps spread at low connectivity but inhibits it at high connectivity.In the high-connectivity case, once contagion occurs, connectivity facilitates its spread.Source: §7 · pp. 33–34
- The general percolated threshold model gives explicit diffusion formulas using the initial condition, degree sequence, and threshold distribution.The model allows different weights for anonymous neighbors.Source: §7 · p. 34
A.1 Technical lemma
The lemma states an identity for x, π, and k, with its proof based on observations involving independent Bernoulli variables.
A.1 Technical lemma
- Lemma 14 states an identity for any x, π ∈ [0, 1] and k ≥ 0.The supplied proof says it follows from observations for x > 0.Source: §A.1 · pp. 36–37
- The proof uses independent Bernoulli variables with parameters π and 1 − x.The passage says these variables correspond to equation (26).Source: §A.1 · p. 37
- The cited passage states that an antecedent corresponds exactly to equation (26), but this excerpt does not identify the antecedent or describe it as a Bernoulli-variable expression.Source: §A.1 · p. 37
A.2 Properties of the functions h and g
The section establishes monotonicity properties of h and h1 and justifies defining the largest zero of g using a maximum. It distinguishes the cases α = 0 and α ≠ 0.
A.2 Properties of the functions h and g
- The auxiliary h1 is expressed using σ(D) and a thinned degree D1−π+πz, with each point retained independently at probability 1−π+πz.Given D = d, the thinning has a binomial distribution Bi(d, x) when the retention probability is x.Source: §A.2 · p. 37
- Both h and h1 are non-decreasing in z and non-increasing in π.Source: §A.2 · p. 37
- For α = 0, h(1; p, t, 0, π) = λ, g(1; p, t, 0, π) = 0, and the defined value ẑ is 1.Source: §A.2 · p. 37
- For α ≠ 0, g(1; α, p, π) > 0, and the downward-only jumps of g support the argument that its largest zero is attained.The section uses continuity of h and g at ẑ to replace the supremum defining ẑ with a maximum.Source: §A.2 · p. 37
A.3 Proof of Lemma 9
Taking expectation in equation (3) gives an expression for E[Xø], which establishes the second part of Lemma 9.
A.3 Proof of Lemma 9
- Taking expectation in equation (3) yields the stated expression for E[Xø] and establishes the second part of Lemma 9.Source: §A.3 · p. 38