Logo image
Back
Closed walk sampler: An efficient method for estimating the spectral radius of large graphs
Conference proceeding

Closed walk sampler: An efficient method for estimating the spectral radius of large graphs

Guyue Han and Harish Sethu
2017 IEEE International Conference on Big Data (Big Data), v 2018-, pp 616-625
Dec 2017
DOI: https://doi.org/10.1109/BigData.2017.8257977

Abstract

Algorithm design and analysis Eigenvalues and eigenfunctions Graph theory Iterative methods Social network services Symmetric matrices Big Data
The spectral radius of a graph, i.e., the largest eigenvalue of its adjacency matrix, is of high interest in graph analytics for Big Data due to its relevance to many important properties of the graph including network resilience, community detection and the speed of viral propagation. Accurate computation of the largest eigenvalue of extremely large graphs is infeasible 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 new and efficient algorithm called Closed Walk Sampler (cWalker) which solves both of the above-mentioned problems. Unlike previous methods which try to extract a subgraph with the most influential nodes, the cWalker samples only a small portion of the large graph via a simple random walk, and arrives at an estimate of the largest eigenvalue by estimating the number of closed walks of a certain length. Our experimental results using real graphs show that the cWalker is substantially faster while also achieving significantly better accuracy on most graphs than the current state-of-the-art algorithms.

Metrics

12 Record Views
2 citations in Web of Science
1 citations in Scopus

Details

Logo image