Scale Free Network 上における 伝播速度限定モデルの情報拡散シミュレーション

Presentation on theme: "Scale Free Network 上における 伝播速度限定モデルの情報拡散シミュレーション"— Presentation transcript:

1 Scale Free Network 上における 伝播速度限定モデルの情報拡散シミュレーション
日本大学文理学部 情報システム解析学科 谷聖一研究室 古池 琢也 ・

2 Scale Free Network 上における 伝播速度限定モデルの 情報拡散シミュレーション
目次 １章　はじめに ２章　グラフ理論の概要 ３章　Scale Free Network ４章　修正版BAモデル ５章　伝播規則 ６章　実験方法 ７章　実験結果 ８章　考察 ９章　課題 ・このような順番で話していく。

3 第１章 はじめに ネットワークの研究 広範囲の分野において行われており，現実世界の 様々な問題を説明する新たな枠組みとして注目
第１章　はじめに ネットワークの研究 広範囲の分野において行われており，現実世界の 様々な問題を説明する新たな枠組みとして注目 効率良くネットワーク上に情報を広めることは重要な課 題であり，モデル化することで，数理的解析が可能とな る 　 　　・病気の流行，噂..etc ・

4 第１章 はじめに ネットワークの情報伝播において 情報がネットワーク全体に 行き渡るまでの時間は 情報を伝える頂点を選択する方法に依存
第１章　はじめに ネットワークの情報伝播において 情報がネットワーク全体に 行き渡るまでの時間は 情報を伝える頂点を選択する方法に依存 　どのように情報を伝える頂点を選べば 　効率よく情報を伝播できるか ・twitter や Facebook　噂、ニュース 　短時間に広範囲に伝わる。 ・〜が問題となってくる。

5 Reverse preferential spread
第１章　はじめに 2012年 Phys. Rev. E 86, (2012) Hiroshi Toyoizumi, Seiichi Tani , Naoto Miyoshi, Yoshio Okamoto Reverse preferential spread in complex networks ある仮定をもとに，数学的に厳密に解析し証明 ・このような論文が発表された ・情報を１単位時間に 　１つの隣接頂点にのみ 　情報を伝えられる伝播速度限定 伝播速度限定モデルでは，次数が小さい頂点に優先的に伝播 無駄な伝播が少なく，効率よく発散

6 第１章 はじめに 2011年度卒業生 伝播速度限定モデルを用いて 情報伝播シミュレーション
第１章　はじめに 2011年度卒業生　　 伝播速度限定モデルを用いて 　　　　情報伝播シミュレーション 生成したネットワークのスケールフリー性 シミュレーションアルゴリズムの妥当性 仮定の妥当性 次数が小さい頂点を優先的に伝播する方法が最も効 率のよい方法だという結果が得られなかった ・論文で主張されていた ・〜が考えられる。 などの原因が挙げられる

7 第１章 はじめに 2011年度卒業生 伝播速度限定モデルを用いて 情報伝播シミュレーション
第１章　はじめに 2011年度卒業生　　 伝播速度限定モデルを用いて 　　　　情報伝播シミュレーション 生成したネットワークのスケールフリー性 シミュレーションアルゴリズムの妥当性 仮定の妥当性 次数が小さい頂点を優先的に伝播する方法が最も効 率のよい方法だという結果が得られなかった ・そこで、今回私は〜に着目 などの原因が挙げられる

8 第１章 はじめに 本演習 情報を伝播するシミュレーションを行うプログラムを作成 伝播時間を測定
第１章　はじめに 本演習 情報を伝播するシミュレーションを行うプログラムを作成 　　伝播時間を測定 実験で用いたネットワークは共有 スケールフリー性が有するのが判定されたネットワークを 使用 ・再実験

