コミュニティ構造

複雑ネットワークの研究では、ネットワークのノードが（潜在的に重複する）ノード セットに簡単にグループ化でき、各ノード セットが内部で密に接続されている場合、ネットワークはコミュニティ構造を持っていると言われます。重複しないコミュニティの検出という特定のケースでは、これは、ネットワークが、内部で密な接続とグループ間の接続がより疎なノード グループに自然に分割されることを意味します。ただし、重複するコミュニティも許可されます。より一般的な定義は、ノードのペアが同じコミュニティのメンバーである場合に接続されている可能性が高く、コミュニティを共有していない場合に接続されている可能性は低いという原則に基づいています。関連しているが異なる問題にコミュニティ検索があり、その目的は特定の頂点が属するコミュニティを見つけることです。

コンピュータや情報ネットワーク、ソーシャルネットワーク、生物学的ネットワークなどのネットワークの研究では、スモールワールド特性、重裾の 次数分布、クラスタリングなど、さまざまな特性が共通して発生することがわかっています。もう1つの一般的な特性はコミュニティ構造です。^{[1] [2] [3] [4] [5]} ネットワークの文脈では、コミュニティ構造とは、右の例の図に示すように、ネットワーク内のノードのグループがネットワークの他の部分よりも内部でより密に接続されていることを指します。この接続の不均一性は、ネットワーク内に特定の自然な分割があることを示唆しています。

コミュニティは、多くの場合、頂点セットの分割という観点から定義されます。つまり、図のように、各ノードは 1 つのコミュニティにのみ配置されます。これは便利な簡略化であり、ほとんどのコミュニティ検出方法では、このタイプのコミュニティ構造が検出されます。ただし、場合によっては、頂点が複数のコミュニティに存在する方が適切な表現になることがあります。これは、各頂点が人物を表し、コミュニティがさまざまな友人グループを表すソーシャル ネットワークで発生する可能性があります。1 つのコミュニティは家族用、別のコミュニティは同僚用、1 つのコミュニティは同じスポーツ クラブの友人用などです。以下で説明するコミュニティ検出でのクリークの使用は、このような重複するコミュニティ構造を検出する方法の 1 つの例にすぎません。

一部のネットワークには、意味のあるコミュニティ構造がない場合があります。たとえば、ランダム グラフやBarabási-Albert モデルなどの多くの基本的なネットワーク モデルでは、コミュニティ構造は表示されません。

コミュニティ構造は現実のネットワークではごく一般的です。ソーシャルネットワークには、共通の場所、興味、職業などに基づいたコミュニティグループ（この用語の由来）が含まれます。^{[5] [6]}

ネットワークに根底にあるコミュニティ構造が存在する場合、それを見つけることはいくつかの理由で重要です。コミュニティはネットワーク内のメタノードのように機能し、ネットワークの研究を容易にするため、大規模なネットワークマップを作成することができます。^[7]

個々のコミュニティは、ネットワークによって表されるシステムの機能にも光を当てます。なぜなら、コミュニティはシステムの機能単位に対応することが多いからです。代謝ネットワークでは、そのような機能グループはサイクルや経路に対応しますが、タンパク質相互作用ネットワークでは、コミュニティは生物細胞内の同様の機能を持つタンパク質に対応します。同様に、引用ネットワークは研究トピックごとにコミュニティを形成します。^[1]ネットワーク内のこれらのサブ構造を識別できれば、ネットワーク機能とトポロジが互いにどのように影響し合うかについての洞察が得られます。このような洞察は、スペクトルクラスタリングなどのグラフ上のいくつかのアルゴリズムを改善するのに役立ちます。^[8]

重要なのは、コミュニティはネットワークの平均的な特性とは非常に異なる特性を持つことが多いということです。したがって、平均的な特性だけに集中すると、ネットワーク内の多くの重要で興味深い特徴を見逃してしまうことがよくあります。たとえば、特定のソーシャルネットワークでは、社交的なグループと控えめなグループが同時に存在する可能性があります。^[7]

コミュニティの存在は、一般的に、ネットワーク上で起こる噂の拡散や伝染病の拡散など、さまざまなプロセスにも影響を及ぼします。したがって、このようなプロセスを適切に理解するには、コミュニティを検出し、さまざまな設定でコミュニティが拡散プロセスにどのように影響するかを研究することが重要です。

最後に、コミュニティ検出がネットワーク科学で発見した重要な応用は、ネットワーク内の欠落リンクの予測と偽リンクの識別です。測定プロセス中に、いくつかのリンクがさまざまな理由で観察されない場合があります。同様に、測定エラーのために、いくつかのリンクがデータに誤って入力される可能性があります。これらの両方のケースは、コミュニティ検出アルゴリズムによって適切に処理されます。これは、特定のノードペア間のエッジの存在確率を割り当てることができるためです。^[9]

