Source author record

Gerard Hooghiemstra

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.PR math.CO math.ST Statistics Theory

Catalog footprint

Research overview

8works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

A preferential attachment model with random initial degrees

In this paper, a random graph process ${G(t)}_{t\geq 1}$ is studied and its degree sequence is analyzed. Let $(W_t)_{t\geq 1}$ 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 are then preferentially connected to older vertices, i.e., conditionally on $G(t-1)$ , the probability that a given edge is connected to vertex i is proportional to $d_i(t-1)+δ$ , where $d_i(t-1)$ is the degree of vertex $i$ at time $t-1$ , independently of the other edges. The main result is that the asymptotical degree sequence for this process is a power law with exponent $τ=\min\{τ_{W}, τ_{P}\}$ , where $τ_{W}$ is the power-law exponent of the initial degrees $(W_t)_{t\geq 1}$ and $τ_{P}$ the exponent predicted by pure preferential attachment. This result extends previous work by Cooper and Frieze, which is surveyed.

preprint2013arXiv

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

In this paper, we study the complete graph $K_n$ with n vertices, where we attach an independent and identically distributed (i.i.d.) weight to each of the n(n-1)/2 edges. We focus on the weight $W_n$ and the number of edges $H_n$ of the minimal weight path between vertex 1 and vertex n. It is shown in (Ann. Appl. Probab. 22 (2012) 29-69) that when the weights on the edges are i.i.d. with distribution equal to that of $E^s$ , where $s>0$ is some parameter, and E has an exponential distribution with mean 1, then $H_n$ is asymptotically normal with asymptotic mean $s\log n$ and asymptotic variance $s^2\log n$ . In this paper, we analyze the situation when the weights have distribution $E^{-s},s>0$ , in which case the behavior of $H_n$ is markedly different as $H_n$ is a tight sequence of random variables. More precisely, we use the method of Stein-Chen for Poisson approximations to show that, for almost all $s>0$ , the hopcount $H_n$ converges in probability to the nearest integer of s+1 greater than or equal to 2, and identify the limiting distribution of the recentered and rescaled minimal weight. For a countable set of special s values denoted by $\mathcal{S}=\{s_j\}_{j\geq2}$ , the hopcount $H_n$ takes on the values j and j+1 each with positive probability.

preprint2012arXiv

Universality for first passage percolation on sparse random graphs

We consider first passage percolation on sparse random graphs with prescribed degree distributions and general independent and identically distributed edge weights assumed to have a density. Assuming that the degree distribution satisfies a uniform X^2\log{X}-condition, we analyze the asymptotic distribution for the minimal weight path between a pair of typical vertices, as well the number of edges on this path or hopcount. The hopcount satisfies a central limit theorem where the norming constants are expressible in terms of the parameters of an associated continuous-time branching process. Centered by a multiple of \log{n}, where the constant is the inverse of the Malthusian rate of growth of the associated branching process, the minimal weight converges in distribution. The limiting random variable equals the sum of the logarithms of the martingale limits of the branching processes that measure the relative growth of neighborhoods about the two vertices, and a Gumbel random variable, and thus shows a remarkably universal behavior. The proofs rely on a refined coupling between the shortest path problems on these graphs and continuous-time branching processes, and on a Poisson point process limit for the potential closing edges of shortest-weight paths between the source and destination. The results extend to a host of related random graph models, ranging from random r-regular graphs, inhomogeneous random graphs and uniform random graphs with a prescribed degree sequence.

preprint2011arXiv

Scale-free percolation

We formulate and study a model for inhomogeneous long-range percolation on $\Zbold^d$. Each vertex $x\in\Zbold^d$ is assigned a non-negative weight $W_x$ , where $(W_x)_{x\in\Zbold^d}$ are i.i.d.\ random variables. Conditionally on the weights, and given two parameters $α,λ>0$ , the edges are independent and the probability that there is an edge between $x$ and $y$ is given by $p_{xy}=1-\exp\{-λW_xW_y/|x-y|^α\}$ . The parameter $λ$ is the percolation parameter, while $α$ describes the long-range nature of the model. We focus on the degree distribution in the resulting graph, on whether there exists an infinite component and on graph distance between remote pairs of vertices. First, we show that the tail behavior of the degree distribution is related to the tail behavior of the weight distribution. When the tail of the distribution of $W_x$ is regularly varying with exponent $τ-1$ , then the tail of the degree distribution is regularly varying with exponent $γ=α(τ-1)/d$ . The parameter $γ$ turns out to be crucial for the behavior of the model. Conditions on the weight distribution and $γ$ are formulated for the existence of a critical value $λ_c\in(0,\infty)$ such that the graph contains an infinite component when $λ>λ_c$ and no infinite component when $λ<λ_c$ . Furthermore, a phase transition is established for the graph distances between vertices in the infinite component at the point $γ=2$ , that is, at the point where the degrees switch from having finite to infinite second moment. The model can be viewed as an interpolation between long-range percolation and models for inhomogeneous random graphs, and we show that the behavior shares the interesting features of both these models.

