Statistical properties of sampled networks

We study the statistical properties of the sampled scale-free networks, deeply related to the proper identification of various real-world networks. We exploit three methods of sampling and investigate the topological properties such as degree and betweenness centrality distribution, average path length, assortativity, and clustering coefficient of sampled networks compared with those of original networks. It is found that the quantities related to those properties in sampled networks appear to be estimated quite differently for each sampling method. We explain why such a biased estimation of quantities would emerge from the sampling procedure and give appropriate criteria for each sampling method to prevent the quantities from being overestimated or underestimated.

Figure 1

Three kinds of sampling method. (a) Node sampling: Select the circled nodes, keep three links among them, and the isolated node is removed. (b) Link sampling: Select the three circled links and six nodes attached to them. (c) Snowball sampling: Starting from the circled node, select nodes and links attached to them by tracing links.

Figure 2

Changes of degree exponent $\gamma$ for each network’s sampled networks according to the sampling fraction $\alpha$, averaged over ten independent realizations. Empty squares (◻) stand for node sampling, filled squares (∎) for link sampling, and empty triangles (▵) for snowball sampling. The horizontal dashed lines are the values for the original exponent of each network, and the solid lines represent the values obtained by Eq. (5).

Figure 3

Degree distribution for sampled networks of (a) C. elegans neural network with $\alpha =120∕297$ and (b) Zachary karate club network with $\alpha =20∕34$, obtained from the node sampling. Empty circles are simulation results from 1000 sampling processes. Solid lines correspond to Eq. (2) and dashed lines to Eq. (5). Insets show the part of large degrees, where the difference between two formulae is prominent, for each graph.

Figure 4

Change of nodes’ degree in BA network for snowball sampling. The sampling fraction is $10000∕30000$.

Figure 5

Changes of APL for each network’s sampled networks according to the ratio $\xi$ of the size of giant component in the sampled networks to that of the original ones, averaged over ten independent realizations. Empty squares (◻) stand for node sampling, filled squares (∎) for link sampling, and empty triangles (▵) for snowball sampling. The horizontal dashed lines are the values for the original APL of each network, and the other lines are guides to the eyes.

Figure 6

Changes of BC exponent $\eta$ for each network’s sampled networks according to the sampling fraction $\alpha$, averaged over ten realizations. Empty squares (◻) stand for node sampling, filled squares (∎) for link sampling, and empty triangles (▵) for snowball sampling. The horizontal dashed lines are the values for the original exponent of each network, and the other lines are guides to the eyes.

Figure 7

Degree and BC of nodes in a sampled network of BA network by node sampling. The sampling fraction is $10000∕30000$. The value of BC is rescaled by the number of nodes.

Figure 8

Changes of assortativity $r$ for each network’s sampled networks according to the sampling fraction $\alpha$, averaged over ten realizations. Empty squares (◻) stand for node sampling, filled squares (∎) for link sampling, and empty triangles (▵) for snowball sampling. The horizontal dashed lines are the values for the original assortativity of each network, and the other lines are guides to the eyes.

Figure 9

$⟨k_{nn}\left(k\right)⟩$ distribution for sampled networks of (a) PIN, (b) arxiv.org by snowball sampling.

Figure 10

Changes of clustering coefficient $C$ for each network’s sampled networks according to the sampling fraction $\alpha$, averaged over ten realizations. Empty squares (◻) stand for node sampling, filled squares (∎) for link sampling, and empty triangles (▵) for snowball sampling. The horizontal dashed lines are the values for the original clustering coefficient of each network, and the other lines are guides to the eyes.