ネットワーク科学 増田直紀

日本における授業、修論、卒論関係の記録です。

修士論文と卒業論文指導（東京大学）

2014年2月28日で、イギリス・ブリストル大学への異動に伴って退職しました。そのため、2014年3月卒業の学生については、増田が指導教員だったのは、2014年2月28日までであり、3月の指導教員（＝ 最終的な指導教員）は竹村彰通教授。

修士論文

2014（平成26）年3月

大橋祐太
階層構造をもつネットワーク上の投票者モデル

齊藤宏大
複雑ネットワークにおける頂点の重要度と辺生成の間に見られる依存関係について

竹内大樹
隠れマルコフモデルを用いた人間行動データの解析

2013（平成25）年3月

石井臨太郎
メタ群集ネットワーク上の感染症伝搬を抑制するための戦略

富田裕章
拡散過程を用いた生物学的オークションの解析

茂木隼
ネットワークを用いたテニスプレイヤーの動的なランキング手法

2012（平成24）年3月

大西隆興
不均一に結合されたメタ群衆における感染症動態の制御

加藤紳也
逆イジング問題に基づく多細胞神経活動の解析手法

2011（平成23）年3月

宇賀山和也
空間構造と外的罰則に基づく協力行動の進化

河瀬康志
ネットワークデザインゲームにおけるポテンシャル最小化

関根亮吾
双曲割引を持つ Temporal Difference 学習の研究

2010（平成22）年3月

立石寛人
コミュニティ構造を有するネットワーク上での多数決モデル

2009（平成21）年3月

坪坂正志
ネットワークのコミュニティ構造を抽出するベイズ推論アルゴリズムの研究

卒業論文

2014（平成26）年3月

岩政勇仁
投票者モデルにおける平均合意時間が最大のグラフ

加藤純
進化ダイナミクスにおいて熱狂者が有する平均固定時間への影響について

2013（平成25）年3月

榎本悠介
コミュニティ検出アルゴリズムの高速化とソーシャルグラフへの応用

村越智文
予算制約ルールのもとで行われるグラフ上の進化ゲーム

渡邉千紘
ネットワーク上の感染状況に基づく予防接種アルゴリズム

2012（平成24）年3月

石原響太
振動子ネットワークの周期の安定性に関する理論的考察

岡野雄起
互恵的協力行動の安定領域の数値解析

2011（平成23）年3月

榊原孝俊
ネットワーク上の感染症における最適なワクチン配布について

田邊奨馬
進化ゲームにおけるBaldwin効果の強化学習による説明

山田直敬
強化学習におけるラプラシアンを用いた価値関数表現

2010（平成22）年3月

糸山浩太郎
空間構造をもつ集団における繰り返し進化ゲーム

大岩良行
金融機関ネットワーク上のバブル崩壊の数理モデリング

土井丈太郎
ネットワーク上の噂伝搬モデル

2009（平成21）年3月

穐田みちる
社会における連鎖的伝播現象の数理モデリング

岩上顕夫
スケールフリー・ネットワークにおける間接互恵性

2008（平成20）年3月

高橋祐子
発火時刻依存シナプス可塑性のもとで生成する神経回路網の解析

塚田健
知人紹介ネットワークの解析

東京大学での講義

03-541530 幾何数理工学
2007（平成19）— 2012（平成24）年度冬学期．1.5単位

4820-1008 数理構造論
2013（平成25）, 2011（平成23）, 2009（平成21）年度夏学期．2単位
（4860-1005 数理モデリング論（創造情報学専攻）と cross-listing）
2013（平成25）年度は英語。英語の講義名は Mathematical Structures in Informatics

03-541620 数理情報工学輪講
2007（平成19）, 2008（平成20）, 2010（平成22）, 2011（平成23）, 2012（平成24）, 2013（平成25）年度夏学期．2単位

演習2A（1回）
2007（平成19）— 2011（平成23）年度夏学期

[1回講義] システム微生物学（メディカルゲノム専攻）
感染流行の疫学
2012/10/11

[1回講義] 教養学部主催・生産技術研究所共催「高校生のための金曜特別講座」
ネットワークの科学 — みんなつながっている
2010（平成22）年度夏学期．2010/06/11

[1回講義] 61065 システム科学特別講義 I（教養学部広域科学科）
ネットワークの科学：基礎から応用まで
2010/10/19

11940 情報技術論
2013（平成25）年度夏学期. 2012/05/07, 05/13
2012（平成24）年度夏学期. 2012/06/04, 06/11
2011（平成23）年度夏学期. 2011/06/20, 06/27
2010（平成22）年度夏学期. 2010/06/21, 06/28

