Influence maximization over strategic diffusion in social networks

We study the problem of diffusion speed maximization over strategic diffusion, where individuals decide to adopt a new behavior or not based on a networked coordination game with their neighbors. For a variety of topological structures of social networks, we design polynomial-time algorithms that provide provable approximation guarantees. By analyzing three graph classes, i.e., Erdös-Rényi, planted partition and geometrically structured graphs, we obtain new topological insights, which does not exists in the literature for popular epidemic-based models. Our results first imply that for globally well-connected graphs, a careful seeding is not necessary. On the other hand, for locally well-connected graphs, their clustering characteristics should be intelligently exploited for good seeding, where seeding inside and intersection of clusters are important for such graphs having big and small clusters, respectively. We believe that these new insights will provide useful tools to understand and control the sociological evolution of innovations spread over large-scale social networks.