ネットワーク上を拡散する 技術革新のシミュレーション 日本大学文理学部 情報システム解析学科 谷研究室 安藤勇希 帆苅裕貴

Slides:



Advertisements
Similar presentations
最上 亮.  近年標的型と呼ばれるサイバー攻撃が増え、大 企業や、政府機関が情報窃取型の標的型メール 攻撃の被害を受けている。  標的型メール攻撃による個人情報漏えいは、企 業に莫大な損失を与えるとともに、信頼を失う。  現在サイバー攻撃における攻撃者、防御者の戦 略をゲーム理論的にモデル化する研究がおこな.
Advertisements

あみだくじ AMIDA-KUJI 井上 康博 Statistical analysis on Amida-kuji, Physica A 369(2006)
CMU2005 海外エンジニアリングワークショップ参加報告書 1 「真の要求を見極めろ!」: teamB 要求定義をどう捉えるか ● 要求定義とは何か? 製品には、顧客の望むことを正しく反映させる必要がある。 そのために必要なものが要求仕様である。 すなわち、要求仕様とは、顧客と製品を結ぶものであり、これを作ることが要求定義である。
ゲーム理論・ゲーム理論Ⅰ(第2回) 第2章 戦略形ゲームの基礎
セキュアネットワーク符号化構成法に関する研究
シミュレーション論Ⅰ 第13回 意思決定とシミュレーション.
© Yukiko Abe 2014 All rights reserved
実証分析の手順 経済データ解析 2011年度.
ゲーム理論・ゲーム理論Ⅰ (第6回) 第4章 戦略形ゲームの応用
Webネットワークにおける 研究者間の分析
伝播速度限定モデル Scale Free Network 上 の情報拡散 日本大学文理学部 情報システム解析学科 谷聖一研究室 古池 琢也
Scale Free Network 上における 伝播速度限定モデルの情報拡散シミュレーション
新ゲーム理論ゼミ 第5章 「繰り返しゲーム」 M1 松村 草也.
圧縮類似度を用いた方言の自動分類 ~ライス符号を用いた前処理~ ~連結クラスタリング法~ ~余弦類似度を用いた方言分類木の評価~
演習3 最終発表 情報科学科4年 山崎孝裕.
Reed-Solomon 符号と擬似ランダム性
神奈川大学大学院工学研究科 電気電子情報工学専攻
ソシオン理論における 三者関係のシミュレーション
法と経済学(file 6) ゲーム理論2 今日の講義の目的 (1)展開型ゲームという考え方を理解する (2)後方帰納法の考え方を理解する
10.Private Strategies in Games with Imperfect Public Monitoring
先端論文紹介ゼミ Role-based Context-specific Multiagent Q-learning
政策決定のプロセス 政策過程論 公共選択 ゲームの理論.
第2章補足Ⅱ 2項分布と正規分布についての補足
初級ミクロ経済学 -ゲーム理論入門- 2014年12月15日 古川徹也 2014年12月15日 初級ミクロ経済学.
ランダムウォークに関するいくつかの話題 ・ランダムウォークの破産問題 ・ランダムウォークの鏡像原理 1 小暮研究会Ⅰ 11月12日
日本大学 文理学部 情報システム解析学科 谷研究室 益田真太郎
集団における適応 知識構造論講座 下嶋研究室          M1 関本 和弘.
ストークスの定理と、 渦度・循環の関係を 直感で理解する方法
慶應義塾大学経済学部 グレーヴァ香子 Takako Fujiwara-Greve
新ゲーム理論 第Ⅰ部 非協力ゲームの理論 第1章 非協力ゲームの戦略形
第13章 フォンノイマン/モルゲンシュテイン解
シミュレーション論Ⅰ 第11回 意思決定とシミュレーション.
パソコンでゲームの理論 第1,2章 ゼロ和2人ゲーム ゼミ合宿 東京理科大学理学部第2部数学科・統計学ゼミ
第Ⅱ部 協力ゲームの理論 第9章 シャープレイ値.
シミュレーション論 Ⅱ 第14回 まとめ.
シミュレーション論 Ⅱ 第15回 まとめ.
応用社会システム計画 (第10回) ここで、学習すること 学籍番号: 氏名: ■これまでの講義内容の整理 ■計画問題の設定と手法
シャノンのスイッチングゲームにおけるペアリング戦略の複雑さについて
独立成分分析 1.問題は何か:例:解法:全体の見通し 2007/10/17 名雪 勲.
論文紹介 Query Incentive Networks
米山研究室紹介 -システム制御工学研究室-
卒論の書き方: 参考文献について 2017年9月27日 小尻智子.
強化学習を用いたバックギャモンプレイヤーの生成 TD-Gammon
社会シミュレーションのための モデル作成環境
4人版リバーシYoninの解析 情報論理研究室 藤本 侑花
意外と身近なゲーム理論 へなちょこ研究室 p.
25. Randomized Algorithms
計測工学 -誤差、演習問題 計測工学(第6回) 2009年5月26日 Ⅱ限目.
Webネットワークにおける 研究者間の分析
所属集団の変更できる社会的ジレンマ実験について2
様々な情報源(4章).
部分的最小二乗回帰 Partial Least Squares Regression PLS
ウィルスって どの位感染しているのかな? 菊池研究室  小堀智弘.
1:Weak lensing 2:shear 3:高次展開 4:利点 5:問題点
近畿大学 理工学部 情報学科 情報論理工学部研究室 潘小月
構造的類似性を持つ半構造化文書における頻度分析
設計情報の再利用を目的とした UML図の自動推薦ツール
Max Cut and the Smallest Eigenvalue 論文紹介
第Ⅱ部 協力ゲームの理論 第14章 交渉集合.
岩手県立大学ソフトウエア情報学部 3年 鈴木研究室所属 井ノ上 憲司
情報工学科 4年 中山直飛 中間発表.
or-8. ゲーム理論 (オペレーションズリサーチを Excel で実習するシリーズ)
囚人のジレンマ ―― 裏切りのインセンティブ ――
ベイジアンネットワーク概説 第3章 ベイジアンネットワークモデルの 数学的基礎 3.1 ベイジアンネットワークモデルの概要
第Ⅰ部 非協力ゲームの理論 第6章 情報の価値 2008/07/01(火) ゲーム理論合宿 M2 渡辺美穂.
ゲーム理論 ー 駆け引きの科学 - (1) 戦略形のゲーム
Speaker: Kazuhiro Inaba Paper Introduction from WSDM 2015
情報処理の概念 #0 概説 / 2002 (秋) 一般教育研究センター 安田豊.
シミュレーション論Ⅱ 第2回 モデル化の手法.
プログラム依存グラフを用いた ソースコードのパターン違反検出法
Presentation transcript:

ネットワーク上を拡散する 技術革新のシミュレーション 日本大学文理学部 情報システム解析学科 谷研究室 安藤勇希 帆苅裕貴 谷研究室 安藤勇希      帆苅裕貴

目次 --はじめに-- 1.背景 1-1.ウィルスの伝播 1-2.技術革新の伝播 1-3.ゲーム理論について 2.先行研究  1-2.技術革新の伝播   1-3.ゲーム理論について 2.先行研究  2-1.ゲーム理論を用いた技術革新の伝播 --研究項目-- 3.研究概要 4.今後の目標 5.結論

背景 世界は様々なネットワークで構築されている ネットワークとは節点(ノード)と経路(リンク 又はエッジ)からなり、流れ(フロー)があるも の 例:インターネット、人間関係、道路...etc その上で色々な情報・要素が流れている

では、ネットワーク上での情報・要素の伝播は どうなっているのか 一部の例をあげて考えてみる 背景 では、ネットワーク上での情報・要素の伝播は どうなっているのか 一部の例をあげて考えてみる

②感染源に接触した人にウィルスが感染(知り合 いのみとし、接触しても必ずしも感染するとは限 らない) 背景 例 ウィルスの感染 ①感染源が出現(ここでは1人のみとする) ②感染源に接触した人にウィルスが感染(知り合 いのみとし、接触しても必ずしも感染するとは限 らない) ③感染者と接触した人にウィルスが感染

