Logo image
Back
Closed Walk Sampler: An Efficient Method for Estimating Eigenvalues of Large Graphs
Journal article   Open access   Peer reviewed

Closed Walk Sampler: An Efficient Method for Estimating Eigenvalues of Large Graphs

Guyue Han and Harish Sethu
IEEE transactions on big data, v 6(1), pp 29-42
01 Mar 2020
DOI: https://doi.org/10.1109/TBDATA.2018.2865805
url
https://doi.org/10.1109/tbdata.2018.2865805View
Accepted (AM)Open Access (Publisher-Specific),  Open

Abstract

Big Data Chemistry eigenvalues Eigenvalues and eigenfunctions graph algorithms graph sampling Graph theory Graphs and networks Iterative methods Social network services spectral graph theory Symmetric matrices
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.

Metrics

7 Record Views
4 citations in Web of Science

Details

InCites Highlights

Data related to this publication, from InCites Benchmarking & Analytics tool:

Web of Science research areas
Computer Science, Information Systems
Computer Science, Theory & Methods
Logo image