Analysis of complex contagions in random multiplex networks

Osman Yagan; Virgil Gligor

Source-linked AI summary

Analysis of complex contagions in random multiplex networks

Osman Yagan, Virgil Gligor

arXiv:1204.0491v3Apr 2, 2012physics.soc-phcs.SI

TL;DR

The paper asks how complex contagions spread when multiplex links have different content-dependent influence, extending models that assume a single undifferentiated network. It introduces a weighted threshold model on coupled random overlay networks and derives cascade conditions, probabilities, and expected sizes. The analysis shows that the same multiplex network can have different cascade behavior for different contents, while simulations confirm corresponding cascade ranges and triggering probabilities.

Problem
Existing complex-contagion studies largely assume identical links, limiting analysis of overlapping multiplex networks and content-dependent influence.
Method
The paper models activation using a threshold on the content-weighted perceived proportion of active neighbors in random overlay networks with classified links.
Results
For the shared range z1 = z2 = 1.0–3.9, the triggering probability at z1 = z2 = 3 is Ptrig = 0.84 for C1 and Ptrig = 0.65 for C2.
Takeaways & Limitations
Content and link classification can produce different spreading characteristics on the same multiplex network, extending cascade theory to overlay networks with shared vertices.

Abstract

from arXiv · show

We study the diffusion of influence in random multiplex networks where links can be of $r$ different types, and for a given content (e.g., rumor, product, political view), each link type is associated with a content dependent parameter $c_i$ in $[0,\infty]$ that measures the relative bias type-$i$ links have in spreading this content. In this setting, we propose a linear threshold model of contagion where nodes switch state if their "perceived" proportion of active neighbors exceeds a threshold τ. Namely, a node connected to $m_i$ active neighbors and $k_i-m_i$ inactive neighbors via type-$i$ links will turn active if $\sum{c_i m_i}/\sum{c_i k_i}$ exceeds its threshold τ. Under this model, we obtain the condition, probability and expected size of global spreading events. Our results extend the existing work on complex contagions in several directions by i) providing solutions for coupled random networks whose vertices are neither identical nor disjoint, (ii) highlighting the effect of content on the dynamics of complex contagions, and (iii) showing that content-dependent propagation over a multiplex network leads to a subtle relation between the giant vulnerable component of the graph and the global cascade condition that is not seen in the existing models in the literature.

I. INTRODUCTION

The paper studies complex contagions in multiplex networks, where link types can differ in their roles for spreading particular content. It develops a content-dependent threshold model and derives conditions, probabilities, and expected sizes of global cascades.

Complex contagions describe initially localized effects that spread through a large fraction of a network, including beliefs, products, diseases, failures, riots, and computer viruses.
The paper addresses the limitation that most existing studies treat all network links as identical, although relationship types can influence different contents differently.Examples include products promoted more through classmates or family members depending on the product.
Each link type receives a content-dependent parameter c_i measuring its relative bias in spreading that content.Larger c_i values indicate that type-i links are more likely to spread the content.
Nodes activate when their perceived proportion of active neighbors, weighted by the content parameters, exceeds their threshold.Setting all c_i equal recovers the ordinary threshold formulation.
For two-type configuration-model subnetworks, the analysis derives when a single active node can trigger a global cascade, along with its probability and expected final size.The global cascade is defined as activation of a linear fraction of nodes in the asymptotic limit.
The results extend prior work to overlapping overlay networks, content-dependent spreading, and multiple vulnerability notions whose relation to global cascades differs from existing models.The constituent networks may share vertices rather than being disjoint.

II. MODEL DEFINITIONS

The model overlays independently generated networks with classified edges and assigns nodes content-dependent threshold dynamics. Its response function weights active and total neighbors by link-type biases before determining activation.

The illustrative system overlays a physical network W with a non-reciprocal online network F on a population of individuals.W contains reciprocal communications, while F represents non-reciprocal online influence.
Every population node belongs to W, whereas each node independently belongs to F with probability α.Thus F can cover only a subset of the population.
Both subnetworks are specified by degree distributions and generated independently using the configuration model.Their union forms the overlay network H.
Edges in H are classified by network type, and each node has a colored degree vector recording its incident edges of each type.For the two-type example, Facebook edges are type 1 and physical edges are type 2.
The overlay can be constructed by randomly pairing same-type stubs until all colored stubs are used.This produces edges only between stubs carrying the same type.

A. Condition and Probability of Global Cascades

Global cascades are analyzed through vulnerable-node branching processes in multiplex networks. The cascade condition depends on directed reachability among vulnerable nodes, while the triggering probability is determined by the extended giant in-component.

