Contents

Modularity

Modularity

モジュラリティとは

モジュラリティは、ランダムに結合されたネットワークとの系統的な偏差によって、分割の質を測る指標である。

\(N\)個のノードと\(L\)個のリンクからなるネットワークを\(C\)個のコミュニティに分割することを考える。 コミュニティ\(c\)は、\(N_c\)個のノードと\(L_c\)個のリンクを持つ。

部分グラフ\(g_c\)がコミュニティであるかを測る指標として、

\[ M_c = \frac{1}{2L} \sum_{(i,j) \in g_c} \left( A_{ij} - p_{ij} \right) \]

を求める。ここで、\(A_{ij}\)は隣接行列の要素であり、ノード\(i,j\)間にリンクが存在するときのみ1をとる。重み付きネットワークの場合、\(A_{ij}\)はその重みとなる。 \(p_{ij}\)は、各ノードが結合されるノードをランダムに選ぶと仮定するとき(Configuration model)、ノード\(i\)(次数\(k_i\))とノード\(j\)(次数\(k_j\))の間にあると想定されるリンクの数であり、

\[ p_{ij} = \frac{k_i k_j}{2L} \]

と表される。ノード\(i\)がノード\(j\)の\(k_j\)本のリンクとつながる確率は\(k_j/2L\)であり、ノード\(i\)の次数が\(k_i\)であることから、\(p_{ij} = k_i \times k_j/2L\)となる。

\(M_c>0\)のとき、\(g_c\)はランダムに結合されたネットワークに想定されるよりも多くのリンクを持つことになり、モジュラリティの値が高いほど良い分割を意味する。 \(M_c=0\)のとき、\(g_c\)はランダム時と同程度の結びつきであり、\(M_c < 0\)のときは、コミュニティになり得ない。

上の式から、\(M_c\)はコミュニティ\(g_c\)内のノードの総次数\(k_c\)を用いて、以下のように変形できる。

\[ M_c = \frac{L_c}{L} - \left(\frac{k_c}{2L}\right)^2 \]

以上をまとめると、ネットワーク全体を\(C\)個のコミュニティに分割するとき、この分割のモジュラリティは、各コミュニティの\(M_c\)の総和

\[ M = \sum_{c=1}^C M_c = \sum_{c=1}^C \left( \frac{L_c}{L} - \left(\frac{k_c}{2L}\right)^2 \right) \]

によって定義される。

References

Modularity

モジュラリティとは

モジュラリティは、ランダムに結合されたネットワークとの系統的な偏差によって、分割の質を測る指標である。

\(N\)個のノードと\(L\)個のリンクからなるネットワークを\(C\)個のコミュニティに分割することを考える。 コミュニティ\(c\)は、\(N_c\)個のノードと\(L_c\)個のリンクを持つ。

部分グラフ\(g_c\)がコミュニティであるかを測る指標として、

\[ M_c = \frac{1}{2L} \sum_{(i,j) \in g_c} \left( A_{ij} - p_{ij} \right) \]

を求める。ここで、\(A_{ij}\)は隣接行列の要素であり、ノード\(i,j\)間にリンクが存在するときのみ1をとる。重み付きネットワークの場合、\(A_{ij}\)はその重みとなる。 \(p_{ij}\)は、各ノードが結合されるノードをランダムに選ぶと仮定するとき(Configuration model)、ノード\(i\)(次数\(k_i\))とノード\(j\)(次数\(k_j\))の間にあると想定されるリンクの数であり、

\[ p_{ij} = \frac{k_i k_j}{2L} \]

と表される。ノード\(i\)がノード\(j\)の\(k_j\)本のリンクとつながる確率は\(k_j/2L\)であり、ノード\(i\)の次数が\(k_i\)であることから、\(p_{ij} = k_i \times k_j/2L\)となる。

\(M_c>0\)のとき、\(g_c\)はランダムに結合されたネットワークに想定されるよりも多くのリンクを持つことになり、モジュラリティの値が高いほど良い分割を意味する。 \(M_c=0\)のとき、\(g_c\)はランダム時と同程度の結びつきであり、\(M_c < 0\)のときは、コミュニティになり得ない。

上の式から、\(M_c\)はコミュニティ\(g_c\)内のノードの総次数\(k_c\)を用いて、以下のように変形できる。

\[ M_c = \frac{L_c}{L} - \left(\frac{k_c}{2L}\right)^2 \]

以上をまとめると、ネットワーク全体を\(C\)個のコミュニティに分割するとき、この分割のモジュラリティは、各コミュニティの\(M_c\)の総和

\[ M = \sum_{c=1}^C M_c = \sum_{c=1}^C \left( \frac{L_c}{L} - \left(\frac{k_c}{2L}\right)^2 \right) \]

によって定義される。

References

previous

Graph Thoery

next

Elimination Graph