Random geometric graphs.

By J. Dall, Michael Christensen. Physical review. E, Statistical, nonlinear, and soft matter physics, 2002

1,923 citations recorded by the source corpus.

We analyze graphs in which each vertex is assigned random coordinates in a geometric space of arbitrary dimensionality and only edges between adjacent points are present. The critical connectivity is found numerically by examining the size of the largest cluster. We derive an analytical expression for the cluster coefficient, which shows that the graphs are distinctly different from standard random graphs, even for infinite dimensionality. Insights relevant for graph bipartitioning are included.

Subfields: Computational Theory and Mathematics, Statistical and Nonlinear Physics, Signal Processing

View Paper: https://www.semanticscholar.org/paper/c41b7a86b527d6bd27fc6b069711686ae0a06871

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Statistical and Nonlinear Physics

In Signal Processing

Citations in the corpus

Synchronization and convergence of linear dynamics in random directed networks (2006, background): “free networks [22] or random geometric graphs [23].”
Randomized Near Neighbor Graphs, Giant Components, and Applications in Data Science (2017, background): “The following problem is classical (we refer to the book of Penrose [20] and references therein).”
A roadmap for the computation of persistent homology (2015, background): “(Equivalently, the random VR complex is the clique complex on the random geometric graph G ( N, (cid:15) ) [101].)”
Limit theorems for network dependent random variables (2019, background): “Markov random fields constitute an alternative class of models of dependence which imposes conditional independence restrictions based on the network structure (see, e.g., Lauritzen (1996) and Pearl (2009); see also Chapter 19 of Murphy (2012) for applications in the literature of machine learning).”
The scaling limit of Poisson-driven order statistics with applications in geometric probability (2012, background): “The Gilbert graph or the random geometric graph is constructed by connecting two points of ηt by an edge if and only if their distance is smaller than a prescribed bound δ > 0; see the monograph [25] for an exhaustive reference and [20] for a closely related recent work.”
A simple, distance-dependent formulation of the Watts-Strogatz model for directed and undirected small-world networks (2014, background): “(1) is the rule used for both random geometric graphs [8] and scale-free networks constructed in the framework of hyperbolic geometry [9], and it is of interest to investigate the properties of spatially embedded networks generated according to Eq.”
On the topology of random complexes built over stationary point processes. (2012, methodology): “Since Jn is a Kd -Lipschitz functional of counting measures for a constant Kd depending only on the dimension d (see [35], Proof of Theorem 3.”
Modelling disease outbreaks in realistic urban social networks (2004, methodology): “A model for this structure is given by adding long-range edges to random geometric graph”
Agreement over random networks (2004, background): “We note that in some situations the assumptions hidden in the random graph model should be relaxed with more appropriate probabilistic models, such as those offered by random geometric graphs [19].”
Connectivity of random k-nearest-neighbour graphs (2005, background): “Regarding connectivity, Penrose [13], [14] showed that if A = Sn and πr2 = c log n, so that each point has on average c log n neighbours, then there is a critical value of c, in the sense described above, which equals 1.”
Functional Poisson approximation in Kantorovich-Rubinstein distance with applications to U-statistics and stochastic geometry (2014, background): “4 in [34] delivers a version of Corollary 7.”
Limit theory for point processes in manifolds (2011, background): “27) extends the results in Penrose [34] (Proposition 3.”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, methodology): “To preserve the connectivity of G(n, r) a radius r = r(n) = log(n)/n is used [152].”
Incremental Sampling-based Algorithms for Optimal Motion Planning (2010, background): “The key insight is that connections between vertices in the graph should be sought within balls whose radius vanishes with a certain rate as the size of the graph increases, and is based on new connections between motion planning and the theory of random geometric graphs [53], [54].”