  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.
