ランダム幾何学グラフ

グラフ理論において、ランダム幾何学グラフ( RGG ) は、数学的に最も単純な空間ネットワーク、すなわち、N個のノードを (指定された確率分布に従って) ある距離空間にランダムに配置し、 2 つのノードの距離が所定の範囲 (たとえば、特定の近傍半径rより小さい) にある場合にのみ、 2 つのノードをリンクで接続することによって構築される無向グラフです。

ランダム幾何学グラフは、さまざまな点で実際の人間のソーシャル ネットワークに似ています。たとえば、コミュニティ構造、つまりモジュール性の高いノードのクラスターが自発的に示されます。エルデシュ-レーニ モデルやバラバシ-アルバート (BA) モデルを使用して生成されるものなど、他のランダム グラフ生成アルゴリズムでは、このタイプの構造は作成されません。さらに、ランダム幾何学グラフは、空間次元に応じて次数のアソート性を示します。 ^[1]「人気のある」ノード (リンクが多いノード) は、特に他の人気のあるノードにリンクされる可能性が高くなります。

RGGの実際の応用としては、アドホックネットワークのモデリングがあります。^{[2]さらに、RGGはグラフアルゴリズムの}ベンチマークを実行するためにも使用されます。

以下では、  頂点の集合Vと辺の集合E ⊆ V × Vを持つ無向グラフをG = ( V , E )で表すものとする。集合のサイズは、| V | = nおよび| E | = mで表される。さらに、特に断りがない限り、ユークリッド距離を持つ距離空間[0,1) ^dが考慮される。つまり、任意の点について、x と y のユークリッド距離は次のように定義される。 ${\displaystyle x,y\in [0,1)^{d}}$

${\displaystyle d(x,y)=||x-y||_{2}={\sqrt {\sum _{i=1}^{d}(x_{i}-y_{i})^{2}}}}$。

ランダム幾何学グラフ（RGG）は、基になる空間[0,1) ^dの一様分布からランダムにサンプリングされたノードを持つ無向幾何学グラフです。^[3] 2つの頂点p、q ∈ Vは、それらの距離がループを除いて、事前に指定されたパラメータr ∈ (0,1)よりも小さい場合にのみ接続されます。したがって、パラメータrとnはRGGを完全に特徴付けます。

単純なアプローチでは、すべての頂点から他のすべての頂点までの距離を計算します。チェックされる可能性のある接続が存在するため、単純なアルゴリズムの時間計算量は です。サンプルは、 上の乱数ジェネレータ(RNG)を使用して生成されます。実際には、 上の d 個の乱数ジェネレータ (各次元に 1 つの RNG) を使用してこれを実装できます。 ${\textstyle {\frac {n(n-1)}{2}}}$${\textstyle \Theta (n^{2})}$${\displaystyle [0,1)^{d}}$${\displaystyle [0,1)}$

V  := generateSamples( n )   // 単位立方体に n 個のサンプルを生成します。
for each  p ∈ V  do 
    for each  q ∈ V \{p} do 
        if distance( p , q ) ≤ r  then 
            addConnection( p , q ) // エッジ (p, q) をエッジデータ構造に追加します。
         end if 
    end for 
end for

このアルゴリズムはスケーラブルではないため(すべての頂点は他のすべての頂点の情報を必要とする)、Holtgrewe らと Funke らはこの問題に対する新しいアルゴリズムを導入しました。

Holtgrewe らによって提案されたこのアルゴリズムは、次元 2 の最初の分散 RGG 生成アルゴリズムでした。^[4]このアルゴリズムは、単位正方形を、辺の長さが少なくとも である等しいサイズのセルに分割します。 指定された数のプロセッサに対して、各プロセッサにセルが割り当てられます。ここで、 は簡単にするために平方数であると想定されますが、これは任意の数のプロセッサに一般化できます。 次に、各プロセッサは頂点を生成し、それぞれの所有者に配布されます。 次に、頂点は、たとえばクイックソートによって、該当するセル番号でソートされます。 次に、各プロセッサは、各処理ユニットが他のユニットとは独立して、パーティション内のエッジを計算できるように、境界セルの頂点に関する情報を隣接するプロセッサに送信します。 予想される実行時間は です。 このアルゴリズムの通信コストの上限は で与えられます。ここで、 は、長さlビットのメッセージをc 個の通信パートナーに送信する全対全通信にかかる時間を表します。 は、長さlビットのメッセージをポイントツーポイントで通信するために必要な時間です。 ${\displaystyle r}$${\displaystyle P=p^{2}}$${\textstyle {k \over p}\times {k \over p}}$${\textstyle k=\left\lfloor {1/r}\right\rfloor .}$${\textstyle P}$${\textstyle {\frac {n}{P}}}$${\textstyle O({\frac {n}{P}}\log {\frac {n}{P}})}$${\displaystyle T_{all-to-all}(n/P,P)+T_{all-to-all}(1,P)+T_{point-to-point}(n/(k\cdot {P})+2)}$${\displaystyle T_{all-to-all}(l,c)}$${\displaystyle T_{point-to-point}(l)}$

