Shortest path discovery of complex networks

Attila Fekete, Gábor Vattay, Márton Pósfai

Research output: Contribution to journalArticlepeer-review

Abstract (may include machine translation)

In this Rapid Communication we present an analytic study of sampled networks in the case of some important shortest-path sampling models. We present analytic formulas for the probability of edge discovery in the case of an evolving and a static network model. We also show that the number of discovered edges in a finite network scales much more slowly than predicted by earlier mean-field models. Finally, we calculate the degree distribution of sampled networks and we demonstrate that they are analogous to a destroyed network obtained by randomly removing edges from the original network.

Original languageEnglish
Article number065101
JournalPhysical Review E - Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics
Volume79
Issue number6
DOIs
StatePublished - 23 Jun 2009
Externally publishedYes

Fingerprint

Dive into the research topics of 'Shortest path discovery of complex networks'. Together they form a unique fingerprint.

Cite this