モジュラリティ

モジュラリティ（英: Modularity）は、コンピューターネットワークや、ソーシャルネットワークなどのネットワークやグラフの解析に用いられる効果関数。ネットワークから、モジュールやコミュニティへの分割の「質」を定量化するものである。

高いモジュラリティを持つような高レベルな分割は、モジュール内部でのノード間の密なネットワークを持つ反面、異なるモジュール間で疎なネットワークを持つ。

ネットワーク内のコミュニティ構造を探し出すための最適化法の基礎としてよく用いられる。

目的

多くの重要な科学的課題がネットワークを用いて表現され、研究されている。 ネットワークとして扱うことができる現実世界の現象の一例として、生物学的・社会学的パターン、WWW、代謝ネットワーク、食物連鎖、神経ネットワーク、病理ネットワークなどが挙げられる。これらはネットワークを用いることで数学的に表現され、またトポロジカルな研究によって予期せぬ構造の性質が明らかになった。

これらのネットワークのほとんどは明確なコミュニティ構造を持つ。コミュニティ構造はネットワークのダイナミクス（ネットワークの生成過程・伝播など）を理解する上で重要である。例えば、密接に繋がった社会的集団では、ゆるく繋がった集団に比べて、情報やうわさ話が速く伝わるだろう。ネットワークが多くのノードとそれを結ぶリンクで表現されるとすると、コミュニティは「グループ内のノード同士は密接に結びついていて、またグループ外のノードとは疎な関係しか持たない」ようなノード集団として定義される。

コミュニティはノードの次数、クラスタ係数、媒介中心性などのネットワークの平均量とは異なる特性であり 、ネットワーク上のコミュニティを識別することは不可欠である。そのようなコミュニティを判定する指標の一つがモジュラリティである。モジュラリティを最大化することによって、与えられたネットワークからコミュニティを見つけることができる。

定義

モジュラリティは、ネットワークの与えられた分割に対して、「グループ内のノード同士が繋がるリンクの割合」から「リンクがランダムに配置された場合の期待値」を引いた値として定義される。

ノードの数 $N$、リンクの数 $M$ のネットワークを考え、ノードを$\left\{g_{1},g_{2},...,g_{C}\right\}$ の $C$ 個のグループに分ける。ネットワークの隣接行列を$A$と表し、行列成分$A_{rs}$はノードr, s 間に存在するリンクの数とする。

モジュラリティはネットワークのリンクに方向や重みがある場合にも定義できるが、ここでは簡単のため方向・重みの無いネットワークを考える。つまり$A$の各成分はリンクの有無によって1か0の2値のみをとり、対称行列であるとする。隣接行列の成分の和は $\sum _{rs}A_{rs}=2M$ となる。

g_iに属するノードと g_j に属するノードが繋がるリンク数の合計の、全リンク数に占める割合は、以下のように書ける。

$e_{ij}=\sum _{r\in g_{i}}\sum _{s\in g_{j}}{\frac {A_{rs}}{2M}}$

よって、同じグループ g_i に属するノード同士が繋がるリンク数の全リンク数に占める割合は e_ii である。

次に、リンクがランダムに配置された場合における e_ii の期待値を考える。ランダムな配置は、次のように行う。まず、M 本の全リンクを切断することで、片側のみノードに接続した「手」を 2M 本作る。次に、ノードに残された「手」をランダムに2つずつ選択して繋ぎ直す。このように繋げ直すことによって、各ノードの「手」の数を保ったままランダムなネットワークを作ることができる。ここでノード r の「手」の数をノード r の次数 (英: degree) と呼び、$k_{r}=\sum _{s}A_{rs}$ と表す。全ノードの次数の合計は $\sum _{r}k_{r}=\sum _{rs}A_{rs}=2M$ である。

上記のような方法によるランダムな配置において、リンクの一方に g_i 内のノードの「手」が選ばれる確率は、以下のように書ける。

$a_{i}=\sum _{r\in g_{i}}{\frac {k_{r}}{2M}}=\sum _{r\in g_{i}}\sum _{s}{\frac {A_{rs}}{2M}}=\sum _{j}\sum _{r\in g_{i}}\sum _{s\in g_{j}}{\frac {A_{rs}}{2M}}=\sum _{j}e_{ij}$

これは、少なくとも一方が g_i 内のノードに繋がるリンク数の、全リンク数に占める割合の期待値である。リンクの両端が g_i 内のノードである場合の、すなわち e_ii の期待値は a_i の2乗となる。

よって、モジュラリティは以下のように定義される。

$Q=\sum _{i=1}^{C}\left(e_{ii}-a_{i}^{2}\right)$

関連項目

• 複雑ネットワーク