| 講演名 | 2016-04-21 未知のグラフに対する影響最大化アルゴリズムにおけるランダムジャンプの効果 三原 正大(関西学院大), 津川 翔(筑波大), 大崎 博之(関西学院大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 我々はこれまで未知のグラフに対する影響最大化問題と、その発見的解法 Influence Maximization for Unknown Graphs (IMUG) を提案している。未知のグラフに対する影響最大化問題は、限られた数のノードを探査することによって得られる部分的なソーシャルネットワークの構造のみから、そのネットワークにおける影響力の強いシードノードを特定することを目的とする。本稿では、これまでに提案した未知のグラフに対する影響最大化アルゴリズム IMUG におけるグラフの探査方式を拡張し、その有効性を検証する。具体的には、IMUG の採用している貪欲的に次数の期待値の高いノードを探査する方式と、ランダムに選択したノードを探査するランダムジャンプを組み合わせた探査方式を用いたアルゴリズム IMUG with Random Flight (IMUG-RF) を提案し、その有効性を検証する。シミュレーション実験の結果、IMUG-RF が未知のグラフに対する影響最大化アルゴリズムとして効率的に動作することを示す。 |
| 抄録(英) | We have proposed a problem called influence maximization for unknown graphs, and a heuristic algorithm for the problem. Influence maximization for unknown graphs is the problem of detecting a set of influential nodes in a social network only using the limited knowledge on its topological structure, which is obtained by limited number of probing. In this paper, we extend the method for probing used in our previous algorithm, and propose an influence maximization algorithm for unknown graphs, which we call IMUG-RF (Influence Maximization for Unknown Graphs with Random Flight). IMUG-RF greedily probes the node with the highest expected degree and also periodically probes a randomly selected nodes in the network. Through simulation, we show that IMUG-RF can successfully identify influential seed nodes in real social networks. |
| キーワード(和) | ソーシャルネットワーク / 影響最大化 / バイラルマーケティング / ランダムジャンプ |
| キーワード(英) | Social Network / Influence Maximization / Viral Marketing / Random Jump |
| 資料番号 | CQ2016-3 |
| 発行日 | 2016-04-14 (CQ) |
| 研究会情報 | |
| 研究会 | CS / CQ |
|---|---|
| 開催期間 | 2016/4/21(から2日開催) |
| 開催地（和） | 機械振興会館 |
| 開催地（英） | Kikai-Shinko-Kaikan Bldg. |
| テーマ（和） | SDN（Software-Defined Networking），NFV（Network Functions Virtualization），ネットワーク仮想化，クラウド，サービス品質，コンテンツ配信，一般 |
| テーマ（英） | SDN (Software-Defined Networking), NFV（Network Functions. Virtualization）, Network Virtualization, Cloud, Service Quality, Contents Delivery, etc |
| 委員長氏名（和） | 坪井 利憲(東京工科大) / 矢守 恭子(朝日大) |
| 委員長氏名（英） | Toshinori Tsuboi(Tokyo Univ. of Tech.) / Kyoko Yamori(Asahi Univ.) |
| 副委員長氏名（和） | 横谷 哲也(金沢工大) / 林 孝典(NTT) / 下西 英之(NEC) |
| 副委員長氏名（英） | Tetsuya Yokotani(Kanazawa Inst. of Tech.) / Takanori Hayashi(NTT) / Hideyuki Shimonishi(NEC) |
| 幹事氏名（和） | 高橋 賢(広島市大) / 谷口 友宏(NTT) / 山崎 康広(NEC) / 松田 崇弘(阪大) |
| 幹事氏名（英） | Satoshi Takahashi(Hiroshima City Univ.) / Tomohiro Taniguchi(NTT) / Yasuhiro Yamasaki(NEC) / Takahiro Matsuzaki(Osaka Univ.) |
| 幹事補佐氏名（和） | / 山本 雅大(OKI) / 古 博(早大) / アベセカラ ヒランタ(NTT) |
| 幹事補佐氏名（英） | / Masahiro Yamamoto(OKI) / Bo GU(Waseda Univ.) / Hirantha Abeysekera(NTT) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Communication Systems / Technical Committee on Communication Quality |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 未知のグラフに対する影響最大化アルゴリズムにおけるランダムジャンプの効果 |
| サブタイトル（和） | |
| タイトル（英） | On the Effects of Random Jump in an Influence Maximization Algorithm for Unknown Graphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ソーシャルネットワーク / Social Network |
| キーワード(2)（和/英） | 影響最大化 / Influence Maximization |
| キーワード(3)（和/英） | バイラルマーケティング / Viral Marketing |
| キーワード(4)（和/英） | ランダムジャンプ / Random Jump |
| 第 1 著者 氏名（和/英） | 三原 正大 / Shodai Mihara |
| 第 1 著者 所属（和/英） | 関西学院大学(略称：関西学院大) Kwansei Gakuin University(略称：Kwansei Gakuin Univ.) |
| 第 2 著者 氏名（和/英） | 津川 翔 / Sho Tsugawa |
| 第 2 著者 所属（和/英） | 筑波大学(略称：筑波大) University of Tsukuba(略称：Univ. of Tsukuba) |
| 第 3 著者 氏名（和/英） | 大崎 博之 / Hiroyuki Ohsaki |
| 第 3 著者 所属（和/英） | 関西学院大学(略称：関西学院大) Kwansei Gakuin University(略称：Kwansei Gakuin Univ.) |
| 発表年月日 | 2016-04-21 |
| 資料番号 | CQ2016-3 |
| 巻番号（vol） | vol.116 |
| 号番号（no） | CQ-10 |
| ページ範囲 | pp.13-18(CQ), |
| ページ数 | 6 |
| 発行日 | 2016-04-14 (CQ) |