双曲幾何グラフ

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

数学的には、HGG は頂点集合V (濃度) と辺集合E を持つグラフ であり、ノードを一定の負のガウス曲率、カットオフ半径、つまり双曲面モデルを使用して視覚化できるポアンカレ円板の半径 の 2 次元双曲空間に配置された点と見なして構築されます。各点には、およびの双曲極座標があります。 ${\displaystyle G(V,E)}$ ${\displaystyle N=|V|}$${\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 }$

双曲余弦定理により、2点間の距離を測定することができる。^[2]${\displaystyle d_{ij}}$${\displaystyle i}$${\displaystyle j}$

${\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 )}.}$

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

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

一般的に、リンクは距離に依存する確率で確立されます 。接続性減衰関数は、距離にあるノードのペアにエッジを割り当てる確率を表します。このフレームワークでは、ランダム幾何学グラフのようなハードコード近傍の単純なケースは、切り捨て減衰関数と呼ばれます。^[3]${\displaystyle d_{ij}}$ ${\displaystyle \gamma (s):\mathbb {R} ^{+}\to [0,1]}$${\displaystyle s}$

Krioukov ら^{[2] は、}半径 の円板上に一様ランダムなノード分布 (および一般化されたバージョン) を持つ双曲幾何グラフを生成する方法を説明しています。これらのグラフは、ノードの次数に対してべき乗分布を生成します。各ポイント/ノードの角度座標は から一様ランダムに選択され、一方、半径座標 r の密度関数は確率分布に従って選択されます。 ${\displaystyle R}$${\displaystyle \mathbb {H} _{\zeta }^{2}}$${\displaystyle \theta }$${\displaystyle [0,2\pi ]}$ ${\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}$

出典: ^[4]

双曲幾何学グラフを生成するための単純なアルゴリズムは、各ポイントの角度座標と半径座標をランダムにサンプリングして選択することにより、双曲ディスク上のノードを分散します。各ノードのペアごとに、それぞれの距離の接続性減衰関数の値の確率でエッジが挿入されます。疑似コードは次のようになります。

${\displaystyle V=\{\},E=\{\}}$
 それぞれのペアに対して行うif then return${\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}$

${\displaystyle N}$は生成するノードの数で、確率密度関数による放射状座標の分布は逆変換サンプリングを使用して実現されます。は、指定された間隔内の値の均一なサンプリングを表します。アルゴリズムはすべてのノードペアのエッジをチェックするため、実行時間は2次式になります。 が大きいアプリケーションの場合、これは実行可能ではなく、サブ2次式のランタイムを持つアルゴリズムが必要になります。 ${\displaystyle \rho }$${\displaystyle U}$${\displaystyle N}$

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

このアルゴリズムと他の拡張を使用すると、（ノード数とエッジ数）の時間計算量が高確率で可能になります。^[7]${\displaystyle {\mathcal {O}}(n\log \log n+m)}$${\displaystyle n}$${\displaystyle m}$

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

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