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