Random Geometric Graphs
Random graphs (graph-theoretic aspects) (05C80) Research exposition (monographs, survey articles) pertaining to probability theory (60-02) Combinatorial probability (60C05) Geometric probability and stochastic geometry (60D05) Interacting random processes; statistical mechanics type models; percolation theory (60K35)
A set of points scattered over a region generates a graph by connecting pairs of points separated by a distance less than a certain specified value. Properties of such graphs generated by a random set of points constitute a substantial part of the theory of geometric probability. This provides a remarkable source for various facts on random geometric graphs. The author unifies numerous facts previously scattered in journal papers and presents a number of new results. The concepts presented in the book have numerous applications in statistics (clustering and classification, scan statistics) and computer science (travelling salesman and other arrangement problems). For a set \(\mathcal{X}_n\) of \(n\) random points denote by \(G(\mathcal{X}_n;r)\) the indirected graph with vertex set \(\mathcal{X}_n\) and with undirected edges connecting all \(r\)-close pairs of points. A number of numerical characteristics of graphs can be formulated in terms of the threshold distance being the smallest \(r\) such that the graph possesses the specified property. For example, the smallest \(r\) for which the graph has at least one edge equals the smallest inter-point distance in \(\mathcal{X}_n\). Although exact formulae for characteristics of \(G(\mathcal{X}_n;r)\) are usually not available, nice mathematical results can be obtained in the asymptotic framework when \(r=r_n\to 0\) and \(n\to\infty\). In many cases the problem can be transformed into considering the random graph built on a finite Poisson process of growing total intensity. Other techniques include Stein-Chen method of Poisson approximation, the normal approximation, and martingales. In many cases the author presents the full spectrum of limit theorems: strong laws of large numbers, convergence in distribution and large deviation results. Part I of the book concerns subgraphs and component counts, i.e. the numbers of copies of some arbitrary specified connected finite graph embedded in the graph \(G(\mathcal{X}_n;r)\). Then the author considers the empirical distribution of the vertex degrees, e.g. properties of the threshold value of \(r\) for which the graph has all vertices of degree at least \(k\). Part II deals with extremes of locally determined quantities, including the maximum degree, the minimum degree, the clique number and the chromatic number. Part III concerns giant components and connectivity properties. If \(r_n\sim c n^{-1/d}\), then, with the constant \(c\) above a certain critical value, a positive fraction of the points likely constitutes a giant connected component of the graph \(G(\mathcal{X}_n;r_n)\). This phenomenon is known as percolation. In addition to laws of large numbers, central limit theorems and large deviations for the order of the largest component, this part contains a significant amount of material on continuum percolation. Applications include consistency results for testing unimodality in statistics and layout problems in computer science. A further important topic in Part III deals with the connectivity of random geometric graphs, and with the number of components, in particular when \(r_n\sim c((\log n)/n)^{-1/d}\). Results include limit laws for the threshold at which the graph becomes connected, and also on multiple connectivity. The book is suitable to design a graduate course in random geometric graphs. Its scope stretches far beyond geometric probability and includes exciting material from Poisson approximation, percolation and statistical physics. This elegantly written monograph belongs to the collection of important books vital for every probabilist.
- Asymptotic behaviors for percolation clusters with uncorrelated weights
- Limit theorems for diameter of a random sample in the unit ball
- Highly connected random geometric graphs
- Gaussian limits for generalized spacings
- Optimal construction of \(k\)-nearest-neighbor graphs for identifying noisy clusters
- Asymptotic theory for the multidimensional random on-line nearest-neighbour graph
- Balanced cut approximation in random geometric graphs
- Expander properties and the cover time of random intersection graphs
- A tutorial survey of topics in wireless networking. II
- Some properties for the largest component of random geometric graphs with applications in sensor networks
- Correlation between graphs with an application to brain network analysis
- Random graphs as a model for pregeometry
- Concentration for Poisson \(U\)-statistics: subgraph counts in random geometric graphs
- Topology of random geometric complexes: a survey
- Consistency of modularity clustering on random geometric graphs
- Limit theorems for persistence diagrams
- Limit theorems for Betti numbers of extreme sample clouds with application to persistence barcodes
- A BKR operation for events occurring for disjoint reasons with high probability
- A random geometric graph built on a time-varying Riemannian manifold
- Phase transitions in discrete structures
- Epidemics on plants: modeling long-range dispersal on spatially embedded networks
- Spatial ``artistic networks: from deconstructing integer-functions to visual arts
- Sharpness of the phase transition and lower bounds for the critical intensity in continuum percolation on \(\mathbb{R}^{d}\)
- Stretch and diameter in random geometric graphs
- A remark on the convergence of Betti numbers in the thermodynamic regime
- Combinatorial quantum gravity: geometry from random bits
- Geometric inhomogeneous random graphs
- Quantitative CLTs for symmetric U-statistics using contractions
- The convex hull of a planar random walk: perimeter, diameter, and shape
- Zero-one law for connectivity in superposition of random key graphs on random geometric graphs
- Asymptotic distribution of isolated nodes in secure wireless sensor networks under transmission constraints
- Strong law of large numbers for Betti numbers in the thermodynamic regime
- On rumour propagation among sceptics
- Normal approximation for stabilizing functionals
- The critical greedy server on the integers is recurrent
- Stable limit theorems for empirical processes under conditional neighborhood dependence
- Logical limit laws for minor-closed classes of graphs
- Law of large numbers for the largest component in a hyperbolic model of complex networks
- Model of a random geometric graph with attachment to the coverage area
- Corrected mean-field model for random sequential adsorption on random geometric graphs
- Central limit theorem for exponentially quasi-local statistics of spin models on Cayley graphs
- Gaussian limits for random measures in geometric probability
- Isolation and connectivity in random geometric graphs with self-similar intensity measures
- Goodness-of-fit tests for complete spatial randomness based on Minkowski functionals of binary images
- Recovering the structure of random linear graphs
- On the expansion and diameter of bluetooth-like topologies
- Spectral clustering based on local linear approximations
- On the stretch factor of randomly embedded random graphs
- Mobile geometric graphs: detection, coverage and percolation
- Minimum spanning trees of random geometric graphs with location dependent weights
- Coalescing random walk on unimodular graphs
- Weighted dependency graphs
- Asymptotic behavior of the Brownian frog model
- Second-order consensus protocols based on transformed \(d\)-path Laplacians
- Information integration from distributed threshold-based interactions
- Burning graphs: a probabilistic perspective
- Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
- Limit theorems for network dependent random variables
- Optimal design for manipulation of random consensus over discrete information in networked systems
- Adaptive estimation of nonparametric geometric graphs
- Network representation using graph root distributions
- On the law of the iterated logarithm and strong invariance principles in stochastic geometry
- Limit theory for isolated and extreme points in hyperbolic random geometric graphs
- Clustering in a hyperbolic model of complex networks
- Poisson approximation and connectivity in a scale-free random connection model
- On the estimation of latent distances using graph distances
- Exponential rate for the contact process extinction time
- Weakly reinforced Pólya urns on countable networks
- On the computational tractability of statistical estimation on amenable graphs
- Phase transitions and percolation at criticality in enhanced random connection models
- Greedy routing and the algorithmic small-world phenomenon
- An infinite-dimensional metapopulation SIS model
- Limit theory of combinatorial optimization for random geometric graphs
- Poisson approximation with applications to stochastic geometry
- Quenched invariance principle for random walks on dynamically averaging random conductances
- The synchronized dynamics of time-varying networks
- Gaussian approximation for sums of region-stabilizing scores
- Quantitative two-scale stabilization on the Poisson space
- The impact of geometry on monochrome regions in the flip Schelling process
- Giant component of the soft random geometric graph
- Functional strong law of large numbers for Betti numbers in the tail
- The distribution of the number of isolated nodes in the 1-dimensional soft random geometric graph
- Localization game for random geometric graphs
- Convergence of persistence diagram in the sparse regime
- Functional convergence of sequential \(U\)-processes with size-dependent kernels
- Large degrees in scale-free inhomogeneous random graphs
- The power of adaptivity in source identification with time queries on the path
- Random connection models in the thermodynamic regime: central limit theorems for add-one cost stabilizing functionals
- Homotopy types of random cubical complexes
- Topological transition in a coupled dynamics in random networks
- Extremal linkage networks
- Extremal lifetimes of persistent cycles
- Markov random geometric graph, MRGG: a growth model for temporal dynamic networks
- From graph cuts to isoperimetric inequalities: convergence rates of Cheeger cuts on data clouds
- Recurrence versus transience for weight-dependent random connection models
- Generalization of effective conductance centrality for egonetworks
- Improved spectral convergence rates for graph Laplacians on \(\varepsilon \)-graphs and \(k\)-NN graphs
- Rare events in random geometric graphs
- Homological connectivity in random Čech complexes
- Community detection with the label propagation algorithm: a survey
This page was built for publication: Random Geometric Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4427412)