このアルゴリズムは通信なしでは動作しないため、Funkeらは処理ユニット間の通信なしで動作する高次元用のスケーラブルな分散RGGジェネレータ ^{[4]を提案した。}

^{このアルゴリズム[4]}で使用されるアプローチは、Holtgrewe のアプローチに似ています。単位立方体を、少なくともrの側面の長さを持つ等しいサイズのチャンクに分割します。したがって、d = 2 では正方形になり、d = 3 では立方体になります。次元ごとに最大で 個のチャンクしか収まらないため、チャンクの数は 個に制限されます。前と同様に、各プロセッサにはチャンクが割り当てられ、そのチャンクに対してプロセッサが頂点を生成します。通信のないプロセスを実現するために、各プロセッサはシードハッシュ関数の疑似ランダム化を利用して、隣接するチャンクに同じ頂点を生成します。このようにして、各プロセッサは同じ頂点を計算するため、頂点情報を交換する必要はありません。 ${\textstyle {\left\lfloor {1/r}\right\rfloor }}$${\textstyle {\left\lfloor {1/r}\right\rfloor }^{d}}$${\textstyle {\left\lfloor {1/r}\right\rfloor }^{d} \over P}$

Funke らは、次元 3 の場合、処理ユニット間の通信コストなしで、予想される実行時間が であることを示しました。 ${\textstyle O({\frac {m+n}{P}}+\log {P})}$

RGG で単一の頂点が孤立している確率は です。^[5]を孤立している頂点の数を数えるランダム変数とします。このとき、 の期待値はです。この項は、 RGG の接続性に関する情報を提供します。 の場合、RGG は漸近的にほぼ確実に接続されています。 の場合、RGG は漸近的にほぼ確実に非接続です。また の場合、RGG は 以上の頂点をカバーする巨大な要素を持ち、パラメータ でポアソン分布します。したがって の場合、RGG が接続されている確率は であり、RGG が接続されていない確率は です。 ${\textstyle (1-\pi r^{2})^{n-1}}$${\textstyle X}$${\textstyle X}$${\textstyle E(X)=n(1-\pi r^{2})^{n-1}=ne^{-\pi r^{2}n}-O(r^{4}n)}$${\textstyle \mu =ne^{-\pi r^{2}n}}$${\textstyle \mu \longrightarrow 0}$${\displaystyle \mu \longrightarrow \infty }$${\textstyle \mu =\Theta (1)}$${\textstyle {\frac {n}{2}}}$${\displaystyle X}$${\displaystyle \mu }$${\textstyle \mu =\Theta (1)}$${\textstyle P[X=0]\sim e^{-\mu }}$${\textstyle P[X>0]\sim 1-e^{-\mu }}$

任意の-ノルム ( ) および任意の次元数 に対して、RGG は定数 でにおける接続性の鋭い閾値を持ちます。2 次元空間およびユークリッドノルム (および) の特殊なケースでは、これは をもたらします。 ${\textstyle l_{p}}$${\textstyle 1\leq p\leq \infty }$${\displaystyle d>2}$${\textstyle r\sim \left({\ln(n) \over \alpha _{p,d}n}\right)^{1 \over d}}$${\displaystyle \alpha _{p,d}}$${\displaystyle d=2}$${\displaystyle p=2}$${\textstyle r\sim {\sqrt {\ln(n) \over \pi n}}}$

