平成 12 年度副テーマ

ネットワークグラフモデルの伝播性に関する Javaシミュレーション

知識科学研究科学籍番号 050016

大久保和彦

2001 年 2 月 28 日 (水)

目次

1 はじめに 2 2 伝播モデルの構成 2

2.1 ランダムモデル . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.2 Web モデルについて . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

3 研究内容および方法 4 3.1 内容 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3.2 方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

4 結果 5 4.1 ランダムモデル . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 4.2 Zipf の法則 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4.3 Web モデル . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

5 考察 13 6 結論 14 7 おわりに 14

1 はじめに

社会における集団あるいは組織は情報処理能力を備えているという。情報を処理するということには、伝達・保存・加工という３つがある。このうち本研究では情報の伝達に関して考えていくことにする。情報の伝播には大きく分けて 2 種類がある。一つは組織における情報の伝播である。そこでは情報が伝播する系統が整っており情報が流れる順序は規則正しく上から下、下から上へ伝播していくものである。もう一つは組織的なものを持たず形式的なルートなどが存在しない情報の伝播である。社会における情報の伝播の多くはこのような組織的な形をとらないものである。流言やうわさなどは、この形態で広まっていくと考えられる。うわさなどの情報が伝播するときには、伝える側と伝わる側の間には差異がなく (権威などには関係なく) すべてが均質なものとみなすことができる。つまりここでは、情報の量と質が変化せずに集団の中を伝播していくと考えるのである。このような非組織集団のなかでの情報の伝播に関しては、金沢工業大学の蜷川ら (2000) によってランダムなネットワークモデルでの研究がなされている。それによると、ランダムなネットワークで情報を伝播させると、一つの要素 (ノード) に対して約 3 本の弧 (エッジ) を持つと、そのノードが属する系全体に蔓延させることが明らかになっている。またその系は、スケールに対する依存性も持っていないとなっている。しかしこのモデルでは時間的な伝播についての変化は述べられていないので情報がどのように伝播していくかが定かではない。そこで本研究では、このランダムなネットワークモデルの伝播性についての時間変化を見ることで時間変化における特徴を見る。さらにランダムなネットワークだけでなく、より現実的なモデルとして、 Web においてのネットワークモデルについて取り上げて、同様な検証を行う。ランダムなネットワークモデルと Web のネットワークモデルにおける特徴を比較することでそれぞれの特徴を見出すことがねらいである。

2 伝播モデルの構成

2.1 ランダムモデル

ある集団において情報が伝播する場合、その集団がまず N 個の要素から成り立っていると考える。この N 個からなる系の各々の要素 (ノード) に対してまず 1, 2, …N と番号をつけておく。各ノードは 0， 1 いずれかの状態を持っている。あるノードに情報が伝播してなければ 0 とし、情報が伝われば 1 としこのノードに対して情報が伝播したこととする。またノード i が点ノード j に対して情報を伝えるときノード i からノード j へのエッジ (i,j) として表現をする。これによってエッジは方向性をもつことになる。したがって (i,j) はあっても (j,i) があるとは限らない。ランダムなネットワークモデル (ランダムモデル) はこのエッジの生成においてがすべてランダムである。実際に伝播する様子は次のように考える。情報は連続した時間の中で進むが、ここでは離散的に時間が進むとする。ステップ０ (伝播開始状態) では、情報は一つのノードだけが知るもの (情報の発信源) とし、そのノードだけ状態を１とする。次のステップでは、つながっているすべてのノード (エッジの方向性にしたがって) の状態を１とする。以降のステップはこれの繰り返しとする。但し、一度状態が１となったものは常に状態を１とする。伝播したノード数 (伝播数) が、一定の値 (定常状態) になったら伝播を終了する。

図 1: Zipf の法則

2.2 Web モデルについて

Web のネットワークモデル (Web モデル) については、 Ravi Kamar ら (1999) による (α, β) モデルの特徴として、系におけるノードとそれが持つエッジの間には Zipf の法則 (図 1) と言われる関係があることが明らかになっている。それによると、ノードとノードから出て行くエッジ (Outdegree) には Log スケールにして‐ 2.38 の傾きがあり、入ってくるエッジ (Indegree) には同スケールで −2.10 の傾きがあることが経験的に求められている。つまりエッジをあまり持っていないノードは多くて、エッジを多く持っているノードの数は少なくなるという法則である。今回このモデルを実現させるために、次のような手順でモデルの生成を行った。 N 個のノード数をもつ系を作る場合、まず一つずつノードを生成させる。このときにエッジも生成する。その際エッジの生成には �新しく追加されたノードの自己ループ �新しいノードから古いノードへのエッジ �古いノードから新しいノードへのエッジ �古いノードから古いノードへのエッジ 4 種類の生成の仕方がある。この 4 種類がそれぞれ確率的に選び出されるようにしてある。�〜�に関してエッジが張られる方を選び出す際、系の中でエッジを多く持つものが選ばれやすくなるようにするため、選び出す確率をエッジを多く持つものは高く、エッジをあまり持たないものは低くなるように振り分ける。但し、エッジを持たないものにも振り分けられる可能性を残すためにすべてのノードが必ず 1 本は持つような状態に設定した上で選び出す。こうすることでエッジを持つものはさらに多く持つような構造に発展し Zipf の法則にのるモデルになる。モデルを生成した後の情報の伝播、停止などの判定の仕方はランダムモデル場合と同じとする。したがって、完全にモデルの構造上の違いだけを比較できることになる。

