Extreme value theory, Poisson-Dirichlet distributions and FPP on random networks

Details Extreme value theory, Poisson-Dirichlet distributions and FPP on random networks Extreme value theory, Poisson-Dirichlet distributions and FPP on random networks

2009-05-27

arxiv.org/abs/0905.4438v1

Mathematics

Probability

Scientific paper

We study first passage percolation on the configuration model (CM) having power-law degrees with exponent $\tau\in [1,2)$. To this end we equip the edges with exponential weights. We derive the distributional limit of the minimal weight of a path between typical vertices in the network and the number of edges on the minimal weight path, which can be computed in terms of the Poisson-Dirichlet distribution. We explicitly describe these limits via the construction of an infinite limiting object describing the FPP problem in the densely connected core of the network. We consider two separate cases, namely, the {\it original CM}, in which each edge, regardless of its multiplicity, receives an independent exponential weight, as well as the {\it erased CM}, for which there is an independent exponential weight between any pair of direct neighbors. While the results are qualitatively similar, surprisingly the limiting random variables are quite different. Our results imply that the flow carrying properties of the network are markedly different from either the mean-field setting or the locally tree-like setting, which occurs as $\tau>2$, and for which the hopcount between typical vertices scales as $\log{n}$. In our setting the hopcount is tight and has an explicit limiting distribution, showing that one can transfer information remarkably quickly between different vertices in the network. This efficiency has a down side in that such networks are remarkably fragile to directed attacks. These results continue a general program by the authors to obtain a complete picture of how random disorder changes the inherent geometry of various random network models.

Affiliated with

Also associated with

No associations

Rating

Extreme value theory, Poisson-Dirichlet distributions and FPP on random networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Extreme value theory, Poisson-Dirichlet distributions and FPP on random networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extreme value theory, Poisson-Dirichlet distributions and FPP on random networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-527823