Diversified Social Influence Maximization
-
Fangshuang Tang, Qi Liu, Hengshu Zhu, Enhong Chen, Feida Zhu
-
ASONAM 2014
概要
-
影響最大化に人の多様性を導入
-
影響拡散と多様性の線形結合を最大化
-
Don't put all your eggs in one basket.
-
全部の卵を一つの篭に入れるな/一つのことにすべてを賭けるな
問題定義
-
$$ F(S) = (1-\gamma)\sigma(S) / \sigma' + \gamma D(\mu^S) / D' $$
-
$$\mu^S$$: $$ \mu^S_j = \Pr[j\text{が活性化} \mid S\text{がシード}]$$
-
$$ D(\mu^S) = \sum_i f(\sum_j w_{ji} \mu^S_j) $$
-
iはカテゴリ(C種類),jは頂点
-
w_jiは頂点jのカテゴリiに関する重み
-
fは単調凹関数
-
割りとそのまんまの定義
-
D(μS)はSについて単調・劣モジュラ
緩和
-
元の定義は計算が大変
-
代わりにD(S)を使う
-
一様: $$ \sum_i f(\sum_{j \in S} w_{ji} \times 1) $$
-
重み: $$ \sum_i f(\sum_{j \in S} w_{ji} \times \sigma(\{j\})) $$
-
もはやσの計算が大変なので,次数やPageRankで選んだりもする
実験
-
MovieLensとYahoo! Answersのデータセット
-
単に影響最大化するより多様
-
σはちょっと劣るけどそうでもない
-
ぼちぼち速い
-
等…
まとめ
-
普通
-
影響を及ぼした頂点集合に関する何かを最適化するのは面白そう
-
targeted influence maximizationの発展みたいな
ASONAM 多様性 影響最大化
2015/07/06 23:32
最終更新:2015年07月14日 12:13