The Power of Random Neighbors in Social Networks - todo314 @ ウィキ

The Power of Random Neighbors in Social Networks

• Silvio Lattanzi, Yaron Singer
• WSDM 2015

概要

• 友達は友達が多い (friendship paradox)
• power-lawが十分条件では無い
• どういうモデルがparadoxを説明できるのか？
• というわけで，モデルを提案
  • 辺を張り替える
• 影響最大化への適用例

友達の逆説 friendship paradox

• 友達は友達が多い
  • （頂点の近傍次数）<<（その頂点の近傍の平均次数）
• power-lawが十分条件では無い
  • 実際にそういう例を作れる
• 極端な例
  • 正則グラフ
  • ☆
• どういうモデルがparadoxを説明できるのか？

提案モデル

• Watts-Strogatzに辺の張り替えを導入
  • 任意のpower-law graph(1<β<3)の辺を定数確率で張り替える
• 平均次数と近傍の平均次数に漸近的に違いが出る
• Θ(log n)頂点の標本Sをとれば，高確率で，
• （Sの1つの近傍の平均次数）/（Sの平均次数）= ω(1)
  • 証明としてはβ=2で分断している

影響最大化

• 明示的にグラフが見れない
• 高い次数が欲しい，けど，power-lawだし難しい

Adaptive seeding

• 予算を2段階に使う
• 初: 適当に選ぶ，近傍を惹きつけてもらう
• 次: 近傍から強影響力の人を選ぶ
• 近傍には高次数が含まれやすいので…
• 実験
  • IC／LTモデルでランダム頂点集合とランダム頂点集合の近傍を比較

まとめ

• 実験は対して読んでないが，理論はかっちりしているっぽい

WSDM グラフ構造 影響最大化

2015/02/23 20:11