TY - CHAP

T1 - Fast Low-Cost Estimation of Network Properties Using Random Walks

AU - Cooper, Colin

AU - Radzik, Tomasz

AU - Siantos, Yiannis

N1 - © 2013 Springer International Publishing.

PY - 2013

Y1 - 2013

N2 - We study the use of random walks as an efficient estimator of global properties of large undirected graphs, for example the number of edges, vertices, triangles, and generally, the number of small fixed subgraphs. We consider two methods based on first returns of random walks: the cycle formula of regenerative processes and weighted random walks with edge weights defined by the property under investigation. We review the theoretical foundations for these methods, and indicate how they can be adapted for the general non-intrusive investigation of large online networks. The expected value and variance of first return time of a random walk decrease with increasing vertex weight, so for a given time budget, returns to high weight vertices should give the best property estimates. We present theoretical and experimental results on the rate of convergence of the estimates as a function of the number of returns of a random walk to a given start vertex. We made experiments to estimate the number of vertices, edges and triangles, for two test graphs.

AB - We study the use of random walks as an efficient estimator of global properties of large undirected graphs, for example the number of edges, vertices, triangles, and generally, the number of small fixed subgraphs. We consider two methods based on first returns of random walks: the cycle formula of regenerative processes and weighted random walks with edge weights defined by the property under investigation. We review the theoretical foundations for these methods, and indicate how they can be adapted for the general non-intrusive investigation of large online networks. The expected value and variance of first return time of a random walk decrease with increasing vertex weight, so for a given time budget, returns to high weight vertices should give the best property estimates. We present theoretical and experimental results on the rate of convergence of the estimates as a function of the number of returns of a random walk to a given start vertex. We made experiments to estimate the number of vertices, edges and triangles, for two test graphs.

UR - http://www.scopus.com/inward/record.url?scp=84893107771&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-03536-9_11

DO - 10.1007/978-3-319-03536-9_11

M3 - Conference paper

AN - SCOPUS:84893107771

SN - 9783319035352

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 130

EP - 143

BT - Algorithms and Models for the Web Graph

A2 - Bonato, Anthony

A2 - Mitzenmacher, Michael

A2 - Pralat, Pawel

PB - Springer International Publishing

T2 - 10th International Workshop on Algorithms and Models for the Web Graph, WAW 2013

Y2 - 14 December 2013 through 15 December 2013

ER -