確率的ブロックモデル

確率的ブロックモデルは、ランダムグラフの生成モデルです。このモデルは、特定のエッジ密度で互いに接続されているノードのサブセットであるコミュニティを含むグラフを生成する傾向があります。たとえば、エッジはコミュニティ間よりもコミュニティ内でより一般的である場合があります。その数学的定式化は、1983 年にPaul W. Hollandらによってソーシャル ネットワーク分析の分野で初めて導入されました^{[ 1 ]}。確率的ブロックモデルは、統計学、機械学習、ネットワーク科学において重要であり、グラフ データ内のコミュニティ構造を復元するタスクの有用なベンチマークとして機能します。

確率的ブロックモデルは、以下のパラメータを取ります。

• 番号${\displaystyle n}$頂点の数。
• 頂点集合の分割${\displaystyle \{1,\ldots ,n\}}$互いに素な部分集合に分割する${\displaystyle C_{1},\ldots ,C_{r}}$コミュニティと呼ばれるもの。
• 対称${\displaystyle r\times r}$マトリックス${\displaystyle P}$エッジ確率の。

次に、エッジセットは次のようにランダムにサンプリングされます。任意の 2 つの頂点$u ∈ Cᵢ$そして${\displaystyle v\in C_{j}}$確率でエッジで接続されている${\displaystyle P_{ij}}$例として、次のような問題があります。 ${\displaystyle n}$頂点では、エッジは説明どおりにサンプリングされ、グループが復元されます。 ${\displaystyle C_{1},\ldots ,C_{r}}$。

確率行列が定数である場合、${\displaystyle P_{ij}=p}$すべての人々のために${\displaystyle i,j}$の場合、結果はエルデシュ・レーニ モデルになります。${\displaystyle G(n,p)}$この事例は退化しており、コミュニティへの分割は無意味になるが、エルデシュ＝レーニモデルとの密接な関係を示している。

植栽された分割モデルは、確率行列の値が${\displaystyle P}$定数である${\displaystyle p}$対角線上にあり、もう1つの定数${\displaystyle q}$対角線から外れている。したがって、同じコミュニティ内の 2 つの頂点は、確率でエッジを共有する。${\displaystyle p}$異なるコミュニティの2つの頂点が確率でエッジを共有する一方${\displaystyle q}$時には、この制限付きモデルが確率的ブロックモデルと呼ばれることがあります。${\displaystyle p>q}$これは同類モデルと呼ばれ、${\displaystyle p<q}$これは異類関係と呼ばれます。

一般的な確率的ブロックモデルに戻ると、モデルが強同類性であるとは、${\displaystyle P_{ii}>P_{jk}}$いつでも${\displaystyle j\neq k}$: すべての対角要素がすべての非対角要素を支配する。モデルは、以下の条件を満たす場合に弱同類性と呼ばれる。${\displaystyle P_{ii}>P_{ij}}$いつでも${\displaystyle i\neq j}$: 各対角要素は、自身の行と列の残りの要素を支配するだけでよい。^{[ 2 ]}この用語の異同形式は、すべての不等式を反転させることで存在する。一部のアルゴリズムでは、この形式の同同条件または異同条件を持つブロックモデルの方が回復が容易になる場合がある。^{[ 2 ]}

アルゴリズムによるコミュニティ検出に関する文献の多くは、検出、部分的な復元、完全な復元という3つの統計的タスクを扱っている。

確率的ブロックモデルは、パーコレーション閾値を彷彿とさせる鋭い閾値効果を示す。^{[ 7 ] [ 3 ] [ 8 ]}サイズを許容すると仮定する${\displaystyle n}$グラフの成長率を一定に保ち、コミュニティのサイズを固定比率に維持します。確率行列が固定されている場合、部分的回復や完全回復などのタスクは、すべての非退化パラメータ設定で実行可能になります。ただし、確率行列を適切な割合で縮小すると、${\displaystyle n}$が増加すると、急激な相転移が観察されます。特定のパラメータ設定では、確率が 1 に近づく回復が可能になりますが、パラメータの閾値の反対側では、どのアルゴリズムを使用しても回復の確率は 0 に近づきます。