9 第２章 グラフ理論の概要 グラフ理論の用語 頂点、ノード：ネットワークにある点 枝 ：頂点を結ぶ線分 次数：頂点から出ている枝の個数
第２章　グラフ理論の概要 グラフ理論の用語 頂点、ノード：ネットワークにある点 　　　　枝　：頂点を結ぶ線分 １本の枝は２つの頂点をつなぐ 枝で直接結ばれる２頂点は隣接しているという 　　　次数：頂点から出ている枝の個数 　１つのネットワークは、 いくつかの頂点といくつかの枝から成る ・田中　説明　簡単に述べる

10 第３章 Scale Free Network 今演習では、Scale Free Network を用いる
ネットワーク上の次数分布　べき則 べき則とは、 P(k) ∝ k ,(γ > 0) (∝は比例を表し，γはべき指数と呼ぶ) ・べき則について簡単に言う。 　例　Facebook 　一部の人は、多くの友人と 　繋がっているが、 　大部分の人は、小数の人としか 　繋がっていない状況が 　見受けられる。 -γ

11 第３章 Scale Free Network Scale Free Network
一部の頂点が他のたくさんの頂点と枝で繋がっており， 大きな次数を持っている一方で，大多数の頂点はごく わずかな頂点としか繋がっておらず，次数は小さいという 性質をもつネットワーク ・よって、〜。

12 第４章 修正版BAモデル 1999年 Barabasi, Albert が提案した
成長： 時間とともに頂点と枝が増えること 優先的選択： 新しく加わった頂点と結びつく頂点は，その時点で次数 が高い頂点が選ばれやすい ・〜を参考にしました。 ・今演習では、 　このBAモデルを簡略化し、 　１本ずつ枝を追加する 　修正版BAモデルを用いた。

13 第４章 修正版BAモデル グラフ生成 枝を保有しない既存のノードが１つ存在する 既存のグラフに対して，頂点を１つ追加する
既存の頂点を１つ選択し，追加頂点から枝をはる 頂点が選択される確率は頂点の次数に比例 以後，２と３を繰り返す ・ネットワークを生成する 　手順の説明。 ・設定した頂点数に 　なるまで繰り返します。

14 第５章 伝播規則 ソースノード： 情報を保持し，情報を発信する頂点 ターゲットノード：
第５章　伝播規則 ソースノード： 情報を保持し，情報を発信する頂点 ターゲットノード： ソースノードが情報を渡す際に，伝播方法によって選ば れた頂点 ・シュミレーションで 　扱う単語の説明。

15 第５章 伝播規則 初期状態 ネットワークの頂点はすべて情報を持っていない
第５章　伝播規則 初期状態 ネットワークの頂点はすべて情報を持っていない ソースノードには隣接頂点の次数だけわかっていて，隣 接頂点がすでに情報を受け取っているかの知識はもって いないとする ・

16 第５章 伝播規則 伝播規則 各ソースノードは，１単位時間に隣接頂点の１つを ターゲットノードとして選択し，情報を伝播
第５章　伝播規則 伝播規則 各ソースノードは，１単位時間に隣接頂点の１つを ターゲットノードとして選択し，情報を伝播 各ソースノードが，ターゲットノードを選択する際，ター ゲットノードを重複して選ばれる場合がある ・すでに情報を受け取った 　頂点にさえ 　情報を送る可能性がある。

17 第５章 伝播規則 伝播規則 情報を受け取った頂点は，新たにソースノードとなり， 隣接頂点の中からターゲットノードを選択する
第５章　伝播規則 伝播規則 情報を受け取った頂点は，新たにソースノードとなり， 隣接頂点の中からターゲットノードを選択する 一度ソースノードとなった頂点は，隣接頂点に情報を 発し続ける ・

18 第５章 伝播規則 ターゲットノードの選び方 等確率で選択する方法 頂点の次数に比例した選び方 (次数が高い頂点を優先的に選択する方法)
第５章　伝播規則 ターゲットノードの選び方 等確率で選択する方法 頂点の次数に比例した選び方 (次数が高い頂点を優先的に選択する方法) 頂点の次数の逆数に比例した選び方 (次数が低い頂点を優先的に選択する方法) 　の３つの伝播方法を用いる。 ・ここでは、伝播方法について

