Skip to Main content Skip to Navigation
Conference papers

Cliques in high-dimensional random geometric graphs

Konstantin Avrachenkov 1 Andrei Bobu 1
1 NEO - Network Engineering and Operations
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Random geometric graphs are good examples of random graphs with a tendency to demonstrate community structure. Vertices of such a graph are represented by points in Euclid space $R^d$ , and edge appearance depends on the distance between the points. Random geometric graphs were extensively explored and many of their basic properties are revealed. However, in the case of growing dimension $d → ∞$ practically nothing is known; this regime corresponds to the case of data with many features, a case commonly appearing in practice. In this paper, we focus on the cliques of these graphs in the situation when average vertex degree grows significantly slower than the number of vertices n with $n → ∞$ and $d → ∞$. We show that under these conditions random geometric graphs do not contain cliques of size 4 a.s. As for the size 3, we will present new bounds on the expected number of triangles in the case $log^2(n) << d << log^3(n)$ that improve previously known results.
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-02397338
Contributor : Konstantin Avrachenkov <>
Submitted on : Friday, December 6, 2019 - 2:56:18 PM
Last modification on : Thursday, January 9, 2020 - 4:33:15 PM
Document(s) archivé(s) le : Saturday, March 7, 2020 - 5:07:42 PM

File

avr-bobu-cliques-in-rgg.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Konstantin Avrachenkov, Andrei Bobu. Cliques in high-dimensional random geometric graphs. COMPLEX NETWORKS 2019 - 8th International Conference on Complex Networks and Their Applications, Dec 2019, Lisbon, Portugal. ⟨10.1007/978-3-030-36687-2_49⟩. ⟨hal-02397338⟩

Share

Metrics

Record views

54

Files downloads

192