In graph theory, the mathematically simplest spatial network
Part of a series on
Network science
Theory
Graph
Complex network
Contagion
Small-world
Scale-free
Community structure
Percolation
Evolution
Controllability
Graph drawing
Social capital
Link analysis
Optimization
Reciprocity
Closure
Homophily
Transitivity
Preferential attachment
Balance theory
Network effect
Social influence
Network types
Informational (computing)
Telecommunication
Transport
Social
Scientific collaboration
Biological
Artificial neural
Interdependent
Semantic
Spatial
Dependency
Flow
on-Chip
Graphs
Features
Clique
Component
Cut
Cycle
Data structure
Edge
Loop
Neighborhood
Path
Vertex
Adjacency list / matrix
Incidence list / matrix
Types
Bipartite
Complete
Directed
Hyper
Labeled
Multi
Random
Weighted
Metrics
Algorithms
Centrality
Degree
Motif
Clustering
Degree distribution
Assortativity
Distance
Modularity
Efficiency
Models
Topology
Random graph
Erdős–Rényi
Barabási–Albert
Bianconi–Barabási
Fitness model
Watts–Strogatz
Exponential random (ERGM)
Random geometric (RGG)
Hyperbolic (HGN)
Hierarchical
Stochastic block
Blockmodeling
Maximum entropy
Soft configuration
LFR Benchmark
Dynamics
Boolean network
agent based
Epidemic/SIR
Lists
Categories
Topics
Software
Network scientists
Category:Network theory
Category:Graph theory
v
t
e
In graph theory, a random geometric graph (RGG) is the mathematically simplest spatial network, namely an undirected graph constructed by randomly placing N nodes in some metric space (according to a specified probability distribution) and connecting two nodes by a link if and only if their distance is in a given range, e.g. smaller than a certain neighborhood radius, r.
Random geometric graphs resemble real human social networks in a number of ways. For instance, they spontaneously demonstrate community structure - clusters of nodes with high modularity. Other random graph generation algorithms, such as those generated using the Erdős–Rényi model or Barabási–Albert (BA) model do not create this type of structure. Additionally, random geometric graphs display degree assortativity according to their spatial dimension:[1] "popular" nodes (those with many links) are particularly likely to be linked to other popular nodes.
A real-world application of RGGs is the modeling of ad hoc networks.[2] Furthermore they are used to perform benchmarks for graph algorithms.
^Antonioni, Alberto; Tomassini, Marco (28 September 2012). "Degree correlations in random geometric graphs". Physical Review E. 86 (3): 037101. arXiv:1207.2573. Bibcode:2012PhRvE..86c7101A. doi:10.1103/PhysRevE.86.037101. PMID 23031054. S2CID 14750415.
^Nekovee, Maziar (28 June 2007). "Worm epidemics in wireless ad hoc networks". New Journal of Physics. 9 (6): 189. arXiv:0707.2293. Bibcode:2007NJPh....9..189N. doi:10.1088/1367-2630/9/6/189. S2CID 203944.
and 26 Related for: Random geometric graph information
In graph theory, a randomgeometricgraph (RGG) is the mathematically simplest spatial network, namely an undirected graph constructed by randomly placing...
In mathematics, randomgraph is the general term to refer to probability distributions over graphs. Randomgraphs may be described simply by a probability...
probability). A HGG generalizes a randomgeometricgraph (RGG) whose embedding space is Euclidean. Mathematically, a HGG is a graph G ( V , E ) {\displaystyle...
network is a lattice or a randomgeometricgraph (see figure in the right), where nodes are distributed uniformly at random over a two-dimensional plane;...
Geometricgraph theory in the broader sense is a large and amorphous subfield of graph theory, concerned with graphs defined by geometric means. In a...
software originally developed by NRL. The traditional model is the randomgeometricgraph. Early work included simulating ad hoc mobile networks on sparse...
and so on. In the graphs above, this formulation is shown on the right. An alternative formulation is that the geometricrandom variable X is the total...
In geometricgraph theory, a unit disk graph is the intersection graph of a family of unit disks in the Euclidean plane. That is, it is a graph with one...
distances bounded. A random walk on a graph is a very special case of a Markov chain. Unlike a general Markov chain, random walk on a graph enjoys a property...
subject of "geometric deep learning", certain existing neural network architectures can be interpreted as GNNs operating on suitably defined graphs. A convolutional...
In graph theory and network analysis, indicators of centrality assign numbers or rankings to nodes within a graph corresponding to their network position...
Appendix:Glossary of graph theory in Wiktionary, the free dictionary. This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes...
and geometric group theory. The structure and symmetry of Cayley graphs makes them particularly good candidates for constructing expander graphs. Let...
Topological sorting Algebraic graph theory Geometricgraph theory Extremal graph theory Probabilistic graph theory Topological graph theory Combinatorics Group...
Exponential RandomGraph Models (ERGMs) are a family of statistical models for analyzing data from social and other networks. Examples of networks examined...
polytope, unit disk graphs, and visibility graphs. Topics in this area include: Graph drawing Polyhedral graphsRandomgeometricgraphs Voronoi diagrams...
computer science, graph traversal (also known as graph search) refers to the process of visiting (checking and/or updating) each vertex in a graph. Such traversals...
pixels. Therefore, the random walk occurs on the weighted graph (see Doyle and Snell for an introduction to random walks on graphs). Although the initial...
S2CID 122784453. Seidel R. Backwards Analysis of RandomizedGeometric Algorithms. Karger, David R. (1999). "Random Sampling in Cut, Flow, and Network Design...
In mathematics, spectral graph theory is the study of the properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors...
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect...
In network science, a biased random walk on a graph is a time path process in which an evolving variable jumps from its current state to one of various...
spectral graph theory, a Ramanujan graph is a regular graph whose spectral gap is almost as large as possible (see extremal graph theory). Such graphs are...
cracks. In 1961, Gilbert introduced the random plane network (more commonly referred to now as a randomgeometricgraph (RGG), or Gilbert Disk model) where...
objects of exchangeable randomgraph models. Graphons are tied to dense graphs by the following pair of observations: the randomgraph models defined by graphons...
geometric group theory is to consider finitely generated groups themselves as geometric objects. This is usually done by studying the Cayley graphs of...
Global Information