Information Propagation in Clustered Multilayer Networks

Yong Zhuang, Osman Yagan

TL;DR

This paper provides a rigorous analytical framework to study how information spreads across multilayer networks—such as the combination of physical face-to-face interactions and online social media—while accounting for the "high clustering" (friends of friends being friends) typical of real-world social structures. The authors demonstrate that while clustering generally makes it harder for information to go viral, the "ideal" network for spreading news depends entirely on how transmissible that news is: dense, small networks favor low-transmissibility info, while large, loose networks favor high-transmissibility info.

What Problem Does This Paper Address?

Most classical models of network diffusion assume a "tree-like" structure, where cycles (like triangles) are rare. However, real-world social networks are highly clustered; if Alice knows Bob and Charlie, there is a high probability Bob and Charlie also know each other. This clustering significantly changes how information flows.

Furthermore, we don't live in a single network. We inhabit "multilayer" environments where information can jump from a physical conversation to a Twitter thread and back to a phone call. Previous research often struggled to mathematically quantify the interplay between these multiple layers and high clustering. The authors set out to find the "epidemic threshold" (the point where a single piece of news goes viral) and the final "epidemic size" (how many people eventually hear it) in these complex, overlapping systems.

Methods

The authors employ a sophisticated mathematical toolkit to model the system:

  • Random Graphs with Clustering: They use the Miller-Newman model, which allows nodes to have a specific distribution of both "single edges" and "triangles."
  • Multilayer Coupling: They define a physical network ($W$) and an overlay social network ($F$). A tunable parameter, $\alpha$, represents the fraction of the population participating in the online network.
  • SIR Model to Bond Percolation: They map the Susceptible-Infectious-Recovered (SIR) diffusion process onto a bond percolation problem. This allows them to treat the spread of information as a connectivity problem in a random graph.
  • Branching Processes & Generating Functions: To solve the model, they use multi-type branching processes. They derive a set of recursive equations (using Jacobian matrices) to find the exact point where a "giant component" (an epidemic) emerges.

Datasets

The paper relies on synthetic datasets generated to match specific statistical properties observed in the real world:

  • Doubly Poisson Distributions: Used for baseline theoretical validation.
  • Power-Law with Exponential Cut-off: Used to simulate more realistic social structures, mimicking the degree distributions found in email networks and the World Wide Web.
  • Simulations: The analytical results were validated against computer simulations involving $n = 5 \times 10^5$ nodes, averaged over 100 independent runs.

Key Insights and Ideas

  • Clustering as an Inhibitor: Clustering creates "redundancy." In a triangle (Alice-Bob-Charlie), if Alice tells Bob and Charlie the news, the edge between Bob and Charlie becomes redundant for the initial spread. This redundancy effectively "wastes" edges that could have reached new parts of the network, thereby increasing the epidemic threshold and reducing the final size.
  • The Transmissibility Trade-off: This is the paper's most striking "aha moment."
    • If information has low transmissibility (hard to spread), it survives better in a small, densely connected social network. The high density keeps the "spark" alive.
  • If information has high transmissibility (easy to spread), it reaches more people via a large, loosely connected network. Here, "reach" is more important than "density."
  • Assortativity Matters: The way networks are coupled (the $\alpha$ parameter) induces "assortative mixing"—where high-degree nodes tend to be connected to other high-degree nodes. This correlation significantly lowers the threshold for an epidemic to start.

Key Results

  • Threshold Shift: Increasing clustering in any layer consistently increases the epidemic threshold. It simply takes "stickier" news to go viral in a clustered world.
  • Size Reduction: Even when an epidemic occurs, clustering reduces the total fraction of the population reached.
  • Theoretical Accuracy: The authors' analytical predictions showed "perfect agreement" with large-scale computer simulations across various degree distributions (Poisson and Power-law).
  • Quantifying the "Social Overlay": The paper quantifies exactly how much an online social network "speeds up" or "scales up" information diffusion relative to the underlying physical network.

Limitations and Future Work

  • Simple vs. Complex Contagion: This work focuses on "simple contagions" (like a virus or a basic piece of news). It does not account for "complex contagions," where an individual might need to hear a rumor from multiple sources before believing or spreading it.
  • Higher-Order Structures: While the model includes triangles, real social networks often contain larger cliques (groups of 4, 5, or more people who all know each other). The authors suggest extending the model to these larger structures.
  • Assortativity Dynamics: While the paper notes the impact of assortativity, the authors acknowledge that the full relationship between multilayer coupling and degree correlation remains an open area for deeper study.

Summary updated

Abstract

In today's world, individuals interact with each other in more complicated patterns than ever. Some individuals engage through online social networks (e.g., Facebook, Twitter), while some communicate only through conventional ways (e.g., face-to-face). Therefore, understanding the dynamics of information propagation among humans calls for a multi-layer network model where an online social network is conjoined with a physical network. In this work, we initiate a study of information diffusion in a clustered multi-layer network model, where all constituent layers are random networks with high clustering. We assume that information propagates according to the SIR model and with different information transmissibility across the networks. We give results for the conditions, probability, and size of information epidemics, i.e., cases where information starts from a single individual and reaches a positive fraction of the population. We show that increasing the level of clustering in either one of the layers increases the epidemic threshold and decreases the final epidemic size in the whole system. An interesting finding is that information with low transmissibility spreads more effectively with a small but densely connected social network, whereas highly transmissible information spreads better with the help of a large but loosely connected social network.
BibTeX
@article{zhuang2016information,
  author = {Yong Zhuang and Osman Yagan},
  title = {{Information Propagation in Clustered Multilayer Networks}},
  journal = {IEEE Trans. Network Science \& Engineering},
  year = {2016},
  url = {https://openreview.net/forum?id=Ae5_yeZ0U-},
}

Loading related content...

Figure