Community Detection with Edge Content in Social Media Networksを読んだ
ICDE2012勉強会に向けて、Social MediaセッションのCommunity Detection with Edge Content in Social Media Networksを読んだ。
ソーシャルネットワークにおけるコミュニティ抽出にEdge contentなるものを取り入れるという論文。Edge contentっていうのは、それぞれのエッジに付随するテキストなどのコンテンツのこと。例えば、E-mailネットワークなら、ある個人間でやり取りされたメールの内容(の単語頻度)など。
概要
- Social Media NetworkにおけるCommunity DetectionにEdge Contentを取り入れる。
- Edge Content: エッジに付随するテキストなどのコンテンツ(Email networkなら、ある個人間でやり取りされたメールの内容など)
- 提案する手法は、Edge contentとノードどうしのlinkageの両方を用いる
- ソーシャルネットワーク上の個人は、様々な興味などを持っていて、複数のコミュニティに属しているのが普通。そのため、異なるコミュ二ティの人とは異なる会話(interaction)をしている。
- 例えば、テニスサークルの友人とはテニスについて会話し、研究室の仲間とは研究についての話をするなど
- そのため、Edge contentは個人の様々な側面を表していて、Community detectionに有効に働くよ!
手法
- 各エッジをk個のコミュニティ{C1, C2, ..., Ck}にクラスタリングする
- ノードには複数の側面(興味など)があるが、エッジには一つの意味合いしかない!
- 各コミュニティCiに属すエッジの両端のノードをコミュニティPiに含める
- あるノードが複数のコミュニティに属すこともある
- エッジのクラスタリングはmatrix factorizationによって行う
- 接続行列Γ(ノードiがエッジjに接続していればij要素が1)をエッジのlatent featureを表す行列Eと、ノードのlatent featureを表す行列Vに分解
- 目的関数を最小化するE,Vを求める
- E,Vの行列積がより正確に接続行列を表すようにする
- はフロベニウスノルム
- Eはk×m行列(kはコミュニティ数、mはエッジ数)であり、各列ベクトル(k次元)はエッジのlatent featureを表す
- そのため、各エッジのlatent featureを用いて、k-meansでエッジをクラスタリングする!
- ここまででは、Edge contentは考慮していないので、目的関数にそれを取り入れる
- matrix factorizationは通常はPLSA(Probabilistic latent semantic analysis)やNMF(non-negative matrix factorization)によって行うが、ここでは目的関数の最小化を行う
- 目的関数は凸関数になっている(論文中に証明なし)ため、勾配法などの簡単な方法で最小化可能
- 高速に最小化する手法が提案されている(詳しくは論文)