確率的ブロックモデル

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

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

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

次に、エッジ セットが次のようにランダムにサンプリングされます。任意の 2 つの頂点とが、確率 でエッジによって接続されます。問題の例: 頂点を持つグラフがあり 、エッジが説明どおりにサンプリングされている場合、グループ を復元します 。 ${\displaystyle u\in C_{i}}$${\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)}$

植え付けられた分割モデルは、確率行列の値が対角線上で定数であり、対角線外でも別の定数である特殊なケースです。したがって、同じコミュニティ内の 2 つの頂点は確率 でエッジを共有し、異なるコミュニティ内の 2 つの頂点は確率 でエッジを共有します。この制限されたモデルは、確率ブロック モデルと呼ばれることがあります。 の場合は同類モデルと呼ばれ、 の場合は非同類モデルと呼ばれます。 ${\displaystyle P}$${\displaystyle p}$${\displaystyle q}$${\displaystyle p}$${\displaystyle q}$${\displaystyle p>q}$${\displaystyle p<q}$

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

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

検出アルゴリズムの目的は、サンプルされたグラフが与えられた場合に、そのグラフに潜在的なコミュニティ構造があるかどうかを判断することです。より正確には、グラフは、既知の事前確率で、既知の確率的ブロックモデルから生成される場合もあれば、類似のエルデシュ・レニモデルから生成される場合もあります。アルゴリズムのタスクは、グラフを生成したこれら2つの基礎モデルのどちらが正しく識別されるかです。^[3]

部分回復では、ランダムな推測よりも有意に真のパーティションと相関するパーティションを見つけるという意味で、コミュニティへの潜在的なパーティションを近似的に決定することが目標です。^[4]

正確な回復では、潜在的なコミュニティへの分割を正確に回復することが目標です。コミュニティのサイズと確率行列は既知である場合も未知である場合もあります^[5 ] 。^[6]

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

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

正確な回復のためには、適切なスケーリングは を取ることであり、その結果、対数平均次数のグラフが得られる。ここでも同様の閾値が存在する。等しいサイズのコミュニティを持つアソートメント・プラント・パーティション・モデルの場合、閾値は である。実際、正確な回復閾値は、完全に一般的な確率的ブロック・モデルで知られている。^[5]${\displaystyle P_{ij}={\tilde {P}}_{ij}\log n/n}$${\displaystyle r}$${\displaystyle {\sqrt {\tilde {p}}}-{\sqrt {\tilde {q}}}={\sqrt {r}}}$

原理的には、最大尤度法を使用して、その実行可能な範囲で正確な回復を解くことができますが、これは、典型的にはNP 完全である最小二分法などの制約付きまたは正規化されたカット問題を解くことに相当します。したがって、最悪の場合の最大尤度推定値を正しく計算する効率的なアルゴリズムは知られていません。

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

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

確率的ブロックモデルは、二部ネットワーク上のトピックモデルとして認識されています。^[17]文書と単語のネットワークでは、確率的ブロックモデルはトピック（同様の意味を持つ単語のグループ）を識別できます。

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

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

• ブロックモデリング
• ガーバン・ニューマンアルゴリズム – コミュニティ検出アルゴリズム
• Lancichinetti–Fortunato–Radicchi ベンチマーク –Pages displaying short descriptions with no spacesコミュニティを持つベンチマーク ネットワークを生成するアルゴリズム