Forskning ved Københavns Universitet - Københavns Universitet


Incomplete and noisy network data as a percolation process

Publikation: Bidrag til tidsskriftReviewForskningfagfællebedømt

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.

TidsskriftJournal of the Royal Society Interface
Udgave nummer51
Sider (fra-til)1411-1419
Antal sider9
StatusUdgivet - 6 okt. 2010
Eksternt udgivetJa

ID: 203898223