Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-23T17:10:43.393Z Has data issue: false hasContentIssue false
  • English
  • Français

Flooding and diameter in general weighted random graphs

Part of: Combinatorial probability Graph theory Operations research and management science

Published online by Cambridge University Press:  04 September 2020

Thomas Mountford  and
Jacques Saliba Open the ORCID record for Jacques Saliba [Opens in a new window]
Thomas Mountford*
Affiliation:
Ecole Polytechnique Fédérale de Lausanne
Jacques Saliba*
Affiliation:
Ecole Polytechnique Fédérale de Lausanne
*
*Postal address: Institut de Mathématiques, Ecole Polytechnique Fédérale de Lausanne, 1015 Lausanne, Switzerland
*Postal address: Institut de Mathématiques, Ecole Polytechnique Fédérale de Lausanne, 1015 Lausanne, Switzerland
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we study first passage percolation on a random graph model, the configuration model. We first introduce the notions of weighted diameter, which is the maximum of the weighted lengths of all optimal paths between any two vertices in the graph, and the flooding time, which represents the time (weighted length) needed to reach all the vertices in the graph starting from a uniformly chosen vertex. Our result consists in describing the asymptotic behavior of the diameter and the flooding time, as the number of vertices n tends to infinity, in the case where the weight distribution G has an exponential tail behavior, and proving that this category of distributions is the largest possible for which the asymptotic behavior holds.

Keywords

First passage percolationconfiguration modeldiameterflooding timecontinuous branching process

MSC classification

Primary: 60C05: Combinatorial probability
Secondary: 05C80: Random graphs 90B15: Network models, stochastic
Type
Research Papers
Information
Journal of Applied Probability , Volume 57 , Issue 3 , September 2020 , pp. 956 - 980
Check for updates
Copyright
© Applied Probability Trust 2020

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Amini, H. and Lelarge, M. (2015). The diameter of weighted random graphs. Ann. Appl. Prob. 25, 1686–1727.CrossRefGoogle Scholar
Amini, H., Draief, M. and Lelarge, M. (2011). Flooding in weighted random graphs. In Workshop on Analytic Algorithmics and Combinatorics (ANALCO 11), pp. 1–15. ACM.CrossRefGoogle Scholar
Athreya, K. B. and Ney, P. E. (2004). Branching Processes. Dover, Mineola, NY.Google Scholar
Bhamidi, S., van der Hofstad, R. and Hooghiemstra, G. (2010). First passage percolation on random graphs with finite mean degrees. Ann. Appl. Prob. 20, 1907–1965.Google Scholar
Bhamidi, S., van der Hofstad, R. and Hooghiemstra, G. (2017). Universality for first passage percolation on sparse random graphs. Ann. Prob. 45, 2568–2630.Google Scholar
Fernholz, D. and Ramachandran, V. (2007). The diameter of sparse random graphs. Random Structures Algorithms 31, 482–516.CrossRefGoogle Scholar
Janson, S. (1999). One, two and three times $\log n/n$ for paths in a complete graph with random weights. Combin. Probab. Comput. 8, 347–361.Google Scholar
van der Hofstad, R. (2016). Random Graphs and Complex Networks (Cambridge Series in Statistical and Probabilistic Mathematics 43). Cambridge University Press.Google Scholar
van der Hofstad, R., Hooghiemstra, G. and Znamenski, D. (2007). A phase transition for the diameter of the configuration model. Internet Math. 4, 113–128.CrossRefGoogle Scholar