Cliques in Hyperbolic Random Graphs

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 omega(G). We observe that there is a phase transition at power-law exponent beta = 3. More precisely, for beta is an element of (2, 3) we prove E[K-k] = n(k(3-beta)/2)Theta(k)(-k) and omega(G) = Theta(n((3-beta)/2)), while for beta >= 3 we prove E[K-k] = n Theta (k)(-k) and omega(G) = Theta(log(n)/log log n). Furthermore, we show that for beta >= 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 beta.