| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 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 |
|
| 研究会情報 | |
| 研究会 | CQ MIKA |
| 開催期間 | 2021-09-09 - 2021-09-10 |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | 無線通信品質、6G、IoT、無線伝送、リソース制御、クロスレイヤー技術、一般 |
| テーマ（英） | Wireless Communications Quality, 6G, IoT, Resource Management, Wireless Transmission, Cross layer Technologies, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | CQ |
| 会議コード | 2021-09-CQ-MIKA |
| 本文の言語 | 日本語 |
| タイトル（和） | 未知のネットワーク上の影響最大化における幅優先探索の有効性 |
| サブタイトル（和） | |
| タイトル（英） | 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) |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第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.) |
| 講演者 | 第1著者 |
| 発表日時 | 2021-09-09 11:35:00 |
| 発表時間 | 20分 |
| 申込先研究会 | CQ |
| 資料番号 | CQ2021-42 |
| 巻番号（vol） | vol.121 |
| 号番号（no） | no.173 |
| ページ範囲 | pp.29-34 |
| ページ数 | 6 |
| 発行日 | 2021-09-02 (CQ) |
[研究会発表申込システムのトップページに戻る]