人と人の友人関係や食うか食われるかという食物連鎖の関係，ウェブページのリンク関係，などは対象をノード，関係をリンクと考えることによってノードとリンクからなる以下の図のようなネットワーク(グラフとも呼ばれます)と考える(モデル化する)ことができます．

最近は，コンピュータの計算能力の向上もあり，こういった様々なネットワークが興味深い性質を持つことがわかって研究が盛んになってきました．これらの研究分野は複雑ネットワーク(Complex Network)と呼ばれています．

自律系工学研究室でも早くから複雑ネットワークの研究に取り組んで多くの成果をあげてきました．ここでは，いくつかの研究テーマについて動画を交えて紹介します．

　
東日本大震災におけるTwitterでの情報伝搬についての分析

Twitterは個々のユーザが140文字以内の短文(ツイート)を投稿するマイクロブログの一つで，現在，多くのユーザが使用するようになっています．ユーザはフォローしている相手のツイートを読むことができ，また­自身のツイートをフォロワー（自身をフォローするユーザ）に伝えることができます．このようにある情報がTwitterを使って伝搬しているのです．以下の動画は，2011年3月11日に起­きた東日本大震災の際にTwitter上で震災に関するある話題についてユーザ間に伝搬した様子をその成長過程とともに示したものです．

これらのネットワークの分析を行うことで，東日本大震災の際に実際に起った震災に関する情報伝播が通常の情報伝播とは様子が異なることがわかりました．より緊迫して多くの人に広く伝えたいと思う情報は多くの人に情報を伝えるハブと呼ばれる人が多く介入していることがわかります．

　
ネットワークをより高速に見やすく配置する可視化手法

ネットワークはノードとそれらをつなぐリンクから構成されており，それらの配置(レイアウト)が異なるとまったく違うネットワークを見ているように感じるかもしれません．ネットワークを人が見やすく，または，特徴がよくわかるように配置する問題は，ネットワーク可視化問題とかグラフレイアウト問題などと呼ばれ，古くから研究されています．

一般的にネットワークのノードを質点，リンクをバネと考えることによって，ネットワーク全体にかかるバネの力（エネルギー）が小さくなるようにノードを配置する方法は力学的手法と呼ばれますが，バネにかかる力を随時計算しつつノードの位置を変更することを繰り返す方法は非常に計算時間がかかり，可視化までに時間がかかることが問題でした．

自律系工学研究室では，力学的手法に基づく可視化手法として，局所エネルギー最小化法(LEM法)を提案しています．これは，バネにかかる力を局所的に計算することで計算時間を削減しつつ，ノードの移動とエネルギー計算を繰り返す方法で従来の方法よりも高速にエネルギーの小さい配置を見つけだすことに成功しています．上記の動画はLEM法によって代表的なネットワークを可視化したときの計算過程を含めた結果を示しています．

　
２人対戦型ボードゲームHexをプレイするコンピュータHexの開発

Hex(ヘックスと読みます)と呼ばれる２人対戦型ボードゲームは，映画「ビューティフルマインド」のモデルにもなったゲーム理論で有名な John Nash が考案したゲームで，ルールは簡単ですが，その戦略性は複雑で奥の深いゲームの一つです．

Hexは，下の動画のように，先手である赤プレイヤーと後手の青プレイヤーが六角形（ヘックス）のマス目にコマを交互に置いて，自分の色のついたボードの対角辺を自分のコマの連鎖によってつなげた方が勝ち，という単純なゲームです．一方のプレイヤーがコマの連鎖で対角辺をつなげた場合は，相手の辺は必ずつながっていないことは簡単に証明ができて，引き分けのないゲームだということがわかります．

このHexというゲームの局面は，コマを置くマスをノード，つながる可能性のあるマス同士の関係をリンクとすることで，ネットワークとして表現可能です．自律系工学研究室では，このHexというゲームを複雑ネットワークとして捉えて，現在の局面の優劣と高速に評価する方法を提案して，より強いコンピュータHexプレイヤーの開発を行なっています．この動画では，赤プレイヤーである人間が，コンピュータHexである青プレイヤーが対戦しています．コンピュータHexは人間が手を打った直後に（高速に）手を打っているにも関わらず人間に勝利している様子がわかります．

このように強いコンピュータHexを開発して対戦し合う世界大会も開催されています．あなたも自分が作ったプログラムがHexの世界チャンピオンとなる夢を実現してみませんか？