Random geometric graph

Example of Random Geometric Graph on a flat 2-d closed square [0, 1] with N=256 vertices and connectivity threshold r=0.1.

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 topological space (according to a specified probability distribution) and connecting two nodes by a link if their distance (according to some metric) is in a given range, e.g. smaller than a certain neighborhood radius, r.

A real-world application of RGGs is the modeling of ad hoc networks.^[1]

Examples

• In 1 dimension, one can study RGGs on a line of unit length (open boundary condition) or on a circle of unit circumference.
• In 2 dimensions, an RGG can be constructed by choosing a flat unit square [0, 1] (see figure) or a torus of unit circumferences [0, 1)² as the embedding space.

The simplest choice for the node distribution is to sprinkle them uniformly and independently in the embedding space.

References

• Penrose, Mathew: Random Geometric Graphs (Oxford Studies in Probability, 5), 2003.

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 Biological Artificial neural Interdependent Semantic Spatial Dependency Flow
Graphs
Features Clique Component Cut Cycle Data structure Edge Loop Neighborhood Path Vertex Adjacency list / matrix Incidence list / matrix Types Bipartite Complete Directed Hyper Multi Random Weighted
Metrics Algorithms
Centrality Degree Betweenness Closeness PageRank Motif Clustering Degree distribution Assortativity Distance Modularity Efficiency
Models
Topology Random graph Erdős–Rényi Barabási–Albert Watts–Strogatz Exponential random (ERGM) Hyperbolic (HGN) Hierarchical Dynamics Boolean network agent based Epidemic/SIR
Lists Categories
Topics Software Network scientists Category:Network theory Category:Graph theory