Hyperbolic geometric graph

From Infogalactic: the planetary knowledge core
Jump to: navigation, search

Lua error in package.lua at line 80: module 'strict' not found.

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}^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 < 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. Lua error in package.lua at line 80: module 'strict' not found.
  2. 2.0 2.1 2.2 Lua error in package.lua at line 80: module 'strict' not found.
  3. Lua error in package.lua at line 80: module 'strict' not found.
  4. Lua error in package.lua at line 80: module 'strict' not found.