任意のネットワーク内でコミュニティを見つけることは、計算上困難な作業となる可能性があります。ネットワーク内のコミュニティの数は、存在する場合でも通常は不明であり、コミュニティのサイズや密度は不均一であることがよくあります。しかし、これらの困難にもかかわらず、コミュニティを見つけるためのいくつかの方法が開発され、さまざまなレベルの成功を収めて使用されています。^[4]

ネットワークを部分に分割する最も古いアルゴリズムの 1 つは、最小カット法 (および比率カットや正規化カットなどのバリエーション) です。この方法は、たとえば、プロセッサ ノード間の通信を最小限に抑えるために、 並列コンピューティングの負荷分散に使用されます。

最小カット法では、ネットワークは、通常ほぼ同じサイズの、あらかじめ決められた数の部分に分割され、グループ間のエッジの数が最小になるように選択されます。この方法は、本来意図されていた多くのアプリケーションでうまく機能しますが、一般的なネットワークでコミュニティ構造を見つけるには理想的とは言えません。なぜなら、コミュニティが構造に暗黙的に含まれているかどうかに関係なくコミュニティを見つけ、その数は固定されているからです。^[10]

ネットワーク内のコミュニティ構造を見つける別の方法は、階層的クラスタリングです。この方法では、ノードペア間の何らかの（通常は位相的な）類似性を定量化する類似性尺度を定義します。一般的に使用される尺度には、コサイン類似度、ジャカード指数、隣接行列の行間のハミング距離などがあります。次に、この尺度に従って類似ノードをコミュニティにグループ化します。グループ化を実行するための一般的なスキームはいくつかありますが、最も単純な 2 つは、異なるグループのすべてのノードペアの類似性が指定されたしきい値よりも低い場合にのみ、2 つのグループが別のコミュニティと見なされる単一リンククラスタリングと、すべてのグループ内のすべてのノードの類似性がしきい値を超える完全リンククラスタリングです。重要なステップは、ほぼ最適なコミュニティ構造を示す凝集クラスタリングを停止するためのしきい値をどのように決定するかです。一般的な戦略は、クラスタリングの特定のステップでピークとなる、ネットワークのグローバルプロパティを監視する 1 つまたは複数のメトリックを構築することです。この方向への興味深いアプローチは、凸和を介して組み合わせたさまざまな類似度または非類似度の尺度の使用です。^[11]もう1つの近似は、クラスター間の密度に対するクラスター内のエッジの密度を監視する量の計算です。たとえば、パーティション密度は、類似度メトリックがエッジ間で定義されている場合に提案されており（これにより、重複するコミュニティの定義が可能になります）、^[12]類似性がノード間で定義されている場合に拡張され、ギルド（つまり、同じ近隣に関して同様の数のリンクを共有するが、必ずしも互いに接続されているわけではないノードのグループ）などのコミュニティの代替定義を検討できます。^[13]これらの方法は、たとえば異なるタイプのリンクを持つノードを持つネットワークを処理する場合など、多次元ネットワークを考慮するように拡張できます。^[13]

コミュニティを見つけるためによく使用される別のアルゴリズムは、ガーバン・ニューマンアルゴリズムです。^[1] このアルゴリズムは、ネットワーク内のコミュニティ間にあるエッジを識別し、それらを削除して、コミュニティ自体だけを残します。識別は、グラフ理論の尺度である媒介中心性を使用して実行されます。媒介中心性は、各エッジに番号を割り当てます。エッジが多数のノードのペアの「間」にある場合は、この番号が大きくなります。

ガーバン・ニューマンアルゴリズムは妥当な品質の結果を返し、多くの標準ソフトウェアパッケージに実装されているため人気があります。しかし、実行速度も遅く、n頂点とm辺のネットワークではO( m2n )^の時間がかかるため、数千ノード以上のネットワークでは実用的ではありません。^[14]

既知の欠点にもかかわらず、コミュニティ検出に最も広く使用されている方法の 1 つはモジュール性最大化です。^[14] モジュール性は、ネットワークをコミュニティに分割する際の品質を測定する利点関数です。モジュール性最大化法では、ネットワークの可能な分割を検索して、特にモジュール性が高い 1 つ以上の分割を検索することにより、コミュニティを検出します。可能な分割をすべて網羅的に検索することは通常困難であるため、実用的なアルゴリズムは、貪欲アルゴリズム、シミュレーテッド アニーリング、スペクトル最適化などの近似最適化手法に基づいており、さまざまなアプローチで速度と精度のバランスが異なります。^{[15] [16]} 一般的なモジュール性最大化アプローチは、現在のコミュニティの状態への摂動を考慮してグローバル モジュール性を改善できなくなるまで、ローカル コミュニティを反復的に最適化するLouvain 法です。^{[17] [18]}

