糞糞糞ネット弁慶

読んだ論文についてメモを書きます.趣味の話は http://repose.hatenablog.com

Romantic Partnerships and the Dispersion of Social Ties: A Network Analysis of Relationship Status on Facebook (CSCW 2014) 読んだ

概要

[1310.6753] Romantic Partnerships and the Dispersion of Social Ties: A Network Analysis of Relationship Status on Facebook
facebook上の友人関係のみを用いて彼氏や彼女,婚約者,配偶者(Romantic Partnership)を特定する.
著者はグラフ,ネットワーク研究でお馴染みfacebookのLars BackstromとJon Kleinberg.CSCW2014のbest paper.

手法

すごく大雑把に書くと,「カップルの友人関係は大きく重なっているわけではないが,異なるコミュニティに少しずつ共通の友達がいる状態だ」という仮説に基づいている.例として,妻の同僚や家族,昔の同級生を夫が知っているという事例が上げられている.この時,それぞれの異なるコミュニティ(同僚,家族,昔の同級生)は互いに知っているわけではなく,夫のみがつながっている状態にある.
これを dispersion という指標で表す.クエリであるノードに対して,部分グラフとその隣接ノード集合で構成されるグラフ,ノードをノードの common neighbors とした時,

とする.この時,は任意の距離関数を取る事,また,距離関数の計算についてはサブグラフからとそれに繋がるエッジを取り除いたものを用いる.論文中では,については,にcommon neighbors が存在せず,エッジも存在しない場合に1,そうでない場合に0を取るものとしている.
この式は上で述べた仮説をそのまま反映している.が存在しない時のの共通の友人がどれだけ距離があるかを考え,距離の総和が大きければ大きいほどその二人はカップルである確率が高い.
あとはこれを友人の数で正規化したりパラメータを追加したり再帰的に定義したりする.

実験結果

ステータスの違い(結婚済み,婚約関係,カップル)にもよるが60%近くの精度を示している.興味深い点を箇条書きにする.

  • 「最も写真に一緒に写っていた相手をパートナーと予測する」というベースラインよりも高い数字を出している事
    • 写真に載せていないからと言ってごまかせるものではない
  • ステータスの親密さが下がるにつれ精度が下がる
    • カップルなどは共通のコミュニティから生まれるものだからではないか
  • betweennessと呼ばれるコミュニティ検出などで用いる指標よりも良い精度を示している
    • この点については興味があったが特に考察はされていない.