Topological Network Growth and the Superstar Effect

Abstract:

Information or influence spreading in online social networks is a network growth process. The popular "preferential attachment" growth model possesses power-law degree distributions observed in infrastructure networks like the Internet or the electric power-grid. In contrast, we find that information-propagation networks such as the micro-blogging site Twitter exhibit non-local phenomena in addition to power-law distributions. Specifically, there is always a "superstar" node with extremely high degree that is not explained by preferential attachment. The primary reason behind the inability of preferential attachment to predict superstars is the fact that it does not utilize any global "semantic" information. We propose a class of topological network growth models based upon semantic information captured by network centrality which accurately reproduces the properties of Twitter networks: power-law degree distribution and the existence of superstars.

Biography:

Tauhid is a PhD student advised by Professor Devavrat Shah. His research focuses on algorithm design for large-scale networks. He has developed algorithms for finding rumor sources in networks and for learning the community structure of networks. During an internship at Microsoft Research Cambridge in the summer of 2010 he designed a system to predict the spread of information on Twitter. He is also a Shell-MIT Energy Fellow.