Vertex degree of random geometric graph on exponentially distributed points

DOI10.1016/J.SPL.2009.06.011MaRDI QIDQ731943zbMATH OpenOpenAlexFDO

Authors Bhupendra Gupta

Publication date 9 October 2009

Published in Statistics \& Probability Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0609193

zbMATH Keywords

almost-sure asymptotic rates convergence/divergenceexponential random geometric graphminimum and maximum vertex degrees

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Geometric probability and stochastic geometry (60D05) Extreme value theory; extremal stochastic processes (60G70)

Abstract: Let $X_1,X_2,\mathrm{...}$ be an infinite sequence of i.i.d. random vectors distributed exponentially with parameter $lam.$ For each $y$ and $ngeq1,$ form a graph $G_n(y)$ with vertex set $V_n=X_1,\mathrm{...},X_n,$ two vertices are connected if and only if edge distance between them is greater then $y$, i.e, $|X_i-X_j|leqy.$ Almost-sure asymptotic rates of convergence/divergence are obtained for the minimum and maximum vertex degree of the random geometric graph, as the number of vertices becomes large $n,$ and the edge distance varies with the number of vertices.

Review text

Let \(X_1,X_2,\dots\) be independent \(d-\)dimensional random vectors, where the components of \(X_i,i=1,2,\dots,\) are i.i.d. exponentially distributed with parameter \(\lambda\). For each \(y\) and \(n \geq 1\), define \(G_n(y)\) as the random graph having \(V_n=\{X_1,\dots,X_n\}\) as the vertex set, and with an edge connecting each pair of vertices \(X_i\) and \(X_j\) in \(V_n\) at distance \(\| X_i-X_j\| \leq y\), where \(\|\cdot \|\) is the \(l_{\infty}\) norm. Let \[ \deg X_{n,i}(y)=\sum_{1 \leq j \not= i \leq n} 1_{\{ \| X_i-X_j\| \leq y\}}, \] \(1 \leq i \leq n\), be the degree of vertex \(X_i\) in the random graph \(G_n(y)\). The author obtains almost-sure asymptotic rates of convergence/divergence for the maximum and minimum vertex degrees of graph, when edge distance \(y=y_n\) varies with the number \(n\) of vertices.

Recommendations

• Topological properties of the one dimensional exponential random geometric graph
• Criticality of the exponential rate of decay for the largest nearest-neighbor link in random geometric graphs
• On the degree sequence of random geometric digraphs
• Nonuniform random geometric graphs with location-dependent radii
• Random Geometric Graphs

Cites work

• Criticality of the exponential rate of decay for the largest nearest-neighbor link in random geometric graphs
• Extremes for the minimal spanning tree on normally distributed points
• Extremes on trees
• scientific article; zbMATH DE number 3658755 (Why is no real title available?)
• Random Geometric Graphs
• The Maximum Vertex Degree of a Graph on Uniform Points in [0, 1]^d
• The Minimum Vertex Degree of a Graph on Uniform Points in [0, 1]^d
• Topological properties of the one dimensional exponential random geometric graph

Cited in

(4)

• The length of the shortest edge of a graph on a sphere
• Criticality of the exponential rate of decay for the largest nearest-neighbor link in random geometric graphs
• The variance of the vertex degrees of randomly generated graphs
• Topological properties of the one dimensional exponential random geometric graph

This page was built for publication: Vertex degree of random geometric graph on exponentially distributed points

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