Diversified Social Influence Maximization - todo314 @ ウィキ

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' $$
  • σ', 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