コミュニティの評価指標について2つだけ

はじめに

ほとんどのデータはグラフ(orネットワーク)として表すことができます.
道路,空港,タンパク質,購買履歴,レシピ,地図...などなど.
言語処理や機械学習でTriple(図書館情報学でおなじみ)やテンソルを用いた学習やGoogleのKnowledge Graphsでもグラフが登場します.

グラフにはコミュニティと呼ばれる密に繋がっている部分集合が存在することがあります.
Twitterを例にあげれば,同じ興味を持ってる人や会社の同期(?)などです.

コミュニティ発見に関する論文は探せばたくさん出てくるので,以下の論文に譲るとして,この記事ではコミュニティの評価について言及します.
Community detection in large-scale networks: a survey and empirical evaluation - Harenberg - 2014 - Wiley Interdisciplinary Reviews: Computational Statistics - Wiley Online Library
http://www.cs.rpi.edu/~szymansk/papers/acm-cs.13.pdf

本題

ノード集合の内部で密に繋がっていればそれをコミュニティとする場合もあるでしょうし,
ノード集合の内部で密に繋がり,かつ外部とはスパースにつなっているようなノード集合をコミュニティとする場合(いわゆる内輪?)もあるでしょう.


例えば,勉強会のメンバーの繋つながりからそのコミュニティを評価したいとき,メンバーが密に繋がっていることで連絡がとりやすいなどのメリットがあるので前者は良さそうです.
後者は,外部も考慮するため,メンバ以外とは疎遠のため,内輪感がでてしまそうな印象を受ける人もいるかもしれません.
というわけで状況に応じてコミュニティの評価は良し悪しは変化しそうです.


コミュニティの評価については,正解データがある場合とない場合の2通りに分けられます.
ground-truthがある場合,F値やNMI,Omega Indexなどで評価を行います.

ない場合は,何かしらの関数で評価を行います.
この論文はground-truthをもとにコミュニティを定義する関数(上でいった何かしらの関数)を比較しています.
http://www-cs.stanford.edu/people/jure/pubs/comscore-icdm12.pdf
これによるとConductanceとTPRがもっともよいという結果を示しています.

TPR

Triangle Participation Ratioの略で,コミュニティ内の3角形(k=3の完全グラフ)に着目した指標です.

{ \displaystyle
TPR(S) =  \frac{|\{u:u \in S,\{ (v,w):v,w \in S,(u,v) \in E, (u,w) \in E, (v,w) \in E \} \neq \phi \} |}{n_s} 
}

  • Sはコミュニティに含まれるノード集合
  • n_S=|S|

つまりコミュニティ内部で1つでもいいかk=3の完全グラフに属しているノードの割合を表しています.
これはコミュニティの内部しかみない指標です.

pythonのnetworkxにはTriangleを数えるメソッドがあるので,それを使えば計算できそうです.

また上であげた論文の著者がsnap.pyというのを公開していて,TPRを計算する関数があります
GetTriadParticip — Snap.py 1.2 documentation

Conductance

Conductanceはコミュニティの外部も考慮する指標です.
0に近いほどいいです.

{ \displaystyle
Conductance(S) =  \frac{c_s}{2m_s + c_s} 
}

  • m_sは接続する2つのノードがコミュニティに含まれているようなエッジの数
  • c_sは接続する1つのノードだけがコミュニティに含まれているエッジの数

これもsnapにありました.
NCP: Network Community Profile


コード書こうとしたらもうあったので以上です.