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)
影響最大化
-
明示的にグラフが見れない
-
高い次数が欲しい,けど,power-lawだし難しい
Adaptive seeding
-
予算を2段階に使う
-
初: 適当に選ぶ,近傍を惹きつけてもらう
-
次: 近傍から強影響力の人を選ぶ
-
近傍には高次数が含まれやすいので…
-
実験
-
IC/LTモデルでランダム頂点集合とランダム頂点集合の近傍を比較
まとめ
-
実験は対して読んでないが,理論はかっちりしているっぽい
WSDM グラフ構造 影響最大化
2015/02/23 20:11
最終更新:2015年02月23日 20:19