Logo image
Back
On estimating the Spectral Radius of large graphs through subgraph sampling
Conference proceeding

On estimating the Spectral Radius of large graphs through subgraph sampling

Xiaoyu Chu and Harish Sethu
2015 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), v 2015-, pp 432-437
Apr 2015
DOI: https://doi.org/10.1109/INFCOMW.2015.7179423

Abstract

Accuracy Algorithm design and analysis Communication networks Conferences Eigenvalues and eigenfunctions Greedy algorithms Social network services
Extremely large graphs, such as those representing the Web or online social networks, require prohibitively large computational resources for an analysis of any of their complex properties. In this paper, we investigate an algorithmic approach to overcoming this difficulty by inferring key properties of the full graph using a strategic sample of small subgraphs of the graph. We focus, in particular, on the spectral radius (the largest eigenvalue of the adjacency matrix) of the graph because of its relationship to multiple highly relevant properties of graphs. We describe the Spectral Radius Estimator (SRE), a new greedy algorithm based on adding nodes with high estimated eigenvalue centrality into sample subgraphs. We present results on the performance of the SRE on real-world graphs and show that it estimates the spectral radius of real graphs with 98% to 99.99% accuracy using a subgraph of size less than about 4% of the full graph. This work demonstrates the feasibility and the potential of subgraph sampling as a computationally cheap means of inferring complex properties of extremely large graphs.

Metrics

13 Record Views
4 citations in Scopus

Details

Logo image