私のブックマーク
複雑ネットワーク（Complex network）
臼井翔平 (東京大学大学院)
はじめに
「ネットワーク」とは点(Node)が線(Edge)で結ばれたもので，繋がりを指します．
社会ネットワークならNodeは人でありEdgeは人間関係となります．
他にも，企業取引関係，食物連鎖，道路網，電力網等，多くのネットワークが身の回りに存在します．
数学的にはグラフと呼ばれ，行列によって表現されます．
この複雑ネットワークの研究は1998年から急速に発展し，それは現在も続いています．
本記事はこれから複雑ネットワークの研究を始める方に有用だと思われる情報を集めて紹介します．
本記事では，以下の5点について紹介をしていきます．
1.複雑ネットワーク入門
ここでは複雑ネットワークの基礎を学べる書籍や，特集記事を紹介していきます．
複雑ネットワーク関連書籍
-
複雑ネットワークに関する書籍を紹介します．
- 林幸雄，”これから学ぶ方々への書籍紹介”，情報処理学会,Vol.49,No.3,pp.317-320 (2008),小特集「複雑ネットワーク科学の拡がり」
- 複雑ネットワークに関する書籍の特集を挙げます．複雑ネットワークに関する読み物から，専門書までが解説付きで紹介されています．
- 増田直記，今野紀雄：複雑ネットワーク 基礎から応用まで, 近代科学社(2010)
- 私が推したい一冊です．複雑ネットワークの成り立ち，基礎理論，特徴量，モデリング，さらに複雑ネットワーク上でのシミュレーションまで大変綺麗にまとめられており，複雑ネットワークのとっかかりとしては十分な一冊です．
- 矢久保考介，複雑ネットワークとその構造 (連携する数学 4), 共立出版 (2013)
- 基礎理論から，様々な特徴量やモデリングについて定式化しながら丁寧に整理されています．またコミュニティー抽出やフラクタル性の話についても解説されています．
- M.E.J Newman：Networks An Introduction, Oxford University Press (2010)
- 複雑ネットワークの最先端の研究者であるM.E.J. Newmanが執筆し，多くの論文から引用されている一冊です．基礎からしっかり学べて，論文のお供にも便利です．
最後に読み物としてお勧めしたい2冊を紹介します．
- Duncan J. Watts (著), 辻 竜平 (翻訳), 友知 政樹 (翻訳), スモールワールド・ネットワーク―世界を知るための新科学的思考法, 阪急コミュニケーションズ (2004)
- 1冊目はDuncan J. Wattsによるものです．複雑ネットワークの導入としては是非とも読んでいただきたい1冊です．
- アルバート・ラズロ・バラバシ (著), 青木 薫 (翻訳)，新ネットワーク思考―世界のしくみを読み解く, NHK出版 (2002)
- もう1冊は，Barabasi Albert Laszloの執筆した一冊です．この書籍は2002年の米国ベストビジネス10冊中に選ばれる程の良書となっています．
複雑ネットワーク関連特集記事
-
ネットワークに関する特集記事を紹介します．
- 林幸雄，”ネットワーク科学が目指すもの”，情報処理学会,Vol.49,No.3,pp.277-281 (2008),小特集「複雑ネットワーク科学の拡がり」
- 複雑ネットワークの成り立ちについて書かれた特集記事を紹介します．複雑ネットワーク科学の誕生から複雑ネットワークを研究する意義等について詳しく述べられています．
- 増田直紀，”ネットワーク上の進化ゲーム”，人工知能学会誌,Vol.23,No.5,pp.652-658 (2008) 特集「繋がりの科学」
- ネットワーク上で行われる進化ゲームの特集記事を紹介します．スケールフリーネットワーク上での進化ゲームについて，過去研究を並べながら紹介している記事です．
- 今野紀雄，”複雑ネットワーク科学はどこに向かうのか？” 第4回横幹連合コンファレンス予稿集, J-STAGE (2012)
- 複雑ネットワーク上での確率モデルの紹介をしながら，複雑ネットワークの今後について述べた記事です．
- 増田直紀，”テンポラルネットワーク”, 人工知能学会誌,Vol.27,No.4,pp.432-436 (2008) 特集「人と環境に見る高次元データフローの生成と解析」
- 現在注目を集めているテンポラルネットワークに関する紹介記事です．テンポラルネットワークは，リンクに時刻情報が付加されたネットワークで近年注目を集めています．本記事は事例を並べながらわかりやすく紹介しています．
2.近年の主な研究動向
ここでは，複雑ネットワークの最新の動向について紹介していきます．まず，複雑ネットワークに関するサーベイ論文を紹介し，その後，複雑ネットワークに関する各種情報を含んだウェブページを紹介します．
サーベイ論文
複雑ネットワークの中でも様々な研究対象があります．それぞれの研究対象でのサーベイ論文を紹介していきます．
- ネットワーク生成モデル
- ネットワーク生成モデルは，現実のネットワークの特徴と同等の特徴を持つネットワークを生成するアルゴリズムを発見する事によって，現実のネットワークの成り立ちを分析するものです．
- Anna Goldenberg, Alice X. Zheng, Stephen E. Fienberg and Edoardo M. Airoldi, “A Survey of Statistical Network Models”, Foundations and TrendsR in Machine Learning, 2010.
- コミュニティー分割
- ネットワークからコミュニティーを抽出する事を目的としています．
- Steve Harenberg, Gonzalo Bello, L. Gjeltema, Stephen Ranshous, Jitendra Harlalka, Ramona Seay, Kanchana Padmanabhan and Nagiza Samatova, “Community detection in large-scale networks: a survey and empirical evaluation.” Wiley Interdisciplinary Reviews: Computational Statistics, 2014.
- 平均経路長の計算の高速化
- 近年，扱うデータの巨大化により，平均経路長の計算コストが膨大となり，扱うのが困難となりました．そこで，平均経路長の計算コストの削減や，推定する研究が多く行われています．
- CHRISTIAN SOMMER, Shortest-Path Queries in Static Networks, ACM Computing Surveys, Vol. 46, No. 4, Article 45, Publication date: March 2014.
- ネットワーク可視化
- ネットワークの特徴を伝えるためには可視化するという選択があります．しかし，的確な可視化法を選択しなければ，特徴を伝える事はできません．そこで，ネットワークの可視化が研究されてきました．
- Hu Yifan, Shi Lei. Visualizing large graphs. WIREs Comp Stat 2015, 7: 115-136. doi: 10.1002/wics.1343
- Temporal network
- ネットワークに時刻情報を付加した動的なネットワークです．このネットワークは静的なネットワークよりも現実に即しているという事で，現在研究がすすめられています．
- Daniel Archambault, James Abello, Jessie Kennedy, Stephen G. Kobourov, Kwan-Liu Ma, Silvia Miksch, Chris Muelder, Alexandru C. Telea, “Temporal Multivariate Networks.” Multivariate Network Visualization 2013: 151-174
- Multiplayer network
- 一つのネットワークは多層構造からなっているとした考えです．テンポラルネットワークと同様に近年，より現実に即しているという事で注目を集めています．
- Mikko Kivela, Alexandre Arenas, Marc Barthelemy, James P. Gleeson, Yamir Moreno, Mason A. Porter, “Multilayer Networks”,J. Complex Netw. 2(3): 203-271 (2014)
ウェブページ
- COMPLEX SYSTEM SOCIETY
- 複雑系システムの研究者コミュニティーのウェブページを紹介します．複雑システム，複雑ネットワーク関連のNEWSやEVENTがまとめられています．複雑ネットワーク関連の国際会議の情報や，論文誌の情報も載っています．
- Recent publications related to complex systems
- 上の研究者たちにによって論文や書籍等がまとめられているページを紹介します．
- complexnetworks.fr
- 複雑ネットワークの研究チームのページです．様々なネットワーク関連の動画や，彼らの論文が多く掲載されています．
3.国内外の関連する会議
国内外の関連する会議
ここでは複雑ネットワークに関する主な国際会議を紹介します．
- Network Science (NetSCI)
- 複雑ネットワークを扱った会議です．複雑ネットワークに関連していれば，コミュニティー抽出から，ネットワーク上のシミュレーションまで多彩な発表があります．
- Complex Networks
- 複雑ネットワークに関するInternational conferenceです．ネットワークモデルや，ネットワーク上の拡散，ダイナミクス等，ネットワークに関する様々な研究を取り扱っています．
- World Wide Web (WWW)
- Web系トップカンファレンスです．ソーシャル系のネットワークを扱っています．
- Autonomous Agents & Multiagent System (AAMAS)
- エージェント系トップカンファレンスです．エージェントシミュレーションを扱ったセッションがあり，ネットワーク上のシミュレーションを扱った発表が数多くあります．
- THE ASSOCIATION FOR THE ADVANCEMENT OF ARTIFICIAL INTELLIGENCE (AAAI)
- AAMASと同様にエージェント系トップカンファレンスです．ネットワーク上のシミュレーションを扱っています．
- International Conference on Weblogs and Social Media(ICWSM)
- ソーシャル系のInternational conferenceです．ソーシャルメディアに特化した会議であり，ソーシャルネットワークを扱っています．
- Social Computing (Social Com)
- ソーシャル系のInternational conferenceです．ソーシャルメディアを扱っており，ソーシャルネットワークに関する研究が多く発表されています．
複雑ネットワーク関連研究会
複雑ネットワークに関する国内外の研究会やworkshopを紹介します．
- ネットワークが創発する知能研究会(WEIN)
- 毎年研究会(JWEIN)を開催している他，人工知能学会全国大会にてセッションを開催しています．また，国際会議AAMASにおいてworkshopを行っています．
- ネットワーク生態学研究会(NetEco)
- 合宿形式の研究会を毎年開催しています．
- Graph Drawing & Network Visualization
- ネットワーク可視化研究のシンポジウムを開催しています．
- Workshop on Simplifying Complex Networks for Practitioners(SIMPLEX)
- WWWにおいてworkshopを開催しています．
School
- Complex networks: theory, methods, and applications
- complex systemに関するlectureが毎年開催されています．
論文誌
- Journal of complex networks
- まだ新しい複雑ネットワークに関する研究を対象とした論文誌です．
4.研究に必要なリソース
ネットワークリソース
ここでは複雑ネットワーク関連の便利なデータセットや，ソフトウェアを紹介しているページを紹介します．ネットワークのデータセットや便利なtoolが公開されているページをまとめてあります．
可視化ツール
- Network Visualization – FlowingData
- 様々な可視化方法が図解されています．
- Survey of Network Visualization Tools
- ネットワーク可視化ツールが紹介されています．
- Cytoscape
- ネットワーク可視化ツールとしてよく使われるcytoscapeのページです．とても簡単にネットワークを可視化でき，使い勝手がよいです．
- Cytoscapeやネットワーク解析・可視化に関する情報の集め方
- cytoscapeの使い方をまとめた解説記事です．
- R seminar on igraph – supplementary information
- Rを使ったネットワーク描画のためのigraphの使い方を詳しく解説しているページです．
- networkXのグラフをgraphvizで出力 (PyGraphviz)
- pythonのNetworkxを使ったネットワークの可視化についての解説ページです．
- vis.js
- javascriptのD3.jsを使ったネットワークの可視化についての解説ページです．
5.国内外の複雑ネットワーク研究室
最後に国内外における複雑ネットワークを扱っている研究室の紹介をします．
- Duncan James Watts, Columbia University
- Steven Strogatz, Cornel University
- Barabasi Albert Laszlo Northeastern University
- Mark Newman University of Michigan
- Ginestra Bianconi Queen Mary University of London
- Mikko Kivela University of Oxford
- Daniel Archambault Swansea University
- 村田剛志 東京工業大学
- 栗原聡 電気通信大学
- 石川孝 日本工業大学
- 鳥海不二夫 東京大学
- 斉藤和巳 静岡県立大学
- 林幸雄 北陸先端科学技術大学院大学
- 風間一洋 和歌山大学
- 中島秀之 公立はこだて未来大学
- 増田直紀 University of Bristol
- Steven Strogatz, Cornel University
おわりに
本稿では複雑ネットワークに関する様々な情報を紹介しました．全てを網羅しているわけではなく，筆者の主観で有用だと思われる情報を紹介しました．これから複雑ネットワークの研究をする方の助力となれば幸いです．