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...

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...

The Weight and Hopcount of the Shortest Path in the Complete Graph with Exponential Weights

Both the hopcount HN (the number of links) and the weight WN (the sum of the weights on links) of the shortest path between two arbitrary nodes in the complete graph KN with i.i.d. exponential link weights is computed. We consider the joint distribution of the pair (HN,WN) and derive, after proper scaling, the joint limiting distribution. One of...