Hyperbolic geometric graph

Theory

Network types

Features
Clique Component Cut Cycle Data structure Edge Loop Neighborhood Path Vertex Adjacency list / matrix Incidence list / matrix
Types
Bipartite Complete Directed Hyper Multi Random Weighted

Models

Topology
Random graph Erdős–Rényi Barabási–Albert Watts–Strogatz Exponential random (ERGM) Hyperbolic (HGN) Hierarchical Stochastic block model
Dynamics
Boolean network agent based Epidemic/SIR

Lists
Categories

Category:Network theory
Category:Graph theory

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

↑ Barthélemy, Marc. "Spatial networks". Physics Reports. 499 (1-3): 1–101. arXiv:1010.0302. doi:10.1016/j.physrep.2010.11.002.
1 2 3 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.
↑ Barnett, L.; Di Paolo, E.; Bullock, S. "Spatially embedded random networks". Physical Review E. 76 (5). doi:10.1103/PhysRevE.76.056115.
↑ 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.

This article is issued from Wikipedia - version of the 7/12/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.