Weak disorder asymptotics in the stochastic mean-field model of distance

DOI10.1214/10-AAP753MaRDI QIDQ2428045zbMATH OpenFDO

Authors Shankar Bhamidi, Remco van der Hofstad

Publication date 20 April 2012

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

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

asymptotic distribution branching processes first-passage percolation shortest paths

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Stochastic network models in operations research (90B15)

Abstract: In the recent past, there has been a concerted effort to develop mathematical models for real-world networks and to analyze various dynamics on these models. One particular problem of significant importance is to understand the effect of random edge lengths or costs on the geometry and flow transporting properties of the network. Two different regimes are of great interest, the weak disorder regime where optimality of a path is determined by the sum of edge weights on the path and the strong disorder regime where optimality of a path is determined by the maximal edge weight on the path. In the context of the stochastic mean-field model of distance, we provide the first mathematically tractable model of weak disorder and show that no transition occurs at finite temperature. Indeed, we show that for every finite temperature, the number of edges on the minimal weight path (i.e., the hopcount) is

T h e t a (l o g n)

and satisfies a central limit theorem with asymptotic means and variances of order

T h e t a (l o g n)

, with limiting constants expressible in terms of the Malthusian rate of growth and the mean of the stable-age distribution of an associated continuous-time branching process. More precisely, we take independent and identically distributed edge weights with distribution

E^{s}

for some parameter

s > 0

, where

E

is an exponential random variable with mean 1. Then the asymptotic mean and variance of the central limit theorem for the hopcount are

s l o g n

and

s^{2} l o g n

, respectively. We also find limiting distributional asymptotics for the value of the minimal weight path in terms of extreme value distributions and martingale limits of branching processes.

Review text

A stochastic model of weighted distances is considered. The underlying graph is the complete graph on \(n\) vertices and each pair \(e\) of distinct vertices is associated with a random variable \(E_e\), which is exponentially distributed with mean 1 and is independent of every other pair. The weight of the edge \(e\) is set to be equal to \((E_e)^s\), where \(s>0\) is a parameter of the system. The optimal path between two vertices is the path that minimizes the sum of weights among all possible paths between these vertices -- this sum is called the cost of the path. When \(s=1\), then the model reduces to the well-studied first-passage percolation process on the complete graph. But when \(s\rightarrow \infty\), then the weight of a path tends to the maximum of the weights among the edges that belong to the path -- this is called the strong disorder regime. The authors determine the asymptotic distribution of the cost of the optimal path between two given vertices as well as the distribution of the number of hops of such a path. The distribution of the cost of the optimal path is associated with a parameter of a continuous-time branching process with a certain offspring distribution.

Recommendations

Cites work

Cited in

(19)

This page was built for publication: Weak disorder asymptotics in the stochastic mean-field model of distance

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