Simple discrete model emulating properties of hyperbolic geometrical graphs

Experimentally observed complex networks often simultaneously exhibit scale-free degree distribution, small-world property and high clusterization. Classical textbook models of network theory (Erdos-Renyi, Barabasi-Albert, Watts-Strogatz, geometrical random graphs in Euclidean space, etc.) cannot simultaneously reproduce all three of these properties. It has been known at least since [1] that geometrical random graphs on a hyperbolic disk can reproduce all three and are therefore a good candidate model for understanding the structure of experimentally observed datasets. This idea gained significant traction in the last years, but its widespread application, especially in multidisciplinary research, is suppressed by heavy reliance on cumbersome formulae of hyperbolic geometry.
Here we suggest a simple discrete model which reproduces the main properties of hyperbolic geometrical random graphs. Namely, consider a regular tree with degree p and n generations, and add a bond between any two vertices if the shortest path connecting them on the tree is not longer than m≤n. It is easy to show that for m=n such a regular graph has a log-periodic discrete power-law degree distribution with scaling exponent -2, diameter 2, and clustering coefficient of order 1. However, it is, strictly speaking, a dense graph: the average degree diverges for n→∞ proportionally to the square root of the number of vertices. There are two possible ways to rectify that.
First, consider a limit when n tends to infinity while m stays finite. In this case the graph has a distinct core-periphery structure, with core consisting of vertices of generations smaller than (n-m), which all have the same degree. However, in the periphery the power-law degree distribution is preserved, while the fraction of monomers in the core is finite and exponentially small for large m. As a result, the degree distribution converges to a curtailed power law, while diameter of the network diverges as n/m, i.e. logarithmically with the number of bonds.
Second possible generalization implies that each node can be either filled or empty, and the probability of filling the node is a function of, generally speaking, the generation k to which a node belongs, and the total number of generations n. If this probability is k-independent and decays with growing $p$ in a way that average degree of a node remains n-independent, the resulting limiting degree distribution is continuous and, for several orders of magnitude, almost exactly power law with scaling exponent -3, similar to the random geometrical graphs on a continuous hyperbolic disk [1]. By changing the k dependence of filling probability one can reproduce power law scaling with different exponents.
Moreover, one can reduce clustering coefficient to fit experimental values by introducing temperature in the system in a way similar to [1].
Thus, the suggested simple model reproduces the main properties of continuous hyperbolic graphs without relying on overcomplicated calculations. It seems that such a simple formulation of a hyperbolic geometrical graph can lead to further insights into their structure and be a good for promotion of their application for data analysis.
This work is partially supported by RFBR grant 18-29-03167.
[1] D. Krioukov, F. Papadopoulos, M. Kitsak, A. Vahdat, M. Boguna, Phys. Rev. E, 82, 036106 (2010).