Algorithms to Affect Influence Propagation on Large Graphs

Dr. Hanghang Tong, IBM Watson Research Center

Wednesday February 15, 2012 at 12:00 PM in CBIM 22 (Multipurpose Room)

Faculty Host: Tina Eliassi-Rad

Abstract: Large graphs are everywhere, and they are becoming a prevalent platform for the masses to interact and disseminate a variety of information (e.g., memes, opinions, rumors, etc). Controlling the outcome of such dissemination on a large graph is an interesting problem in many disciplines, such as epidemiology, computer security, marketing, etc. In this talk, we focus on the problem of optimally affecting the outcome of influence propagation by manipulating the underlying graph structure. We show that for a large family of influence propagation models, the problem becomes optimizing the leading eigenvalue of an appropriately defined system matrix associated with the underlying graph. We then present two algorithms as the instantiations of such an optimization problem - one to minimize the leading eigenvalue (e.g., stopping virus propagation) by deleting nodes from the graph, and the other to maximize the eigenvalue (e.g., promoting product adoption) by adding edges to the graph.

Bio: Dr. Hanghang Tong is currently a research staff member at IBM T.J. Watson Research Center. Before that, he was a Post-doctoral fellow in Carnegie Mellon University. He received his M.Sc and Ph.D. degree from Carnegie Mellon University in 2008 and 2009, both majored in Machine Learning. His research interest is in large scale data mining for graphs and multimedia. He was a co-PI in NSF sponsored project on virus and influence propagation on large graphs. He is currently a co-PI in two DARPA sponsored projects on computational social science (ADAMS and SMISC). He is an IBM PI and task lead in the Social and Cognitive Networks Academic Research Center (SCNARC) sponsored by Army Research Lab. His current task focuses on composite networks in organization and team performance. He has received several awards, including best research paper award in ICDM 2006 and best paper award in SDM 2008. He has published over 40 referred articles and served as a program committee member of SIGKDD, PKDD, and WWW.

Suggested readings:

  • Hanghang Tong, B. Aditya Prakash, Charalampos E. Tsourakakis, Tina Eliassi-Rad, Christos Faloutsos, and Duen Horng Chau. On the Vulnerability of Large Graphs. IEEE Int. Conf. on Data Mining (ICDM), 2010.