| 講演名 | 2021-09-09 未知のネットワーク上の影響最大化における幅優先探索の有効性 脇坂 悠生(関西学院大), 松尾 涼太郎(関西学院大), 津川 翔(筑波大), 大崎 博之(関西学院大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 近年、未知のネットワーク上の影響最大化問題が注目されている。未知のネットワーク上の影響最大化問題は、ネットワークサンプリングによって得られた部分ネットワークの構造のみから、ネットワーク上の影響伝播によって影響を受けるノード数を最大化するように、影響伝播の開始ノードを決定することを目的としている。未知のネットワーク上で効果的な影響伝播を実現するためには、ネットワークサンプリング戦略やサンプルサイズを適切に決定する必要がある。そこで我々はこれまでに、サンプリング戦略としてランダムサンプリングを用いた場合のサンプルサイズと被影響ノード数の関係を解析的に明らかにした。本稿ではこれまでの解析を発展させ、代表的なクローリングによるサンプリング戦略である幅優先探索を用いた場合の影響伝播による被影響ノード数の期待値を導出する。さらにいくつかの数値例により、未知のネットワークの影響最大化におけるランダムサンプリングと幅優先探索を用いたサンプリングの有効性を調査する。その結果、幅優先探索を用いたサンプリングの方がランダムサンプリングよりも、同じ被影響ノード数を達成するのに必要なサンプルサイズが小さく抑えられることがわかった。 |
| 抄録(英) | 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) |
| 資料番号 | CQ2021-42 |
| 発行日 | 2021-09-02 (CQ) |
| 研究会情報 | |
| 研究会 | CQ |
|---|---|
| 開催期間 | 2021/9/9(から2日開催) |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | 無線通信品質、6G、IoT、無線伝送、リソース制御、クロスレイヤー技術、一般 |
| テーマ（英） | Wireless Communications Quality, 6G, IoT, Resource Management, Wireless Transmission, Cross layer Technologies, etc. |
| 委員長氏名（和） | 岡本 淳(NTT) |
| 委員長氏名（英） | Jun Okamoto(NTT) |
| 副委員長氏名（和） | 平栗 健史(日本工大) / 長谷川 剛(東北大) |
| 副委員長氏名（英） | Takefumi Hiraguri(Nippon Inst. of Tech.) / Gou Hasegawa(Tohoku Univ.) |
| 幹事氏名（和） | アベセカラ ヒランタ(NTT) / 山本 寛(立命館大) |
| 幹事氏名（英） | Hirantha Abeysekera(NTT) / Hiroshi Yamamoto(Ritsumeikan Univ.) |
| 幹事補佐氏名（和） | 西川 由明(NEC) / 堅岡 良知(KDDI総合研究所) / 川嶋 喜美子(NTT) |
| 幹事補佐氏名（英） | Yoshiaki Nishikawa(NEC) / Ryoichi Kataoka(KDDI Research) / Kimiko Kawashima(NTT) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Communication Quality |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 未知のネットワーク上の影響最大化における幅優先探索の有効性 |
| サブタイトル（和） | |
| タイトル（英） | On the Effectiveness of Breadth-First Search for Influence Maximization on Unknown Networks |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 影響最大化 / Influence Maximization |
| キーワード(2)（和/英） | 情報拡散 / Information Diffusion |
| キーワード(3)（和/英） | ソーシャルネットワーク / Social Networks |
| キーワード(4)（和/英） | 未知のネットワーク / Unknown Networks |
| キーワード(5)（和/英） | ネットワークサンプリング / Network Sampling |
| キーワード(6)（和/英） | 幅優先探索 / BFS (Breadth-First Search) |
| 第 1 著者 氏名（和/英） | 脇坂 悠生 / Yuki Wakisaka |
| 第 1 著者 所属（和/英） | 関西学院大学(略称：関西学院大) Kwansei Gakuin University(略称：Kwansei Gakuin Univ.) |
| 第 2 著者 氏名（和/英） | 松尾 涼太郎 / Ryotaro Matsuo |
| 第 2 著者 所属（和/英） | 関西学院大学(略称：関西学院大) Kwansei Gakuin University(略称：Kwansei Gakuin Univ.) |
| 第 3 著者 氏名（和/英） | 津川 翔 / Sho Tsugawa |
| 第 3 著者 所属（和/英） | 筑波大学(略称：筑波大) University of Tsukuba(略称：Tsukuba Univ.) |
| 第 4 著者 氏名（和/英） | 大崎 博之 / Hiroyuki Ohsaki |
| 第 4 著者 所属（和/英） | 関西学院大学(略称：関西学院大) Kwansei Gakuin University(略称：Kwansei Gakuin Univ.) |
| 発表年月日 | 2021-09-09 |
| 資料番号 | CQ2021-42 |
| 巻番号（vol） | vol.121 |
| 号番号（no） | CQ-173 |
| ページ範囲 | pp.29-34(CQ), |
| ページ数 | 6 |
| 発行日 | 2021-09-02 (CQ) |