Skip to content
検索結果に戻る

確率的ブロックモデル — ネットワークにおける確率的コミュニティ検出

年
1983
種類
Probabilistic generative graph model

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

確率的ブロックモデル(SBM)は、Holland、Laskey、Leinhardt(1983)によって導入された、ノードを潜在ブロックに割り当て、ブロック間の接続確率をパラメトリックに推定するグラフの確率的生成モデルである。これは、コミュニティ検出、コア・周辺構造の特定、ネットワーク分析における階層構造発見の基礎的なアプローチである。

手法の背後にある直感

人々が同僚、家族、スポーツチームなどのグループにクラスタリングされ、グループ内の接続がグループ間の接続よりも可能性が高いソーシャルネットワークを想像してみよう。確率的ブロックモデルは、この直感を形式化する。すなわち、すべてのノードに隠れたグループラベルが存在し、任意の2つのノード間のエッジの確率は、それらのノードが属するグループのみに依存すると仮定する。モデルの適合とは、観測されたエッジパターンを最もよく説明する隠れたラベルを見つけることを意味する。その結果、グループが密なクリークである必要なしに、ネットワークをブロックに分割する、原則的で統計的に根拠のあるパーティションが得られる。このモデルは、コア・周辺構造や、グループ間接続がグループ内接続を超える非同種パターンさえも収容する。

歴史学

確率的ブロックモデルは、社会ネットワーク分析における以前のブロックモデリング作業の確率的一般化として、Holland、Laskey、Leinhardtが1983年のSocial Networks論文で導入した。20年間は主に理論的ツールであったが、2010年代のスケーラブルな推論アルゴリズム(変分EMおよびMCMC)の開発により実用的な牽引力を得た。次数補正SBMは、次数異質性の問題に対処するためにKarrerとNewman(2011)によって導入された。LeeとWilkinsonによる2019年のApplied Network Scienceのレビューは、植え付けられたパーティションモデル、混合メンバーシップSBM、階層的バリアントをカバーし、拡張ファミリーを統合した。今日、SBMとその派生モデルは、コミュニティ検出およびグラフクラスタリングの参照確率的フレームワークである。

使うべき場面

少なくとも50ノードを持つネットワークで、グループが密なクリークである必要がないという仮定なしに潜在的なグループ構造を発見したい場合に、確率的ブロックモデルを使用する。有向または無向グラフ、重み付きまたは重みなしグラフに適しており、探索的タスクと分類タスクの両方に適している。ノード次数が大きく変動する場合は、DCSBMバリアントが好ましい。グラフが20ノード未満の場合は、コミュニティ構造を確実に推定できず、より単純な記述統計量を使用すべきである。仮定:ブロックメンバーシップは潜在的であり観測されない。ブロック接続行列は、各ブロックペア内で同種であると仮定される。Kは任意に固定するのではなく、BICまたはベイズ因子によって選択されなければならない。

限界と注意点

  • 信頼性の高いブロック推定には少なくとも約50ノードが必要。非常に小さいグラフでは不安定な解が得られる。
  • 大規模グラフでは推論が計算上高コストである。変分EMまたはMCMCが必要であり、収束は保証されない。
  • 基本SBMのブロックペア内の同種性の仮定は、ブロック内の接続率が変動する場合に破綻する。DCSBMはこれを緩和するが、完全に排除するわけではない。
  • BICまたはベイズ因子によるブロック選択は、グラフが弱く分離されたコミュニティを持つ場合、依然として過小または過大セグメンテーションを引き起こす可能性がある。

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • BICまたはベイズ因子によるモデル選択を可能にする、原則的な確率的フレームワークであり、任意のパラメータ選択を回避する。
  • アルゴリズム的手法による密なクリークの仮定を超えて、コミュニティ、コア・周辺、二部グラフ、階層構造など、幅広い構造パターンに対応する。
  • 次数補正バリアントは、ブロック割り当てを歪めることなく、異種次数分布やハブを持つグラフを処理する。
  • 事後メンバーシップ確率を提供し、ハードパーティションではなくソフトまたは不確かなノード割り当てを可能にする。

応用

  • 社会科学および自然科学における引用ネットワークおよび共同研究ネットワークにおける研究コミュニティの検出。
  • タンパク質間相互作用および遺伝子共発現グラフなどの生物学的ネットワークにおける機能モジュールの特定。
  • トランザクションネットワークおよび金融ネットワークにおける顧客セグメントまたは不正リングの発見。
  • 組織間または国家間貿易ネットワークにおけるコア・周辺構造の特徴付け。
  • SBM生成合成グラフを真のデータとして使用した、他のコミュニティ検出アルゴリズムのベンチマークおよび評価。

使い方

使い方

1

