ネットワーククラスタリングについて (1)

大学院での研究では、一部ネットワークにまつわるものをやっていました。ネットワークといっても通信の方ではなく、ノードとエッジから構成されるグラフの方です。最近は、ネットワークの構造に基づいてノードを教師なしで分類していくネットワーククラスタリングに興味があり、備忘録がてらまとめていきます。また、ここでは簡単のため重複エッジや自己ループを許さない無向グラフのみを対象とします。

0. コミュニティとは

ネットワーク科学では、ノードのクラスタのことをしばしば「コミュニティ」とよびます。人間や企業などの主体をノードとして扱うことが多いからかもしれません。コミュニティの定義は難しそうですが、感覚的な特徴には以下のようなものが考えられます。

コミュニティ内では繋がりが密である
大きなネットワークの一部分である
コミュニティ外のノードとよりも、コミュニティ内との繋がりが強い

このような感覚的な表現を出発として、コミュニティを表すような様々な概念が定義されてきました。

1. クリーク

「大きなネットワークの一部分では、その全てのノード同士が結びついている」
このような状況は、コミュニティとみなすのに易いでしょう。このような部分グラフを、クリークといいます。クリークを以下で定義します。ここで「極大である」とは、クリーク内のすべてのノードと接続しているノードがクリーク外に存在しないことを意味します。

クリーク：極大である完全誘導部分グラフ

ネットワークにおいて三角形はよく見られますが、大規模なクリークを発見することは難しいでしょう。ノード数が増えたときは「完全部分グラフ」であることが難しくなるため、様々なクリークの条件を緩和することが考えられてきました。

2. クリークの条件緩和

クリークよりも弱いものを紹介します。

$n$ -クラン：含まれる任意のノードどうしの距離が $n$ 以下であるような極大誘導部分グラフ。直径が $n$ 以下となります
$n$ -クラブ： $n$ -クランのうち、直径が $n$ であるもの
$k$ -プレックス：含まれるどの頂点の次数も $n-k$ 以上である極大誘導部分グラフ
$k$ -コア：どの頂点の次数も $k$ を下回らない誘導部分グラフ。 $k$ -プレックスの $k$ がクリークとの差を表すのに対し、 $k$ -コアの $k$ は絶対的な次数です

また、ネットワークのノード数や密度は様々であるため、コミュニティ内とコミュニティ外の相対的な割合をみる強いコミュニティと弱いコミュニティが知られています。

準備として、 $N$ 個ノードで構成されるネットワーク $G$ の部分グラフのノード集合を $S$ とする。また、 $G$ の隣接行列を $A$ とします。 $A$ の要素 $a _{uv}$ は、ノード $u,v$ が接続されているとき1、接続されていないとき0です。ここで、ノード $u$ が部分グラフ $S$ に対して持つ内部次数と外部次数を定義します。 $u$ 自体が部分グラフに属しているかどうかは関係ないことに注意が必要です。

内部次数： $k _ u ^ {int} = \sum _ {v \in S} a _{u, v}$
外部次数： $k _ u ^ {ext} = \sum _ {v \notin S} a _{u, v}$

内部次数と外部次数を用いて弱いコミュニティ、強いコミュニティは次のように定義されます。

強いコミュニティ：コミュニティ内の任意のノード $u \in S$ で $k _ u ^ {int} > k _ u ^ {ext}$
弱いコミュニティ： $\sum _ {u \in S} k _ u ^ {int} > \sum _ {u \in S} k _ u ^ {ext}$

3. 凝集性 (cohesion)

強いコミュニティ・弱いコミュニティは「コミュニティとみなせるか否か」を与える定義ですが、「コミュニティになっている程度」を連続値として与える凝集性という指標がしられています。ここで、 $n _ s$ は部分グラフ内のノード数とします。

凝集性： $\frac{\sum _ {u \in S} k _ u ^ {int}} {n _ s(n _ s-1)} / \frac{\sum _ {u \in S} k _ u ^ {ext}} {n _ s(N-n _ s)}$

凝集性は（部分グラフ内での密度） / （部分グラフ内から部分グラフ外に対する密度）で表されているため、「凝集性が1以上であれば、また大きければ大きいほど、部分グラフは外部と区別でき、コミュニティの傾向をもっている」と解釈することができます。

4. モジュラリティ

以上では、1つのコミュニティのあり方について、様々な定義や程度の指標を見てきました。実際のネットワーククラスタリングでは、ネットワーク全体を複数のクラスタに分けることを行います。このような問題はグラフ分割とよばれることがあり、特にモジュール数が自動的に決定されるようなタスクをコミュニティ検出といったりします。妥当なクラスタリングを行うためには「分割の質の良さ」を測る必要がありますが、特に有名な指標としてモジュラリティ (modurality)が知られています。

モジュラリティの根底にあるアイデアは、「ランダムグラフはコミュニティ構造をもたない」というものです。コミュニティの特徴をもう一度振り返ると、「部分グラフ内に張られるリンクの割合がそれ以外よりも多い」ことが重要でした。つまり、与えられた分割に対して、「グループ内で張られているエッジの割合」と「エッジがランダムに張られた場合の期待値」との差が重要になります。

いま、ネットワーク $G$ を $m$ 個の部分グラフ $S _ 1, S _ 2, \dots, S _ m$ に分割し、部分グラフ間に張られるエッジ数の割合を要素にもつ $m\times m$ の行列 $E$ を用意します。つまり、 $E$ の $i, j$ 要素は $e _ {i, j} =\frac{1}{2\sum _ {u,v} a _ {u,v}} \sum _ {u \in S _ i} \sum _ {v \in S _ j} a _ {u, v}$ となります。 $E$ の対角成分は分割されたグループ内で張られるエッジの割合であり、非対角成分は異なるグループ間で張られるエッジの割合です。また、グループ $i$ に接続するエッジの割合を考えると、 $E$ の行和 $E _ i = \sum _ {j = 1} ^ m e _ {i, j}$ となります。

もしネットワークが完全にランダムであり、コミュニティ構造を持たないなら、 $e _ {i,j}$ は $i, j$ で独立になるため、それぞれの行和の積 ${\hat e _ {i,j}} = E _ i E _ j$ と期待されます。よって、「グループ内で張られているエッジの割合」と「エッジがランダムに張られた場合の期待値」との差を表すモジュラリティ指標 $Q$ は次式で定義することができます。