Exploring complex networks through random walks

Most real complex networks—such as protein interactions, social contacts, and the Internet—are only partially known and available to us. While the process of exploring such networks in many cases resembles a random walk, it becomes a key issue to investigate and characterize how effectively the nodes and edges of such networks can be covered by different strategies. At the same time, it is critically important to infer how well can topological measurements such as the average node degree and average clustering coefficient be estimated during such network explorations. The present article addresses these problems by considering random, Barabási-Albert (BA), and geographical network models with varying connectivity explored by three types of random walks: traditional, preferential to untracked edges, and preferential to unvisited nodes. A series of relevant results are obtained, including the fact that networks of the three studied models with the same size and average node degree allow similar node and edge coverage efficiency, the identification of linear scaling with the size of the network of the random walk step at which a given percentage of the nodes/edges is covered, and the critical result that the estimation of the averaged node degree and clustering coefficient by random walks on BA networks often leads to heavily biased results. Many are the theoretical and practical implications of such results.

Figure 1

A simple network (a) and two incompletely specified networks obtained by a random walk considering neighboring nodes and (b) the latter plus the edges between adjacent nodes (c). The gray nodes correspond to those sampled during the random walk.

Figure 2

The ratio of tracked edges in terms of the steps $t$ for $N=3000$ and $N=10000$ considering the values of $m$ as presented in the legend, for the random (left), BA (middle), and geographical (right) network models.

Figure 3

The quarter-lives of the percentage of visited nodes (left column) and edges (right column) for the random (top), BA (middle), and geographical (bottom) models, for traditional, preferential to untracked nodes, and preferential to unvisited edges random walk strategies.

Figure 4

Slopes of the ratios of visited nodes obtained for traditional random walks for $m=3,4,\dots ,8$ considering random, BA, and geographical network models (in logarithmic scale). Error bars show the asymptotic standard error of the regression.

Figure 5

Curve (actually a kind of random walk) defined by the estimations $\mathbf{(}k\left(t\right),C\left(t\right)\mathbf{)}$, through traditional random walk, of the average node degree $k\left(t\right)$ and average clustering coefficient $C\left(t\right)$ in a random (a), BA (b), and geographical (c) network with $N=10000$ and $m=5$.

Figure 6

Average degree (a), (b), and (c); and average clustering coefficient (d), (e), and (f); for the Erdős-Rényi (a), and (d); Barabási-Albert (b), and (e), and geographical (c), and (f) network models. The values shown are ratios from averages computed in the random walks (after 50 000 steps) to the real network values.

Figure 7

Degree distributions for the random (a), BA (b), and geographical (c) networks, computed for the real network and for the nodes on the walk (after 50 000 steps). Note that the distribution of the BA case is shown in logarithmic axes.