ネットワーク上を拡散する 技術革新のシミュレーション 日本大学文理学部 情報システム解析学科 谷研究室 安藤勇希 帆苅裕貴 谷研究室 安藤勇希 帆苅裕貴
目次 --はじめに-- 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で作成したスケールフリーグラフの数値を 抽出して、作成したプログラムに入れ、ノイズを 変えてシミュレートする
結論 参考にした論文の証明ができる 技術革新の伝播にゲーム理論を用いることができ ることが分かる