研 究 計 画 書
Research Planning of Master’s Thesis
Date of submission: ____/____/____ (MM/DD/YYYY) 学籍番号Student ID number −
氏名 皆川 拓 専攻（分野）
Department
基 幹 理 工 学 研 究 科 数 学 応 用 数理専攻
指導教員 豊泉 洋
Name 研究指導名
Research guidance
Advisor 印
Seal 研究題目
Title
現実のネットワークに即した効率的な情報伝搬方法の探求 修士課程 Master Course 1年(Grade) １．研究目的 Purpose of Research
本研究の目的は、現実に近いネットワーク及び人々の行動を考慮した情報伝搬を考え、その中 での最も効率的な情報伝搬方法の探求を行うことである。ネットワークの情報伝搬は、感染症 の広がり方を示す確率モデル[1]、イノベーションの広がりを表す確率モデル[2]、伝搬速度を 限定した情報伝搬モデル[3]等の様々なモデルが提案されている。中でも伝搬速度を限定した情 報伝搬モデルにおいては、Uncorrelated性を持つネットワークであれば最も効率的な情報伝搬 方法の存在性が数学的に証明されている[3]。一方で、現実のネットワークでUncorrelated性を 満たすものは多くはなく、家族・友人関係・社会等、局所的な関係が多数を占めるのが一般的 である。また、情報を拡散する人々は全員同じ戦略をとるとは限らず、一人一人異なる戦略を 持つと考えられる。
そのため本研究では現実に近い構造のネットワークを生成し、かつ一人一人の戦略も考えた上 で、最も効率的な情報伝搬方法は何かを探求する。情報伝搬に関する研究は情報に限らず感染 症、コンピューターウィルス等に応用することが容易である。また、より現実に即したものを 考えることで、実際の広告ビジネス、ウィルス対策ソフトウェアに応用できる可能性がある。 [1]Kempe, D, Kleinberg, J. and Tardos, E., “ Maximizing the spread of influence through a social network”, Proc. KDD ’03, pp. 137-146, 2003.
[2]D.J.Watts, “A simple model of global cascades on random networks”, Proc. National Academy of Science, USA, col.99, pp.5766-5771, 2002.
[3]H. Toyoizumi, S. Tani, N. Miyoshi, and Y. Okamoto, “Reverse preferential spread in complex networks,” Phys. Rev. E, vol. 86, p. 021103, Aug 2012.
２．従来の研究 Existing Research
早稲田大学理工学術院 Waseda University The Faculty of Science and Engineering
早稲田大学理工学術院 Waseda University The Faculty of Science and Engineering
WWWのリンクの り方や、人から人へと情報が伝わる様子はスケールフリーネットワーク上 の情報伝搬モデルを当てはめることができる。スケールフリーネットワークとは頂点の次数分 布がべき則に従うモデルである。上述の情報伝搬モデルの一つとして、伝搬速度を限定した情 報伝搬モデルが考えられている[1]。伝搬速度を限定した情報伝搬モデルとは以下の条件を満た すモデルである。
1.情報を受け取った頂点は情報源となり隣接頂点に情報を流し続ける。 2.各情報源が単位時間に情報を渡せる頂点数は定数で限定されている。
3.各情報源頂点が隣接頂点から情報伝搬先頂点を選択する際に使える情報は隣接頂点の次数の みで，それ以外のネットワークの構造に関する情報や，隣接頂点がすでに情報を持っている
（情報源となっている）かどうかの情報は使用できない(頂点間で，情報を交換したり，共有 することもできない）。
このモデルに関して、次数相関を持たないネットワークならばReverse preferential controlと呼ば れる次数が少ない頂点に優先的に情報を流す方法により、ネットワークに情報が伝搬する平均 時間が最小になることが証明されている[1]。この事柄について、谷らはBAモデルと呼ばれる スケールフリーネットワーク生成法によりネットワークを生成し、シミュレーション結果を示 している[4]。
[4]谷聖一，枝國雄太，香取秀柄，逸見優聡，豊泉洋,"BA モデルにより生成されたネットワー クに対する伝搬速度 限定モデル情報伝搬シミュレーション", 第12回ネットワーク生態学シンポ ジウム
３．研 究 計 画 Research Planning
本研究では豊泉[1]の提案している情報伝搬モデルを発展させ、より現実に即したモデルを提案 し、かつその中で最適な情報伝搬方法は何かを探求する。
スケジュールは以下のように進める予定である。 3~7月
現在判明している疑問点・問題点
1.ネットワークがUncorrelated性を持つときは最も効率的な情報伝搬方法が存在するが、その性 質を持たない時の効率的な伝搬方法の存在は示されていない。
2.現実の人々は人それぞれの考え方を持って行動をすると考えられるため、一人一人の情報伝搬 戦略を考えなければ、現実との乖離が大きくなってしまう。
上述の疑問点・問題点を解決すべく、現実のネットワーク構造について調査を行うこと(twitter やfacebook等を参考にする)、また一人一人の戦略を細かく記述・分析することができるNon Linear Markov Processの知識の習得に努める。
8月
ゼミ合宿において進 状況の報告及び軌道修正を行う。
その後、より現実に即したネットワークで現実に近い人々の動きを組み込んだモデルを作成す る。
9~12月
情報拡散シミュレーションを行い効率的な情報伝搬方法の探求及び修士論文の執筆を行う。
