シュミレータその後 geodesics, geodesic line, geodesic dome

物事は始めなければ終わらない。記事もとにかく書き始めなければ終わらない。

前々から書こうと思っていたスケールフリー・ネットワーク・シュミレーターの続きを書こう。一部の方にはすでに開示済みの情報で申し訳ない。

前回から何点かの改善、改良を行った。

リンクの可視化

入力した数のノードまでの自動生成

最短パスの算出

例によって、ActiveBasicのお世話になった。

プログラムのソースファイル

プログラムのEXEファイル

「可視化」は論より証拠で絵でみてもらうのがてっとり早い。ユキジさんの論文の図を見てまねをした。円周上にノードを置いて、それぞれにリンクを直線であらわしている。下の図は本来白黒の画面だが見やすいように反転してある。

「自動生成」は単に繰り返しの機能をつけただけだから、説明に及ばない。ただ、今後ファイルの入出力機能を付加したときには、力を発揮する予定だ。Basicの「open」とか「close」とかいう命令文は、一文字でも間違うと閉じれないファイルを生んだりするので嫌いだ。

今回の改善点の中では、最短パスが一番重要な要素だった。最短パスとは、ネットワークでつながれているノードとノードの間がいくつのリンクでつながれているからを示す。２つのノードがひとつのリンクでつながっている「隣り合わせ」状態であれば、「リンク数」＝「パス長」＝１となる。隣の隣なら１＋１で２になる。すべてのノードを縦横にならべた時に、お互いのパス数が最短でいくつになるかのマトリックスをどう求めるかということが問題だった。最短パス長がある意味ネットワークの形の基本だともいえる。

ネットワーク分析用語集　@　社会ネットワーク研究所

最短パス長をもとめる上で、議論すべき問題はいくつかある。Webのリンクのような場合は、有方向でAというページから張られたBへのリンクは、Bへ移動することができてもAに戻ることはできない。まあ、最近ではリファラの情報を活用することもできるがWebのトポロジー上は表現されていない。逆に、SNSの場合は両方向だといえようお互いにリンクをたどることができる。下に示した論文のようにこの辺の関係をうまく数量化し、強い絆を持つコミュニティーを同定しようとする試みもあるようだ。こうした試みは実際グーグルのPageRankを超える検索やWebの「お隣さん」を発見するアルゴリズムにつながりうる。

強連結成分の細分化による コミュニティ発見（パワーポイント・ファイル）　by　正田 備也さん、高須 淳宏さん、安達 淳さん

有方向のパス長を求めるプログラムもリンクのマトリックスで右上の象限か左下の象限かで方向を区別すれば可能なのだが、分析したいと考えているのが社会的なネットワークであるため双方向と仮定した（対角線は自分自身へのリンクを示す）。

最短パスについて、参考文献をネットで探し、アルゴリズム求めたが案外少なかった。佐藤史隆さんらの同志社大学のグループがきちんと論文を明らかにしてくださっていた。

複雑ネットワークの調査および問題定義　by　佐藤　史隆さん、廣安 知之さん、三木 光範さん

最短経路問題におけるアルゴリズム【ダイクストラ法】の調査　by　佐藤　史隆さん、廣安 知之さん、三木 光範さん

最短経路問題におけるアルゴリズム【ウォーシャル・フロイド法】の調査　by　佐藤　史隆さん、廣安 知之さん、三木 光範さん

この中の「ウォーシャル・フロイド法」というのが興味深かったので、実装した。私のシュミレーターの場合、全部のノードの最短パスを求めるつもりであったので、適用できそうだという第一印象があった。論文の中で、「ノードi」と「ノードj」の間の最短パス長を求めるのに、「ノードｋ」からそれぞれのノードへの距離を使うというアルゴリズムが出てきた。これは、実際の人間関係で例えればお互いの「共通の知人」だと考えればわかりやす。Ａという人物と、Ｂという人物でＣという人物が共通の知人なら「２」というパスになるし。Ａのまた直接の知人ＤとＢとは、１＋２で３というパスになる。今回、この考え方を素直にＢＡＳＩＣでプログラムしてみた。当初、ノードのリンクのマトリックスの縦のラインしかみていなかったので、無限ループにはまってしまい相当苦労したのだが、人間関係も縦横全部がつながりだと気づき、少々プログラムの負荷は増えたが「リンク」＝「人間関係」全部をチェックしてその内の最短の「共通の知人」を探すようにしてやったら、うまくいった。この辺は、案外社会的な常識と数学的な妥当性がマッチするところだ。

と、ここまで努力に努力を重ねようやくバグ取りがおわってほっとした翌日「P2P TODAY」のoff会に参加させていただいておっちーさんからすばらしいものをご紹介いただいた。

成長するネットワークのシミュレーションということでしたら、ぜひこのシミュレーションプラットフォームをお使い下さい。慶應大学SFCのBoxed Economy Projectが提案しているもので、日本が世界に誇る（ことになるであろう）、汎用性、拡張性ともに群を抜いて優れたシミュレーション基盤です。
こちらから、ダウンロードできます。
http://www.boxed-economy.org/

どうもこれはすごいことになっているらしい。

しかし、まだこのシュミレーターが使いこなせていない！誰かワークショップでもやってくれないだろうかと悩んでいる毎日だ。

■余談

最短パス長を一般に「geodesics」あるいは「geodesics line」というそうだが、「geodesics dome」というとあの有名な「フラードーム」を指すらしい。非常に興味深い。

■参照リンク
・、社会ネットワークの形成過程シミュレーション　―マルチエージェント・モデルによる表現と拡張―　by　古川園　智樹さん、石元　龍太郎さん、小林　慶太さん、笠井　賢紀さん、赤松　正教さん
井庭　崇†††