Hyperbolic geometric graph

Related on Lably

Through Graph (discrete mathematics), Cardinality and Position (geometry)

Lab · Class 6–12Data Visualization Lab Lab · Class 8–9Introduction to Graphs Lab · Class 8–9Data Handling & Graphs Lab · Class 9–11Graph Plotter

Mathematical formulation

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 $H_{ζ}^{2}$ of constant negative Gaussian curvature, $- ζ^{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}, θ_{i})$ with $0 \leq r_{i} \leq R$ and $0 \leq θ_{i} < 2 π$ .

The hyperbolic law of cosines allows to measure the distance $d_{i j}$ between two points $i$ and $j$ ,

\cosh (ζ d_{i j}) = \cosh (ζ r_{i}) \cosh (ζ r_{j})

- \sinh (ζ r_{i}) \sinh (ζ r_{j}) \cos (\underset{Δ}{\underset{⏟}{π - | π - | θ_{i} - θ_{j} | |}}) .

The angle $Δ$ 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_{i j} \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}$ . A connectivity decay function $γ (s) : 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 more chapters are free with a Lably account.

Generating hyperbolic geometric graphs

Krioukov et al. describe how to generate hyperbolic geometric graphs with uniformly random node distribution (as well as generalized versions) on a disk of radius $R$ in $H_{ζ}^{2}$ . These graphs yield a power-law distribution for the node degrees. The angular coordinate $θ$ of each point/node is chosen uniformly random from $[0, 2 π]$ , while the density function for the radial coordinate r is chosen according to the probability distribution $ρ$ :

ρ (r) = α \frac{\sinh (α r)}{\cosh (α R) - 1}

