Cliques in Hyperbolic Random Graphs

• Published in: Algorithmica 2018-08, Vol.80 (8), p.2324-2344
• Main Authors: Bläsius, Thomas, Friedrich, Tobias, Krohmer, Anton
• Format: Article
• Language: English
• Subjects: Algorithm Analysis and Problem Complexity; Algorithms; Clustering; Computer Science; Computer Systems Organization and Communication Networks; Data Structures and Information Theory; Graphs; Mathematics of Computing; Phase transitions; Theory of Computation
• ISSN: 0178-4617; 1432-0541
• DOI: 10.1007/s00453-017-0323-3

Most complex real world networks display scale-free features. This characteristic motivated the study of numerous random graph models with a power-law degree distribution. There is, however, no established and simple model which also has a high clustering of vertices as typically observed in real data. Hyperbolic random graphs bridge this gap. This natural model has recently been introduced by Krioukov et al. (in Phys Rev E 82(3):036106, 2010 ) and has shown theoretically and empirically to fulfill all typical properties of real world networks, including power-law degree distribution and high clustering. We study cliques in hyperbolic random graphs G and present new results on the expected number of k -cliques E K k and the size of the largest clique  ω ( G ) . We observe that there is a phase transition at power-law exponent β = 3 . More precisely, for β ∈ ( 2 , 3 ) we prove E K k = n k ( 3 - β ) / 2 Θ ( k ) - k and ω ( G ) = Θ ( n ( 3 - β ) / 2 ) , while for β ⩾ 3 we prove E K k = n Θ ( k ) - k and ω ( G ) = Θ ( log ( n ) / log log n ) . Furthermore, we show that for β ⩾ 3 , cliques in hyperbolic random graphs can be computed in time O ( n ) . If the underlying geometry is known, cliques can be found with worst-case runtime O ( m · n 2.5 ) for all values of β .