部分的な回復の場合、適切なスケーリングは${\displaystyle P_{ij}={\チルダ {P}}_{ij}/n}$固定の場合${\displaystyle {\tilde {P}}}$その結果、平均次数が一定のグラフが得られる。2つの同サイズのコミュニティの場合、確率行列を用いた同類植栽分割モデルでは $${\displaystyle P=\left({\begin{array}{cc}{\tilde {p}}/n&{\tilde {q}}/n\\{\tilde {q}}/n&{\tilde {p}}/n\end{array}}\right),}$$ 部分的な回復は、確率で実現可能である^{[ 4 ]}${\displaystyle 1-o(1)}$いつでも${\displaystyle ({\チルダ {p}}-{\チルダ {q}})^{2}>2({\チルダ {p}}+{\チルダ {q}})}$、一方、推定器は確率で部分的な回復に失敗します^{[ 3 ]}${\displaystyle 1-o(1)}$いつでも${\displaystyle ({\チルダ {p}}-{\チルダ {q}})^{2}<2({\チルダ {p}}+{\チルダ {q}})}$。

正確な回復のためには、適切なスケーリングは${\displaystyle P_{ij}={\チルダ {P}}_{ij}\log n/n}$その結果、対数平均次数を持つグラフが得られる。ここでも同様の閾値が存在する。同類植栽分割モデルの場合、${\displaystyle r}$同規模のコミュニティの場合、その閾値は${\displaystyle {\sqrt {\チルダ {p}}}-{\sqrt {\チルダ {q}}}={\sqrt {r}}}$実際、完全な一般確率ブロックモデルについては、正確な回復閾値が知られています。^{[ 5 ]}

原理的には、実行可能な範囲内であれば最尤法を用いて正確な復元問題を解くことができるが、これは最小二分法のような制約付きまたは正則化されたカット問題を解くことになり、通常はNP困難である。したがって、既知の効率的なアルゴリズムでは、最悪の場合の最尤推定値を正しく計算することはできない。

しかし、平均的なケースではさまざまなアルゴリズムが良好なパフォーマンスを発揮し、部分回復と完全回復の両方の設定で、多くのアルゴリズムに対して高い確率のパフォーマンス保証が証明されています。成功したアルゴリズムには、頂点のスペクトルクラスタリング^{[ 9 ] [ 4 ] [ 5 ] [ 10 ]} 、半正定値計画法^{[ 2 ] [ 8 ] 、}信念伝播の形式[ ^{7 ] [ 11 ]}、コミュニティ検出^{[ 12 ]}などがあります。

このモデルにはいくつかのバリエーションが存在する。小さな変更点の一つは、固定された分割ではなく、カテゴリ分布に従ってランダムに頂点をコミュニティに割り当てることである。 ^{[ 5 ]}より重要なバリエーションとしては、次数補正確率ブロックモデル^{[ 13 ]}、階層的確率ブロックモデル^{[ 14 ] 、幾何学的ブロックモデル[ 15 ]}、検閲ブロックモデル、混合メンバーシップブロックモデル^{[ 16 ]などがある。}

確率的ブロックモデルは、二部グラフ上のトピックモデルとして認識されています。^{[ 17 ]}文書と単語のネットワークにおいて、確率的ブロックモデルは、類似の意味を持つ単語のグループであるトピックを識別できます。

符号付きグラフは、好ましい関係と好ましくない関係の両方を許容し、相関クラスタリングなどのさまざまなデータ分析アプリケーションで一般的なモデルとして使用されます。確率的ブロックモデルは、正と負の両方のエッジ重みを割り当てるか、または同等に2つの確率的ブロックモデルの隣接行列の差を使用することで、符号付きグラフに簡単に拡張できます。^{[ 18 ]}

GraphChallenge ^{[ 19 ] は}、ソーシャルメディア、センサーフィード、科学データから得られるグラフや疎なデータを分析するための新しいソリューションを開発するためのコミュニティのアプローチを奨励し、現場で展開されるイベント間の関係を発見できるようにします。ストリーミング確率的ブロック分割は、2017 年以来のチャレンジの 1 つです。^{[ 20 ]}スペクトルクラスタリングは、元のアルゴリズムや改良された^{[ 21 ]} ベースアルゴリズムと比較して優れたパフォーマンスを示し、クラスタの品質は同等でありながら、数桁高速です。^{[ 22 ] [ 23 ]}

• ブロックモデリング
• ガーバン・ニューマンアルゴリズム– コミュニティ検出アルゴリズム 
• Lancichinetti–Fortunato–Radicchiベンチマーク–コミュニティを含むベンチマークネットワークを生成するためのスペースのない短い説明を表示するアルゴリズムページ