19 第５章 伝播規則 ｑ ｑ = 等確率でターゲットノードを決める 隣接頂点 b がターゲットノードとなりえる確率 ｂ １ b
第５章　伝播規則 等確率でターゲットノードを決める 隣接頂点 b がターゲットノードとなりえる確率 ｑ ｂ ・はじめに ・確率の計算の仕方 １ ｑ = b ソースノードの次数

20 第５章 伝播規則 等確率でターゲットノードを決める ・例をあげて説明。 ソースノード 10 ターゲットノード 2 8
第５章　伝播規則 １ ソースノードの次数 等確率でターゲットノードを決める ソースノード 10 ターゲットノード 2 8 2 が選ばれる確率　1 / 3 3 が選ばれる確率　1 / 3 4 が選ばれる確率　1 / 3 1 3 1 7 1 ・例をあげて説明。 4 6 9 5

21 第５章 伝播規則 等確率でターゲットノードを決める ・例をあげて説明。 ソースノード 10 ターゲットノード 2 8
第５章　伝播規則 １ ソースノードの次数 等確率でターゲットノードを決める ソースノード 10 ターゲットノード 2 8 2 が選ばれる確率　1 / 3 3 が選ばれる確率　1 / 3 4 が選ばれる確率　1 / 3 1 3 1 7 1 ・例をあげて説明。 4 6 9 5

22 第５章 伝播規則 等確率でターゲットノードを決める ・ ソースノード 10 ターゲットノード 2 8 2 が選ばれる確率 1 / 3
第５章　伝播規則 等確率でターゲットノードを決める ソースノード 10 ターゲットノード 2 8 2 が選ばれる確率　1 / 3 3 が選ばれる確率　1 / 3 4 が選ばれる確率　1 / 3 1 3 1 7 1 ・ 4 6 9 5

23 第５章 伝播規則 ｑ ｑ = 頂点の次数に比例した選び方 隣接頂点 b がターゲットノードとなりえる確率 ｂ ターゲットノードに
第５章　伝播規則 頂点の次数に比例した選び方 隣接頂点 b がターゲットノードとなりえる確率 ｑ ｂ ターゲットノードに 　　　　なりえる頂点の次数 ・次に ｑ = b ソースノードの隣接頂点 　　　　　　　の次数の合計

24 第５章 伝播規則 頂点の次数に比例した選び方 ・ ソースノード 10 ターゲットノード 2 8
第５章　伝播規則 ターゲットノードになり える頂点の次数 ソースノードの隣接頂点の次 数の合計 頂点の次数に比例した選び方 ソースノード 10 ターゲットノード 2 8 2 が選ばれる確率　2 / = 2 / 9 3 が選ばれる確率　4 / = 4 / 9 4 が選ばれる確率　3 / = 3 / 9 1 3 1 7 1 ・ 4 6 9 5

25 第５章 伝播規則 頂点の次数に比例した選び方 ・ ソースノード 10 ターゲットノード 2 8
第５章　伝播規則 頂点の次数に比例した選び方 ソースノード 10 ターゲットノード 2 8 2 が選ばれる確率　2 / = 2 / 9 3 が選ばれる確率　4 / = 4 / 9 4 が選ばれる確率　3 / = 3 / 9 1 3 1 7 1 ・ 4 6 9 5

26 第５章 伝播規則 ｑ ｑ = 頂点の次数の逆数に比例した選び方 隣接頂点 b がターゲットノードとなりえる確率 ｂ ターゲットノードに
第５章　伝播規則　 頂点の次数の逆数に比例した選び方 隣接頂点 b がターゲットノードとなりえる確率 ｑ ｂ ターゲットノードに 　なりえる頂点の次数の逆数 ・ ｑ = b ソースノードの隣接頂点 　　　　の次数の逆数の合計

