At a Glance
- Created a hybrid contagion-blocking strategy using community detection and targeted inter-community links.
- This approach outperformed purely structural or dynamic methods, especially for complex contagions.
- Demonstrated that combining network structure and contagion dynamics yields better containment.
Visual highlights
The Problem
- Pure structural (proactive) blocking can fail to stop spread, especially for complex contagions.
- Pure dynamics-based (reactive) methods are effective but slow and require detailed model data.
- Little prior work addressed blocking contagions that require multiple confirmations (complex contagions).
The Solution
- Developed a cluster-based algorithm: partition the network into communities, then focus blocking on inter-community connections.
- Assumed contagion spreads quickly inside communities, so prioritized preventing cross-community transmission.
- Implemented a hybrid node selection approach combining structural metrics and contagion simulations.
- Tested on multiple networks, showing this hybrid method outperformed purely centrality- or simulation-based strategies.
Architecture Overview
- Used a progressive threshold model (complex contagion) for simulations (nodes require ≥2 infected neighbors to activate).
- Applied community detection (e.g., modularity clustering) to divide the network into dense clusters.
- Identified all edges between communities as potential “choke points” for contagion crossing.
- Applied reactive blocking on these boundary regions: after limited spread, froze a minimal set of boundary nodes to stop transmission.
Results and Impacts
- The community-based hybrid method contained complex contagions more effectively than degree-based interventions.
- It matched or surpassed the performance of state-of-the-art simulation-only methods, validating the hybrid approach.
- Tested on three real networks, demonstrating the strategy’s scalability and generality.
- Provided an effective strategy for complex contagions, influencing later contagion intervention research.
Skills and Tools Used
| Technique/Skill | Tools/Implementation |
|---|---|
| Community detection | Graph clustering (modularity algorithms) |
| Complex contagion simulation | Threshold model testing and refinement |
| Hybrid algorithm design | Combined structural metrics with simulation feedback |
| Empirical evaluation | Contagion diffusion code and statistical analysis |
| Multi-domain insight | Combined social network analysis with contagion modeling |
Cross-Project Capabilities
- Community-based blocking complements edge removal by focusing on cross-community links as critical cuts.
- Approach applies to other domains (e.g., immunization or cybersecurity) that can leverage community structure.
- Hybrid proactive-reactive concept influenced integrated strategies across contagion projects, showing combined methods yield better results.
Published Papers/Tools
- Blocking Complex Contagions Using Community Structure – AAMAS Workshop 2013. Paper
- Developed the Community-based Node Selection (CNS) hybrid blocking algorithm.
- Extended results in a journal submission, with this work incorporated into broader contagion intervention studies.