モジュール性最適化の有用性は疑問視されており、ネットワークのサイズ（解像度限界^[19]）に応じて、モジュール性最適化では、あるスケールよりも小さいクラスターを検出できないことが多いことが示されている。一方、モジュール性値のランドスケープは、絶対最大値に近い高いモジュール性を持つパーティションの巨大な退化によって特徴付けられ、それらは互いに大きく異なる可能性がある。^[20]

統計的推論に基づく方法は、コミュニティ構造をエンコードするネットワークデータに生成モデルを当てはめようとします。他の方法と比較したこのアプローチの全体的な利点は、より原理的な性質と、統計的有意性の問題に本質的に対処する能力です。文献に記載されているほとんどの方法は、確率的ブロックモデル^[21]と、混合メンバーシップ^{[22] [23]} 次数補正^[24]および階層構造[ ^25] などのバリエーションに基づいています。モデル選択は、最小記述長^{[26] [27]} (または同等のベイズモデル選択^[28] ) や尤度比検定[29 ^]などの原理的なアプローチを使用して実行できます。現在、確率的ブロックモデルの効率的な推論を実行するためのアルゴリズムが多数存在し、その中には信念伝播^{[30] [31]} や凝集型モンテカルロ^[32]などがあります。

目的関数を与えられたネットワークをクラスタリングしようとするアプローチとは対照的に、このクラスの方法は生成モデルに基づいており、ネットワークの大規模な構造を記述するだけでなく、データを一般化し、ネットワーク内の欠落または偽のリンクの発生を予測するためにも使用できます。^{[33] [34]}

クリークは、すべてのノードがクリーク内の他のすべてのノードに接続されているサブグラフです。ノードはこれ以上密に接続できないため、グラフ内のクリークの検出と、これらがどのように重複しているかの分析に基づいて、ネットワーク内のコミュニティ検出に多くのアプローチがあるのは当然のことです。ノードは複数のクリークのメンバーになることができるため、これらの方法ではノードは複数のコミュニティのメンバーになることができ、「重複するコミュニティ構造」が生まれます。

1つのアプローチは、「最大クリーク」を見つけることです。つまり、他のクリークのサブグラフではないクリークを見つけることです。これらを見つけるための古典的なアルゴリズムは、ブロン・ケルボッシュアルゴリズムです。これらの重なりは、いくつかの方法でコミュニティを定義するために使用できます。最も単純な方法は、最小サイズ（ノード数）よりも大きい最大クリークのみを考慮することです。これらのクリークの結合によりサブグラフが定義され、そのコンポーネント（切断された部分）がコミュニティを定義します。^[35]このようなアプローチは、UCInetなどの ソーシャルネットワーク分析ソフトウェアでよく実装されています。

代わりのアプローチは、固定サイズ のクリークを使用することです。これらの重なりを使用して、一種の -正規ハイパーグラフ、または「クリーク グラフ」として知られる線グラフの一般化( の場合)である構造を定義できます。 ^[36] クリーク グラフには、元のグラフのクリークを表す頂点があり、クリーク グラフのエッジは元のグラフのクリークの重なりを記録します。以前のコミュニティ検出方法 (各ノードをコミュニティに割り当てる) のいずれかをクリーク グラフに適用すると、各クリークがコミュニティに割り当てられます。次に、これを使用して、クリーク内のノードのコミュニティ メンバーシップを決定できます。また、ノードは複数のクリークに存在する可能性があるため、複数のコミュニティのメンバーになることができます。たとえば、 クリーク パーコレーション法^{[37]では、コミュニティを}-クリークのパーコレーション クラスターとして定義します。これを行うには、ネットワーク内のすべての -クリーク、つまり -ノードのすべての完全なサブグラフを検索します。次に、2 つの- クリークがノードを共有する場合、それらの- クリークは隣接していると定義されます。つまり、これはクリーク グラフのエッジを定義するために使用されます。次に、一連の- クリーク隣接関係を通じて任意の - クリークから任意の - クリークに到達できる - クリークの最大の和集合としてコミュニティが定義されます。つまり、コミュニティはクリーク グラフ内の接続されたコンポーネントにすぎません。ノードは複数の異なる- クリーク パーコレーション クラスターに同時に 属することができるため、コミュニティは互いに重なり合うことができます。${\displaystyle k}$${\displaystyle k}$${\displaystyle k=2}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k-1}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$

