Maximizing influence propagation in networks with community structure
Authors:
- 1 May 2009
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 79 (5) , 056102
Abstract
We consider the algorithmic problem of selecting a set of target nodes that cause the biggest activation cascade in a network. In case when the activation process obeys the diminishing return property, a simple hill-climbing selection mechanism has been shown to achieve a provably good performance. Here we study models of influence propagation that exhibit critical behavior and where the property of diminishing returns does not hold. We demonstrate that in such systems the structural properties of networks can play a significant role. We focus on networks with two loosely coupled communities and show that the double-critical behavior of activation spreading in such systems has significant implications for the targeting strategies. In particular, we show that simple strategies that work well for homogenous networks can be overly suboptimal and suggest simple modification for improving the performance by taking into account the community structure.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Critical phenomena in complex networksReviews of Modern Physics, 2008
- The Structure and Function of Complex NetworksSIAM Review, 2003
- Evolution of networksAdvances in Physics, 2002
- A simple model of global cascades on random networksProceedings of the National Academy of Sciences, 2002
- Immunization of complex networksPhysical Review E, 2002
- Statistical mechanics of complex networksReviews of Modern Physics, 2002
- Epidemic dynamics and endemic states in complex networksPhysical Review E, 2001
- Breakdown of the Internet under Intentional AttackPhysical Review Letters, 2001
- Epidemic Spreading in Scale-Free NetworksPhysical Review Letters, 2001
- Threshold Models of Collective BehaviorAmerican Journal of Sociology, 1978