TY - JOUR

T1 - Incomplete and noisy network data as a percolation process

AU - Stumpf, Michael P.H.

AU - Wiuf, Carsten

PY - 2010/10/6

Y1 - 2010/10/6

N2 - 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.

AB - 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.

KW - Complex networks

KW - Protein interaction networks

KW - Random graphs

KW - Sampling problems

UR - http://www.scopus.com/inward/record.url?scp=77957136340&partnerID=8YFLogxK

U2 - 10.1098/rsif.2010.0044

DO - 10.1098/rsif.2010.0044

M3 - Review

AN - SCOPUS:77957136340

VL - 7

SP - 1411

EP - 1419

JO - Journal of the Royal Society. Interface

JF - Journal of the Royal Society. Interface

SN - 1742-5689

IS - 51

ER -