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

S. Bhamidi, J.A. Goodman, R.W. Hofstad, van der, J. Komjáthy

Onderzoeksoutput: Boek/rapportRapportAcademic

55 Downloads (Pure)

Uittreksel

In this article, we explicitly derive the limiting distribution of the degree distribution of the shortest path tree from a single source on various random network models with edge weights. We determine the power-law exponent of the degree distribution 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 explain 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 [7, 8, 6] of analyzing the effect of attaching random edge lengths on the geometry of random network models.
Originele taal-2Engels
Plaats van productieEindhoven
UitgeverijEurandom
Aantal pagina's35
StatusGepubliceerd - 2013

Publicatie series

NaamReport Eurandom
Volume2013028
ISSN van geprinte versie1389-2355

Vingerafdruk

Shortest Path Tree
Degree Distribution
Power Law
Mean-field Model
Random Networks
Network Model
Stochastic Model
Exponent
Continuous Distributions
Sampling Methods
Regular Graph
Limiting Distribution
Complete Graph
Disorder
Random variable
Configuration
Graph in graph theory

Citeer dit

Bhamidi, S., Goodman, J. A., Hofstad, van der, R. W., & Komjáthy, J. (2013). Degree distribution of shortest path trees and bias of network sampling algorithms. (Report Eurandom; Vol. 2013028). Eindhoven: Eurandom.
Bhamidi, S. ; Goodman, J.A. ; Hofstad, van der, R.W. ; Komjáthy, J. / Degree distribution of shortest path trees and bias of network sampling algorithms. Eindhoven : Eurandom, 2013. 35 blz. (Report Eurandom).
@book{e387ba67cec44ba886b020c381523aaf,
title = "Degree distribution of shortest path trees and bias of network sampling algorithms",
abstract = "In this article, we explicitly derive the limiting distribution of the degree distribution of the shortest path tree from a single source on various random network models with edge weights. We determine the power-law exponent of the degree distribution 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 explain 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 [7, 8, 6] of analyzing the effect of attaching random edge lengths on the geometry of random network models.",
author = "S. Bhamidi and J.A. Goodman and {Hofstad, van der}, R.W. and J. Komj{\'a}thy",
year = "2013",
language = "English",
series = "Report Eurandom",
publisher = "Eurandom",

}

Bhamidi, S, Goodman, JA, Hofstad, van der, RW & Komjáthy, J 2013, Degree distribution of shortest path trees and bias of network sampling algorithms. Report Eurandom, vol. 2013028, Eurandom, Eindhoven.

Degree distribution of shortest path trees and bias of network sampling algorithms. / Bhamidi, S.; Goodman, J.A.; Hofstad, van der, R.W.; Komjáthy, J.

Eindhoven : Eurandom, 2013. 35 blz. (Report Eurandom; Vol. 2013028).

Onderzoeksoutput: Boek/rapportRapportAcademic

TY - BOOK

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

AU - Bhamidi, S.

AU - Goodman, J.A.

AU - Hofstad, van der, R.W.

AU - Komjáthy, J.

PY - 2013

Y1 - 2013

N2 - In this article, we explicitly derive the limiting distribution of the degree distribution of the shortest path tree from a single source on various random network models with edge weights. We determine the power-law exponent of the degree distribution 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 explain 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 [7, 8, 6] of analyzing the effect of attaching random edge lengths on the geometry of random network models.

AB - In this article, we explicitly derive the limiting distribution of the degree distribution of the shortest path tree from a single source on various random network models with edge weights. We determine the power-law exponent of the degree distribution 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 explain 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 [7, 8, 6] of analyzing the effect of attaching random edge lengths on the geometry of random network models.

M3 - Report

T3 - Report Eurandom

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

PB - Eurandom

CY - Eindhoven

ER -

Bhamidi S, Goodman JA, Hofstad, van der RW, Komjáthy J. Degree distribution of shortest path trees and bias of network sampling algorithms. Eindhoven: Eurandom, 2013. 35 blz. (Report Eurandom).