分析者は、ブロック数Kの候補範囲を指定し、バリアントを選択する。基本SBMは同種の内ブロック次数分布を仮定する一方、次数補正SBM(DCSBM)はハブや異種次数系列を扱うためにノードレベルの次数パラメータを追加する。バリアントの選択は、観測グラフの次数分布に基づいて行われる。

2

隣接行列が与えられると、モデルは推論アルゴリズムを使用してブロックメンバーシップと接続確率のK×K行列を推定する。小規模から中規模のグラフでは、厳密な最大化が可能である。大規模グラフでは、変分期待値最大化(変分EM)またはマルコフ連鎖モンテカルロ(MCMC)サンプリングが推論を扱いやすくするために使用される。

3

ブロック数Kは事前に知られておらず、データから選択する必要がある。好ましい選択基準は、モデルの複雑さをペナルティ付けし、適合度と簡潔さのバランスを最もよく取るKを選択するベイズ情報量基準(BIC)とベイズ因子である。最小記述長(MDL)原理は、graph-toolの実装の根底にある。

4

最適なKとブロック割り当てが決定されると、ブロック接続行列を検査して構造を特徴付ける。同種ブロックはコミュニティに対応し、非同種ブロックは二部グラフ様パターンに対応し、混合プロファイルはコア・周辺配置に対応する。ノードメンバーシップは、推論アルゴリズムが提供する場合、事後確率とともに報告される。

よくある落とし穴

  • BICまたはベイズ因子ではなく、任意にKを固定すると、信頼性の低いパーティションが得られる。常に原則的なモデル選択基準を使用すること。
  • 異種次数系列(ハブ、べき乗則次数分布)を持つグラフに基本SBMを適用すると、ブロック数推定値が膨張する。代わりにDCSBMを使用すること。
  • 事後確率が拡散している場合にブロックメンバーシップを確実とみなすと、信頼度を過大評価することになる。利用可能な場合は不確実性を報告すること。
  • SBMの出力と真のコミュニティを混同すること。モデルは統計的に妥当な潜在構造を見つけるのであり、必ずしも社会学的に意味のあるグループではない。ドメイン知識と照合して検証すること。
  • 20ノード未満でSBMを実行すると、退化した解が得られる。小規模グラフの場合は、記述的ネットワーク統計量または単純なコミュニティ検出に戻ること。

よくある質問

確率的ブロックモデルは、モジュラリティベースのコミュニティ検出とどう違うのか?

モジュラリティ最大化(例:Louvain、Leiden)は、同種でほぼ均等なサイズのコミュニティを暗黙的に仮定し、小さなコミュニティの検出を妨げる既知の解像度限界を持つ、ヒューリスティックな目的関数を最適化する。SBMは、明示的な仮定を持つ生成確率モデルである。ブロック数は、ヒューリスティックな最適化ではなく、モデル選択(BICまたはベイズ因子)によって選択され、モジュラリティベースの手法が見逃す非同種およびコア・周辺構造を検出できる。

基本SBMの代わりにDCSBMを使用すべきなのはいつか?

ノード次数分布が異種である場合、例えば少数のハブがエッジの大部分を占める場合、または次数系列がべき乗則近似に従う場合に使用する。基本SBMはブロック内のすべてのノードを交換可能とみなすため、ハブが独自の偽のブロックに引き込まれる。DCSBMは次数補正項を追加し、構造的位置と次数を分離することで、そのようなグラフでより解釈可能なブロック割り当てを生成する。

ブロック数Kをどのように選択するか?

Kの値の範囲でモデルを適合させ、BICを最小化するかベイズ因子を最大化する(または記述長を等価的に最小化する)ものを選択する。グラフの視覚的検査や事前期待に基づいてKを選択しないこと。ほとんどの実装(graph-tool、Rのblockmodels)はこの検索を自動化する。感度分析(Kを1だけ変化させたときに定性的なブロック構造が変化するかどうかを確認する)も推奨される。

SBMが信頼できる最小ネットワークサイズは?

レジストリは、信頼性の高い推論のために最低50ノードを指定している。20ノード未満では、モデルは意味のあるコミュニティ構造を特定できず、ノイズに適合する。記述的ネットワーク統計量または単純なコミュニティ検出を使用すること。20から50ノードの間では、結果は探索的とみなされ、注意して解釈すべきである。

関連する手法

参考文献

  1. Holland, P.W., Laskey, K.B. & Leinhardt, S. (1983). Stochastic Blockmodels: First Steps. Social Networks, 5(2), 109-137.

    DOI 文献を開く
    コピーしました。
  2. Lee, C. & Wilkinson, D.J. (2019). A Review of Stochastic Block Models and Extensions for Graph Clustering. Applied Network Science, 4(1), 122.

    DOI 文献を開く
    コピーしました。