ネットワークは、表現学習法によって潜在空間上に表現または投影され、システムを効率的に表現することができます。そして、さまざまなクラスタリング手法を使用してコミュニティ構造を検出できます。ユークリッド空間の場合、埋め込みベースのシルエットコミュニティ検出^[38]などの手法を利用できます。超幾何潜在空間の場合、臨界ギャップ法または修正密度ベース、階層ベース、またはパーティションベースのクラスタリング手法を利用できます。^[39]

コミュニティ構造の検出にどのアルゴリズムが優れているかを判断するアルゴリズムの評価は、まだ未解決の問題です。これは、既知の構造を持つネットワークの分析に基づく必要があります。典型的な例は「4 グループ」テストです。このテストでは、ネットワークを 4 つの均等なサイズのグループ (通常は各 32 ノード) に分割し、グループ内およびグループ間の接続の確率を変化させて、検出アルゴリズムにとってより困難な構造を作成します。このようなベンチマーク グラフは、CondonとKarp のプランテッド l パーティション モデル^[40]の特殊なケース、またはより一般的には「確率的ブロック モデル」の特殊なケースです。これは、コミュニティ構造を含むランダム ネットワーク モデルの一般的なクラスです。LFRベンチマーク^{[41] [42]}など、さまざまなグループ サイズと非自明な次数分布を可能にする、より柔軟なベンチマークが提案されています 。これは、ノード次数とコミュニティ サイズの不均一な分布を含む 4 グループ ベンチマークの拡張であり、コミュニティ検出方法のより厳しいテストになっています。^{[43] [44]}

一般的に使用されるコンピュータ生成ベンチマークは、明確に定義されたコミュニティのネットワークから始まります。その後、この構造はリンクの再配線や削除によって劣化し、アルゴリズムが元のパーティションを検出することがますます困難になります。最終的に、ネットワークは本質的にランダムなポイントに到達します。この種のベンチマークは「オープン」と呼ばれることがあります。これらのベンチマークのパフォーマンスは、正規化された相互情報量や情報の変化などの尺度によって評価されます。アルゴリズム^[42]によって得られたソリューションを元のコミュニティ構造と比較し、両方のパーティションの類似性を評価します。

近年、さまざまなグループによって、コミュニティ検出問題に相転移が存在することを示すかなり意外な結果が得られました。これは、コミュニティ内およびコミュニティ間の接続の密度がますます均等になるか、または両方が小さくなると（つまり、コミュニティ構造が弱くなりすぎるか、ネットワークが疎になりすぎると）、突然コミュニティが検出できなくなることを示しています。ある意味では、エッジの有無がエンドポイントのコミュニティメンバーシップと相関しているため、コミュニティ自体はまだ存在します。しかし、偶然よりも優れたノードのラベル付けや、コミュニティ構造のないエルデシュ-レニモデルなどのヌルモデルによって生成されたグラフとの区別が情報理論的に不可能になります。この遷移は、コミュニティを検出するために使用されているアルゴリズムの種類とは無関係であり、最適なベイズ推論を使用しても（つまり、計算リソースに関係なく）、ネットワーク内のコミュニティを検出する能力に根本的な限界があることを意味しています。^{[45] [46] [47]}

合計ノード数、グループサイズが等しい確率的ブロックモデルを考え、 をそれぞれグループ内およびグループ間の接続確率とします。 の場合、グループ内のリンク密度がグループ間のリンク密度よりも高くなるため、ネットワークはコミュニティ構造を持ちます。 疎なケースでは、は平均次数が一定になるようにスケールします。 ${\displaystyle n}$${\displaystyle q=2}$${\displaystyle p_{\text{in}}}$${\displaystyle p_{\text{out}}}$${\displaystyle p_{\text{in}}>p_{\text{out}}}$${\displaystyle p_{\text{in}}}$${\displaystyle p_{\text{out}}}$${\displaystyle O(1/n)}$

${\displaystyle p_{\text{in}}=c_{\text{in}}/n}$そして${\displaystyle p_{\text{out}}=c_{\text{out}}/n}$

次のような場合にはコミュニティを検出することは不可能となる: ^[46]

${\displaystyle c_{\text{in}}-c_{\text{out}}={\sqrt {2(c_{\text{in}}+c_{\text{out}})}}}$

• 複雑なネットワーク
• 階層
• ネットワーク理論
• 浸透理論

• グラフによるコミュニティ検出 – 入門
• グラフ内のコミュニティ検出アルゴリズムの実装はありますか? – Stack Overflow
• igraph のコミュニティ検出アルゴリズムの違いは何ですか? – Stack Overflow