On the eigen‐functions of dynamic graphs: Fast tracking and attribution algorithms
Abstract
Eigen‐functions are of key importance in graph mining since they can be used to approximate many graph parameters, such as node centrality, epidemic threshold, graph robustness, with high accuracy. As real‐world graphs are changing over time, those parameters may get sharp changes correspondingly. Taking virus propagation network for example, new connections between infected and susceptible people appear all the time, and some of the crucial infections may lead to large decreasing on the epidemic threshold of the network. As a consequence, the virus would spread around the network quickly. However, if we can keep track of the epidemic threshold as the graph structure changes, those crucial infections would be identified timely so that counter measures can be taken proactively to contain the spread process. In our paper, we propose two online eigen‐functions tracking algorithms which can effectively monitor those key parameters with linear complexity. Furthermore, we propose a general attribution analysis framework which can be used to identify important structural changes in the evolving process. In addition, we introduce an error estimation method for the proposed eigen‐functions tracking algorithms to estimate the tracking error at each time stamp. Finally, extensive evaluations are conducted to validate the effectiveness and efficiency of the proposed algorithms. © 2016 Wiley Periodicals, Inc. Statistical Analysis and Data Mining: The ASA Data Science Journal, 2016
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jun 30, 2016
- Source ID
- 10.1002/sam.11310
Entities
People
- Chen Chen
- Hanghang Tong
Organizations
- Arizona State University
- Defense Advanced Research Projects Agency
- National Institutes of Health
- National Science Foundation
- United States Army Research Laboratory