3 研究内容および方法

3.1 内容

ランダムモデルと Web モデルを生成し、それぞれに情報を伝播させたときの時間変化などの特性について比較する。

3.2 方法

本研究は、 Java 言語を用いたシミュレーションを行うことによってモデルの検証をする。ノード数は 500、 1000 の 2 種類によって同様のシミュレーションを行うことで比較をする。情報の伝播においてのランダムモデルの形成、伝播したとの判定方法などのプログラムは、蜷川ら (2000) の研究で用いた方法で行う。その際、伝播する過程がどのように時間的変化をするのかを知るために、ステップごとに伝播している伝播数を計測する。また一つの計測には基本として 10 回計測を行う。以下に今回の計測についての詳細を述べる。

1. 500、 1000 のノード数を持つ系に対して、それぞれランダムモデルを生成して伝播数の計測を行う。このときノードが持つ平均エッジ数によってそれぞれ違いが見られることが予想されるので、すべてのエッジ数をノードで割った平均の数 (平均エッジ数) をいくつか変えて、それぞれの変化について計測する。

2. Web モデルを生成させるにあたって、それが Zipf の法則に準じているかどうかをみるために、 Web モデルを生成した時点でその系に属するノードが持つ OutDegree， Indegree についてエッジごとに計測する。

3. Web モデルについても 500、 1000 のノードに対して伝播数の計測を行う。その際 Web モデルの場合は初めに伝播させるノードによっての違いが予想される。そのため、開始させるノードをランダムに選び出す方法と、ノードがもつ Outdegree が最も多いノードを選び出しそこから開始させる方法それぞれについて行う。

4 結果

結果として得られたものが図 2〜図 43 である。以下研究方法における手順にしたがって結果を述べていく。

4.1 ランダムモデル

図１〜図 10 は, 図の番号が偶数のものがノード数 500 に対応しており、図の番号が奇数のものがノード数 1000 に対応している。図の説明でノード数の脇にある括弧書きの中の数字は、それぞれノード一個に対する平均エッジ数になっている。（例えば 0.97 は、ノード一個に対してのエッジの本数が平均 0.97 本に相当することを意味している。）ここでこの数字が半端な数となってしまったのは、 Web モデルを生成に際する処理の過程で起こっているものであり、それにすべてのデータを比較させるためにランダムモデルにおいても合わせているためである。ノード数 500 とノード数 1000 において、その伝播における定常状態に関しての伝播数である最終伝播数の数の割合はほぼ同じになっていることがわかる。伝播に関して定常状態となるまでには、開始するノードあるいは過程に通過するノードによってばらつきが多く見うけられる。しかし最終伝播数に関してはどれも似たような値まで達していることもわかる。図 6〜図 11 に関しては蔓延状態 (最終伝播数がノード数全体の 9 割を超えた状態) に達していることも確認されている。平均エッジ数が増えれば増えるほど蔓延状態に達しやすく、また時間的な変化においても明らかに速く系全体に行き渡っていることもわかる。さらに詳しく見てみると、平均エッジ数が同じでも伝播に掛かる時間 (伝播時間) はノード数 500 の方が短いことがわかる。

図 2: N=500(0.97)  図 3: N=1000(0.97)

図 4: N=500(2.2)  図 5: N=1000(2.2)

図 6: N=500(3.5)  図 7: N=1000(3.5)

図 8: N=500(4.8)  図 9: N=1000(4.8)

図 10: N=500(6.1)  図 11: N=1000(6.1)

4.2 Zipf の法則

