Hyperbolic geometric graph

A hyperbolic geometric graph (HGG) or hyperbolic geometric network (HGN) is special spatial network where nodes are (1) sprinkled according to a probability distribution onto a hyperbolic space of constant negative curvature and (2) an edge between two nodes is present if they are close according to a function of the metric,^[1][2] a HGG generalizes a random geometric graph (RGG) whose embedding space is Euclidean.

Mathematical formulation

Mathematically, a HGG is a graph $G(V,E)$ with a vertex set V (cardinality $N=|V|$) and a edge set E constructed by considering the nodes as points placed onto a 2-dimensional hyperbolic space ${\mathbb {H}}_{\zeta }^{2}$ of constant negative Gaussian curvature, $-\zeta ^{2}$ and cut-off radius $R$, i.e. the radius of the Poincaré disk which can be visualized using a hyperboloid model. Each point $i$ has hyperbolic polar coordinates $(r_{i},\theta _{i})$ with $0\leq r_{i}\leq R$ and $0\leq \theta _{i}<2\pi$.

The hyperbolic law of cosines allows to measure the distance $d_{ij}$ between two points $i$ and $j$,^[2]

$\cosh(\zeta d_{{ij}})=\cosh(\zeta r_{i})\cosh(\zeta r_{j})$$-\sinh(\zeta r_{i})\sinh(\zeta r_{j})\cos {\bigg (}\underbrace {\pi \!-\!{\bigg |}\pi -|\theta _{i}\!-\!\theta _{j}|{\bigg |}}_{{\Delta }}{\bigg )}.$

The angle $\Delta$ is the (smallest) angle between the two position vectors.

In the simplest case, an edge $(i,j)$ is established iff (if and only if) two nodes are within a certain neighborhood radius $r$, $d_{{ij}}\leq r$, this corresponds to an influence threshold.

Connectivity decay function

In general, a link will be established with a probability depending on the distance $d_{ij}$. A connectivity decay function $\gamma (s):{\mathbb {R}}^{+}\to [0,1]$ represents the probability of assigning an edge to a pair of nodes at distance $s$. In this framework, the simple case of hard-code neighborhood like in random geometric graphs is referred to as truncation decay function.^[3]

Findings

For $\zeta =1$ (Gaussian curvature $K=-1$), HGGs form an ensemble of networks for which is possible to express the degree distribution analytically as closed form for the limiting case of large number of nodes.^[2] This is worth mentioning since this is not true for many ensemble of graphs.

Applications

HGGs have been suggested as promising model for social networks where the hyperbolicity appears through a competition between similarity and popularity of an individual.^[4]

References

1. Barthélemy, Marc. "Spatial networks". Physics Reports. 499 (1-3): 1–101. arXiv:1010.0302. doi:10.1016/j.physrep.2010.11.002.
2. Krioukov, Dmitri; Papadopoulos, Fragkiskos; Kitsak, Maksim; Vahdat, Amin; Boguñá, Marián. "Hyperbolic geometry of complex networks". Physical Review E. 82 (3). arXiv:1006.5169. doi:10.1103/PhysRevE.82.036106.
3. Barnett, L.; Di Paolo, E.; Bullock, S. "Spatially embedded random networks". Physical Review E. 76 (5). doi:10.1103/PhysRevE.76.056115.
4. Papadopoulos, Fragkiskos; Kitsak, Maksim; Serrano, M. Ángeles; Boguñá, Marián; Krioukov, Dmitri (12 September 2012). "Popularity versus similarity in growing networks". Nature. 489 (7417): 537–540. arXiv:1106.0286. doi:10.1038/nature11459.