Hanghang Tong, CUNY City University of New York

Friday, 10/25, 2:30-3:30 pm, CS 2311

Optimal Dissemination on Graphs: Theory and Algorithms

Abstract

Big graphs are prevalent and are becoming a popular platform for the dissemination of a variety of information (e.g., viruses, memes, opinions, rumors, etc). In this talk, we focus on the problem of optimally affecting the outcome of dissemination by manipulating the underlying graph structure. We aim to answer two questions: (1) what are the key graph parameters for the so-called tipping point? and (2) how can we design effective algorithms to optimize such parameters in a desired way? 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) and the other to maximize the eigen-value (e.g., promoting product adoption). If time allowed, I will also introduce our other work on analyzing big graphs.

Bio

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 70 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).