影響伝搬確率の誤差に対する影響最大化アルゴリズムのロバスト性評価

TSUGAWA Sho; OHSAKI Hiroyuki

文献

J-GLOBAL ID：201702254041913870 整理番号：17A0604995

影響伝搬確率の誤差に対する影響最大化アルゴリズムのロバスト性評価

Evaluation of the Robustness of Influence Maximization Algorithms against Random Perturbations to Influence Spread Probability

出版者サイト複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=17A0604995&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=17A0604995&from=J-GLOBAL&jstjournalNo=S0532B") }}

著者 (2件)： ,
資料名：
巻： 117 号： 5(CQ2017 1-13) ページ： 53-58 発行年： 2017年04月13日
JST資料番号： S0532B ISSN： 0913-5685 資料種別：会議録 (C)
記事区分：原著論文発行国：日本 (JPN) 言語：英語 (EN)

ソーシャルネットワークにおける影響最大化問題が活発に研究されている。影響最大化は,ソーシャルネットワーク上の少数のシードノードから,与えられた影響伝搬モデルに従って確率的に影響を伝搬させた時に,影響を受けるノード数を最大化するようなシードノードの集合を特定することを目的とする。既存の影響最大化アルゴリズムの多くは,入力として各ノード間の影響伝搬確率が正確に与えられることを前提としている。ただし,現実のソーシャルネットワークに対して影響最大化アルゴリズムを適用することを考えると,アルゴリズムの入力となる影響伝搬確率と実際の影響伝搬確率の間に誤差が存在することを仮定するのが自然である。本稿では,影響伝搬確率の誤差に対する影響最大化アルゴリズムのロバスト性を評価する。その結果,影響最大化の近似アルゴリズムは,影響伝搬確率の誤差の影響を受けてその有効性を大きく低下させること,誤差が大きい場合には,近似アルゴリズムよりも軽量な発見的アルゴリズムが有効であることなどが示唆された。(著者抄録)

, , , ,
, , , ,

その他の情報処理

引用文献 (22件)：

D. Kempe, J. M. Kleinberg, and E. Tardos, ′′Maximizing the spread of influence through a social network,′′ in Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'03), Aug. 2003, pp.137-146.
P. Domingos and M. Richardson, ′′Mining the network value of cus-tomers,′′ in Proceedings of the 7th ACM SIGKDD International Con-ference on Knowledge Discovery and Data Mining (KDD'01), Aug. 2001, pp.57-66.
W. Chen, Y. Wang, and S. Yang, ′′Efficient influence maximization in social networks,′′ in Proceedings of the 15th ACM SIGKDD In-ternational Conference on Knowledge Discovery and Data Mining (KDD'09), Jun. 2009, pp.199-208.
Y. Tang, X. Xiao, and Y. Shi, ′′Influence maximization: Near-optimal time complexity meets practical efficiency,′′ in Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data (SIGMOD' 14), Jun. 2014, pp.75-86.
S. Mihara, S. Tsugawa, and H. Ohsaki, ′′Influence maximization problem for unknown social networks,′′ in Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Net-works Analysis and Mining (ASONAM' 15), Aug. 2015, pp.1539-1546.

, , , , , ,

前のページに戻る