講演抄録/キーワード |
講演名 |
2021-09-09 11:35
未知のネットワーク上の影響最大化における幅優先探索の有効性 ○脇坂悠生・松尾涼太郎(関西学院大)・津川 翔(筑波大)・大崎博之(関西学院大) CQ2021-42 |
抄録 |
(和) |
近年、未知のネットワーク上の影響最大化問題が注目されている。未知のネットワーク上の影響最大化問題は、ネットワークサンプリングによって得られた部分ネットワークの構造のみから、ネットワーク上の影響伝播によって影響を受けるノード数を最大化するように、影響伝播の開始ノードを決定することを目的としている。未知のネットワーク上で効果的な影響伝播を実現するためには、ネットワークサンプリング戦略やサンプルサイズを適切に決定する必要がある。そこで我々はこれまでに、サンプリング戦略としてランダムサンプリングを用いた場合のサンプルサイズと被影響ノード数の関係を解析的に明らかにした。本稿ではこれまでの解析を発展させ、代表的なクローリングによるサンプリング戦略である幅優先探索を用いた場合の影響伝播による被影響ノード数の期待値を導出する。さらにいくつかの数値例により、未知のネットワークの影響最大化におけるランダムサンプリングと幅優先探索を用いたサンプリングの有効性を調査する。その結果、幅優先探索を用いたサンプリングの方がランダムサンプリングよりも、同じ被影響ノード数を達成するのに必要なサンプルサイズが小さく抑えられることがわかった。 |
(英) |
Recently, the influence maximization problem for unknown networks has received much attention. The problem aims to identify a small set of influential nodes only from a partial structure of the network obtained by network sampling. To achieve efficient influence propagation on unknown networks, it is necessary to determine the sampling strategy and the number of sample nodes appropriately. We have analytically clarified the relationship between the sample size and the number of activated nodes when random sampling is used as the sampling strategy through theoretical analysis. In this paper, we extend our previous analysis to derive the expected number of activated nodes when breadth-first search, which is a typical crawl-based sampling strategy, is used. Furthermore, we comparatively investigate the effectiveness of random sampling and breadth-first search in influence maximization for unknown networks through several numerical examples. The results show that sampling with breadth-first search requires a smaller sample size to achieve the same number of activated nodes than random sampling. |
キーワード |
(和) |
影響最大化 / 情報拡散 / ソーシャルネットワーク / 未知のネットワーク / ネットワークサンプリング / 幅優先探索 / / |
(英) |
Influence Maximization / Information Diffusion / Social Networks / Unknown Networks / Network Sampling / BFS (Breadth-First Search) / / |
文献情報 |
信学技報, vol. 121, no. 173, CQ2021-42, pp. 29-34, 2021年9月. |
資料番号 |
CQ2021-42 |
発行日 |
2021-09-02 (CQ) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
CQ2021-42 |