Eigen-Optimization on Large Graphs by Edge Manipulation
Abstract
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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jun 14, 2016
- Source ID
- 10.1145/2903148
Entities
People
- B. Aditya Prakash
- Chen Chen
- Christos Faloutsos
- Hanghang Tong
- Michalis Faloutsos
- Tina Eliassi-rad
Organizations
- Arizona State University
- Carnegie Mellon University
- Defense Advanced Research Projects Agency
- Defense Threat Reduction Agency
- Lawrence Livermore National Laboratory
- National Endowment for the Humanities
- National Institute for Health and Care Research
- National Science Foundation
- Oak Ridge National Laboratory
- Rutgers University
- United States Army Research Laboratory
- University of New Mexico
- Virginia Tech