図 12、図 13 は Zipf の法則における Outdegree に関するものでそれぞれノード数 500、ノード数 1000 に対応している。横軸はエッジ数、縦軸はノード数となっている。図 14、図 15 は同様に Indegree に関するものである。また図 12、図 13 に引いてある直線は経験則で導かれている傾き −2.38、図 14、図 15 に引いてあるものは傾き −2.10 となっている。エッジ数が少ないとき、多いときが直線からのずれとなっているが、実際のモデルも両極端のエッジ数に関しては直線にのらず、今回生成した結果のようにずれているので無視する。図 12〜図 15 はそれぞれ直線からの大きなズレはおこっておらず、 Zipf の法則に従う結果となっている。

図 12: Outdegree N=500(4.8) 図 13: Outdegree N=1000(4.8)

図 14: Indegree N=500(4.8) 図 15: Indegree N=1000(4.8)

4.3 Web モデル

図 16〜図 25 までは、ノード数 500 に対する伝播数の結果であり、図 26〜37 に関してはノード数 1000 に対する結果、図 38〜図 43 はランダムモデルと Web モデルについてエッジ数での変化を示している。このうち説明書きの中で max となっているのは、開始するノードが Outdegree の最も多いノードから始めた場合 (max) であり、表示していないものは開始するノードをランダムに選んだもの (ran) である。ノード数 500 についてみてみる。平均エッジ数 0.97 の場合は伝播数が低くなっているが、 max のほうが相対的に伝播数が高い。最終伝播数に関しては、双方ともに大差なく同じような値で推移している。 max は ran に比べてのばらつきが少なく同じような伝播性を有している。平均エッジ数が 4.8 のあたりで、蔓延状態に達している様子が伺える。次にノード数 1000 についてみてみる。全体的な伝搬性に関してノード数 500 と差がなくほぼ同一の性質を有している。これは max と ran においても同様のことが見られる。図 34， 35 はノード数 500、 1000 ともに見てわかるように蔓延状態に達しているものがるので、もう少し詳しく見るたに 100 回試行した結果である。図ではわかりにくいが、実際に伝播数が蔓延状態に達したものは max が 40 ％で ran が 39 ％であった。両方のノードの結果からは、 max のほうが ran に比べてその伝播時間が短くなっている。図 38〜図 43 の結果を見ると全体的な伝播数は、ランダムモデルのほうが同じ平均エッジ数で比べると最終伝播数の数が多い。しかし伝播時間は、平均エッジ数が多いときにはあまり変化が見られないが、 Web モデルのほうが短くなっている。 Web モデルにおいてはノードによる差がないことが max、 ran ともに見てとれる。

図 16: N=500(0.97)  図 17: N=500(0.97 max)

図 18: N=500(2.2)  図 19: N=500(2.2 max)

図 20: N=500(3.5)  図 21: N=500(3.5 max)

図 22: N=500(4.8)  図 23: N=500(4.8 max)

図 24: N=500(6.1)  図 25: N=500(6.1 max)

図 28: N=1000(2.2)  図 29: N=1000(2.2 max)

図 30: N=1000(3.5)  図 31: N=1000(3.5 max)

図 34: 100 回試行 N=1000(4.8)  図 35: 100 回試行 (max)  N=1000(4.8)

図 36: N=1000(6.1)  図 37: N=1000(4.8 max)

図 38: 比較 (ランダム 500)  図 39: 比較 (ランダム 1000)

図 40: 比較 (ネット 500)  図 41: 比較 (ネット 1000)

図 42: 比較 (ネット max500)  図 43: 比較 (ネット max1000)

5 考察

1. 結果 4.1 について考える。ノード数によって最終伝播数の割合が同じであるということはスケールに対する依存性がないことである。また平均エッジ数が 3.5 以上持つものでは、蔓延状態に達しているという 2 つの結果は蜷川ら (2000) と同様でる。伝播時間に関しては、平均エッジ数が多いほうが速くなっている。平均エッジ数が多くなれば次へ伝播する際に伝播することができるノード数が増えるために全体として時間が短くなっている。また全体の系のスケールが大きいほうが伝播時間が長くなるいという結果になっている。これは、ランダムモデルが持つ性質の特徴といえる。ランダムモデルはエッジの張り方自体がランダムであることから全体的に見れば局所的な部分が存在せずに、一様であると言える。ここで開始させるノードはここでは一ヶ所なので、伝播していく速さは変わらないのでスケールが大きいほうが定常状態までにかかる時間は大きくなり、平均エッジ数が多いほうが伝播時間が短くなるのは必然的な結果である。

2. 結果 4.2 について考える。 Outdegree、 Indegree ともに経験的に示された値での傾き −2.38 および −2.10 にのるような形で分布をしていることがわかる。ノードのもつエッジが少ない場合と、多い場合はこの直線からずれが生じている。しかし実際の Web モデルにおいても同じような形でずれが生じている Andrei et al.(2000)。したがって、今回用いたプログラムで生成された Web モデルは実際の Web の構造を反映しているといえる。このことから、今回行った研究方法３の項目に関しての結果は意味を持つものとして捉えることができる。

