成長するネットワークのモデル
複雑なネットワークの科学とは,社会ネットワーク分析など社会科学分野では古くから注目されていたネットワークの構造的特徴や発生メカニズムを分析・開明することを目的とした学問である.従来のネットワーク分析との大きな違いは,計算機の向上などを受けて,従来は困難であった大規模なネットワークを対象とした現象の分析や視覚化,動的な要因も含めたモデル化などが試みられているおり,それは,計算機科学の分野以外でも広く研究されている.
我々は,複雑なネットワークの分野の中でも,特に,様々な系がもつ構造(ネットワーク)に着目し,そのネットワークから創発される現象の分析や,ネットワークが形成される過程の解明が試みている.さらに,こでまは,系の上での現象は個々の要素間での相互作用が注目されていたエージェントの協調行動などを,ネットワークの視点から,相互作用がどのような構造であるのかを分析することで,構造の特徴とその系の上での行動の結果として創発される現象との関係性に注目していきたいと考えている.
- 複雑系ネットワークの研究とは
中心性に基づくネットワーク形成
本研究では,中心性をエージェントの合理性の基準となる効用と捉え,その効用を高めることを目的としてネットワーク形成に参画するエージェント群によるネットワークの形成モデルを提案している.提案モデルでは,各エージェントが,現在のネットワークに追加するリンクを,全てのエージェントの投票(ボルダ方式)によって選ばれる.提案モデルでは,エージェントが効用とする中心性の違いによって,次のような特徴的なネットワーク構造が表れる.
- 中心性に基づくネットワークのモデル
- 複数中心性に基づくネットワークの成長要因の推定
ネットワーク形成の合理性の推定
従来のモデルにて,エージェントが中心性を高めることを目的としてネットワークを形成することで,特徴的な構造をもつネットワークが形成されることが明らかになっている.このモデルを,各中心性を異なる属性をもつ指標と見なし,エージェントがネットワークの形成に参画する際の効用を複数の中心性によって表わすように拡張することで,既存のネットワーク構造から,そのネットワークに内在するエージェントの合理性の基準を推定することを試みる.
空間ネットワークの分析
空間上に広がるネットワークは,現在の社会で構造的に生じる任意の場所間の人や物,情報などの移動を支える手段であると同時に,将来的な構造の有り様にも何かしらの影響を与える.
本研究では,空間上のネットワークである,高速道路網や鉄道網などを対象としたネットワークの分析やナビゲーション手法の開発を行なう.
研究者─学会の2部グラフの抽出
Web上のデータを利用して,2部グラフの抽出を行い,その後,2部グラフ,3部グラフを利用したサービスの考察を行う.
多層ネットワークモデルの構築
一般的に,社会ネットワークの分析では,特定の集団,もしくは関係性からなるネットワークを対象として抽出・分析が行われている.しかしながら,Webのリンク構造,人間関係,交通網など実在する”社会ネットワーク”は,必ずしも単一の関係性からなっているわけでは無く,また,個々の関係性によって形成されるネットワークの構造的特徴が異なるのでは無いかと考える.具体的には,人間関係であれば,パブリックな関係もあればプライベートな関係によって,また会話やメールのようなコミュニケーションツールの違いによっても各々一つのネットワークとしての成長を見せ,それぞれ異なる成長をみせるているのではないだろうか.そして,それら複数のネットワークは人間関係という一つのネットワークの中で個々の成長が互いに影響をあたえあってネットワークとして形成されると考えている.つまり,社会ネットワークは一つのネットワークとして分析するのではなく多層なネットワークとして分析すべきではないかというのがこの研究の主張点となる.
本研究を行ううえで必要な技術は,以下の2点と考える.
- 単一の関係性からなるネットワークの成長モデル
- ネットワーク間の影響を考慮したメタネットワークモデル
また,この研究の応用範囲としては以下の分野が考えられる.
- 公共交通機関の交通網のダイナミックス
- 観光・防犯などを考慮したレンタサイクルシステム設計
- オンラインゲーム内でのコミュニティバランスのデザイン
- フランチャイズ展開の戦略決定のためのシミュレーション
なお,下記の資料は,2009年度のさきがけに本研究テーマで応募した書類である.とりあえず面接には呼んでいただけたが,必ずしも評価がよかったとはいえず,次年度に向けては,テーマの大幅な見直しの必要があるため,ここに公開する.
- さきがけ提案書[PDF]
- さきがけプレゼン資料[ODP]
マルチエージェントシミュレーション
群集シミュレーション
一般的な群衆シミュレーションでは,環境から集団に対する情報提示(アクセス)によって,全体の挙動をコントロール可能であるかなどが研究の対象となる.それに対して,我々は,環境から個々の個人に直接アクセス可能なデバイス(パラサイトヒューマン)を想定し.その状況下での集団の行動の様相を変化できるかを試みる.
サッカーシミュレーション
災害救助シミュレーション
災害状況を想定した環境下を再現することを目的としたシミュレータが災害救助シミュレータである.そのシミュレータを用いて,効率的な災害時の救助活動の発見や制度設計,都市環境の評価などを行うことを目的としている.
我々は,当該シミュレータを用いるに辺り,適切な実験環境を提供するための仕組みの一つとして,エージェント群の振る舞いをシナリオとして表現する環境の整備を試みた.これは,社会シミュレーションでは,特定の目的を実験するには,様々な環境条件の設定が必要となるが,災害救助の対象者となる一般市民の様に,その中にエージェントがどのように振る舞うかも含まれる.だが,その振る舞いは多様であると同時に,振る舞いの設計自身が,結果を大きく左右する可能性もある.そこで本研究では,
- 容易な記述による行動設計
- 単純な仕組みよる行動の組み替え
- Posit: 並列シナリオ記述
- R_Civilian: RoboCupRescue用市民エージェント
ネットワーク生成シミュレーション
上記の成長するネットワークのモデルのシミュレーションなどに利用.実装には C++, boost, ruby などのプログラミング言語・ライブラリを使用している.
ソーシャルタギング
When2.0的EventTagging
災害救助支援
デマンドバス
デマンドバスとは,イメージとしては乗り合いタクシーが近く,乗客のデマンドにあわせて比較的自由なルート設定が可能なバスのことである.いわゆる路線バスとの違いは,路線バスが運営側が地域の定期的に発生するニーズに併せた路線や時刻の設定を行なったうえで,乗客がそれにあわせて行動するという作業が必要であるのに対して,デマンドバスでは不定期なニーズに併せた柔軟な資源の割り当てを行なうことで,移動に関する流動性を促す効果を狙ったものである.
われわれは,固定路線のメリットが強いとされる都市部でのデマンドバスの効果をシミュレーションを用いて測ることを試みた.
研究のツール
graphviz: ネットワーク描画ツール
ネットワーク図などを描くときに利用する.ただし,大規模なネットワークやリンクが密な場合の表示は,不得手である.その場合には LGL を使用するのが一般的らしい.
boost: C++ライブラリ
こちらも主にネットワークデータの処理に使用している.我々が導入した時点ではなかった betweenness の計算もライブラリとして提供されている.すでに実装したあとだったので使ってはいないけど,比較的高速されるアルゴリズムで実装されているようで,edge_betweennessの計算なども可能.
その他にも,多数のライブラリをそろえているライブラリ群である.
Ruby
おもに,プログラムに与えるパラメータの自動化などに利用.そのほか,簡単なクローラー作成などにも利用している.
JavaScript
いわゆる Ajax 的なアプリ構築や,firefox の拡張機能作成のために使用.
Repast
Agent Simulation Toolkit
関連研究のサーベイ
- 2008.03.16: 国際会議ネットワークを追加
- 2008.02.05: 群集行動シミュレーションを追加
- 2007.11.20: R_Civilianを追加
- 2007.07.01: 関連研究のサーベイの追加
- 2007.07.01: 2部グラフの抽出を追加
- 2007.04.29: 暫定版公開