と、でき、グラフを使って表すことができる 背景 この伝播を数学的に捉えると 感染源・接触者 → ノード 接触(知り合い)→ エッジ ウィルス → 要素・情報 と、でき、グラフを使って表すことができる 

背景 例:ノード数8,エッジ数10のグラフでウィルス の伝播を表していく 今回は病気が治るということは考えない A C H E G F B D

背景 感染源:A 伝播規則:感染しているノードに隣接している ノードは確率1 / 2 で感染 A C H E G F B D 感染 未感染

背景 A C H E G F B D 感染 未感染

背景 A C H E G F B D 感染 未感染

背景 A C H E G F B D 感染 未感染

背景 A C H E G F B D 感染 未感染

背景 A C H E G F B D 感染 未感染

背景 技術革新の伝播について 技術革新は必ずしも取り入れる訳ではない 広まらない技術革新もある 既存の技術の方が使われているということも多々 ある その例をあげてみる

背景 例として、ドリームキャストの普及について考え る 最初の頃は賑わいを見せたが、PS2が普及するに あたって衰退していき、普及しなくなった

背景 始点:A 伝播規則:技術革新を取り入れているノードに隣 接しているノードは確率1 / 2 で技術革新を取り入 れる 技術革新 C H E G F B D 技術革新 既存の技術

背景 A C H E G F B D 技術革新 既存の技術

背景 A C H E G F B D 技術革新 既存の技術

背景 A C H E G F B D 技術革新 既存の技術

背景 ここまでの伝播の例はランダムで伝播していく というものだったが、 それでは人間関係というモデルを使用するには、 欠如してくるもの(感情や環境など)が出てくる そこで今回はゲーム理論を使うことにした

ある特定の条件下において、お互いに影響 を与え合う複数のプレイヤーの間で生じる 戦略的な相互関係を研究する数学の分野 ゲーム理論とは ある特定の条件下において、お互いに影響 を与え合う複数のプレイヤーの間で生じる 戦略的な相互関係を研究する数学の分野

ゲームで一般的に定義するもの 1.ゲームを支配するルール 2.ゲームにおける目的達成のための戦略の意思決 定をおこなうプレイヤー 3.プレイヤーの選択可能な戦略 4.プレイヤーの意思決定を左右する情報

ゲームの一例 ここでのゲームは将棋 対局する2人のプレイヤーがいる 各プレイヤーは全ての駒のとりうる行動を計算可 能であり、お互い全ての駒の配列情報がわかる環 境にあり、偶発的な事象はおこらない。

ゲーム理論の分析 戦略的な状況における未来の行動を予測したり、 過去の行動を客観的に評価することを目的として いる。 各プレイヤーの行動が相互の利害に影響すること を考慮しなければならない。つまり、プレイヤー Aはある行動を選択する前に、自分の利益を最大 にするためには相手プレイヤーBが敵対的な行動 に出ることを考慮しなければならない。

共同に犯罪を行った2人が捕まった 警察はこの犯罪の証拠が少ないため2人に司法取 引する 囚人のジレンマの問題 共同に犯罪を行った2人が捕まった 警察はこの犯罪の証拠が少ないため2人に司法取 引する

囚人のジレンマの解説1 囚人2人にとってお互いが自白して10年ずつより も、お互いが黙秘して2年ずつが得である。 しかし、囚人が自分の利益のみを追求すると お互いが自白してしまう結果になる。

囚人のジレンマの解説2 囚人Aの行動と考えは 1.囚人Bが黙秘した場合、囚人Aは黙秘すると2年 、自白すると1年なので「自白」が得