3. 結果 4.3 について考える。結果にあるように max の方が伝播時間が短くなっているのは、開始するノードのもつ Outdegree が多いために生じている。次に伝わるノード数が多くなるため全体として伝播時間が短くなる結果になっている。そのため max では、ほぼすべてが同じような伝播性を持つために 100 回試行してもばらつきが小さくなっていることがわかる。その点 ran は、開始するノードもランダムに選択されるため伝播される過程には大きくばらつきが生じている。しかし、その伝播過程において差異が生じているにもかかわらず平均エッジ数が同じものを比較すると、その最終伝播数はほぼ同じ結果である。つまり伝播過程においては、 max と ran では差異が生じるが、伝播されるノード数には関係性を持たないことを示唆している。ノード数 500、 1000 を比較してもそれは同じ傾向であることがわかる。このことは、スケールに対する依存がないということである。これは Zipf の法則で、その分布から得られる直線の傾きがスケールに依存しないことからも示されているが、ここで改めて依存性がないことがわかる。ランダムモデルと Web モデルの比較すると、ランダムモデルのほうが同じ平均エッジ数を持つときに伝播数が多くなることと、蔓延状態を導くのに必要な平均エッジ数が少なくてすむという結果には大いに関係がある。それには以下のような違いがあるために起こったと考えられる。ランダムモデルでは、その構造には特徴がなく一様であることは前述した。それに対して Web モデルでは、構造的に一様性はなく Zipf の法則に従った特徴を有している。つまりエッジを多く持つものノードの方が、より多くのエッジを持ちやすいためにエッジの集まり方に濃淡が存在している。系全体に対して蔓延させるためには、エッジの分布が一様にならなくてはならない。そのために Web モデルにおいて蔓延状態にするためにはより多くのエッジを用いなくてはならない。そのためにランダムモデルよりも多くのエッジを必要としている。ここでランダムモデルと Web モデルが違うのは、蔓延状態を起こすために必要な平均エッジ数だけでなく、伝播時間もスケール依存を受けないこともあげられる。これは Zipf の法則がもつ特徴によって形成されたモデルであるために生じている特徴である。したがってランダムモデルは本研究で行ったノード数を遥かに超えるスケールでは伝播時間は長くなるのに対して、 Web モデルではいくらスケールを変えようとその伝播時間に関しては同じであるという特徴がある。 Web モデルに代表されるネットワーク構造を持つ系は、その構造自体ランダムモデルよりも複雑な形を有しているため、同規模の系を生成するのには時間がかかってしまう。しかし、一度生成された系での情報の伝播時間はランダムモデルよりも短く全体に行き渡ることができる。情報を伝播させる範囲は同じであっても、「速さ」という情報には必要不可欠な要素である観点から捉えると、 Web モデルのほうが優れたモデルであるということができる。

6 結論

1. ランダムモデルの伝播時間はスケールに比例する。

2. Web モデルにおける情報の伝播には、スケールに対する依存が全くない。

3. Web モデルにおいる蔓延状態には、平均約 5 本のエッジをもつ必要がある。

4. Web モデルはランダムモデルより伝播時間が短い。

7 おわりに

今回、ランダムモデルと Web モデルについて情報の伝播における時間的変化を比較する形で研究を進めることで、伝播速度と Web モデルの伝播性について結果が得られた。結論として導かれたものは、直感的に察知できるものであるがシミュレーションを行うことでより具体的に捉えることができた。本研究で行った時間的な変化はその伝播時間にのみを考えたが、図からもわかるように伝播する速さは一定ではない。開始からしばらくすると線形的に伝播数が増加ているところが見うけられる。また、 Web モデルにおいて OutDegree が最もおおいノードからの開始を行ったが、そのノードを系から削除した状態ではどのような伝播をするのか。逆に、 OutDegree を一本程度しか持たないノードを系から削除した場合どのような伝播が起こるのかなど、今後の課題として取り上げていきたい。

参考文献

[1] 蜷川 繁, 津田 伸生, 服部 進実:”うわさの伝播モデル”, 情報処理学会 (2000),Vol.41 No.2

[2] Ravi Kumar et al.:”Extracting large-scale knowledge base from the web”,IEEE Int.Conf.on VLDB,Edinbargh,Scotland(1999)

[3] Andrei Border et al.:”Graph structure in the Web”,Computer Networks 33(2000),p309-320

[4] 柴内 康文:”電子メディア社会における情報伝播”, 第二回 CMCC 研究会 (1999)

[5] 吉田 正昭:”情報の伝播”, 共立出版 (1971)