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.
Mathematical formulation Mathematically, a HGG is a graph G ( V , E ) {\displaystyle G(V,E)} with a vertex set V (cardinality N = | V | {\displaystyle N=|V|} ) and an edge set E constructed by considering the nodes as points placed onto a 2-dimensional hyperbolic space H ζ 2 {\displaystyle \mathbb {H} _{\zeta }^{2}} of constant negative Gaussian curvature, − ζ 2 {\displaystyle -\zeta ^{2}} and cut-off radius R {\displaystyle R} , i.e. the radius of the Poincaré disk which can be visualized using a hyperboloid model. Each point i {\displaystyle i} has hyperbolic polar coordinates ( r i , θ i ) {\displaystyle (r_{i},\theta _{i})} with 0 ≤ r i ≤ R {\displaystyle 0\leq r_{i}\leq R} and 0 ≤ θ i < 2 π {\displaystyle 0\leq \theta _{i}<2\pi } . The hyperbolic law of cosines allows to measure the distance d i j {\displaystyle d_{ij}} between two points i {\displaystyle i} and j {\displaystyle j} ,
cosh ( ζ d i j ) = cosh ( ζ r i ) cosh ( ζ r j ) {\displaystyle \cosh(\zeta d_{ij})=\cosh(\zeta r_{i})\cosh(\zeta r_{j})}
− sinh ( ζ r i ) sinh ( ζ r j ) cos ( π − | π − | θ i − θ 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 ( i , j ) {\displaystyle (i,j)} is established iff (if and only if) two nodes are within a certain neighborhood radius r {\displaystyle r} , d i j ≤ 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 d i j {\displaystyle d_{ij}} . A connectivity decay function γ ( s ) : R + → [ 0 , 1 ] {\displaystyle \gamma (s):\mathbb {R} ^{+}\to [0,1]} represents the probability of assigning an edge to a pair of nodes at distance s {\displaystyle s} . In this framework, the simple case of hard-code neighborhood like in random geometric graphs is referred to as truncation decay function.
… excerpt ends here. Continue reading the full article.
