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 prob-lem of optimally affecting the outcome of dissemination by ma-nipulating 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 opti-mizing 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 prob-lem - 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 is available, Tong will also introduce other work on analyzing big graphs.