November 26, 2024 | Jesper Dall* and Michael Christensen
This paper analyzes random geometric graphs (RGGs), which are graphs where 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 determined numerically by examining the size of the largest cluster. An analytical expression for the cluster coefficient is derived, showing that RGGs are distinct from standard random graphs, even in infinite dimensions. Insights relevant to graph bipartitioning are included.
RGGs are a type of random graph with geometric properties, constructed by assigning each vertex random coordinates in a d-dimensional box. The degree distribution of a RGG with average connectivity α is similar to that of a random graph, but RGGs have unique properties not captured by standard random graph theory. The probability that three vertices are cyclically connected differs between random graphs and RGGs.
The critical distance in RGGs is the radius of the excluded volume associated with each point. The connectivity in RGGs can be increased more naturally than in lattices. RGGs are relevant in modeling systems with a metric, such as the spread of diseases.
The paper studies RGGs in arbitrary dimensions. In low dimensions, systems are dominated by local interactions, while in higher dimensions, RGGs are believed to approach standard random graphs. The paper focuses on phase transitions at the percolation threshold by examining the size of the largest cluster and determines how the critical parameter in RGGs approaches that of random graphs as the dimension increases. The distribution of cluster sizes in the critical region is also analyzed.
The cluster coefficient, a quantity of interest in network theory, is derived. Results relevant to graph bipartitioning are established. The paper discusses how to implement RGGs efficiently, using a data structure with a runtime of O(N^β), where β ≈ 1.3, allowing the study of RGGs with up to N = 4^11 > 4 × 10^6 vertices.
The critical connectivity α_c(d) is found to approach α_c(∞) = 1 in a power-law fashion as the dimension increases. The cluster coefficient decreases exponentially with dimension. RGGs and random graphs become more similar as the dimension increases, but they are not identical in all respects.
The paper also examines graph bipartitioning, showing that the critical connectivity for bipartitioning in RGGs depends on the dimension and system size. The results suggest that the critical connectivity for bipartitioning in RGGs is close but not identical to that in random graphs.
The paper concludes that RGGs are useful in network theory and percolation studies, and that they have unique properties that distinguish them from standard random graphs. The implementation of RGGs is efficient, and the results provide insights into the behavior of RGGs in various dimensions.This paper analyzes random geometric graphs (RGGs), which are graphs where 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 determined numerically by examining the size of the largest cluster. An analytical expression for the cluster coefficient is derived, showing that RGGs are distinct from standard random graphs, even in infinite dimensions. Insights relevant to graph bipartitioning are included.
RGGs are a type of random graph with geometric properties, constructed by assigning each vertex random coordinates in a d-dimensional box. The degree distribution of a RGG with average connectivity α is similar to that of a random graph, but RGGs have unique properties not captured by standard random graph theory. The probability that three vertices are cyclically connected differs between random graphs and RGGs.
The critical distance in RGGs is the radius of the excluded volume associated with each point. The connectivity in RGGs can be increased more naturally than in lattices. RGGs are relevant in modeling systems with a metric, such as the spread of diseases.
The paper studies RGGs in arbitrary dimensions. In low dimensions, systems are dominated by local interactions, while in higher dimensions, RGGs are believed to approach standard random graphs. The paper focuses on phase transitions at the percolation threshold by examining the size of the largest cluster and determines how the critical parameter in RGGs approaches that of random graphs as the dimension increases. The distribution of cluster sizes in the critical region is also analyzed.
The cluster coefficient, a quantity of interest in network theory, is derived. Results relevant to graph bipartitioning are established. The paper discusses how to implement RGGs efficiently, using a data structure with a runtime of O(N^β), where β ≈ 1.3, allowing the study of RGGs with up to N = 4^11 > 4 × 10^6 vertices.
The critical connectivity α_c(d) is found to approach α_c(∞) = 1 in a power-law fashion as the dimension increases. The cluster coefficient decreases exponentially with dimension. RGGs and random graphs become more similar as the dimension increases, but they are not identical in all respects.
The paper also examines graph bipartitioning, showing that the critical connectivity for bipartitioning in RGGs depends on the dimension and system size. The results suggest that the critical connectivity for bipartitioning in RGGs is close but not identical to that in random graphs.
The paper concludes that RGGs are useful in network theory and percolation studies, and that they have unique properties that distinguish them from standard random graphs. The implementation of RGGs is efficient, and the results provide insights into the behavior of RGGs in various dimensions.