Maximizing Influence Propagation in Networks with Community Structure
arXiv:0905.1108 · doi:10.1103/PhysRevE.79.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 returns 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 homogeneous networks can be overly sub-optimal, and suggest simple modification for improving the performance, by taking into account the community structure.
7 pages, 8 figures
References in corpus (13)
- Statistical mechanics of complex networks
- The structure and function of complex networks
- Community structure in social and biological networks
- Modularity and community structure in networks
- Epidemic spreading in scale-free networks
- Random graphs with arbitrary degree distributions and their applications
- Evolution of networks
- Comparing community structure identification
- Critical phenomena in complex networks
- Epidemic dynamics and endemic states in complex networks
- Breakdown of the Internet under intentional attack
- Immunization of complex networks
- Cascading Dynamics in Modular Networks
Cited by in corpus (4)
- Probing Limits of Information Spread with Sequential Seeding
- Stochastic Dynamic Programming Heuristics for Influence Maximization-Revenue Optimization
- Balancing Speed and Coverage by Sequential Seeding in Complex Networks
- Influence Maximization for Social Good: Use of Social Networks in Low Resource Communities