King's College London

Research portal

Estimating network parameters using random walks

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review

Original languageEnglish
Title of host publicationProceedings of the 2012 4th International Conference on Computational Aspects of Social Networks, CASoN 2012
Pages33-40
Number of pages8
DOIs
Published2012
Event2012 4th International Conference on Computational Aspects of Social Networks, CASoN 2012 - Sao Carlos, Brazil
Duration: 21 Nov 201223 Nov 2012

Conference

Conference2012 4th International Conference on Computational Aspects of Social Networks, CASoN 2012
Country/TerritoryBrazil
CitySao Carlos
Period21/11/201223/11/2012

King's Authors

Abstract

Sampling from large graphs is an area of great interest, especially since the emergence of huge structures such as Online Social Networks (OSNs) and the World Wide Web (WWW). These networks, when viewed as graphs, often contain hundreds of millions of vertices and billions of edges. The large scale properties of a network can be summarized in terms of parameters of the underlying graph, such as the total number of vertices, edges and triangles. The large size of these networks makes it computationally expensive to obtain such structural properties of the underlying graph by exhaustive search. If we can estimate these properties by taking small but representative samples from the network, then size is no longer such a problem. In this paper we present a general framework to estimate network properties using random walks. These methods work under the assumption we are able to obtain local characteristics of a vertex during each step of the random walk, for example the number and labels of the neighboring vertices of a specific vertex These assumptions are relatively reasonable in practice, but may add some additional query cost to each step of the random walk. We also present some practical methods to estimate the total number of edges/links m, number of vertices/nodes n and number of connected triads of vertices (triangles) t in graphs with degree distributions which follow a power-law and higher number of triangles higher than expected in random graphs. We use these graphs since they tend to better correspond to the structure of large online networks, and in fact some of the data used are taken from such a network. Additionally we present experimental estimates for n, m, t we obtained using our methods on real or manufactured networks. In order to make the methods practical, the total number of steps made by the walk was limited to at most the size n of the network. In fact the results appear to converge for a lower number of steps, indicating that our proposed methods are feasible in practice.

View graph of relations

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