CS Colloquium: Finding Efficient Spreaders for Information Diffusion in Social Networks

Date and Location

Nov 07, 2018 - 3:00pm to 5:00pm
HFH 1132


Bolek Szymanski
Rensselaer Polytechnic Institute


Recent global events and their poor predictability are often attributed to the complexity of the world event dynamics. To improve the predictability, we use a simple but classic threshold model of contagion spreading in complex social systems in which information propagates with certain probability from nodes just activated to their non-activated neighbors. Diffusion cascades can be triggered by activation of even a small set of nodes. We consider the heterogeneity of individuals' susceptibility to new ideas. We investigate numerically and analytically the transition in the behavior of threshold-limited cascades in the presence of multiple initiators as the distribution of thresholds is varied between the two extreme cases of identical thresholds and a uniform distribution. We show that individuals' heterogeneity of susceptibility governs the dynamics, resulting in different sizes of initiators needed for consensus. Furthermore, given the impact of heterogeneity on the cascade dynamics, we introduce two new selection strategies for Influence Maximization. One of them focuses on finding the balance between targeting nodes which have high resistance to adoptions versus nodes positioned in central spots in networks. The second strategy focuses on the combination of nodes for reaching consensus, by targeting nodes which increase the group's influence. Our strategies outperform other existing strategies regardless of the susceptibility diversity and network degree assortativity. Initial activation of seeds is commonly performed in a single stage. We discuss a novel approach based on sequential seeding. We present experimental results comparing single stage and sequential approaches on directed and undirected graphs to the well-known greedy approach to provide the objective measure of the sequential seeding benefits. Surprisingly, applying sequential seeding to a simple degree-based selection leads to higher coverage than achieved by the expensive greedy approach currently considered the best heuristic.

Collaborators: Gyorgy Korniss, Panagiotis Karampourniotis, Casey Doyle (RPI); Jaroslaw Jankowski (SUT, Poland)

Dr. Boleslaw K. Szymanski is the Claire and Roland Schmitt Distinguished Professor of Computer Science and a Professor of Cognitive Science at RPI. He is the Founding Director of the ARL Social and Cognitive Networks Academic Research Center and of the RPI NEST Center. He received Ph.D. in Computer Science from National Academy of Sciences in Warsaw, in 1976. He published over 400 scientific articles, is a foreign member of the National Academy of Science in Poland, an IEEE Fellow, and a National Lecturer for the ACM. In 2009, he received the Wilkes Medal of British Computer Society and in 2003 the Willey Distinguished Faculty Award from RPI. His current research interests focus on network science and computer and social networks.

Host: Ambuj Singh, Professor of Computer Science