Vulnerability structure: Unless c = 1, vulnerability depends separately on the two link types, so vulnerable nodes form a directed subgraph rather than an ordinary undirected component.A node may be F-vulnerable but not W-vulnerable, or vice versa; the paper defines the vulnerable component through mutual activation within the induced subgraph.
Cascade condition: The giant vulnerable component corresponds to the GSCC, but the global cascade condition corresponds to the appearance of a GIN among vulnerable nodes.Global cascades require a linear fraction of vulnerable nodes with infinite out-components, not merely the existence of a giant strongly connected component.
Triggering probability: The triggering probability equals the fractional size of EGIN, which includes nonvulnerable vertices that can activate a node in GIN.EGIN contains GIN and vertices that can reach it after activation, so it differs from the vulnerable-node GIN itself.
Branching-process analysis: A branching process beginning from an arbitrary activated node computes the number of vulnerable nodes reached and activated, under a locally tree-like network assumption.The assumption is justified for colored degree-driven networks because their clustering coefficient scales as 1/n.
Branching-process analysis: The vulnerability probabilities distinguish F-vulnerable, W-vulnerable, jointly vulnerable, and exclusively vulnerable node classes by colored degree.These probabilities specify whether one active neighbor through each link type can activate a node.
Branching-process analysis: Generating functions g1 and g2 describe finite vulnerable branches reached through the two edge types, while G describes the resulting vulnerable-node count.Their fixed point at x = 1 is tested for stability by linearizing the recursion and examining the Jacobian Jp.
Cascade condition: If the spectral radius of Jp is at most one, G(1) = 1 and global cascades are impossible; if it exceeds one, cascades occur with positive probability 1 − G(1).The unstable regime yields a solution with G(1) < 1, and the deficit gives the probability that activation reaches infinitely many vulnerable nodes.
Triggering probability: The generating function G measures EGIN rather than GIN, while a separate function H is required to obtain the asymptotic size of GIN.The distinction arises because the initially activated node may be nonvulnerable.

B. Expected Cascade Size

The paper estimates expected cascade size by analyzing contagion on a locally tree-like multiplex network, using recursive activation probabilities and fixed-point stability. The resulting recursion yields the same global-cascade condition as the generating-function approach while quantifying final cascade size and cascade probability.

The analysis replaces the locally tree-like multiplex network with a rooted tree whose nodes have colored degrees for the two link types.The top node connects through Facebook and physical links, while lower-level nodes retain parent-dependent degree adjustments.
Activation probabilities q1,ℓ and q2,ℓ are propagated upward through tree levels after lower-level nodes update.These probabilities track activation through the two link types, with active-neighbor combinations evaluated using the neighborhood response function F(m, k).
The limiting probabilities q1,∞ and q2,∞ determine the expected final active fraction S as the probability that the root becomes active.Monotonicity under irreversible activation ensures convergence of the recursive probabilities.
A nontrivial cascade solution is identified by linearizing the recursive equations around the zero fixed point and testing its stability.The zero solution gives S = 0, while instability permits a positive limiting solution.
The recursive analysis produces the same global-cascade condition, σ(Jp) > 1, as the generating-function approach, while the latter also quantifies cascade probability.The equality follows because the two Jacobians have equal spectral radii.

IV. NUMERICAL RESULTS

Numerical results show that content-dependent link bias changes cascade windows, triggering probabilities, and cascade sizes, while validating the analytical predictions on locally tree-like networks. Tests on clustered networks reveal the expected limitation of the zero-clustering theory.

Content-dependent cascade windows: For C1, global cascades occur for 1.0 ≤ z1 = z2 ≤ 4.9, while C2 spreads globally only for 0.7 ≤ z1 = z2 ≤ 3.9.Over the shared range 1.0 ≤ z1 = z2 ≤ 3.9, triggering probabilities can differ substantially: at z1 = z2 = 3, Ptrig is 0.84 for C1 and 0.65 for C2.
Validation and clustering: Analytical predictions agree well with simulations for Erdős–Rényi networks, but they do not match cascade sizes in positively clustered networks.With clustering, cascade sizes are lower at small average degree and higher after a degree-dependent crossover, consistent with the reported two-faceted effect.
Content-dependent cascade windows: Changing c can create non-monotonic cascade behavior because link bias alters both effective connectivity and local stability.For z1 = 1.5 and z2 = 5.5, increasing c first suppresses and then restores global cascades as spreading shifts toward the lower-degree F network.
Content-dependent cascade windows: When z1 = z2 = 0.7, global cascades occur only for 0.5 ≤ c ≤ 2.5 because F and W must spread the content collaboratively.For c ≤ 0.4 or c ≥ 2.6, one network dominates and triggering events remain finite.
Content-dependent cascade windows: When z1 = 6.0 and z2 = 1.5, global cascades occur only for c ≤ 0.5; contents with c ≥ 0.6 die out before reaching a non-trivial fraction of the network.The high-degree F network makes larger c values increase local stability and inhibit spreading.
Cascade windows: For c = 1 and c = 0.1, cascades remain possible up to τ⋆ ≤ 0.25, whereas c = 4 reduces the upper threshold bound to 0.23.Thus, c changes the range of z1 = z2 supporting global cascades and can shift the maximum viable threshold.

V. CONCLUSION

The paper determines global-cascade conditions, probabilities, and sizes for a content-dependent threshold model on random networks with classified links. It extends complex-contagion analysis to overlapping multiplex networks and shows that different contents can spread differently over the same network.

Main contribution: The theory determines the condition, probability, and size of global cascades when nodes respond to a content-dependent perceived proportion of active neighbors.The model assigns relative content biases to link types and uses them in the activation rule.
Main contribution: The results extend complex-contagion analysis to multiple overlay networks whose vertex sets are not disjoint.This generalizes results previously developed for single networks with arbitrary degree distributions.
Scientific implication: Different contents can have different spreading characteristics over the same network because link classification affects cascade behavior.The framework represents content-specific relative bias through the link types used in propagation.
Relation to existing models: The framework contains bond percolation, simple contagion, and Watts’ threshold model as special cases through suitable response functions and parameter choices.This places several established cascade models within the same general formulation.
Scientific implication: The results may help understand cascade processes and support more efficient control of cascading failures and marketing cascades.The paper identifies control of cascades as particularly relevant in interdependent structures and marketing contexts.