モジュール性（ネットワーク）

モジュール性は、ネットワークまたはグラフの構造の尺度であり、ネットワークをモジュール (グループ、クラスター、またはコミュニティとも呼ばれる) に分割する強度​​を測るものです。モジュール性が高いネットワークでは、モジュール内のノード間の接続は密ですが、異なるモジュール内のノード間の接続はまばらです。モジュール性は、ネットワーク内のコミュニティ構造を検出するための最適化手法でよく使用されます。動物の脳を含む生物学的ネットワークは、高度なモジュール性を示します。ただし、モジュール性の最大化は統計的に一貫しておらず、独自のヌル モデル、つまり完全にランダムなグラフでコミュニティを見つけるため、経験的ネットワークで統計的に有意なコミュニティ構造を見つけるために使用することはできません。さらに、モジュール性には解像度の制限があるため、小さなコミュニティを検出できないことが示されています。

科学的に重要な問題の多くは、ネットワークを使用して表現し、経験的に研究することができます。たとえば、生物学的および社会的パターン、ワールド ワイド ウェブ、代謝ネットワーク、食物網、ニューラル ネットワーク、病理学的ネットワークは、数学的に表現し、位相的に研究して、いくつかの予期しない構造的特徴を明らかにすることができる現実世界の問題です。^[1]これらのネットワークのほとんどは、ネットワークのダイナミクスに関する理解を構築する上で重要な特定のコミュニティ構造を持っています。たとえば、密接に接続された社会的コミュニティは、緩く接続されたコミュニティよりも、それらの間での情報や噂の伝達速度が速いことを意味します。したがって、ネットワークが、ノード間の一定の相互作用を示すリンクによって接続された多数の個別のノードによって表現される場合、コミュニティは、ネットワークの残りの部分とまばらに接続されている、密に相互接続されたノードのグループとして定義されます。したがって、コミュニティは、ノードの次数、クラスタリング係数、媒介性、中心性など、^[2]など、平均的なネットワークとはまったく異なる特性を持つ可能性があるため、ネットワーク内のコミュニティを識別することが不可欠である可能性があります。モジュール性はそのような尺度の 1 つであり、最大化されると、特定のネットワーク内にコミュニティが出現します。

モジュール性は、与えられたグループ内に含まれるエッジの割合から、エッジがランダムに分布した場合に期待される割合を引いたものです。重み付けされていない無向グラフのモジュール性の値は、 の範囲にあります。^[3] グループ内のエッジの数が偶然に基づいて期待される数を超える場合、モジュール性は正になります。ネットワークの頂点をいくつかのモジュールに分割した場合、モジュール性は、モジュールに関係なくすべてのノード間のリンクのランダムな分布と比較した、モジュール内のエッジの集中を反映します。 ${\displaystyle [-1/2,1]}$

モジュール性を計算するにはさまざまな方法があります。^[1]この概念の最も一般的なバージョンでは、各頂点の次数を保存するようにエッジのランダム化が行われます。ノードとリンク（エッジ）を持つグラフを考えます。このグラフは、メンバーシップ変数 を使用して 2 つのコミュニティに分割できます。ノードがコミュニティ 1 に属する場合は 、ノードがコミュニティ 2 に属する場合は です。ネットワークの隣接行列を で表すとします。ここで、 はノード間にエッジ（相互作用）がないことを意味し、は2 つのノード間にエッジがあることを意味します。また、簡単にするために、無向ネットワークを検討します。したがって です。（2 つのノード間には複数のエッジが存在する可能性があることに注意することが重要ですが、ここでは最も単純なケースを評価します）。 ${\displaystyle n}$ ${\displaystyle m}$${\displaystyle s}$${\displaystyle v}$${\displaystyle s_{v}=1}$${\displaystyle v}$${\displaystyle s_{v}=-1}$${\displaystyle A}$${\displaystyle A_{vw}=0}$${\displaystyle v}$${\displaystyle w}$${\displaystyle A_{vw}=1}$${\displaystyle A_{vw}=A_{wv}}$

モジュール性は、指定されたネットワークと同じノード次数分布を持つランダム グラフのグループ 1 または 2 に含まれるエッジの割合から、グループ 1 と 2 内のエッジの予想数を引いたものとして定義されます。 ${\displaystyle Q}$

エッジの期待数は、構成モデルの概念を使用して計算されるものとする。^[4]構成モデルは、特定のネットワークをランダムに実現したものである。各ノードがノード次数を持つネットワークが与えられると、構成モデルは各エッジを半分に切り、スタブと呼ばれる各半分のエッジをネットワーク内の他のスタブとランダムに再配線する。このとき、自己ループ（スタブが同じノードから別のスタブに再配線されるときに発生）や、同じ2つのノード間の複数エッジも許可される。したがって、グラフのノード次数分布はそのままであっても、構成モデルは完全にランダムなネットワークをもたらす。 ${\displaystyle n}$${\displaystyle v}$${\displaystyle k_{v}}$

