双曲線幾何グラフ

双曲幾何グラフ (HGG)または双曲幾何ネットワーク (HGN)は、 (1) ノードの潜在座標が確率密度関数に従って一定の負の曲率を持つ双曲空間に 散布され、(2) 2 つのノード間のエッジがメトリックの関数^{[ 1 ] [ 2 ]}に従って近接している場合に存在するという特殊なタイプの空間ネットワークです(通常、ある閾値距離よりも近い頂点間の決定論的な接続をもたらすヘヴィサイド階段関数、または接続確率をもたらす双曲距離の減衰関数のいずれか)。HGG は、埋め込み空間がユークリッドであるランダム幾何グラフ(RGG)を一般化したものです。

数学的に言えば、HGGはグラフである。${\displaystyle G(V,E)}$頂点集合V (濃度)${\displaystyle N=|V|}$）そして、ノードを2次元双曲空間上に配置された点とみなして構築されたエッジセットE${\displaystyle \mathbb {H} _{\zeta }^{2}}$一定の負のガウス曲率の、${\displaystyle -\zeta ^{2}}$およびカットオフ半径${\displaystyle R}$つまり、双曲面モデルを使用して視覚化できるポアンカレ円盤 の半径です。各点${\displaystyle i}$双曲線極座標を持つ${\displaystyle (r_{i},\theta _{i})}$と${\displaystyle 0\leq r_{i}\leq R}$そして$\displaystyle 0\leq \theta _{i}<2\pi }$。

双曲線余弦定理により距離を測定できます${\displaystyle d_{ij}}$2点間${\displaystyle i}$そして${\displaystyle j}$[ ^{2 ]​}

${\displaystyle \cosh(\zeta d_{ij})=\cosh(\zeta r_{i})\cosh(\zeta r_{j})}$${\displaystyle -\sinh(\zeta r_{i})\sinh(\zeta r_{j})\cos {\bigg (}\underbrace {\pi \!-\!{\bigg |}\pi -|\theta _{i}\!-\!\theta _{j}|{\bigg |}} _{\Delta }{\bigg )}.}$

角度 ${\displaystyle \Delta }$は、2 つの位置ベクトル間の（最小の）角度です 。

最も単純なケースでは、エッジ${\displaystyle (i,j)}$2 つのノードが特定の近傍半径内にある場合に限り、確立される。 ${\displaystyle r}$、${\displaystyle d_{ij}\leq r}$これは、影響力の閾値に相当する。

Krioukov ら^{[ 2 ]}は、半径 の円盤上に、一様にランダムなノード分布を持つ双曲幾何グラフ (およびその一般化バージョン) を生成する方法について説明しています。${\displaystyle R}$で${\displaystyle \mathbb {H} _{\zeta }^{2}}$これらのグラフは、節点次数に関してべき乗則分布を示す。角度座標${\displaystyle \theta }$各点/ノードは、${\displaystyle [0,2\pi ]}$一方、動径座標rの密度関数は確率分布に従って選択される。${\displaystyle \rho }$:

${\displaystyle \rho (r)=\alpha {\frac {\sinh(\alpha r)}{\cosh(\alpha R)-1}}}$

成長パラメータ${\displaystyle \alpha >0}$分布を制御する:${\displaystyle \alpha =\zeta }$分布は一様である${\displaystyle \mathbb {H} _{\zeta }^{2}}$値が小さい場合、ノードはディスクの中心に向かって分布し、値が大きい場合は境界に向かって分布します。このモデルでは、ノード間のエッジは${\displaystyle u}$そして${\displaystyle v}$存在するならば${\displaystyle d_{uv}<R}$または確率的に${\displaystyle \gamma (d_{uv})}$より一般的な接続減衰関数を使用する場合、平均次数は半径によって制御されます。${\displaystyle R}$双曲円盤の。以下が示せる。${\displaystyle \alpha /\zeta >1/2}$ノード次数は指数を持つべき乗則分布に従う。${\displaystyle \gamma =1+2\alpha /\zeta }$。

この画像は、さまざまな値に対してランダムに生成されたグラフを示しています。${\displaystyle \alpha }$そして${\displaystyle R}$で${\displaystyle \mathbb {H} _{1}^{2}}$どのように${\displaystyle \alpha }$ノードの分布に影響を与え、${\displaystyle R}$グラフの接続性について。距離変数が真の双曲線値をとるネイティブ表現がグラフの可視化に使用されるため、エッジは直線になります。

${\displaystyle V=\{\},E=\{\}}$のために${\displaystyle i\gets 0}$に${\displaystyle N-1}$する${\displaystyle \theta \gets U[0,2\pi ]}$${\displaystyle r\gets {\frac {1}{\alpha }}{\text{acosh}}(1+(\cosh \alpha R-1)U[0,1])}$${\displaystyle V=V\cup \{(r,\theta )\}}$すべてのペアについて${\displaystyle (u,v)\in V\times V,u\neq v}$実行する場合${\displaystyle U[0,1]\leq \gamma (d_{uv})}$それから${\displaystyle E=E\cup \{(u,v)\}}$戻る${\displaystyle V,E}$

サブ二次生成

すべてのノードペア間のエッジをチェックする手間を省くため、最新のジェネレーターはグラフをバンドに分割する追加のデータ構造を使用します。 ^{[ 5 ] [ 6 ]}この視覚化では、バンドの境界がオレンジ色で描かれた双曲グラフが示されます。この場合、分割は放射状軸に沿って行われます。ポイントは、それぞれのバンド内で角度座標でソートされて格納されます。各ポイントについて${\displaystyle u}$半径の双曲円の限界${\displaystyle R}$は（過大に）推定することができ、円と交差する帯状領域にある点のみのエッジチェックを実行するために使用できます。さらに、各帯状領域内のソートを使用して、角度座標が の 1 の周りの特定の範囲内にある点のみを考慮することで、調べる点の数をさらに減らすことができます。${\displaystyle u}$（この範囲は、双曲線円を過大評価することによっても計算されます。${\displaystyle u}$)

このアルゴリズムやその他の拡張を使用すると、時間計算量は${\displaystyle {\mathcal {O}}(n\log \log n+m)}$（どこ${\displaystyle n}$はノードの数であり、${\displaystyle m}$エッジの数）は高い確率で起こり得る。^{[ 7 ]}

のために${\displaystyle \zeta =1}$（ガウス曲率）${\displaystyle K=-1}$HGGは、ノード数が多い極限の場合に次数分布を解析的に閉形式で表現できるネットワークのアンサンブルを形成します。 ^{[ 2 ]}これは、多くのグラフのアンサンブルでは当てはまらないため、言及する価値があります。

HGGは、個人の類似性と人気度の間の競争を通じて双曲性が現れるソーシャルネットワークの有望なモデルとして提案されている。 ^{[ 8 ]}