でかいチーズをベーグルする

でかいチーズはベーグルすべきです。

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^T \cdot V - \Gamma ||^2_Fを最小化するE,Vを求める
      • E,Vの行列積がより正確に接続行列を表すようにする
      • ||\cdot ||_Fはフロベニウスノルム
    • Eはk×m行列(kはコミュニティ数、mはエッジ数)であり、各列ベクトル(k次元)はエッジのlatent featureを表す
      • そのため、各エッジのlatent featureを用いて、k-meansでエッジをクラスタリングする!
  • ここまででは、Edge contentは考慮していないので、目的関数にそれを取り入れる
    • edge contentを表す特徴ベクトル(メールの単語頻度など)を考え、各エッジペアごとに類似度を計算(コサイン尺度など)し、類似度行列S(m×m)を作成
    • Sijの値が大きなエッジペアのlatent feature vector(Eの列ベクトル)の差が小さくなるような項を目的関数に取り入れる(詳しくは論文)
      • これによって、基の接続行列Γをよく表現し、かつEdge contentから作成した特徴ベクトルが類似しているエッジペアのlatent feature vectorの差が小さくなるようなE,Vが得られる
  • matrix factorizationは通常はPLSA(Probabilistic latent semantic analysis)やNMF(non-negative matrix factorization)によって行うが、ここでは目的関数の最小化を行う
    • 目的関数は凸関数になっている(論文中に証明なし)ため、勾配法などの簡単な方法で最小化可能
    • 高速に最小化する手法が提案されている(詳しくは論文)
実験
  • Enron Email Data SetとFlicker Data Setを用いる
  • 他の様々な手法と比較
    • リンクのみを用いるもの
    • コンテンツのみを用いるもの
    • リンクと、ノードのコンテンツを用いるもの
    • リンクと、エッジのコンテンツを用いるもの(提案手法)
  • 提案手法が一番良かったよ!めでたし