読者です 読者をやめる 読者になる 読者になる

Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large Graph Collections (WWW'13)

  • OSN を,巨大な疎なグラフでなく,小さな密グラフの集合として着目.
    • 友人,グループ,イベント
  • 3 点部分グラフの出現頻度
    • ランダムグラフと比較 → 三角形が多いなぁ
  • モデル
    • だいたいランダムだけど,三角形を作りやすくする
  • Extremal Bounds
    • 色々な不等式を使って,理論的な bound を計算
  • 分類
    • 友人,グループ,イベントは4点部分グラフの出現頻度で機械的に分類可能
    • R_G, R_λ:差を使う