[4Yin-B] Poster 7

[4Yin-B-KA01] (Other)人工知能基本問題研究会（SIG-FPAI）

〇中村 健吾¹ (1. NTT)

ネットワークおよび，シードとよばれる最初に情報を付与されるノード集合が与えられたとき，影響拡散とは確率的な情報伝播のモデルのもとで最終的に情報を受け取るノード数の期待値である．独立カスケードモデルとよばれる情報伝播モデルのもとでは，影響拡散は有向曖昧グラフにおいてシードから到達可能なノード数の期待値であり，その厳密計算には例えばソーシャルネットワークにおける影響最大化問題など様々な応用がある．影響拡散の厳密計算は#P困難な問題だが，一方でパス幅が定数であるグラフに対して影響拡散をネットワークのノード数と辺数の積に比例する時間で厳密計算するアルゴリズムが知られていた．我々はこのアルゴリズムを改良し，パス幅が定数であるグラフに対し影響拡散をネットワークのノード数と変数の和に比例する時間，すなわちグラフサイズの線形時間で厳密計算するアルゴリズムを提案する．