「UBLF: An Upper Bound Based Approach to Discover Influential Nodes in Social ...」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
* UBLF: An Upper Bound Based Approach to Discover Influential Nodes in Social Networks
- Chuan Zhou, Peng Zhang, Jing Guo, Xingquan Zhu, Li Guo
* 概要
- CELFは最初のiterationが遅い！
- もうちょっとだけ早くするんじゃ
- 大まかな見積もりを行列計算でやる
- タイトかは分からんが正しい上界が出る
- 上界順にMonte-Carloして、それが最上位って分かったら抜ける
- シミュレーション数95%カット
- 速度は2~5倍(´・ω・`)
* 提案手法
** 上界の見積もり方
- Pr_{S,t}[v]: Sが時刻tにvをactivateする確率
- ↑の値はvの近傍uvについて、そのどれもが失敗することは無い、で書けるので
- 1-Π_{uv}(1-Pr_{S,t-1}[u]*p_{uv})
- こんな感じ（気分）
- 1-Π(1-x_i)≦Σx_iで抑えれば
- Pr_{S,t}[v]≦Σ_u Pr_{S,t-1}[u]*p_{uv}
- ポイントは↑が厳密に上界であること（他のヒューリスティクスとは違う
- しかもシンプルな式なのでp_{uv}を要素に持つ行列のべき乗和Pで表現できる
- 正確には
- Π_{S,t}を↑のPrのベクトルと思えば
- Π_{S,t}≦Π_{S,t-1}P
- これを繰り返して
- σ(S)≦Σ_t Π_{S,0}P^t I
- まぁ結局(E-P)の逆行列になる（上の式からあきらか
** UBLF
+ 最初に上ので上界を出す
+ 上界の大きい順に頂点vを取り出す
+ σ(v)を計算
+ σ(v)≧次の上界ならもうvでOK
- もっと簡単に一回だけ上界出してそれをスコアとしてk個選んでるけどダメだろう…
* 実験
- 比較対象
-- CELF、PageRank、Degree、Random
- Monte-Carloシミュレーション数
-- 総回数は5%位に減った
- influence spread
-- CELFと同じ
- 計算時間
- CELFの2～5倍速くなった
-- (´・ω・`)
* まとめ
- 上界がまともに出てくるという点で面白いと思った
- 実際にシミュレーション回数が激減しているのもすごい
- ただ余り速くなっていないので本末転倒
- もっと早く2008,9年とかだったら高評価だったに違いない
- いずれにしてもICDM通っているのでなんだかな～という感じ
&tags()
&update()
* UBLF: An Upper Bound Based Approach to Discover Influential Nodes in Social Networks
- Chuan Zhou, Peng Zhang, Jing Guo, Xingquan Zhu, Li Guo
- ICDM 2013
* 概要
- CELFは最初のiterationが遅い！
- もうちょっとだけ早くするんじゃ
- 大まかな見積もりを行列計算でやる
- タイトかは分からんが正しい上界が出る
- 上界順にMonte-Carloして、それが最上位って分かったら抜ける
- シミュレーション数95%カット
- 速度は2~5倍(´・ω・`)
* 提案手法
** 上界の見積もり方
- Pr_{S,t}[v]: Sが時刻tにvをactivateする確率
- ↑の値はvの近傍uvについて、そのどれもが失敗することは無い、で書けるので
- 1-Π_{uv}(1-Pr_{S,t-1}[u]*p_{uv})
- こんな感じ（気分）
- 1-Π(1-x_i)≦Σx_iで抑えれば
- Pr_{S,t}[v]≦Σ_u Pr_{S,t-1}[u]*p_{uv}
- ポイントは↑が厳密に上界であること（他のヒューリスティクスとは違う
- しかもシンプルな式なのでp_{uv}を要素に持つ行列のべき乗和Pで表現できる
- 正確には
- Π_{S,t}を↑のPrのベクトルと思えば
- Π_{S,t}≦Π_{S,t-1}P
- これを繰り返して
- σ(S)≦Σ_t Π_{S,0}P^t I
- まぁ結局(E-P)の逆行列になる（上の式からあきらか
** UBLF
+ 最初に上ので上界を出す
+ 上界の大きい順に頂点vを取り出す
+ σ(v)を計算
+ σ(v)≧次の上界ならもうvでOK
- もっと簡単に一回だけ上界出してそれをスコアとしてk個選んでるけどダメだろう…
* 実験
- 比較対象
-- CELF、PageRank、Degree、Random
- Monte-Carloシミュレーション数
-- 総回数は5%位に減った
- influence spread
-- CELFと同じ
- 計算時間
- CELFの2～5倍速くなった
-- (´・ω・`)
* まとめ
- 上界がまともに出てくるという点で面白いと思った
- 実際にシミュレーション回数が激減しているのもすごい
- ただ余り速くなっていないので本末転倒
- もっと早く2008,9年とかだったら高評価だったに違いない
- いずれにしてもICDM通っているのでなんだかな～という感じ
&tags()
&update()
