Exact Computation of Influence Spread by Binary Decision Diagrams - todo314 @ ウィキ

Exact Computation of Influence Spread by Binary Decision Diagrams

• Takanori Maehara, Hirofumi Suzuki, Masakazu Ishihata
• WWW 2017

概要

• BDDで影響拡散を厳密計算する方法を提案
• 最大で100点くらいのグラフなら出来る！

提案手法

• 到達可能性に関する情報を圧縮すれば良い
• もしBDDが構築できたら、後は任意の辺確率設定について、DAG上の動的計画法で計算できる
• 各頂点対(s,t)について構築できればOK；あとは併合すればいいので
• [sからtへ到達可能]を考えて、フロンティア法を実行
  • $$\texttt{isOneTerminal}$$: 今1の辺だけでsからtに到達可能
  • $$\texttt{isZeroTerminal}$$: 今1の辺∪残りの辺を足してもsからtに到達不能
  • 等価判定: いい感じのもの,configuration,を作っておく
• 後は併合するだけ、もうちょっと色々してる

その他

• 棄却なしランダムサンプリング：DPの結果を酔歩で辿る
• 条件付き影響拡散：出来ます
• 辺確率で微分できます

実験

• 経路の数え上げなので、ちょっと大きくなるとやばおだけど、141点320辺で動く

まとめ

• 良い話
• 厳密な影響最大化もしたくなりますね。

WWW 影響拡散 影響最大化

2017/10/02