May 16, 2014

Hanghang Tong.

Hanghang Tong: Assistant Professor, Computer Science Department @ City College, City University of New York

Optimal Dissemination on Graphs: Theories and Algorithms

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 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) and the other to maximize the eigenvalue (e.g., promoting product adoption). If time is available, Tong will also introduce other work on analyzing big graphs.