The growth parameter $α > 0$ controls the distribution: For $α = ζ$ , the distribution is uniform in $H_{ζ}^{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_{u v} < R$ or with probability $γ (d_{u v})$ 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 $α / ζ > 1 / 2$ the node degrees follow a power law distribution with exponent $γ = 1 + 2 α / ζ$ .

The image depicts randomly generated graphs for different values of $α$ and $R$ in $H_{1}^{2}$ . It can be seen how $α$ 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:

<span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt67" data-mw='{"name":"math","attrs":{},"body":{"extsrc":" V = \\{ \\}, E = \\{ \\} "}}' id="mwgg"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle V=\{\},E=\{\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>V</mi> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mi>E</mi> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle V=\{\},E=\{\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/878073633f339850adf83f1256368e52ac8c3840" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.444ex; height:2.843ex;" alt="{\displaystyle V=\{\},E=\{\}}"/></span> <b id="mwgw">for</b> <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt68" data-mw='{"name":"math","attrs":{},"body":{"extsrc":" i \\gets 0 "}}' id="mwhA"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle i\gets 0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> <mo stretchy="false">←<!-- ← --></mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i\gets 0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/83306299648e80b8f73280df6fb3e7d2e000b1ae" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.579ex; height:2.176ex;" alt="{\displaystyle i\gets 0}"/></span> <b id="mwhQ">to</b> <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt69" data-mw='{"name":"math","attrs":{},"body":{"extsrc":" N - 1 "}}' id="mwhg"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle N-1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> <mo>−<!-- − --></mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N-1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/86aeb216b214f70df1341f34ce273cd3582ce2aa" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.066ex; height:2.343ex;" alt="{\displaystyle N-1}"/></span> <b id="mwhw">do</b> <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt70" data-mw='{"name":"math","attrs":{},"body":{"extsrc":" \\theta \\gets U[0, 2\\pi] "}}' id="mwiA"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \theta \gets U[0,2\pi ]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>θ<!-- θ --></mi> <mo stretchy="false">←<!-- ← --></mo> <mi>U</mi> <mo stretchy="false">[</mo> <mn>0</mn> <mo>,</mo> <mn>2</mn> <mi>π<!-- π --></mi> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \theta \gets U[0,2\pi ]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bc8612fded049bc692f75795727f5e5aad0daeab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.472ex; height:2.843ex;" alt="{\displaystyle \theta \gets U[0,2\pi ]}"/></span> <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt71" data-mw='{"name":"math","attrs":{},"body":{"extsrc":" r \\gets \\frac{1}{\\alpha} \\text{acosh} (1 + (\\cosh \\alpha R - 1) U[0, 1]) "}}' id="mwiQ"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle r\gets {\frac {1}{\alpha }}{\text{acosh}}(1+(\cosh \alpha R-1)U[0,1])}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>r</mi> <mo stretchy="false">←<!-- ← --></mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mi>α<!-- α --></mi> </mfrac> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mtext>acosh</mtext> </mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mo stretchy="false">(</mo> <mi>cosh</mi> <mo>⁡<!-- ⁡ --></mo> <mi>α<!-- α --></mi> <mi>R</mi> <mo>−<!-- − --></mo> <mn>1</mn> <mo stretchy="false">)</mo> <mi>U</mi> <mo stretchy="false">[</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">]</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r\gets {\frac {1}{\alpha }}{\text{acosh}}(1+(\cosh \alpha R-1)U[0,1])}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bceaae145512c1a462ca19969d44b7d38a59a10a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:38.654ex; height:5.176ex;" alt="{\displaystyle r\gets {\frac {1}{\alpha }}{\text{acosh}}(1+(\cosh \alpha R-1)U[0,1])}"/></span> <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt72" data-mw='{"name":"math","attrs":{},"body":{"extsrc":" V = V \\cup \\{ (r, \\theta)\\} "}}' id="mwig"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle V=V\cup \{(r,\theta )\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>V</mi> <mo>=</mo> <mi>V</mi> <mo>∪<!-- ∪ --></mo> <mo fence="false" stretchy="false">{</mo> <mo stretchy="false">(</mo> <mi>r</mi> <mo>,</mo> <mi>θ<!-- θ --></mi> <mo stretchy="false">)</mo> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle V=V\cup \{(r,\theta )\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/dd60f117076a3f532f880107dc07285d9244f935" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.563ex; height:2.843ex;" alt="{\displaystyle V=V\cup \{(r,\theta )\}}"/></span> <b id="mwiw">for every pair </b> <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt73" data-mw='{"name":"math","attrs":{},"body":{"extsrc":" (u, v) \\in V \\times V, u \\neq v"}}' id="mwjA"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle (u,v)\in V\times V,u\neq v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>u</mi> <mo>,</mo> <mi>v</mi> <mo stretchy="false">)</mo> <mo>∈<!-- ∈ --></mo> <mi>V</mi> <mo>×<!-- × --></mo> <mi>V</mi> <mo>,</mo> <mi>u</mi> <mo>≠<!-- ≠ --></mo> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (u,v)\in V\times V,u\neq v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a2342b94d2eb18464f7be3999fb2ea886418953d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.146ex; height:2.843ex;" alt="{\displaystyle (u,v)\in V\times V,u\neq v}"/></span> <b id="mwjQ">do</b> <b id="mwjg">if</b> <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt74" data-mw='{"name":"math","attrs":{},"body":{"extsrc":" U[0, 1] \\leq \\gamma(d_{uv}) "}}' id="mwjw"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle U[0,1]\leq \gamma (d_{uv})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>U</mi> <mo stretchy="false">[</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">]</mo> <mo>≤<!-- ≤ --></mo> <mi>γ<!-- γ --></mi> <mo stretchy="false">(</mo> <msub> <mi>d</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>u</mi> <mi>v</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle U[0,1]\leq \gamma (d_{uv})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/06d82e17a0aeeefd0764e7c79b471f6866d0cad9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.784ex; height:2.843ex;" alt="{\displaystyle U[0,1]\leq \gamma (d_{uv})}"/></span> <b id="mwkA">then</b> <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt75" data-mw='{"name":"math","attrs":{},"body":{"extsrc":" E = E \\cup \\{ (u,v) \\} "}}' id="mwkQ"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle E=E\cup \{(u,v)\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>E</mi> <mo>=</mo> <mi>E</mi> <mo>∪<!-- ∪ --></mo> <mo fence="false" stretchy="false">{</mo> <mo stretchy="false">(</mo> <mi>u</mi> <mo>,</mo> <mi>v</mi> <mo stretchy="false">)</mo> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle E=E\cup \{(u,v)\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ffb71dbfc1ba34514cae277a0bfa3bc95fefa56b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.858ex; height:2.843ex;" alt="{\displaystyle E=E\cup \{(u,v)\}}"/></span> <b id="mwkg">return</b> <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt76" data-mw='{"name":"math","attrs":{},"body":{"extsrc":" V, E "}}' id="mwkw"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle V,E}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>V</mi> <mo>,</mo> <mi>E</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle V,E}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e779fc22e4863935337975b745a1bea4b0547b03" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.597ex; height:2.509ex;" alt="{\displaystyle V,E}"/></span>

$N$ is the number of nodes to generate, the distribution of the radial coordinate by the probability density function $ρ$ 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.

Sub-quadratic generation

To avoid checking for edges between every pair of nodes, modern generators use additional data structures that partition the graph into bands. A visualization of this shows a hyperbolic graph with the boundary of the bands drawn in orange. In this case, the partitioning is done along the radial axis. Points are stored sorted by their angular coordinate in their respective band. For each point $u$ , the limits of its hyperbolic circle of radius $R$ can be (over-)estimated and used to only perform the edge-check for points that lie in a band that intersects the circle. Additionally, the sorting within each band can be used to further reduce the number of points to look at by only considering points whose angular coordinate lie in a certain range around the one of $u$ (this range is also computed by over-estimating the hyperbolic circle around $u$ ).

Using this and other extensions of the algorithm, time complexities of $O (n \log \log n + m)$ (where $n$ is the number of nodes and $m$ the number of edges) are possible with high probability.

Findings

For $ζ = 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.

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.