TY - JOUR

T1 - Shortest path discovery of complex networks

AU - Fekete, Attila

AU - Vattay, Gábor

AU - Pósfai, Márton

PY - 2009/6/23

Y1 - 2009/6/23

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

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

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

U2 - 10.1103/PhysRevE.79.065101

DO - 10.1103/PhysRevE.79.065101

M3 - Article

AN - SCOPUS:67650099196

SN - 1539-3755

VL - 79

JO - Physical Review E - Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics

JF - Physical Review E - Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics

IS - 6

M1 - 065101

ER -