Cliques in geometric inhomogeneous random graphs

Riccardo Michielan*, Clara Stegehuis

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

2 Downloads (Pure)

Abstract

Many real-world networks were found to be highly clustered and contain a large amount of small cliques. We here investigate the number of cliques of any size k contained in a geometric inhomogeneous random graph: a scale-free network model containing geometry. The interplay between scale-freeness and geometry ensures that connections are likely to form between either high-degree vertices, or between close by vertices. At the same time, it is rare for a vertex to have a high degree, and most vertices are not close to one another. This trade-off makes cliques more likely to appear between specific vertices. In this article, we formalize this trade-off and prove that there exists a typical type of clique in terms of the degrees and the positions of the vertices that span the clique. Moreover, we show that the asymptotic number of cliques as well as the typical clique type undergoes a phase transition, in which only k and the degree-exponent τ are involved. Interestingly, this phase transition shows that for small values of τ⁠, the underlying geometry of the model is irrelevant: the number of cliques scales the same as in a non-geometric network model.
Original languageEnglish
Article numbercnac002
JournalJournal of Complex Networks
Volume10
Issue number1
Early online dateJan 2022
DOIs
Publication statusPublished - 9 Feb 2022

Keywords

  • UT-Hybrid-D

Fingerprint

Dive into the research topics of 'Cliques in geometric inhomogeneous random graphs'. Together they form a unique fingerprint.

Cite this