Incomplete and noisy network data as a percolation process

Michael P.H. Stumpf; Carsten Wiuf

doi:10.1098/rsif.2010.0044

Incomplete and noisy network data as a percolation process

Michael P.H. Stumpf, Carsten Wiuf

6 Citations (Scopus)

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.

Original language	English
Journal	Journal of the Royal Society Interface
Volume	7
Issue number	51
Pages (from-to)	1411-1419
Number of pages	9
ISSN	1742-5689
DOIs	https://doi.org/10.1098/rsif.2010.0044
Publication status	Published - 6 Oct 2010
Externally published	Yes

Keywords

Complex networks
Protein interaction networks
Random graphs
Sampling problems

Access to Document

10.1098/rsif.2010.0044

http://rsif.royalsocietypublishing.org/content/7/51/1411.full.pdf

Cite this

@article{a7d22d1327bb460e99c6972e7ca058d0,

title = "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.",

keywords = "Complex networks, Protein interaction networks, Random graphs, Sampling problems",

author = "Stumpf, {Michael P.H.} and Carsten Wiuf",

year = "2010",

month = oct,

day = "6",

doi = "10.1098/rsif.2010.0044",

language = "English",

volume = "7",

pages = "1411--1419",

journal = "Journal of the Royal Society. Interface",

issn = "1742-5689",

publisher = "The/Royal Society",

number = "51",

}

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

SN - 1742-5689

VL - 7

SP - 1411

EP - 1419

JO - Journal of the Royal Society. Interface

JF - Journal of the Royal Society. Interface

IS - 51

ER -

Incomplete and noisy network data as a percolation process

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this