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…

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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 (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.

Mathematically, a HGG is a graph G(V,E) with a vertex set V (cardinality N=|V| ) and an edge set E constructed by considering the nodes as points placed onto a 2-dimensional hyperbolic space \mathbb{H}^2_\zeta 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 . The hyperbolic law of cosines allows to measure the distance d_{ij} between two points i and j , \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. \rho(r) = \alpha \frac{\sinh(\alpha r)}{\cosh(\alpha R) - 1} The growth parameter \alpha > 0 controls the distribution: For \alpha = \zeta , the distribution is uniform in \mathbb{H}_\zeta^2 , for smaller values the nodes are distributed more towards the center of the disk and for bigger values more towards the border.

In this model, edges between nodes u and v exist iff d_{uv} or with probability \gamma(d_{uv}) if a more general connectivity decay function is used. The average degree is controlled by the radius R of the hyperbolic disk. It can be shown, that for \alpha / \zeta > 1/2 the node degrees follow a power law distribution with exponent \gamma = 1 + 2\alpha / \zeta .

The image depicts randomly generated graphs for different values of \alpha and R in \mathbb{H}_1^2 . It can be seen how \alpha has an effect on the distribution of the nodes and R on the connectivity of the graph. The native representation where the distance variables have their true hyperbolic values is used for the visualization of the graph, therefore edges are straight lines.

Quadratic complexity generator

Source: The naive algorithm for the generation of hyperbolic geometric graphs distributes the nodes on the hyperbolic disk by choosing the angular and radial coordinates of each point are sampled randomly. For every pair of nodes an edge is then inserted with the probability of the value of the connectivity decay function of their respective distance.

The pseudocode looks as follows: V = \{ \}, E = \{ \} for i \gets 0 to N - 1 do \theta \gets U[0, 2\pi] r \gets \frac{1}{\alpha} \text{acosh} (1 + (\cosh \alpha R - 1) U[0, 1]) V = V \cup \{ (r, \theta)\} for every pair (u, v) \in V \times V, u \neq v do if U[0, 1] \leq \gamma(d_{uv}) then E = E \cup \{ (u,v) \} return V, E N is the number of nodes to generate, the distribution of the radial coordinate by the probability density function \rho is achieved by using inverse transform sampling. U denotes the uniform sampling of a value in the given interval.

Because the algorithm checks for edges for all pairs of nodes, the runtime is quadratic. For applications where N is big, this is not viable any more and algorithms with subquadratic runtime are needed.

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. This is worth mentioning since this is not true for many ensembles of graphs.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1314054230 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001314054230 · captured 1759145709.0 · version history

Cite this page as: encyclopegia.org, “Hyperbolic geometric graph”, snapshot enwiki-001314054230. https://encyclopegia.org/a/hyperbolic-geometric-graph

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.