# Hyperbolic geometric graph

A hyperbolic geometric graph (HGG) or hyperbolic geometric network (HGN) is a special type of spatial network where (1) latent coordinates of nodes are sprinkled according to a probability density function into 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] (typically either a Heaviside step function resulting in deterministic connections between vertices closer than a certain threshold distance, or a decaying function of hyperbolic distance yielding the connection probability). A HGG generalizes a random geometric graph (RGG) whose embedding space is Euclidean.

## Mathematical formulation

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

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

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

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

In the simplest case, an edge ${\displaystyle (i,j)}$ is established iff (if and only if) two nodes are within a certain neighborhood radius ${\displaystyle r}$, ${\displaystyle 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 ${\displaystyle d_{ij}}$. A connectivity decay function ${\displaystyle \gamma (s):\mathbb {R} ^{+}\to [0,1]}$ represents the probability of assigning an edge to a pair of nodes at distance ${\displaystyle 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 ${\displaystyle \zeta =1}$ (Gaussian curvature ${\displaystyle 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 ensembles 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. Bibcode:2011PhR...499....1B. doi:10.1016/j.physrep.2010.11.002.
2. ^ a b c Krioukov, Dmitri; Papadopoulos, Fragkiskos; Kitsak, Maksim; Vahdat, Amin; Boguñá, Marián. "Hyperbolic geometry of complex networks". Physical Review E. 82 (3). arXiv:1006.5169. Bibcode:2010PhRvE..82c6106K. doi:10.1103/PhysRevE.82.036106.
3. ^ Barnett, L.; Di Paolo, E.; Bullock, S. "Spatially embedded random networks". Physical Review E. 76 (5). Bibcode:2007PhRvE..76e6115B. 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. Bibcode:2012Natur.489..537P. doi:10.1038/nature11459. PMID 22972194.