Cliques in high-dimensional random geometric graphs
- PDF / 3,201,394 Bytes
- 24 Pages / 595.276 x 790.866 pts Page_size
- 100 Downloads / 265 Views
pplied Network Science
Open Access
RESEARCH
Cliques in high‑dimensional random geometric graphs Konstantin E. Avrachenkov and Andrei V. Bobu*
*Correspondence: [email protected] INRIA, 2004, route des Lucioles, 06902 Valbonne, France
Abstract Random geometric graphs have become now a popular object of research. Defined rather simply, these graphs describe real networks much better than classical Erdős– Rényi graphs due to their ability to produce tightly connected communities. The n vertices of a random geometric graph are points in d-dimensional Euclidean space, and two vertices are adjacent if they are close to each other. Many properties of these graphs have been revealed in the case when d is fixed. However, the case of growing dimension d is practically unexplored. This regime corresponds to a real-life situation when one has a data set of n observations with a significant number of features, a quite common case in data science today. In this paper, we study the clique structure of random geometric graphs when n → ∞ , and d → ∞ , and average vertex degree grows significantly slower than n. We show that under these conditions, random geometric graphs do not contain cliques of size 4 a. s. if only d ≫ log1+ǫ n . As for the cliques of size 3, we present new bounds on the expected number of triangles in the case log2 n ≪ d ≪ log3 n that improve previously known results. In addition, we provide new numerical results showing that the underlying geometry can be detected using the number of triangles even for small n. Keywords: Random geometric graphs, High dimension, Clique number, Triangles
Introduction Graphs are the most natural way to model many real-world networks. The links between nodes in a network are often occasional, that is why deterministic graphs are often irrelevant for network modeling. Random graphs, in which the link presence is a random variable, appear in the 20 th century with the simplest model proposed by Erdős and Rényi (see Erdős and Rényi 1960; Bollobás 2001; Alon and Spencer 2004). In this model, the edges between vertices appear independently with equal probability. However, this model fails to describe some important properties of many real networks, such as the community structure. Many models have been proposed to overcome this and other problems: the Barabási–Albert model (see Albert and Barabási 2002, 1999; Fronczak et al. 2003), random geometric graphs (see Gilbert 1961; Penrose 2003), hyperbolic geometric graphs (see Barthélemy 2011; Krioukov et al. 2010). Perhaps random geometric graphs are the simplest natural model where the edge appearance depends only on the Euclidean distance between given © The Author(s) 2020. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The
Data Loading...
