Evolution of degree distribution during measurement

When one wants to study a complex network, one generally first has to conduct an intricate and expensive measurement. This measurement gives a sample of the network which is generally partial and may be biased.

In Complex Network Measurements: Estimating the Relevance of Observed Properties, we propose to observe how the properties observed on the sample evolve when the sample grows. If it does not converge, then certainly stopping the measurement at some time and considering the obtained sample as representative of the whole makes little sense: the observed properties would be significantly different on a larger or smaller sample.

Degree distribution is one of the main properties of complex networks. It gives, for each possible value of the degree (on the horizontal axis), the fraction of nodes with this degree (vertical axis).

The video above represents the evolution, as the sample grows, of the observed degree distribution of a peer-to-peer exchange graph (see the paper for details).

It appears clearly that, although its global shape seems to converge, the precise degree distribution still changes when the sample grows, even by the end of the measurement. One may expect that the leftmost points, i.e. the fraction of nodes of degree i for small values of i, will reach a steady value. However, in this example, even these simple statistics still evolve.

Finally, we conclude that the observed degree distribution should not be trusted if precise values are needed. Though, qualitative conclusions like the heterogeneity of the observed degree distribution are still possible.

Category:

Science & Technology

Tags:

• measurement
• degree distribution
• complex networks

[MVBDProductions]

What is it?