Maximizing influence propagation in networks with community structure

Aram Galstyan, Vahe Musoyan, Paul Cohen

    Research output: Contribution to journalArticlepeer-review

    36 Scopus citations


    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.

    Original languageEnglish (US)
    Article number056102
    JournalPhysical Review E - Statistical, Nonlinear, and Soft Matter Physics
    Issue number5
    StatePublished - May 1 2009

    ASJC Scopus subject areas

    • Statistical and Nonlinear Physics
    • Statistics and Probability
    • Condensed Matter Physics


    Dive into the research topics of 'Maximizing influence propagation in networks with community structure'. Together they form a unique fingerprint.

    Cite this