Abstract

Most real-world networks have a modular structure, i.e., they are composed of clusters of well connected nodes, with relatively lower density of links across different clusters. Here we report on our studies of a simple cascading process in a structured heterogeneous population composed of two loosely coupled communities. We demonstrate that under certain conditions the cascading dynamics in such a network has a two-tiered structure that characterizes activity spreading at different rates in the communities. We also demonstrate that the structure has implication on problems such as influence maximization. In particular, it is shown that targeting heuristics that work provably well for homogenous networks can produce significantly sub-optimal results for heterogenous networks. We suggest a simple modification of the heuristics that accounts for the community structure, and observe improved performance.

Date

November 20, 2013

Authors

Aram Galstyan

Book

Handbook of Human Computation

Pages

779-789

Publisher

Springer New York