モジュラリティのソースを表示

{{for|数学|モジュラー形式|{{ill2|モジュラー束|en|Modular lattice}}}}
'''モジュラリティ'''（{{lang-en-short|Modularity}}）は、コンピューターネットワークや、ソーシャルネットワークなどの[[複雑ネットワーク|ネットワーク]]やグラフの解析に用いられる効果関数。ネットワークから、モジュールやコミュニティへの分割の「質」を定量化するものである。

高いモジュラリティを持つような高レベルな分割は、モジュール内部での[[頂点 (グラフ理論)|ノード]]間の密なネットワークを持つ反面、異なるモジュール間で疎なネットワークを持つ。

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

==目的==
多くの重要な科学的課題がネットワークを用いて表現され、研究されている。
ネットワークとして扱うことができる現実世界の現象の一例として、生物学的・社会学的パターン、[[World Wide Web|WWW]]、代謝ネットワーク、[[食物連鎖]]、神経ネットワーク、病理ネットワークなどが挙げられる。これらはネットワークを用いることで数学的に表現され、またトポロジカルな研究によって予期せぬ構造の性質が明らかになった<ref name="npnas">{{cite journal
 | author = Newman, M. E. J.
 | year = 2006
 | title = Modularity and community structure in networks
 | journal = PROCEEDINGS- NATIONAL ACADEMY OF SCIENCES USA
 | volume = 103
 | issue = 23
 | pages = 8577?8696
 | doi = 10.1073/pnas.0601602103
 | pmid=16723398
 | pmc=1482622
 }}</ref>。

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

コミュニティはノードの次数、クラスタ係数、媒介中心性などのネットワークの平均量とは異なる特性であり<ref name="mathnet">{{cite journal
 | author = Newman, M. E. J.
 | year = 2007
 | title = Mathematics of networks
 | journal = The New Palgrave Encyclopedia of Economics
 | edition = 2
 | editors = Palgrave Macmillan, Basingstoke
 }}</ref>
、ネットワーク上のコミュニティを識別することは不可欠である。そのようなコミュニティを判定する指標の一つがモジュラリティである。モジュラリティを最大化することによって、与えられたネットワークからコミュニティを見つけることができる。

==定義==
モジュラリティは、ネットワークの与えられた分割に対して、「グループ内のノード同士が繋がるリンクの割合」から「リンクがランダムに配置された場合の期待値」を引いた値として定義される<ref>{{cite journal
| author = Newman, M. E. J.
| year = 2006
| title = Fast algorithm for detecting community structure in networks
| journal = Phys. Rev. E
| volume = 70
| issue = 6
| pages = 066133
| doi = 10.1103/PhysRevE.69.066133
}}</ref>。

ノードの数 <math>N</math>、リンクの数 <math>M</math> のネットワークを考え、ノードを<math>\left\{ g_1, g_2, ..., g_C \right\}</math> の <math>C</math> 個のグループに分ける。ネットワークの[[隣接行列]]を<math>A</math>と表し、行列成分<math>A_{rs}</math>はノード''r'', ''s'' 間に存在するリンクの数とする。

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

''g''<sub>''i''</sub>に属するノードと ''g''<sub>''j''</sub> に属するノードが繋がるリンク数の合計の、全リンク数に占める割合は、以下のように書ける。
:<math>
e_{ij}= \sum_{r \in g_i} \sum_{s \in g_j} \frac{A_{rs}}{2M}
</math>
よって、同じグループ ''g''<sub>''i''</sub> に属するノード同士が繋がるリンク数の全リンク数に占める割合は ''e''<sub>''ii''</sub> である。

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

上記のような方法によるランダムな配置において、リンクの一方に ''g''<sub>''i''</sub> 内のノードの「手」が選ばれる確率は、以下のように書ける。
:<math>
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}
</math>
これは、少なくとも一方が ''g''<sub>''i''</sub> 内のノードに繋がるリンク数の、全リンク数に占める割合の期待値である。リンクの両端が ''g''<sub>''i''</sub> 内のノードである場合の、すなわち ''e''<sub>''ii''</sub> の期待値は ''a''<sub>''i''</sub> の2乗となる。

よって、モジュラリティは以下のように定義される。
:<math>
Q = \sum_{i=1}^C \left( e_{ii} - a_{i}^{2} \right)
</math>

== 脚注 ==
{{脚注ヘルプ}}
<references />

==関連項目==
*[[複雑ネットワーク]]

{{Applied-math-stub}}
{{デフォルトソート:もしゆらりてい}}
[[Category:グラフ理論]]
[[Category:数学に関する記事]]
[[Category:代数的グラフ理論]]
[[Category:複雑系]]
[[Category:モジュール方式|*]]