Sampling properties of random graphs: The degree distribution

We discuss two sampling schemes for selecting random subnets from a network, random sampling and connectivity dependent sampling, and investigate how the degree distribution of a node in the network is affected by the two types of sampling. Here we derive a necessary and sufficient condition that guarantees that the degree distributions of the subnet and the true network belong to the same family of probability distributions. For completely random sampling of nodes we find that this condition is satisfied by classical random graphs; for the vast majority of networks this condition will, however, not be met. We furthermore discuss the case where the probability of sampling a node depends on the degree of a node and we find that even classical random graphs are no longer closed under this sampling regime. We conclude by relating the results to real Eschericia coli protein interaction network data.

Figure 1

(Color online) Sampling nodes from the network (top) will give rise to subnets (bottom). If edges are only observed if both nodes incident on an edge are included in the subnet [indicated in bold (dark blue)], then the degree distributions (as well as other characteristics) of the subnet and global network will be different. In the text we show that sometimes, however, degree distributions in both networks can be related under random sampling of nodes.

Figure 2

(Color online) Degree distributions of full network and subnets obtained by sampling each node with probability $p=0.8$ and 0.2, respectively, for classical random graphs (a) and scale-free networks (b).

Figure 3

(Color online) Degree distributions of protein interaction network data available for E. coli in April of the years 2003, 2004, and 2005, respectively. As the fraction of sampled proteins decreases, statistical weight is shifted from the tail toward lower degrees.