A hyperbolic geometric graph (HGG) or hyperbolic geometric network (HGN) is a special type of
spatial network
A spatial network (sometimes also geometric graph) is a graph in which the vertices or edges are ''spatial elements'' associated with geometric objects, i.e., the nodes are located in a space equipped with a certain metric.M. Barthelemy, "M ...
where (1) latent coordinates of nodes are sprinkled according to a
probability density function
In probability theory, a probability density function (PDF), or density of a continuous random variable, is a function whose value at any given sample (or point) in the sample space (the set of possible values taken by the random variable) can ...
into a
hyperbolic space
In mathematics, hyperbolic space of dimension n is the unique simply connected, n-dimensional Riemannian manifold of constant sectional curvature equal to -1. It is homogeneous, and satisfies the stronger property of being a symmetric space. Th ...
of
constant negative
curvature
In mathematics, curvature is any of several strongly related concepts in geometry. Intuitively, the curvature is the amount by which a curve deviates from being a straight line, or a surface deviates from being a plane.
For curves, the canonic ...
and (2) an
edge
Edge or EDGE may refer to:
Technology Computing
* Edge computing, a network load-balancing system
* Edge device, an entry point to a computer network
* Adobe Edge, a graphical development application
* Microsoft Edge, a web browser developed by ...
between two nodes is present if they are close according to a function of the
metric
Metric or metrical may refer to:
* Metric system, an internationally adopted decimal system of measurement
* An adjective indicating relation to measurement in general, or a noun describing a specific type of measurement
Mathematics
In mathema ...
(typically either a
Heaviside step function
The Heaviside step function, or the unit step function, usually denoted by or (but sometimes , or ), is a step function, named after Oliver Heaviside (1850–1925), the value of which is zero for negative arguments and one for positive argume ...
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
In graph theory, a random geometric graph (RGG) is the mathematically simplest spatial network, namely an undirected graph constructed by randomly placing ''N'' nodes in some metric space (according to a specified probability distribution) and con ...
(RGG) whose embedding space is
Euclidean.
Mathematical formulation
Mathematically, a HGG is a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
with a vertex
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
''V'' (
cardinality
In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
) and an edge set ''E'' constructed by considering the nodes as points placed onto a 2-dimensional hyperbolic space
of constant negative
Gaussian curvature
In differential geometry, the Gaussian curvature or Gauss curvature of a surface at a point is the product of the principal curvatures, and , at the given point:
K = \kappa_1 \kappa_2.
The Gaussian radius of curvature is the reciprocal of .
F ...
,
and cut-off radius
, i.e. the radius of the
Poincaré disk
Poincaré is a French surname. Notable people with the surname include:
* Henri Poincaré (1854–1912), French physicist, mathematician and philosopher of science
* Henriette Poincaré (1858-1943), wife of Prime Minister Raymond Poincaré
* L ...
which can be visualized using a
hyperboloid model
In geometry, the hyperboloid model, also known as the Minkowski model after Hermann Minkowski, is a model of ''n''-dimensional hyperbolic geometry in which points are represented by points on the forward sheet ''S''+ of a two-sheeted hyperboloid ...
.
Each point
has hyperbolic polar coordinates
with
and
.
The
hyperbolic law of cosines In hyperbolic geometry, the "law of cosines" is a pair of theorems relating the sides and angles of triangles on a hyperbolic plane, analogous to the planar law of cosines from plane trigonometry, or the spherical law of cosines in spherical trigono ...
allows to measure the distance
between two points
and
,
:
The angle
is the (smallest) angle between the two
position vectors.
In the simplest case, an edge
is established iff (if and only if) two nodes are within a certain ''neighborhood radius''
,
, this corresponds to an influence threshold.
Connectivity decay function
In general, a link will be established with a probability depending on the distance
.
A ''connectivity decay function''