Source-linked AI summary
Epidemic spreading on complex networks with community structures
Clara Stegehuis, Remco van der Hofstad, Johan S. H. van Leeuwaarden
TL;DR
The paper asks how community structure affects epidemic and percolation processes on real-world networks and which aspects of that structure matter. It introduces two random graph models that preserve different community information, finding that mesoscopic communities are crucial while exact internal wiring has little influence. The models also show that community structure can either enforce or inhibit diffusion.
Problem
The paper investigates how community structure affects epidemic spreading on real-world networks and which properties of that structure have the greatest influence.
Method
The authors introduce HCM, which preserves intra-community edges while rewiring inter-community edges, and HCM*, which randomizes both under community constraints.
Results
The models accurately capture real-world percolation behavior, showing that mesoscopic community sets matter while precise intra-community structure has minor influence.
Takeaways & Limitations
Community structure is a central determinant of epidemic and percolation behavior and can either enforce or inhibit diffusion.
Takeaways & Limitations
HCM fixes intra-community edges and is therefore prone to overfitting, whereas randomizing them in HCM* makes analytical analysis harder.
Abstract
from arXiv · showhide
Many real-world networks display a community structure. We study two random graph models that create a network with similar community structure as a given network. One model preserves the exact community structure of the original network, while the other model only preserves the set of communities and the vertex degrees. These models show that community structure is an important determinant of the behavior of percolation processes on networks, such as information diffusion or virus spreading: the community structure can both \textit{enforce} as well as \textit{inhibit} diffusion processes. Our models further show that it is the mesoscopic set of communities that matters. The exact internal structures of communities barely influence the behavior of percolation processes across networks. This insensitivity is likely due to the relative denseness of the communities.
Introduction
Network structure affects epidemic and percolation dynamics, but community structure is not captured by degree-based properties alone. The paper studies models preserving different parts of community structure and finds that mesoscopic communities strongly shape diffusion while their internal wiring has limited influence.
- Motivation: Percolation and epidemic models represent processes such as information or virus spreading, motivating study of how network structure affects their dynamics.Understanding these processes can inform epidemic control and the spread of messages.
- Community structure: Real-world networks contain densely connected groups with comparatively few edges between groups, forming a mesoscopic community structure.These communities are small relative to the full network but scale with network size.
- Research question: The paper addresses how community structure influences epidemics on real-world networks and which community properties matter most.The extent of this influence was described as largely unexplained despite prior stylized models.
- Main findings: Community structure can enforce or inhibit percolation, while the set of communities matters more than the precise internal community structure.The models capture epidemic or percolation behavior on real-world networks accurately; HCM* also reduces HCM's overfitting concern by randomizing intra-community edges.
- Models: Two random graph models preserve different community information: HCM keeps intra-community edges fixed and randomizes inter-community edges, whereas HCM* randomizes both while preserving community constraints.Both models retain more mesoscopic structure than the configuration model, which preserves only the degree distribution.
Results
HCM and HCM* reproduce real-world percolation behavior more accurately than CM, showing that mesoscopic community structure largely determines epidemic spreading. Community effects vary by network and process, while exact internal community structure has limited influence in typical percolation settings.
- Connectedness: The size of the giant component is well predicted by HCM using community sizes and outgoing-edge counts, improving on CM estimates that are generally a few percent off.For connected HCM* communities, the giant-component size is independent of precise community shapes.
- Percolation results: HCM and HCM* accurately capture bond-percolation behavior in real-world networks, unlike CM.The models also perform well for other percolation processes and an SIR epidemic.
- Targeted attacks: HCM and HCM* are generally close to original-network behavior, but targeted attacks can reveal differences between the models and the original graph.Facebook is more resistant than its corresponding CM because most high-degree vertices lie in one community.
- Network-specific effects: The yeast network is an exception: CM performs as well as HCM and HCM* because its almost tree-like structure has no noticeable community structure.Comparing these models can therefore indicate whether detected communities are meaningful for percolation behavior.
- Network-specific effects: Community structure can inhibit percolation in the Enron, High Energy Physics, and PGP networks but enforce it in the Autonomous Systems network.The Autonomous Systems effect may reflect its star-like community structure.
- Model interpretation: HCM* preserves epidemic-spreading behavior despite failing to reproduce clustering and assortativity well, indicating that mesoscopic properties can suffice.HCM is preferable when reproducing microscopic clustering is also important.
Conclusion
Community structure is essential for describing epidemic and percolation processes, while the precise internal organization of communities is generally less important. The models also suggest overlapping communities as a potential extension.
- Conclusion: Community structure is essential for describing percolation and epidemic spreading in complex networks.The conclusion covers bond percolation, bootstrap percolation, and SIR epidemics.
- Conclusion: The precise internal structure of communities is far less important for describing epidemic outbreaks, likely because communities are relatively dense.For sparse communities, internal structure is expected to have a more decisive effect.
- Conclusion: Including overlapping communities is proposed as a possible way to improve descriptions of percolation across complex networks.
Supplementary Notes
The supplementary material defines network statistics and reports that graph distances in HCM and HCM* can sometimes better match real networks than CM. It also describes community modularity, assortativity, clustering, and connectedness measures.
- Network statistics: The degree distribution p_k is the fraction of vertices having degree k.For N vertices and N_k vertices of degree k, p_k = N_k/N.
- Network statistics: The average clustering coefficient is the average of each vertex’s fraction of neighbor pairs that are connected to one another.For vertex i, the number of neighbor pairs is d_i(d_i − 1)/2.
- Network statistics: Higher modularity indicates that a partition contains more within-community edges than expected under random connections.
- Network statistics: Positive assortativity means high-degree vertices tend to connect to other high-degree vertices, whereas negative assortativity indicates connections to low-degree vertices.
- Network statistics: The giant-component proportion S is the fraction of vertices in the largest connected component.It is defined as S = |C_max|/N.
- Graph distances: HCM and HCM* sometimes capture graph distances better than CM, although CM is already close to the original network for some datasets.Graph distance is the minimum number of edges in a path between two vertices.
Community detection
The study uses Infomap to detect network communities for the HCM and HCM* models. Infomap uses random walks and has complexity O(N log(N)), supporting application to large networks.
- Community detection: The HCM and HCM* models use community structures detected with the Infomap algorithm.Infomap detects communities from a random-walk perspective.
- Community detection: Infomap has computational complexity O(N log(N)) for a network with N vertices, making it applicable to large networks.
HCM and HCM*
HCM preserves the original intra-community edges while rewiring inter-community connections, whereas HCM* also randomizes edges within communities. Their analytical and empirical results show that community sizes and inter-community connectivity largely determine component structure and network statistics, while dense communities usually remain connected.
- Model construction: HCM keeps intra-community edges fixed and randomly rewires inter-community edges, while HCM* additionally randomizes edges within every community.Both models preserve the given sets of communities; HCM* is designed to avoid HCM's tendency to overfit by retaining internal edges.
- Analytical characterization: The largest-component equations use community sizes and inter-community degrees, rather than the precise internal community shapes.When HCM* communities remain connected, the same equations give the largest-component size for both models.
- Network statistics: HCM and HCM* match the original network's assortativity more closely than a configuration model, although HCM's observed values can differ from its theoretical values.The discrepancy is attributed to simple-graph constraints omitted from the theoretical estimate, especially the effect of self-loops on assortativity.
- Community preservation: Community-structure overlap is generally large, but it is smaller for the AS network because its less-dense communities are more easily shifted by inter-community rewiring.HCM* can also produce disconnected communities; this is less likely when communities are denser.
Supplementary Note 4
The supplementary note defines several percolation and epidemic processes by specifying how vertices or edges are removed or infected and which final or time-dependent quantity is measured.
- Bond percolation: Bond percolation independently deletes each edge with probability 1 − p and measures the largest-component fraction.
- Site percolation: Site percolation independently deletes each vertex and its adjacent edges with probability 1 − p, then measures the largest-component fraction.
- Targeted attack: Targeted attack removes a fraction p of vertices in descending degree order and measures the remaining giant-component fraction.
- Bootstrap percolation: Bootstrap percolation starts with randomly selected infected vertices and repeatedly infects vertices having at least t infected neighbors; the analysis uses t = 2.The measured outcome is the final fraction of infected vertices.
- SIR epidemic: In the SIR model, one uniformly selected vertex is initially infected, infections occur at rate β, recovery occurs at rate γ, and the infected-plus-recovered fraction is tracked over time.The specified parameters are γ = 1 and β = 3 ⟨d⟩/γ.
Supplementary Discussion
HCM fixes all intra-community edges, whereas HCM* randomizes them to avoid overfitting. In most cases, this randomization changes many internal edges, except where community size or degree structure leaves few admissible graphs.
- Supplementary Discussion: HCM may overfit because it keeps the data set's entire set of intra-community edges fixed.HCM* was introduced partly to address this concern by randomizing internal as well as inter-community edges.
- Supplementary Discussion: HCM* generally rewires a large fraction of intra-community edges, but few edges change in small, complete, or star-shaped communities.These cases offer few simple graphs with the same degree sequence, sometimes leaving only one possible graph.
Supplementary Tables
The supplementary tables summarize assortativity, the fraction of internal community edges, and HCM* community connectedness and structural overlap.
- Supplementary Table 1: Supplementary Table 1 compares assortativity for HCM, HCM*, and CM against the real network and the theoretical HCM value.Each reported model value is averaged over 500 generated graphs.
- Supplementary Table 2: Supplementary Table 2 reports the fraction of data-set edges located inside communities.
- Supplementary Table 3: Supplementary Table 3 reports HCM* community connectedness and overlap between generated and original community structures.The overlap is defined using the similarity measure introduced in equation (16).
Supplementary Figures
The supplementary figures compare HCM, HCM*, and CM with real-world networks across bootstrap, targeted-attack, site-percolation, SIR, rewiring, and distance analyses. Results are averaged over generated graphs, with the figures specifying the procedures and parameters for each comparison.
- Bootstrap percolation infects vertices with at least 2 infected neighbors after random initial seeding, and reports final infected fractions averaged over 500 generated graphs.
- Targeted attack removes the highest-degree 1 −p fraction of vertices, while site percolation independently removes each vertex with probability 1 −p before measuring the largest component.
- SIR panels report infected and recovered individuals using γ = 1 and β = 3 ⟨d⟩/γ, with averages over 500 generated graphs.
- For HCM*, each dot represents a community and the rewired-edge fraction compares randomized intra-community edges with edges absent from the original community.
- Network distances are estimated from all pairwise distances among 5,000 sampled nodes, with HCM, HCM*, and CM values averaged over 100 generated graphs.