Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large ... - todo314 @ ウィキ

Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large Graph Collections

• Johan Ugander, Lars Backstrom, Jon Kleinberg
• In WWW 2013

メモ

• 岩田さん

概要

• social networkを全体を見て解析するのではなく、密な部分ごとに見る
• 3-4頂点の部分グラフの出現頻度を見ると特徴がわかる

実験データ

• Facebook
  • Lars BackstromがFacebookの人だからしょーがないね(´・ω・`)
• 抽出する部分グラフ
• Neighborhoods
  • 友人
• Groups
  • グループのメンバー
• Events
  • イベント参加者

出現頻度

• 明らかに傾向がある
• social特有なのか、一般のグラフが持つのか・・・？
• random graphと比較してみよう！
• 微妙に違う
• ※ここで考えているのは、例えば3頂点の辺の状態を指定する
• で、Erdős–Rényiのpを変化させた時に、その指定したグラフが部分グラフとして出現する割合

Edge Formation Random Walk with Triadic Closure

• 辺が増える wp γ
• 辺が減る wp δ
• 3点のパスが△に変化 wp λ
• こういうrandom walkの定常分布
• パラメータをフィットさせる

Extremal Bounds

• 疑問: そもそも、この確率に対する頻度のとる範囲は[0,1]ではない
  • もっと狭い
• 不等式を気合いで計算してもっとよく見てみよう
• 3-4頂点について計算した

Classification

• 部分グラフの出現頻度から、neighbors、groups、eventのどれか分類