preprint2010arXiv

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 literature proving that, quite generally, PA-graphs possess power-law degree sequences with a power-law exponent τ>2. We prove that the diameter of the PA-model is bounded above by a constant times \log{t}, where t is the size of the graph. When the power-law exponent τexceeds 3, then we prove that \log{t} is the right order, by proving a lower bound of this order, both for the diameter as well as for the typical distance. This shows that, for τ>3, distances are of the order \log{t}. For τ\in (2,3), we improve the upper bound to a constant times \log\log{t}, and prove a lower bound of the same order for the diameter. Unfortunately, this proof does not extend to typical distances. These results do show that the diameter is of order \log\log{t}. These bounds partially prove predictions by physicists that the typical distance in PA-graphs are similar to the ones in other scale-free random graphs, such as the configuration model and various inhomogeneous random graph models, where typical distances have been shown to be of order \log\log{t} when τ\in (2,3), and of order \log{t} when τ>3.

preprint2010arXiv

First passage percolation on random graphs with finite mean degrees

We study first passage percolation on the configuration model. Assuming that each edge has an independent exponentially distributed edge weight, we derive explicit distributional asymptotics for the minimum weight between two randomly chosen connected vertices in the network, as well as for the number of edges on the least weight path, the so-called hopcount. We analyze the configuration model with degree power-law exponent $τ>2$ , in which the degrees are assumed to be i.i.d. with a tail distribution which is either of power-law form with exponent $τ-1>1$ , or has even thinner tails ( $τ=\infty$ ). In this model, the degrees have a finite first moment, while the variance is finite for $τ>3$ , but infinite for $τ\in(2,3)$ . We prove a central limit theorem for the hopcount, with asymptotically equal means and variances equal to $α\log{n}$ , where $α\in(0,1)$ for $τ\in(2,3)$ , while $α>1$ for $τ>3$ . Here $n$ denotes the size of the graph. For $τ\in (2,3)$ , it is known that the graph distance between two randomly chosen connected vertices is proportional to $\log \log{n}$ [Electron. J. Probab. 12 (2007) 703--766], that is, distances are ultra small. Thus, the addition of edge weights causes a marked change in the geometry of the network. We further study the weight of the least weight path and prove convergence in distribution of an appropriately centered version. This study continues the program initiated in [J. Math. Phys. 49 (2008) 125218] of showing that $\log{n}$ is the correct scaling for the hopcount under i.i.d. edge disorder, even if the graph distance between two randomly chosen vertices is of much smaller order. The case of infinite mean degrees ( $τ\in[1,2)$ ) is studied in [Extreme value theory, Poisson--Dirichlet distributions and first passage percolation on random networks (2009) Preprint] where it is proved that the hopcount remains uniformly bounded and converges in distribution.

preprint2010arXiv

First passage percolation on the Erdős-Rényi random graph

In this paper we explore first passage percolation (FPP) on the Erdős-Rényi random graph $G_n(p_n)$ , where each edge is given an independent exponential edge weight with rate 1. In the sparse regime, i.e., when $np_n\to λ>1,$ we find refined asymptotics both for the minimal weight of the path between uniformly chosen vertices in the giant component, as well as for the hopcount (i.e., the number of edges) on this minimal weight path. More precisely, we prove a central limit theorem for the hopcount, with asymptotic mean and variance both equal to $λ/(λ-1)\log{n}$ . Furthermore, we prove that the minimal weight centered by $\log{n}/(λ-1)$ converges in distribution. We also investigate the dense regime, where $np_n \to \infty$ . We find that although the base graph is a {\it ultra small} (meaning that graph distances between uniformly chosen vertices are $o(\log{n})$ ), attaching random edge weights changes the geometry of the network completely. Indeed, the hopcount $H_n$ satisfies the universality property that whatever be the value of $p_n$ , \ $H_n/\log{n}\to 1$ in probability and, more precisely, $(H_n-β_n\log{n})/\sqrt{\log{n}}$ , where $β_n=λ_n/(λ_n-1)$ , has a limiting standard normal distribution. The constant $β_n$ can be replaced by 1 precisely when $λ_n\gg \sqrt{\log{n}}$ , a case that has appeared in the literature (under stronger conditions on $λ_n$ ). We also find bounds for the maximal weight and maximal hopcount between vertices in the graph. This paper continues the investigation of FPP initiated by the authors. Compared to the setting on the configuration model studied in \cite{BHHS08}, the proofs presented here are much simpler due to a direct relation between FPP on the Erdős-Rényi random graph and thinned continuous-time branching processes.

preprint2005arXiv

Distances in random graphs with finite mean and infinite variance degrees

In this paper we study random graphs with independent and identically distributed degrees of which the tail of the distribution function is regularly varying with exponent $τ\in (2,3)$ . The number of edges between two arbitrary nodes, also called the graph distance or hopcount, in a graph with $N$ nodes is investigated when $N\to \infty$ . When $τ\in (2,3)$ , this graph distance grows like $2\frac{\log\log N}{|\log(τ-2)|}$ . In different papers, the cases $τ>3$ and $τ\in (1,2)$ have been studied. We also study the fluctuations around these asymptotic means, and describe their distributions. The results presented here improve upon results of Reittu and Norros, who prove an upper bound only.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Gerard Hooghiemstra

Research overview

Is this your work?

8 publications

A preferential attachment model with random initial degrees

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

Universality for first passage percolation on sparse random graphs

Scale-free percolation

Diameters in preferential attachment models

First passage percolation on random graphs with finite mean degrees

First passage percolation on the Erdős-Rényi random graph

Distances in random graphs with finite mean and infinite variance degrees

See the researcher in context

Building this map preview