Incomplete and noisy network data as a percolation process

Abstract

We discuss the ramifications of noisy and incomplete observations of network data on the existence of a giant connected component (GCC). The existence of a GCC in a random graph can be described in terms of a percolation process, and building on general results for classes of random graphs with specified degree distributions we derive percolation thresholds above which GCCs exist. We show that sampling and noise can have a profound effect on the perceived existence of a GCC and find that both processes can destroy it. We also show that the absence of a GCC puts a theoretical upper bound on the false-positive rate and relate our percolation analysis to experimental protein-protein interaction data.

Figure 1.

Contour-plot of the fraction of nodes contained in the GCC for different fractions of true-positive and false-positive edges in a network (area labels refer to the whole area to the right and above of the corresponding curves). Only when the fraction of true and false positives are both very small, will the GCC disappear. On the left-hand side of the figure we show illustrative examples of cases which correspond (loosely) to areas in the (ρ, Ξ) plane indicated by the arrow-tips. Real edges are indicated in blue, whereas false-positive edges are drawn in green.

Figure 2.

Average fraction of nodes in subnets of a network with 5000 nodes and 15 000 edges against sampling fraction/subnet size. Shown are results obtained for a scale-free network grown under the BA preferential attachment model (black), the corresponding BC graph (see text for details) (grey), and an Erdös–Rényi random graph. Averages were taken over 1000 independent simulated networks (black circles, scale-free RGG; crosses, scale-free BC; triangles, ER, random graph).

Figure 3.

Representations of eight networks in the IntAct database. The two early data sets generated by mass spectrometry (Ho et al. 2002; Gavin et al. 2002) do not show evidence for a GCC, as may well be expected given that they focus on protein complexes. The details of the data sets are provided in table 1.

Figure 4.

The coloured regions indicate combinations in (〈k²〉, ρ, Ξ)-space for which we will observe a GCC. (a) The corresponds to the case of p̂ in Ito et al. (2001), (b) to the case of p̂ in Gavin et al. (2002). Perhaps somewhat unexpectedly we also observe a pronounced effect of p̂ (ξ ≈ 14.5% in (a) and ≈ 12.1% in (b)) on the boundary of the parameter space allowing for a GCC with high probability.