What is the real size of a sampled network? The case of the Internet

Fabien Viger, Alain Barrat, Luca Dall’Asta, Cun-Hui Zhang, and Eric D. Kolaczyk

Phys. Rev. E 75, 056111 – Published 17 May 2007

Abstract

Most data concerning the topology of complex networks are the result of mapping projects which bear intrinsic limitations and cannot give access to complete, unbiased datasets. A particularly interesting case is represented by the physical Internet. Router-level Internet mapping projects generally consist of sampling the network from a limited set of sources by using traceroute probes. This methodology, akin to the merging of spanning trees from the different sources to a set of destinations, leads necessarily to a partial, incomplete map of the Internet. The determination of the real Internet topology characteristics from such sampled maps is therefore, in part, a problem of statistical inference. In this paper we present a twofold contribution in order to address this problem. First, we argue that inference of some of the standard topological quantities is, in fact, a version of the so-called “species” problem in statistics, which is important in categorizing the problem and providing some indication of its inherent difficulties. Second, we tackle the issue of estimating arguably the most basic of network characteristics—its number of nodes—and propose two estimators for this quantity, based on subsampling principles. Numerical simulations, as well as an experiment based on probing the Internet, suggest the feasibility of accounting for measurement bias in reporting Internet topology characteristics.

Received 10 January 2007

DOI:https://doi.org/10.1103/PhysRevE.75.056111

Authors & Affiliations

Fabien Viger¹, Alain Barrat^2,3,4, Luca Dall’Asta^2,3, Cun-Hui Zhang⁵, and Eric D. Kolaczyk⁶

¹LIP6, UMR 7606 du CNRS, Université de Paris-6, 4 place Jussieu, 75005, Paris, France
²LPT, UMR 8627 du CNRS, 91405 Orsay cedex, France
³Université Paris-Sud, 91405 Orsay cedex, France
⁴Complex Networks Lagrange Laboratory, ISI Foundation, Viale. S. Severo 65, 10133 Turin, Italy
⁵Department of Statistics, Rutgers University, 504 Hill Center, Busch Campus, Piscataway, NJ 08854–8019 USA
⁶Department of Mathematics and Statistics, Boston University, 111 Cummington Street, Boston, MA 02215 USA

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand

Issue

Vol. 75, Iss. 5 — May 2007

Reuse & Permissions

Access Options

Author publication services for translation and copyediting assistance advertisement

Images

Figure 1
A comparison of the quantities $N^{*} ∕ N$ and $E [N^{* *}] ∕ N^{*}$ , as a function, respectively, of $q_{T} = n_{T} ∕ N$ and $q_{T}^{*} = n_{T}^{*} ∕ N^{*}$ , for the three networks described in Sec. 5. Here $n_{S} = n_{S}^{*} = 10$ . The top row shows the averages of $N^{*} ∕ N$ and $E [N^{* *}] ∕ N^{*}$ over ten realizations of $G^{*}$ . The bottom row shows the average of the difference of these two quantities, relative to $N^{*} ∕ N$ , over the same ten realizations. The comparison in the top row confirms the validity of the assumption (8) underlying the resampling estimator derived in Sec. 4A, while the comparison in the bottom row indicates that better performance of the estimator can be expected with increasing $q_{T}$ (one standard deviation error bars are smaller than the symbol size in most cases).Reuse & Permissions
Figure 2
Illustration of the obtention of the resampling estimator, in the case of a BA graph (see Sec. 5 for more details on the networks) of size $N = 10^{5}$ . The initial sampling was obtained with $n_{S} = 10$ sources and $n_{T} = 10^{4}$ targets $(q_{T} = 0.1)$ , yielding a graph $G^{*}$ of size $N^{*} = 33 178$ . The circles show the ratio of the average size of the resampled graph $G^{* *}$ , ${\bar{N}}^{* *} ∕ N^{*}$ , as a function of the ratio $n_{T}^{*} ∕ n_{T}$ , with $n_{S}^{*} = n_{S} = 10$ sources. The error bars give the variance with respect to the various placements of sources and targets used for the resampling. The straight line is $y = x$ and allows one to find the value of $n_{T}^{*}$ such that $n_{T} ∕ n_{T}^{*} = N^{*} ∕ {\bar{N}}^{* *}$ .Reuse & Permissions
Figure 3
(Color online) Comparison of the various estimators for the BA (top), ER (middle), and Skitter (bottom) networks. The curves show the ratios of the various estimators to the true network size, as a function of the target density $q_{T}$ . Full circles: ${\hat{N}}_{L 1 O} ∕ N$ ; empty squares: ${\hat{N}}_{RS} ∕ N$ ; stars: $N^{*} ∕ N$ . Values and one standard deviation error bars are based on 100 trials, with random choice of sources and targets for each trial. Left figures: $n_{S} = 1$ source; middle: $n_{S} = 10$ sources; right: $n_{S} = 100$ sources.Reuse & Permissions
Figure 4
(Color online) Effect of the size $N$ of the graph $G$ for BA and ER graphs at constant number of sources and density of targets. The curves show the ratios of the various estimators to the true network size, as a function of the graph size $N$ . Full circles: ${\hat{N}}_{L 1 O} ∕ N$ ; empty squares: ${\hat{N}}_{RS} ∕ N$ ; stars: $N^{*} ∕ N$ . Values and one standard deviation error bars are based on 100 trials, with random choice of sources and targets for each trial. $n_{S} = 10$ . Left figures: $q_{T} = 10^{- 3}$ ; middle: $q_{T} = 10^{- 2}$ ; right: $q_{T} = 10^{- 1}$ .Reuse & Permissions
Figure 5
(Color online) Effect of the size $N$ of the graph $G$ for BA and ER graphs at constant number of sources and targets. The curves show the ratios of the various estimators to the true network size, as a function of the graph size $N$ . Full circles, ${\hat{N}}_{L 1 O} ∕ N$ ; empty squares, ${\hat{N}}_{RS} ∕ N$ ; stars, $N^{*} ∕ N$ . Values and one standard deviation error bars are based on 100 trials, with random choice of sources and targets for each trial. $n_{S} = 10$ . Left figures, $n_{T} = 10^{2}$ targets; middle, $n_{T} = 10^{3}$ targets; right, $n_{T} = 10^{4}$ targets.Reuse & Permissions
Figure 6
(Color online) Performance of resampling estimators for the number of edges $M_{RS}$ compared with the performance of ${\hat{N}}_{RS}$ . (A) ER network; (B) BA network. In both cases $N = 10^{5}$ , average degree 6, and $n_{S} = 10$ .Reuse & Permissions

Physical Review E

covering statistical, nonlinear, biological, and soft matter physics