TY - BOOK

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

AU - Bhamidi, S.

AU - Hofstad, van der, R.W.

PY - 2010

Y1 - 2010

N2 - In the recent past, there has been a concerted effort to develop mathematical models for real-world networks and 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 all fixed finite temperatures, the number of edges on the minimal weight path (i.e the hopcount) is always $\Theta(\log{n})$ and satisfies a central limit theorem with asymptotic means and variances of order $\Theta(\log{n})$, with limiting constants expressible in terms of the Malthusian rate of growth and the mean of the stable-age distribution of the 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\log{n}$ and $s^2 \log{n}$ respectively. We also find limiting distributional asymptotics for the value of the minimal weight path in terms of extreme value distributions, Cox processes and martingale limits of branching processes.

AB - In the recent past, there has been a concerted effort to develop mathematical models for real-world networks and 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 all fixed finite temperatures, the number of edges on the minimal weight path (i.e the hopcount) is always $\Theta(\log{n})$ and satisfies a central limit theorem with asymptotic means and variances of order $\Theta(\log{n})$, with limiting constants expressible in terms of the Malthusian rate of growth and the mean of the stable-age distribution of the 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\log{n}$ and $s^2 \log{n}$ respectively. We also find limiting distributional asymptotics for the value of the minimal weight path in terms of extreme value distributions, Cox processes and martingale limits of branching processes.

UR - http://arxiv.org/pdf/1002.4362

M3 - Report

T3 - arXiv.org [math.PR]

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

PB - s.n.

ER -