囚人のジレンマの解説3 囚人Bも同じ考えをもつので 囚人2人はどちらも「自白」してしまう。 しかし、ゲーム全体とすればお互いが「黙秘」が 最適な戦略だったはずなので囚人は最適な選択を 達成していないことがジレンマとなる。

ゲーム理論を用いた技術革新の伝搬1 On the Spread of Innovations in Social Network という論文がゲーム理論を用いた技術革新の伝搬 を紹介している ゲーム理論を用いることで起点が周囲のノードの 影響を受けて戦略を決めることができる

新しい技術を取り入れるのが得であることは明確 だが人間は周囲の状況を見て行動の判断をする よって技術革新の伝搬をゲーム理論で表していく ゲーム理論を用いた技術革新の伝搬2 新しい技術を取り入れるのが得であることは明確 だが人間は周囲の状況を見て行動の判断をする よって技術革新の伝搬をゲーム理論で表していく

先行研究 ここでは技術革新(新しい技術)を{+1}、既存の技 術を{-1}とする 一般例だと、スマフォを使うことが{+1}、ガラ ケーを使っていることが{-1}

先行研究 定義① |V|=n とプレイヤーの集合Vの間で、T=1,2,3...の 時間で試行される 各プレイヤーi∈Vはx∈{+1,-1}の二つの戦略を持つ 利得行列Aは2*2の行列 iの利得はΣj∈N(i) A(xi, xj) ,N(i)は隣り合うノード iは隣り合うノードと同じ戦略を取ればより高い 利得を得るので、a>d,b>c (a-d)|N+(i)| ≧ (b-c)|N-(i)| の場合iは+1であり、それ 以外の場合は-1 ++ a - + c + - d - - b

先行研究 定義② h = a-d-b+c / a-d+b-c , hi = h |N(i)| 符号の式:hi + Σj∈N(i)xj ノイズとは人と人の間を伝播するにあたって、感 情や環境によって合理的な判断をしない場合のモ デル βはノイズを表す(0≦β) βが無限に近づくほどノイズフリーになる T+:全てのノードが{+1}になった時の時間

e^β(hi + Σj∈N(i)xj) + e^-β(hi + Σj∈N(i)xj) 先行研究 【式①】piβ(yi | xN(i)) = e^βyi(hi + Σj∈N(i)xj) ——————————————————— e^β(hi + Σj∈N(i)xj) + e^-β(hi + Σj∈N(i)xj) β=0の時,上式=1 / 2 β = ∞ の時,上式= 1 となるので,確率は1/2~1となる

先行研究 定義に沿って先ほどのグラフを使って 簡単に流れを説明していく まず全体に{+1,-1}を入れていく

先行研究 始点:A β = 0 ≦ x , β ≠ ∞ 伝播規則:隣接するノードの戦略を見て、自分が より高い利得を得る戦略を取る(式①に基づいた 確率で戦略を取る) A C H E G F B D T = 0 {+1} {-1}

先行研究 A C H E G F B D T = 1 {+1} {-1}

先行研究 A C H E G F B D T = 2 {+1} {-1}

先行研究 A C H E G F B D T = 3 {+1} {-1}

先行研究 T+:全てのノードが{+1}になった時の時間 A C H E G F B D T = 4 = T+ {+1} {-1}

研究概要 シミュレーションをするためまずはグラフを生成 する 今回はスケールフリーグラフ(BAモデル)で作る ことにした

グラフ作成でスケールフリー性を 採用する理由 人間関係では知り合いが多い人少ない人がいて 1人の影響する人数が変わってくる よって人間関係はスケールフリー性になる なのでスケールフリーのグラフでシュミレーショ ンをすることにする

スケールフリーの生成

今後の目標 Gephiで作成したスケールフリーグラフの数値を 抽出して、作成したプログラムに入れ、ノイズを 変えてシミュレートする

結論 参考にした論文の証明ができる 技術革新の伝播にゲーム理論を用いることができ ることが分かる