Journal
IEEE TRANSACTIONS ON BIG DATA
Volume 6, Issue 1, Pages 29-42Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TBDATA.2018.2865805
Keywords
Graphs and networks; graph algorithms; graph sampling; eigenvalues; spectral graph theory
Funding
- National Science Foundation [1250786]
- Div Of Information & Intelligent Systems
- Direct For Computer & Info Scie & Enginr [1250786] Funding Source: National Science Foundation
Ask authors/readers for more resources
Eigenvalues of a graph are of high interest in graph analytics for Big Data due to their relevance to many important properties of the graph including network resilience, community detection and the speed of viral propagation. Accurate computation of eigenvalues of extremely large graphs is usually not feasible due to the prohibitive computational and storage costs and also because full access to many social network graphs is often restricted to most researchers. In this paper, we present a series of new sampling algorithms which solve both of the above-mentioned problems and estimate the two largest eigenvalues of a large graph efficiently and with high accuracy. Unlike previous methods which try to extract a subgraph with the most influential nodes, our algorithms sample only a small portion of the large graph via a simple random walk, and arrive at estimates of the two largest eigenvalues by estimating the number of closed walks of a certain length. Our experimental results using real graphs show that our algorithms are substantially faster while also achieving significantly better accuracy on most graphs than the current state-of-the-art algorithms.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available