First Passage Percolation on the Erd?s–Rényi Random Graph

First passage percolation on random graphs with finite mean degrees

Extreme value theory, Poisson-Dirichlet distributions, and first passage percolation on random networks

We study first passage percolation (FPP) on the configuration model (CM) having power-law degrees with exponent ? ? [1, 2) and exponential edge 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, both of which can be computed in...

Diameters in preferential attachment models

In this paper, we investigate the diameter in preferential attachment (PA-) models, thus quantifying the statement that these models are small worlds. The models studied here are such that edges are attached to older vertices proportional to the degree plus a constant, i.e., we consider affine PA-models. There is a substantial amount of...

Universality for distances in power-law random graphs

We survey the recent work on phase transition and distances in various random graph models with general degree sequences. We focus on inhomogeneous random graphs, the configuration model, and affine preferential attachment models, and pay special attention to the setting where these random graphs have a power-law degree sequence. This means that...

Universality for the Distance in Finite Variance Random Graphs

We generalize the asymptotic behavior of the graph distance between two uniformly chosen nodes in the configuration model to a wide class of random graphs. Among others, this class contains the Poissonian random graph, the expected degree random graph and the generalized random graph (including the classical Erdos-Renyi graph). In the paper we...

A preferential attachment model with random initial degrees

In this paper, a random graph process {G(t)} (ta parts per thousand yen1) is studied and its degree sequence is analyzed. Let {W (t) } (ta parts per thousand yen1) be an i.i.d. sequence. The graph process is defined so that, at each integer time t, a new vertex with W (t) edges attached to it, is added to the graph. The new edges added at time t...

The Weight of the Shortest Path Tree

The minimal weight of the shortest path tree in a complete graph with independent and exponential (mean 1) random link weights, is shown to converge to a Gaussian distribution. We prove a conditional central limit theorem and show that the condition holds with probability converging to 1.

A Phase Transition for the Diameter of the Configuration Model

In this paper, we study the configuration model (CM) with independent and identically-distributed (i.i.d.) degrees. We establish a phase transition for the diameter when the power-law exponent ? of the degrees satisfies ? ? (2, 3). Indeed, we show that for ? > 2 and when vertices with degree 1 or 2 are present with positive probability, the...

Size and Weight of Shortest Path Trees with Exponential Link Weights

We derive the distribution of the number of links and the average weight for the shortest path tree (SPT) rooted at an arbitrary node to m uniformly chosen nodes in the complete graph of size N with i.i.d. exponential link weights. We rely on the fact that the full shortest path tree to all destinations (i.e., m = N ? 1) is a uniform recursive...

Critical two-point functions and the lace expansion for spread-out high-dimensional percolation and related models

We consider spread-out models of self-avoiding walk, bond percolation, lattice trees and bond lattice animals on ${\mathbb{Z}^d}$, having long finite-range connections, above their upper critical dimensions $d=4$ (self-avoiding walk), $d=6$ (percolation) and $d=8$ (trees and animals). The two-point functions for these models are respectively the...

Performance of DS-CDMA systems with optimal hard-decision parallel interference cancellation

On the efficiency of multicast

A scaling law for the hopcount in internet