King's College London

Research portal

Fast Low-Cost Estimation of Network Properties Using Random Walks

Research output: Contribution to journalArticlepeer-review

Original languageEnglish
Pages (from-to)221-238
Number of pages18
JournalInternet Mathematics 1
Issue number4
Early online date24 Mar 2016
Accepted/In press26 Feb 2016
E-pub ahead of print24 Mar 2016
Published24 Mar 2016


King's Authors


We study the use of random walks as an efficient method to estimate global properties of large connected undirected graphs. Typical examples of the properties of interest include the number of edges, vertices, and triangles, and more generally, the number of small fixed subgraphs. We consider two methods based on first returns of random walks: (1) the cycle formula of regenerative processes and (2) 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 nonintrusive investigation of large online networks.The expected value and variance of the time of the first return 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.

Download statistics

No data available

View graph of relations

© 2020 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454