総合科目（一般F）「数理工学のすすめ」
複雑ネットワークの数理
2012（平成24）年度夏学期. 2012/05/01, 05/10
2011（平成23）年度夏学期. 2011/06/29, 07/06
2010（平成22）年度夏学期. 2010/06/23, 06/30
2009（平成21）年度夏学期. 2009/05/14, 05/21
2008（平成20）年度夏学期. 2008/06/12, 06/19
2007（平成19）年度夏学期. 2007/05/31, 06/07

俯瞰講義
国境なき数学－ことばを越えて社会とともに
8. ネットワークがもつ普遍的な構造
9. 不平等性の数理
10. ネットワーク上の感染症伝播
2011（平成23）年度冬学期
講義映像

生物情報科学特別講義II
2013/06/24, 07/01

他大学での講義

• [1回講義] 玉川大学 大学院特別講義，脳科学研究科の授業「先端セミナー」，
  2015/08/20
  
  
• [集中講義] 茨城大学 大学院理工学研究科 応用数理特講II
  2012/11/01-02
  
  
• [1回講義] お茶の水女子大学 情報科学科 情報科学特別講義II
  2012/10/31 13:20-14:50
  
  
• [集中講義] 京都大学理学研究科．複雑ネットワークと社会相互作用のモデリング．
  2011/10/19-21
  
  
• [集中講義] 東京工業大学 大学院総合理工学研究科 「知能システム科学特別講義第六」（サブタイトル：　複雑ネットワークの数理と応用）. 2011/1/12 9:00- 2時限
  第1限：複雑ネットワーク導入編
  第2限：複雑ネットワーク上の相転移と感染現象
  
  
• [集中講義] 名古屋大学 大学院理学研究科 生命理学専攻 「生命理学特別講義15」（講義題目：複雑ネットワーク）．
  2010/05/27-05/28
  
  
• [1回講義] 東京理科大学 大学院共通特別講義第7回 「シナプス学習を通じたニューラル・ネットワークの生成について」．
  2008/10/30 14:30-16:00
  
  
• [集中講義] 東京工業大学 工学部 社会工学科 (学部3年生).「社会シミュレーション」
  平成25年度 2013/04/13, 05/11, 05/25, 06/15
  平成24年度 2012/04/14, 04/28, 05/26, 06/02
  平成23年度 2011/04/23, 05/07, 06/18, 07/02
  平成22年度 2010/08/09-08/12
  平成21年度 2009/08/11-08/14
  平成20年度 2008/08/11-08/14
  
  
