Degree distribution of shortest path trees and bias of network sampling algorithms

DOI10.1214/14-AAP1036MaRDI QIDQ2354885zbMATH OpenFDO

Authors Shankar Bhamidi, Jesse Goodman, Remco van der Hofstad, Júlia Komjáthy

Publication date 27 July 2015

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.5672, https://projecteuclid.org/euclid.aoap/1432212430

zbMATH Keywords

Bellman-Harris processesbiasfirst passage percolationflowshopcountmean-field model of distancenetwork algorithmspower lawrandom graphrandom networkstable-age distributionweak disorder

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Stochastic network models in operations research (90B15)

Abstract: In this article, we explicitly derive the limiting degree distribution of the shortest path tree from a single source on various random network models with edge weights. We determine the asymptotics of the degree distribution for large degrees of this tree and compare it to the degree distribution of the original graph. We perform this analysis for the complete graph with edge weights that are powers of exponential random variables (weak disorder in the stochastic mean-field model of distance), as well as on the configuration model with edge-weights drawn according to any continuous distribution. In the latter, the focus is on settings where the degrees obey a power law, and we show that the shortest path tree again obeys a power law with the same degree power-law exponent. We also consider random $r$-regular graphs for large $r$, and show that the degree distribution of the shortest path tree is closely related to the shortest path tree for the stochastic mean-field model of distance. We use our results to shed light on an empirically observed bias in network sampling methods. This is part of a general program initiated in previous works by Bhamidi, van der Hofstad and Hooghiemstra [Ann. Appl. Probab. 20 (2010) 1907-1965], [Combin. Probab. Comput. 20 (2011) 683-707], [Adv. in Appl. Probab. 42 (2010) 706-738] of analyzing the effect of attaching random edge lengths on the geometry of random network models.

Recommendations

• On the bias of traceroute sampling
• Bounding the bias of tree-like sampling in IP topologies
• On the bias of traceroute sampling
• An empirical study of the structure of the shortest path tree
• Sampling networks by the union of \(m\) shortest path trees

Cites work

• A critical point for random graphs with a given degree sequence
• Asymptotics in the random assignment problem
• Complex graphs and networks
• Emergence of Scaling in Random Networks
• Explosiveness of age-dependent branching processes
• Extreme value theory, Poisson-Dirichlet distributions, and first passage percolation on random networks
• First passage percolation on random graphs with finite mean degrees
• First passage percolation on the Erdős-Rényi random graph
• scientific article; zbMATH DE number 3555176 (Why is no real title available?)
• scientific article; zbMATH DE number 1026574 (Why is no real title available?)
• scientific article; zbMATH DE number 2042286 (Why is no real title available?)
• scientific article; zbMATH DE number 1866312 (Why is no real title available?)
• scientific article; zbMATH DE number 2119076 (Why is no real title available?)
• Joint distribution of distances in large random regular networks
• Length of optimal path in random networks with strong disorder
• Limiting theorems for age-dependent branching processes
• On the bias of traceroute sampling
• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
• Performance Analysis of Communications Networks and Systems
• Point processes, regular variation and weak convergence
• Random assignment and shortest path problems
• Random graph dynamics
• Random graphs.
• Relaxing the uniformity and independence assumptions using the concept of fractal dimension
• Short paths for first passage percolation on the complete graph
• The degree sequence of a scale-free random graph process
• The diameter of a scale-free random graph
• The growth and composition of branching populations
• The probability that a random multigraph is simple
• The structure and dynamics of networks
• The Structure and Function of Complex Networks
• Weak disorder asymptotics in the stochastic mean-field model of distance

Cited in

(7)

• Local neighbourhoods for first-passage percolation on the configuration model
• Shortest path tree sampling for landmark selection in large networks
• On the bias of traceroute sampling
• On the bias of traceroute sampling
• First passage percolation on Erdös-Rényi graphs with general weights
• Bounding the bias of tree-like sampling in IP topologies
• Sampling networks by the union of \(m\) shortest path trees

This page was built for publication: Degree distribution of shortest path trees and bias of network sampling algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2354885)