King's College London

Research portal

Fast Low-Cost Estimation of Network Properties Using Random Walks

Research output: Chapter in Book/Report/Conference proceedingConference paper

Original languageEnglish
Title of host publicationAlgorithms and Models for the Web Graph
Subtitle of host publication10th International Workshop, WAW 2013, Cambridge, MA, USA, December 14-15, 2013, Proceedings
EditorsAnthony Bonato, Michael Mitzenmacher, Pawel Pralat
PublisherSpringer International Publishing
Pages130-143
Number of pages14
ISBN (Electronic)9783319035369
ISBN (Print)9783319035352
DOIs
Published2013
Event10th International Workshop on Algorithms and Models for the Web Graph, WAW 2013 - Cambridge, MA, United States
Duration: 14 Dec 201315 Dec 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8305 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference10th International Workshop on Algorithms and Models for the Web Graph, WAW 2013
Country/TerritoryUnited States
CityCambridge, MA
Period14/12/201315/12/2013

Bibliographical note

© 2013 Springer International Publishing.

King's Authors

Abstract

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.

View graph of relations

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