27 第５章 伝播規則 頂点の次数の逆数に比例した選び方 ・ ソースノード 10 ターゲットノード 2 8 2 が選ばれる確率 1 / 2 6
第５章　伝播規則 ターゲットノードになりえる頂点 の次数の逆数 ソースノードの隣接頂点の次数 の逆数の合計 頂点の次数の逆数に比例した選び方 ソースノード 10 ターゲットノード 2 8 2 が選ばれる確率　 1 / 1 / / / 3 が選ばれる確率 1 / 4 が選ばれる確率　 1 / 1 3 1 = 1 7 ・ 4 = 6 9 5 =

28 第５章 伝播規則 頂点の次数の逆数に比例した選び方 ・ ソースノード 10 ターゲットノード 2 8 2 が選ばれる確率 1 / 2 6
第５章　伝播規則 頂点の次数の逆数に比例した選び方 ソースノード 10 ターゲットノード 2 8 2 が選ばれる確率　 1 / 1 / / / 3 が選ばれる確率 1 / 4 が選ばれる確率　 1 / 1 3 1 = 1 7 ・ 4 = 6 9 5 =

29 第６章 実験方法 頂点数： 1000, 10000 ネットワーク個数：それぞれ 100 個 シミュレーション回数：
第６章　実験方法 頂点数：　1000, 10000 ネットワーク個数：それぞれ 100 個 シミュレーション回数： 各ネットワークに対して 50 回 乱数の種 50 個設定 一回のシミュレーションが終わるまで、 同じ伝播方法を用いる ・

30 第６章 実験方法 シュミレーション方法 ランダム選択を行う際に rand 関数を用いる。 ・ 乱数生成の種を設定 等確率で選択する方法
第６章　実験方法 シュミレーション方法 ランダム選択を行う際に rand 関数を用いる。 乱数生成の種を設定 等確率で選択する方法 ・ 次数に比例した選び方 次数の逆数に比例した選び方

31 第６章 実験方法 シミュレーションアルゴリズム 1. ネットワーク上からランダムにソースノードを１つ選択する
第６章　実験方法 シミュレーションアルゴリズム 1. ネットワーク上からランダムにソースノードを１つ選択する 2. 各ソースノードが情報を伝えるターゲットノードをそれぞれ１つ 選択し，情報を伝達する 全ソースノードが同時に行う この回数を 1 ステップとする 3. ネットワーク上のすべての頂点がソースノードとなると終了 ・

32 第７章　実験結果 頂点数 の異なる５つのネットワーク ・

33 第７章　実験結果 頂点数 の異なる５つのネットワーク ・初めは効率よく 　全体に伝わるまでには 　時間がかかったことがわかる。

34 第７章　実験結果 頂点数 の異なる５つのネットワーク ・最も効率も悪い

35 第７章　実験結果 １つの図にまとめると ・結果が明らか。

36 第７章　実験結果 頂点数 の同じネットワークで異なる種 ・情報が広がっている 　ほぼ同じように伝播されている

37 第７章　実験結果 頂点数 の同じネットワークで異なる種 ・同じ動き

38 第７章　実験結果 頂点数 の同じネットワークで異なる種 ・次数が高い頂点(ハブ) 　に伝わりにくい 　それが影響している

39 第８章　考察 論文と相反する結果が得られた 原因として... 頂点数の問題 修正版BAモデルでは成り立たない 仮定の妥当性 ・

40 第８章 考察 頂点数の問題 さらに，頂点数を増やせばどうなるのか？ ・ある程度伝わったら、横伸びで 最後の頂点に伝わるのに 時間がかかる
第８章　考察 頂点数の問題 ・ある程度伝わったら、横伸びで 　最後の頂点に伝わるのに 　時間がかかる ・それに比べて、突き刺さるように 　伝播が終わっている 　頂点数を増やせば 　傾きを保ったまま、効率の良い 　余地があると考える さらに，頂点数を増やせばどうなるのか？

