EECS500 Spring 2013 Department Seminar

Hanghang Tong
Optimal Dissemination on Graphs: Theory and Algorithms.
IBM TJ Watson Research (Data mining)
White Bldg., Room 411
11:30am - 12:30pm
March 21, 2013

Large graphs are everywhere, and they are becoming a prevalent platform for the masses to interact and disseminate a variety of information (e.g., viruses, 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 dissemination by manipulating the underlying graph structure. We show that for a large family of dissemination models, the problem becomes optimizing the leading eigen-value 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 eigen-value (e.g., stopping virus propagation) by deleting nodes from the graph, and the other to maximize the eigen-value (e.g., promoting product adoption) by adding edges to the graph.


Hanghang Tong is currently an assistant professor at Computer Science Department, City College, City University of New York. Before that, he was a research staff member at IBM T.J. Watson Research Center and 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. His research has been funded by NSF, DARPA and ARL. He has received several awards, including best paper award in CIKM 2012, best paper award in SDM 2008 and best research paper award in ICDM 2006. He has published over 60 referred articles and more than 20 patents. He has served as a program committee member in top data mining, databases and artificial intelligence venues (e.g., SIGKDD, SIGMOD, AAAI, WWW, CIKM, etc).