2次元の場合、閾値はハミルトン閉路（ハミルトン経路）の存在に関する情報も提供することが示されている。 ^[6]任意の に対して、 の場合、RGG には漸近的にほぼ確実にハミルトン閉路が存在せず、任意の に対しての場合、RGG には漸近的にほぼ確実にハミルトン閉路が存在する。 ${\textstyle r\sim {\sqrt {\ln(n) \over \pi n}}}$${\displaystyle \epsilon >0}$${\textstyle r\sim {\sqrt {\ln(n) \over (\pi +\epsilon )n}}}$${\textstyle r\sim {\sqrt {\ln(n) \over (\pi -\epsilon )n}}}$${\textstyle \epsilon >0}$

RGGのクラスタリング係数は、基礎空間の次元d [0,1) ^dのみに依存する。クラスタリング係数は^{[7]である。}

${\textstyle C_{d}=1-H_{d}(1)}$偶数の場合は、奇数の場合はとなります。ただし が大きい場合、これは と簡略化されます。 ${\displaystyle d}$${\textstyle C_{d}={3 \over 2}-H_{d}({1 \over 2})}$${\displaystyle d}$$${\displaystyle H_{d}(x)={1 \over {\sqrt {\pi }}}\sum _{i=x}^{d \over 2}{\Gamma (i) \over \Gamma (i+{1 \over 2})}\left({3 \over 4}\right)^{i+{1 \over 2}}}$$${\displaystyle d}$${\displaystyle C_{d}\sim 3{\sqrt {2 \over \pi d}}\left({3 \over 4}\right)^{d+1 \over 2}}$

1988 年に Waxman ^[8]は、Gilbert が提案した決定論的な接続関数ではなく、確率的な接続関数を導入することにより、標準的な RGG を一般化しました。Waxman が導入した例は、2 つのノード および が、によって与えられる確率で接続する伸張された指数関数でした。ここで、 はユークリッド距離、 はシステムによって決定されるパラメーターです。確率的な接続関数を持つこのタイプの RGG は、多くの場合、ソフト ランダム ジオメトリック グラフと呼ばれます。これは現在、2 つのランダム ソース、つまりノード (頂点) の位置とリンク (エッジ) の形成を持っています。この接続関数は、干渉のないワイヤレス ネットワークの研究によく使用される文献でさらに一般化されています。パラメーター は、信号が距離とともにどのように減衰するかを表します。 が自由空間のとき、 は町のような雑然とした環境 (= 6 はニューヨークのような都市をモデル化) をモデル化し、 は反射率の高い環境をモデル化します。 についてはが Waxman モデルであるのに対し、 および については標準的な RGG であることがわかります。直感的に、これらのタイプの接続関数は、リンクが作成される確率が距離とともにどのように減衰するかをモデル化します。 ${\displaystyle i}$${\displaystyle j}$${\textstyle H_{ij}=\beta e^{-{r_{ij} \over r_{0}}}}$${\displaystyle r_{ij}}$${\displaystyle \beta }$${\displaystyle r_{0}}$${\textstyle H_{ij}=\beta e^{-\left({r_{ij} \over r_{0}}\right)^{\eta }}}$${\displaystyle \eta }$${\displaystyle \eta =2}$${\displaystyle \eta >2}$${\displaystyle \eta <2}$${\displaystyle \eta =1}$${\displaystyle \eta \to \infty }$${\textstyle \beta =1}$

指数関数的接続関数を持つネットワークの高密度極限では、孤立ノードの数はポアソン分布し、結果として得られるネットワークには、一意の巨大コンポーネントと孤立ノードのみが含まれます。^{[9]したがって、孤立ノードが存在しないことを確認することで、密な領域では、ネットワークは完全に接続されます。これは、 [10]}でディスク モデルに対して示された結果と同様です。媒介中心性^[11]や接続性^[9]などのこれらのネットワークの特性は、境界効果が無視できるほど小さいことを意味する密度の極限で研究されることがよくあります。ただし、ネットワークが有限である現実の世界では、非常に密集していても、境界効果は完全な接続性に影響を与えます。実際、 ^[12]では、指数関数的接続関数を持つ完全な接続性は、ドメインのコーナー/面に近いノードがバルク内のノードと比較して接続する可能性が低いため、境界効果によって大きく影響されることが示されています。結果として、完全な接続性は、バルクとジオメトリ境界からの寄与の合計として表すことができます。無線ネットワークの接続関数のより一般的な分析では、完全な接続の確率は、接続関数のいくつかのモーメントと領域の形状によってよく近似できることが示されています。^[13]${\displaystyle \to \infty }$