ここで、上で説明したようにランダムに再配線されたネットワークから、それぞれノード次数とを持つ2つのノードとを考えます。これらのノード間の完全なエッジの予想数を計算します。 ${\displaystyle v}$${\displaystyle w}$${\displaystyle k_{v}}$${\displaystyle k_{w}}$

ノード の各スタブについて考え、それらに関連付けられたインジケータ変数 を作成し、この特定のランダムグラフで - 番目のスタブがノード のスタブの1 つに接続する場合はとなる。接続しない場合は となる。ノード の - 番目のスタブは、残りのスタブのいずれにも等確率で接続できるため(は元のグラフのエッジの数)、ノード に関連付けられたスタブに接続できるスタブがあるため、明らかに ${\displaystyle k_{v}}$${\displaystyle v}$${\displaystyle I_{i}^{(v,w)}}$${\displaystyle i=1,\ldots ,k_{v}}$${\displaystyle I_{i}^{(v,w)}=1}$${\displaystyle i}$${\displaystyle k_{w}}$${\displaystyle w}$${\displaystyle I_{i}^{(v,w)}=0}$${\displaystyle i}$${\displaystyle v}$${\displaystyle 2m-1}$${\displaystyle m}$${\displaystyle k_{w}}$${\displaystyle w}$

${\displaystyle p(I_{i}^{(v,w)}=1)=E[I_{i}^{(v,w)}]={\frac {k_{w}}{2m-1}}}$

との間の完全な辺の総数はちょうど なので、この量の期待値は ${\displaystyle J_{vw}}$${\displaystyle v}$${\displaystyle w}$${\displaystyle J_{vw}=\sum _{i=1}^{k_{v}}I_{i}^{(v,w)}}$

${\displaystyle E[J_{vw}]=E\left[\sum _{i=1}^{k_{v}}I_{i}^{(v,w)}\right]=\sum _{i=1}^{k_{v}}E[I_{i}^{(v,w)}]=\sum _{i=1}^{k_{v}}{\frac {k_{w}}{2m-1}}={\frac {k_{v}k_{w}}{2m-1}}}$

そして多くのテキストでは、多数のエッジを持つランダムネットワークに対して、次のような近似を行っています。 が大きい場合、上記の分母での の減算は省略し、 2つのノード間のエッジの期待数の近似式を単に使用します。さらに、大規模なランダムネットワークでは、自己ループとマルチエッジの数は無視できるほど小さくなります。^[5]自己ループとマルチエッジを無視すると、任意の2つのノード間には最大で1つのエッジがあると想定できます。その場合、はバイナリ指標変数になるため、その期待値は に等しい確率でもあり、これはノードとの間にエッジが存在する確率を と近似できることを意味します。 ${\displaystyle m}$${\displaystyle 1}$${\displaystyle {\frac {k_{v}k_{w}}{2m}}}$${\displaystyle J_{vw}}$${\displaystyle 1}$${\displaystyle v}$${\displaystyle w}$${\displaystyle {\frac {k_{v}k_{w}}{2m}}}$

したがって、ノードと間の実際のエッジ数とそれらの間の期待されるエッジ数の差は ${\displaystyle v}$${\displaystyle w}$

${\displaystyle A_{vw}-{\frac {k_{v}k_{w}}{2m}}}$

すべてのノードペアを合計すると、モジュール性の方程式が得られます。[ ^1]${\displaystyle Q}$

式3は2つのコミュニティに分割する場合にのみ有効であることに注意することが重要です。階層的分割（つまり、2つのコミュニティに分割し、次に2つのサブコミュニティをさらに2つの小さなサブコミュニティに分割してQを最大化する）は、ネットワーク内の複数のコミュニティを識別するための可能なアプローチです。さらに、（3）はネットワークをc個のコミュニティに分割するために一般化できます。^[6]

ここで、e _{ij は}、一方の端点がコミュニティiにあり、もう一方の端点がコミュニティjにある辺の割合です。

${\displaystyle e_{ij}=\sum _{vw}{\frac {A_{vw}}{2m}}1_{v\in c_{i}}1_{w\in c_{j}}}$

a _{i は}コミュニティiの頂点に接続されている辺の端の割合です。

${\displaystyle a_{i}={\frac {k_{i}}{2m}}=\sum _{j}e_{ij}}$

10 個のノードと 12 個のエッジを持つ無向ネットワークと次の隣接行列を考えます。

グラフ内のコミュニティは、図 1 の赤、緑、青のノード クラスターで表されます。最適なコミュニティ パーティションは、図 2 に示されています。

モジュラリティの別の定式化は、特にスペクトル最適化アルゴリズムで有用であり、次のようになる。^[1]頂点がグループに属する場合は を、そうでない場合は と 定義する。すると ${\displaystyle S_{vr}}$${\displaystyle 1}$${\displaystyle v}$${\displaystyle r}$${\displaystyle 0}$

${\displaystyle \delta (c_{v},c_{w})=\sum _{r}S_{vr}S_{wr}}$

そしてそれゆえ

