Shortest path discovery of complex networks
arXiv:0810.1428 · doi:10.1103/PhysRevE.79.065101
Abstract
In this paper 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 slower 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 destructed network obtained by randomly removing edges from the original network.
10 pages, 4 figures
References in corpus (18)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- Random graphs with arbitrary degree distributions and their applications
- Evolution of networks
- Network robustness and fragility: Percolation on random graphs
- Resilience of the Internet to random breakdowns
- Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
- Universal Behavior of Load Distribution in Scale-free Networks
- Class of correlated random networks with hidden variables
- Statistical properties of sampled networks
- A General Formalism for Inhomogeneous Random Graphs
- Accuracy and Scaling Phenomena in Internet Mapping
- Traceroute sampling makes random graphs appear to have power law degree distributions
- Scale-free trees: the skeletons of complex networks
- Shortest paths and load scaling in scale-free trees
- Exploration of scale-free networks
- Network Inference from TraceRoute Measurements: Internet Topology `Species'
- Distribution of Edge Load in Scale-free Trees