41 第８章 考察 修正版BAモデルでは成り立たない 修正版BAモデル 木構造 現実世界ではクラスターが 形成されることが多い クラスター
第８章　考察 修正版BAモデルでは成り立たない 修正版BAモデル　　　　木構造 現実世界ではクラスターが 形成されることが多い クラスター 「自分の知人の知人が、実は自分の直接の知人だっ た」 情報を伝播する経路も多い！ ・経路が限られてくる。 ・ハブに伝わりやすくなる ・ハブに情報を伝えるまでの 　ステップは、余計な伝播

42 第９章　課題 今後の目標 頂点数の変更 現実世界に近いネットワーク 伝播規則の変更 ・

43 第１章　はじめに　　

44 第２章　グラフ理論の概要　　

45 第３章　Scale Free Network　　

46 第４章　修正版BAモデル　　

47 第５章　伝播規則　　

48 第６章　実験方法　　

49 第７章　実験結果　　

50 第８章　考察　　

51 第９章　課題　　

52 ご清聴ありがとうございました。

53 第１章 はじめに ネットワーク 日常用語としてはインターネットの意味で用いられること が圧倒的に多いが...。 つながり全般 ・人間関係
第１章　はじめに ネットワーク 日常用語としてはインターネットの意味で用いられること が圧倒的に多いが...。 つながり全般 　　　　　　　　　　・人間関係 　　　　　　　　　　・食物網 　　　　　　　　　　・道路網

54 第１章 はじめに ネットワークの対象は、点が線で結ばれた下図のようなも の。 例１：点を人、線を二者間の交友関係とすれ ば、人間関係。
第１章　はじめに ネットワークの対象は、点が線で結ばれた下図のようなも の。 例１：点を人、線を二者間の交友関係とすれ　　　 ば、人間関係。 例２：点を駅、線を線路とすれば、鉄道網。

55 第３章 Scale Free Network べき則のグラフ 例：地震の規模 ｘ軸…震度 ｙ軸...場所の数
　ｘ軸…震度 　ｙ軸...場所の数 ja.wikipedia.org

56 第４章　修正版BAモデル 1999年にバラバシ(Barabasi)とアルバート(Albert)が、ス ケールフリー性が実現されるネットワークのモデル(BAモデ ル)を提案。 BAモデルの２つの特徴 成長 優先的選択

57 第４章　修正版BAモデル 成長の際、一度に２本以上の辺を追加するとその辺の 接続先を独立的に選ぶことができなくなり、扱うのが難し くなってしまう。 今研究では、毎回１本ずつ辺が追加される修正版BA モデルで生成した Scale Free 性のネットワークでシュミ レーションを行う。

58 第４章　修正版BAモデル １step ２ １ 1 / 1

59 第４章　修正版BAモデル ２step ２ 1 / 2 １ 1 / 2 3

60 第４章　修正版BAモデル ３step 4 ２ 2 / 4 １ 1 / 4 3 1 / 4

61 第４章　修正版BAモデル ４step 1 / 6 4 ２ 3 / 6 １ 5 1 / 6 3 1 / 6

62 第４章　修正版BAモデル ５step 1 / 8 4 ２ 6 4 / 8 １ 5 1 / 8 1 / 8 3 1 / 8

63 第４章　修正版BAモデル ６step 2 / 10 4 ２ 6 4 / 10 1 / 10 １ 5 7 1 / 10 1 / 10 3 1 / 10

64 第４章　修正版BAモデル ７step 2 / 12 4 8 ２ 6 5 / 12 1 / 12 １ 5 7 1 / 12 1 / 12 3 1 / 12 1 / 12

65 実際に論文を細部まで解析する必要がある。
第８章　考察 仮定は正しかったのか。 近似はどの程度妥当だったのか。 実際に論文を細部まで解析する必要がある。

66 第７章 これから 生成するグラフの頂点数をどれくらいに設定すれば良い か、具体的に考える。
第７章　これから 生成するグラフの頂点数をどれくらいに設定すれば良い か、具体的に考える。 １つのネットワークに関して、何回シュミレーションを行え ば、正確なデータを得られるか考える。 実際に、実験を開始する。 実験から得られたデータから、考察。 伝播規則の変更。