${\displaystyle Q={\frac {1}{4m}}\sum _{vw}\sum _{r}\left[A_{vw}-{\frac {k_{v}k_{w}}{2m}}\right]S_{vr}S_{wr}={\frac {1}{4m}}\mathrm {Tr} (\mathbf {S} ^{\mathrm {T} }\mathbf {BS} ),}$

ここで、は要素を持つ（非正方）行列であり、は要素を持ついわゆるモジュラリティ行列である。 ${\displaystyle S}$${\displaystyle S_{v}}$${\displaystyle B}$

${\displaystyle B_{vw}=A_{vw}-{\frac {k_{v}k_{w}}{2m}}.}$

モジュラリティ行列のすべての行と列の合計はゼロになります。つまり、分割されていないネットワークのモジュラリティも常に になります。 ${\displaystyle 0}$

ネットワークが2つのコミュニティに分かれている場合は、代わりにノードが属する コミュニティを示すように定義することもできます。${\displaystyle s_{v}=\pm 1}$${\displaystyle v}$

${\displaystyle Q={1 \over 4m}\sum _{vw}B_{vw}s_{v}s_{w}={1 \over 4m}\mathbf {s} ^{\mathrm {T} }\mathbf {Bs} ,}$

ここで は要素を持つ列ベクトルである。^[1]${\displaystyle s}$${\displaystyle s_{v}}$

この関数は、イジングスピングラスのハミルトニアンと同じ形式を持ち、この関係は、例えばシミュレーテッドアニーリングを使用してモジュール性を最大化する単純なコンピュータアルゴリズムを作成するために利用されてきた。任意の数のコミュニティのモジュール性の一般的な形式はポッツスピングラスに相当し、同様のアルゴリズムをこの場合にも開発することができる。^[7]

モジュール性最大化の方法はヌルモデルからの偏差を計算することによって動機付けられていますが、この偏差は統計的に一貫した方法で計算されていません。^[8]このため、この方法では、定義上統計的に有意ではないヌルモデル ^[9] （構成モデル）で高スコアのコミュニティが見つかることで有名です。このため、この方法は、経験的ネットワークで統計的に有意なコミュニティ構造を確実に得るために使用することはできません。

モジュラリティは、クラスター内のエッジの数を、ネットワークが同じ数のノードを持ち、各ノードがその次数を維持し、エッジがランダムに接続されているランダム ネットワークである場合にクラスター内で見つかるエッジの予想数と比較します。このランダム ヌル モデルは、各ノードがネットワークの他の任意のノードに接続できることを暗黙的に想定しています。ただし、ネットワークが非常に大きい場合、この想定は不合理です。ノードのホライズンにはネットワークの小さな部分しか含まれず、その大部分は無視されるためです。さらに、これは、ネットワークのサイズが大きくなると、2 つのノード グループ間のエッジの予想数が減少することを意味します。したがって、ネットワークが十分に大きい場合、モジュラリティのヌル モデル内の 2 つのノード グループ間のエッジの予想数は 1 未満になる可能性があります。これが発生すると、2 つのクラスター間の単一のエッジは、2 つのクラスター間の強い相関関係の兆候としてモジュラリティによって解釈され、モジュラリティを最適化すると、クラスターの特徴とは無関係に、2 つのクラスターがマージされます。そのため、ネットワークが十分に大きければ、内部エッジの密度が最も高く、最も識別しやすいコミュニティを表す弱く相互接続された完全グラフであっても、モジュール最適化によってマージされるだろう。^[10] このため、大規模ネットワークでモジュールを最適化すると、たとえ小さなコミュニティが明確に定義されている場合でも、そのコミュニティを解決できない。このバイアスは、グローバルヌルモデルに依存するモジュール最適化などの方法では避けられない。^[11]

モジュール性コンテキスト内で解像度の限界を解決しようとする主なアプローチは 2 つあります。1 つは、すべてのノードに自己ループの形で抵抗rを追加し、ノードがコミュニティを形成することを嫌う度合いを増加 ( r>0 ) または減少 ( r<0 ) させる方法です。 ^[12]または、モジュール性の定義でヌルケース項の前にパラメーターγ>0を追加します。これは、コミュニティの内部リンクとヌルモデル間の相対的な重要性を制御します。 ^[7]これらのパラメーターの値を適切な範囲でモジュール性を最適化すると、すべてのノードが同じコミュニティに属するマクロスケールから、すべてのノードが独自のコミュニティを形成するマイクロスケールまで、ネットワークのメソスケール全体を回復できます。そのため、マルチ解像度法と呼ばれます。ただし、コミュニティのサイズが非常に不均一な場合、これらの方法には限界があることが示されています。^[13]

優れたモジュール性を備えたグラフのクラスタリングを計算できるソフトウェア ツールがいくつかあります。

マルチレベルルーヴァン法のオリジナルの実装。^[14]

さらに接続されていないコミュニティを回避するライデンアルゴリズム。[ ^15]

並列ミームアルゴリズムであるウィーングラフクラスタリング（VieClus）アルゴリズム。^[16]

• 複雑なネットワーク
• コミュニティ構造
• ヌルモデル
• 浸透理論