King's College London

Research portal

Estimating network parameters using random walks

Research output: Contribution to journalArticlepeer-review

Original languageEnglish
Article number168
Number of pages19
JournalSocial Network Analysis and Mining
Volume4
Issue number1
Early online date22 Feb 2014
DOIs
Accepted/In press23 Nov 2013
E-pub ahead of print22 Feb 2014
PublishedDec 2014

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 and the World Wide Web (WWW). 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. However, 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 of its neighbours, and their labels. As examples of this approach, we present 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. We also give a general method to count any type of small connected subgraph, of which vertices, edges and triangles are specific examples. Additionally we present experimental estimates for n, m, t we obtained using our methods on real or synthetic networks. The synthetic networks were random graphs with power-law degree distributions and designed to have a large number of triangles. We used these graphs as they tend to correspond to the structure of large online networks. The real networks were samples of the WWW and social networks obtained from the SNAP database. In order to test that the methods are indeed practical, the total number of steps made by the walk was limited to at most the size n of the network. In fact the estimates appear to converge to the correct value at 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