Eigen-optimization on Large Graphs by Edge Manipulation

C. Chen, H. Tong, B.A. Prakash, T. Eliassi-Rad, M. Faloutsos, C. Faloutsos
ACM Transactions on Knowledge Discovery in Data (TKDD)
10(4), Article 49, June 2016.
July 4, 2016


Large graphs are  prevalent in many applications and enable a variety of information  dissemination processes, e.g., meme, virus, and influence propagation. How  can we optimize the underlying graph structure to affect the outcome of such  dissemination processes in a desired way (e.g., stop a virus propagation,  facilitate the propagation of a piece of good idea, etc)? Existing research  suggests that the leading eigenvalue of the underlying graph is the key  metric in determining the so-called epidemic threshold for a variety of  dissemination models. In this paper, we study the problem of how to optimally  place a set of edges (e.g., edge deletion and edge addition) to optimize the  leading eigenvalue of the underlying graph, so that we can guide the dissemination  process in a desired way. We propose effective, scalable algorithms for edge  deletion and edge addition, respectively. In addition, we reveal the  intrinsic relationship between edge deletion and node deletion problems.  Experimental results validate the effectiveness and efficiency of the  proposed algorithms.

Related publications