• [集中講義] 九州工業大学 大学院 生命体工学研究科 「情動・学習機構」平成18年度 2007/01/17-20, 平成17年度 2006/01/25-28
  
  
• [1回講義] 慶應義塾大学 総合政策学部「モデリングシミュレーション入門」(井庭崇 専任講師 担当 2006年度秋学期　金曜日2時限）2006/11/17
  
  
• [1回講義] 埼玉大学 大学院 理工学研究科 情報システム工学専攻 博士前期課程 「情報工学特別講義 II」．講演会「複雑ネットワーク入門」2005/05/12 16:00-17:30
  
  

数理情報工学輪講（東京大学在籍時。学部４年生夏学期）のテキスト

2013（平成25）年度

概要：ネットワーク科学や社会物理学と呼ばれる研究分野に関連する論文を1人1編ずつ発表する．実世界にあるネットワークの構造，伝播現象，人の移動行動などの論文を扱う．予備知識は必要としない．

テキスト：
A.-L. Barabási. The origin of bursts and heavy tails in human dynamics. Nature, Vol. 435, pp. 207-211 (2005).
A. Vazquez, B. Rácz, A. Lukács, A.-L. Barabási. Impact of non-Poissonian activity patterns on spreading processes. Physical Review Letters. Vol. 98, article No. 158702 (2007).
B. Min, K.-I. Goh, I.-M. Kim. Waiting time dynamics of priority-queue networks. Physical Review E, Vol. 79, article No. 056110 (2009).
B. Min, K.-I. Goh, A. Vazquez. Spreading dynamics following bursty human activity patterns. Physical Review E, Vol. 83, article No. 036102 (2011).
G. M. Viswanathan, S. V. Buldyrev, S. Havlin, M. G. E. da Luz, E. P. Raposo, H. E. Stanley. Optimizing the success of random searches. Nature, Vol. 401, pp. 911-914 (1999).
D. Brockmann, L. Hufnagel, T. Geisel. The scaling laws of human travel. Nature, Vol. 439, pp. 462-465 (2006).
M. C. González, C. A. Hidalgo, and A.-L. Barabási. Understanding individual human mobility patterns. Nature, Vol. 453, pp. 779-782 (2008).

2012（平成24）年度

概要：進化ゲーム理論は，社会的ジレンマ状況（囚人のジレンマなど）における人間や他の動物の行動（利他性，利己性など）を説明する強力な枠組みである．そのようなテーマを扱う本書のいくつかの章を輪読する．微分方程式，力学系，確率過程が主に関係する．予備知識は必要としない．

テキスト：Karl Sigmund. The Calculus of Selfishness. Princeton University Press (2010).

2011（平成23）年度

概要：複雑ネットワーク（あるいは，ネットワーク科学）と呼ばれる研究分野に関連する，代表的な論文を1人1編ずつ発表する．実世界にあるネットワークの構造，ネットワークの頑健性，グループ構造，待ち行列などの論文を扱う．予備知識は必要としない．

テキスト：
D. J. Watts, S. H. Strogatz. Collective dynamics of `small-world' networks. Nature, Vol. 393, pp. 440-442 (1998).
A.-L. Barabási, R. Albert. Emergence of scaling in random networks. Science, Vol. 286, pp. 509-512 (1999).
M. Girvan, M. E. J. Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America, Vol. 99, pp. 7821-7826 (2002).
A. Clauset, C. Moore, M. E. J. Newman. Hierarchical structure and the prediction of missing links in networks. Nature, Vol. 453, pp. 98-101 (2008).
Y.-Y. Ahn, J. P. Bagrow, S. Lehmann. Link communities reveal multiscale complexity in networks. Nature, Vol. 466, pp. 761-764 (2010).
E. Lieberman, C. Hauert, M. A. Nowak. Evolutionary dynamics on graphs. Nature, Vol. 433, pp. 312-316 (2005).
A.-L. Barabási. The origin of bursts and heavy tails in human dynamics. Nature, Vol. 435, pp. 207-211 (2005).

2010（平成22）年度

概要：複雑ネットワーク（あるいは，ネットワーク科学）と呼ばれる研究分野における，代表的な論文を1人1編ずつ発表する．実世界にあるネットワークの構造，ネットワークの頑健性，情報検索，グループ構造などの論文を扱う．予備知識は必要としない．

テキスト：
D. J. Watts, S. H. Strogatz. Collective dynamics of `small-world' networks. Nature, Vol. 393, pp. 440-442 (1998).
A.-L. Barabási, R. Albert. Emergence of scaling in random networks. Science, Vol. 286, pp. 509-512 (1999).
R. Albert, H. Jeong, A.-L. Barabási. Error and attack tolerance of complex networks. Nature, Vol. 406, pp. 378-382 (2000).
L. A. Adamic, R. M. Lukose, A. R. Puniyani, B. A. Huberman. Search in power-law networks. Physical Review E, Vol. 64, article No. 046135 (2001).
R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, U. Alon. Network motifs: simple building blocks of complex networks. Science, Vol. 298, pp. 824-827 (2002).
M. Girvan, M. E. J. Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America, Vol. 99, pp. 7821-7826 (2002).
A. Clauset, C. Moore, M. E. J. Newman. Hierarchical structure and the prediction of missing links in networks. Nature, Vol. 453, pp. 98-101 (2008).

2008（平成20）年度

概要：ニューロン達は、離散的・非線形的である発火 (=spike) イベントを介して情 報をやりとりする。本書は、そのようなニューロンのモデル、ニューラル・ネッ トワーク、学習、同期、振動、ノイズ、脳のコードなどの数理モデルを扱って いる。前半のいくつかの章を輪講する。予備知識は必要としない。

テキスト：Wulfram Gerstner, Werner Kistler. Spiking neuron models - single neurons, populations, plasticity. Cambridge University Press (2002).

2007（平成19）年度

概要：人間行動の利己性や利他性、病原菌の毒性、ガン、言語などの現象を、進化の 数理モデルの枠組みで統一的に説明した本。最新までの内容と、なるべく簡単 な式で本質を数理モデル化する、という精神と技法を学べる。前半の進化ゲームのいくつかの章を輪講する。予備知識は必要としない。

テキスト：Martin A. Nowak. Evolutionary dynamics --- exploring the equations of life. The Belknap Press of Harvard University Press (2006).

社会シミュレーション（東工大）

[1回目の演習内容]

Kevin Bacon ゲームを楽しむ

gephi のインストール

注：student アカウントだとインストールできない．

上記サイトにある tutorial (2種類) を行い，慣れる．「ユーザーマニュアル」の下にある。チュートリアルにあるレ・ミゼラブルが読み込めない場合は、このサイトの中に他のデータセットも置いてあるので、それでやればよい。

読み込み時に選ぶ， directed は枝に方向つき，undirected は枝に方向なし

テストデータ読み込み

描画．色々なレイアウトを試してみる．

特定の頂点の色を変えてみる．

パネルがメイン画面から消えてしまった場合、「ウィンドウ」メニューの下のタブから選択して出す。左側には「パーティション」、「ランキング」、「レイアウト」の3つのパネルがあるのが基本。真ん中は「グラフ」のパネルがあるのが基本。

解析 (1)

• 頂点数
• 枝数
• 平均次数，次数分布
• 右のパネルで，Average Degree を Run すると平均次数と同時に，各頂点の次数（右から2番目にある Data Table パネルの中の表に格納される）や次数分布の図も求まる．
• 有向ネットワークの場合，出力結果の degree = indegree + outdegree
• 次数分布をよりきれいに描くためには，Data Table からデータを読み出して（copy & paste でもよい)，他のソフト(Excel, gnuplot, etc.) で描くのがよい．
• L (characteristic path length)
• ある特定の点から，もう１つの特定の点への距離?
• その分布
• C, C_i (局所的なクラスター係数）．右のパネルで Avg. Clustering Coefficient の "Run" を押すと，平均クラスター係数 C と C_i が同時に求まる．C_i の計算結果は，右から2番目のパネル (Data Table) に表示される．
• カラースケール（または，丸の大きさ）で次数を表す．
• パネル（？）によっては，フルサイズにしないと隠れてしまっているボタンがあるので注意．

[2回目の演習内容]

他の一般的なデータ形式の読み込み（サンプルファイルはこの頁の一番下にある）．

Pajek dataset の読み込み

Pajek のデータ形式（拡張子は .net）の最小構成の例は以下。*Edges の3列目は枝重み。

*Vertices 5
1
2
3
4
5
*Edges
1 2 1.0
1 3 2.0
1 4 1.0
2 5 1.0

読み込んだデータに対して，描画や解析 (1) をしてみる．

解析 (2)

• 様々な中心性，その分布，特に近接中心性，媒介中心性
• 次数 vs 媒介中心性のプロット
• gephi の中だけではできない (or やりにくい）ので，Excel や他のプロットソフト（たとえば gnuplot はフリーの中ではお薦め）で行う．そのためには，
• "Data Laboratory" を開く．
• 右上の "Export File" を実行．
• 例えば "Separator" を Tab としておいて，必要な項目をエクスポートする．
• Excel で読みたいなら，.csv を .txt にリネームする．
• Excel で開く（他のもっとエレガントな開き方はあるかもしれないが）．
• コミュニティ構造の図示
• 右側のパネルの Statistics の Modularity を実行．すると，Q 値（コミュニティ構造に分けた時の「良さ」）が求まると同時に，コミュニティ分けも完了する．コミュニティ分割の結果を頂点の色分けで図示するには，左上の Partition パネルの "更新"（2つの黄緑色の矢印ボタン）を押した上で，pulldown メニュから，"Modularity Class" を選んで "Apply" して，描画をやり直す．
• 図の保存
• 上方の "Preview" → 微調整 → 左下の "Export (SVG/PDF)"

[3回目の演習内容]

他の解析指標の理解，利用

有向ネットワークを読み込む．

gephi の dataset に例がある？ あるいは，他のリソースから？

PageRank の計算．

元のネットワークが有向 (directed) か無向 (undirected) かを（いちいち）選択しなければならないことに注意．

Probability (p) は teleportation しない確率．授業や増田・今野の赤い本 (2010) では q.

Epsilon の値はいじらなくてよい．

無向ネットワークでは PageRank は次数と一致し，有向ネットワークでは一致しないことを確かめる．多少ずれる？

[補足]

以下のPlugInは有用そう．

SNAMetricsPlugin
右の "Statistics" パネルで解析できる項目が増える ("Erdos 数" など).

Complex Generators
一番上のマックメニュの "File" → "Generate" で scale-free network, random graph など，いろいろな人工ネットワークを作れるようになる． gephi の全ての操作を解説した manual は存在しないらしい．