Communications and Signal Processing Seminar

Impact of Community Structure on Cascades

Vijay SubramanianAssociate ProfessorUniversity of Michigan, Department of EECS

The threshold model is widely used to study the propagation of opinions and technologies in social networks. In this model individuals adopt the new behavior based on how many neighbors have already chosen it. We study cascades under the threshold model on sparse random graphs with community structure to see whether the existence of communities affects the number of individuals who finally adopt the new behavior. Specifically, we consider the permanent adoption model where nodes that have adopted the new behavior cannot change their state. When seeding a small number of agents with the new behavior, the community structure has little effect on the final proportion of people that adopt it, i.e., the contagion threshold is the same as if there were just one community. On the other hand, seeding a fraction of population with the new behavior has a significant impact on the cascade with the optimal seeding strategy depending on how strongly the communities are connected. In particular, when the communities are strongly connected, seeding in one community outperforms the symmetric seeding strategy that seeds equally in all communities. This is joint work with Mehrdad Moharrami and Mingyan Liu at the University of Michigan, and Marc Lelarge at ENS/INRIA, Paris, France.
Vijay Subramaniam received the B.Tech. degree in Electronics Engineering from IIT Madras in 1993. Subsequently, he obtained M.Sc. (Engg.) degree in Electrical Communication Engineering from IISc Bangalore in 1995 and Ph.D. in Electrical Engineering from University of Illinois at Urbana-Champaign. He worked in the research arm of the Networks Business Sector of Motorola in Arlington Heights, Illinois, USA until May 2006. In May 2006, he moved to the Hamilton Institute of the National University of Ireland, Maynooth as a Research Fellow. During Summer 2010, he was a visiting reseacher at LIDS MIT. From Nov 2010 to Oct 2011, he was a Senior Research Associate in the EECS Department at Northwestern University. From November 2011 until August 2014 he was a Research Assistant Professor in the EECS Department at Northwestern University. Currently, he is an Assistant Professor in the EECS Department at the University of Michigan. His interests are in stochastic modeling, communications, information theory and applied mathematics. A large portion of his past work has been on probabilistic analysis of communication networks, especially analysis of scheduling and routing algorithms. In the past he has also done some work with applications in immunology and coding of stochastic processes. His current research interests are on game theoretic and economic modeling of socio-technological systems and networks, and the analysis of associated stochastic processes.

Sponsored by


Faculty Host

Dave Neuhoff