執筆者 Takeshi Sakaki
この節では下記のことを学習します。
ネットワーク分析とは、現実世界に存在する巨大で複雑なネットワークの性質について分析することを指す，
現実世界に存在するネットワークは多様であり、巨大で複雑な構造を有しているが、一定の共通する性質を見出すことができる。それらの性質は「スケールフリー性」（次数分布のべき乗則）、「スモールワールド性」、「クラスター性」と呼ばれている。
従来、こうした社会的ネットワークの性質は主に社会学の研究対象となってきたが、1998年に発表された「スモールワールドモデル」という数学モデルが注目を集めた。スモールワールドモデルは、現実世界のネットワークに近いような性質を持つネットワークモデルを、極めて単純なアルゴリズムで生成するものである。この研究に触発される形で、現実世界のネットワークが持つ性質への関心が高まり、インターネット、食物連鎖、さらには論文の被引用関係や言語の文法構造といったネットワークにおいても共通の性質が発見された。
有名な事例としては，「六次の隔たり」と「蛍の木の発光同期現象」が挙げられる。
「六次の隔たり」とは「人は自分の知り合いを6人以上介すと世界中の人々と間接的な知り合いになることができる」という社会ネットワークのスモールワールド性に基づいた仮説である。
イェール大学の心理学者スタンレー・ミルグラム教はネブラスカ州オマハの住人160人を無作為に選び、「同封した写真の人物はボストン在住の株式仲買人です。この顔と名前の人物をご存知でしたらその人の元へこの手紙をお送り下さい。この人を知らない場合は貴方の住所氏名を書き加えた上で、貴方の友人の中で知っていそうな人にこの手紙を送って下さい」という文面の手紙をそれぞれに送った。その結果42通 (26.25%) が実際に届き、42通が届くまでに経た人数の平均は5.83人であった。コロンビア大学の教授ダンカン・ワッツらが電子メールで同様の実験を行った際は、到達率2%、理論的な仲介人数は5～7人であった。
「蛍の木の発光同期現象」とは，パプアニューギニア等にある「蛍の木」で，数万匹の蛍が同時に点滅を繰り返す現象である。
ダンカン・ワッツとスティーブン・ストロガッツは、
「周囲5匹と同期を取れること」「ある程度離れていても同期が取れること」ができれば、
10000匹の蛍が同時点滅できることをネットワークシミュレーションによって示した。
言い換えれば。1つのノードが周囲5つのノードに影響を及ぼせば，それがノード10000のネットワークに
情報を伝達することできる，ということである．
詳細は http://www.nature.com/nature/journal/v393/n6684/abs/393440a0.html を参照。
現実世界の様々な現象を説明する新たなパラダイムとして、複雑ネットワークの研究は現在急速に進展しており、他の研究分野との相互影響も活発化している。今後、複雑ネットワークの科学は、ネットワークの問題が関連する多数の分野において、普遍性と重要性を増していくものと予想される。
*スケールフリー性
現実世界のネットワークが持つ第1の性質は「スケールフリー性」（次数分布のべき乗則）である。これは、一部のノードが他のたくさんのノードとエッジで繋がっており、大きな次数を持っている一方で、大多数のノードはごくわずかなノードとしか繋がっておらず、次数は小さいという性質である。次数の大きなノードは「ハブ」とも呼ばれる。
数学的には、スケールフリー性はノードが次数 k を持つ確率 p(k) の確率分布が p(k) ∝ k-γ のべき乗則になると表現される[4]。このような次数分布では、分布の偏りを特徴付ける平均的な尺度（スケール）といったものが存在しない。グラフがこのような性質を持つことを「スケールフリー」と呼ぶ。また、このような確率分布のとき分散 V は無限大となる。
*スモールワールド性
現実世界のネットワークが持つ第2の性質は「スモールワールド性」である。これは、任意の2つのノードが、中間にわずかな数のノードを介するだけで接続されるという性質である。上述のミルグラムの実験は現実世界のスモール・ワールド現象を最初に実証しようとした試みであるが、近年の研究ではネットワークのスモールワールド性が実際に測定されている。
数学的には、スモールワールド性はグラフの「平均最短距離」（固有パス長もしくは直径ともいう） L がノード数 n の大きさに比べて小さい値となることで表現される。無方向・重み無しのグラフにおいて、任意のノード vi からノード vj へ行くまでに通過しなければならないエッジの最小の本数を「パス長」（距離ともいう）、パス長の中で最短のものを ij 間の「最短距離」 dij と呼ぶが、dij の平均値がそのグラフの平均最短距離である。グラフにおいて n が増大したときに L が高々 log(n) に比例する程度でゆるやかに増加するとき、そのグラフはスモールワールド性を満たすと定義される。
*クラスター性
現実世界のネットワークが持つ第3の性質は「クラスター性」である。身の回りの知人関係のネットワークを見てみよう。「自分と知人Aさんがいるときに、自分もAさんもどちらも知っている共通の知人Bさんのような人が1人もいない」という状況は、出会い系サイトでも利用しない限りまずありえない。すなわち、現実世界のネットワークには、自分、Aさん、Bさんから構成される三角形のネットワークがたくさん含まれている。このような性質を、ワッツとストロガッツは「クラスター性」と名づけた。
*エゴセントリックネットワーク
ある社会的行為者（集団を含む）が、他行為者とどのような関係を形成しているかを分析する
例１：「ある一人暮らしの老人が、どれだけの社会的サポートを得ているか」
定期的に会話をする人はどれだけいるか
最も頻繁に連絡をとっているのは誰か
例２：「ある企業が他の企業とどのような関係を持っているか」
その企業が、他の企業に対してどの程度の融資をしているか
その企業が、どのような企業の株式をどれだけ保有しているか
*ソシオセントリックネットワーク
ある社会システムが、「全体としてどのような状態にあるか」を分析する
例１：「あるサークルの運営はうまく行っているか」
サークルの中で、中心的や役割を果たしている人物は誰か
サークルの構成員の参加頻度はどのぐらいか
例２：「ある電子掲示板（ＢＢＳ）はどのような状態にあるか」
そのＢＢＳの中で、誰がどのぐらい発言しているか
ＢＢＳ参加者の間で、「派閥」ができていないか
次数分布
ネットワークにに含まれる各ノードの次数がどのように分布しているかを表す次数。
平均経路長
ネットワークに含まれるノードの全ペアの最短パス長を平均した値。
平均最短距離、平均パス長、固有パス長、直径とも呼ばれる。
次数相関
あるノードの次数とそのノードの周囲にあるノードの次数の相関を表す値。
より次数の高いノードがよりノードの高い次数とリンクを持ちやすい場合、次数相関性は正となる。
より次数の高いノードがよりノードの低い次数とリンクを持ちやすい場合、次数相関性は負となる。
クラスタ係数
ネットワークにおいて，クラスタを発見する確率。
当該ノードに接続しているリンク数。
他のノードとの距離が近さ。
当該ノードを通る経路数。
自分に対してエッジを張っているノードがどれだけの中心性を持っているか。。
*Structural Holes
ネットワークにおいて、仮にある複数ノード間にノードが存在する過程すると、
ネットワークの平均経路長が大幅に小さくなるような関係性のことを指す。「構造的空隙」とも呼ばれる。
逆に言えば、あるネットワークにおいて高いBetweeness Centralityの高いノードNを除いた際
その除いた後のネットワークにおいてNのあった場所がStructural Holeとなる。
階層的手法は，さらに分枝型 (divisive) と凝集型 (agglomerative) に分けられますが，ここでは後者のみを扱います．
この手法は，N 個の対象からなるデータが与えられたとき，1個の対象だけを含む N 個のクラスタがある初期状態を，まず作ります．この状態から始めて，対象 x1 と x2 の間の距離 d(x1,x2) (非類似度)からクラスタ間の距離 d(C1,C2) を計算し，最もこの距離の近い二つのクラスタを逐次的に併合します．そして，この併合を，全ての対象が一つのクラスタに併合されるまで繰り返すことで階層構造を獲得します．この階層構造は図4(b)のようなデンドログラムによって表示されます．デンドログラムとは，各終端ノードが各対象を表し，併合されてできたクラスタを非終端ノードで表した二分木です．非終端ノードの横軸は，併合されたときのクラスタ間の距離を表します．クラスタ C1 と C2 の距離関数 d(C1,C2) の違いにより以下のような手法があります．
*最短距離法 (nearest neighbor method) または 単連結法 (single linkage method)
d(C1,C2)=minx1∈C1,x2∈C2d(x1,x2)
*最長距離法 (furthest neighbor method) または 完全連結法 (complete linkage method)
d(C1,C2)=maxx1∈C1,x2∈C2d(x1,x2)
*群平均法 (group average method)
d(C1,C2)=1|C1||C2|∑x1∈C1∑x2∈C2d(x1,x2)
*ウォード法 (Ward’s method)
d(C1,C2)=E(C1∪C2)−E(C1)−E(C2)
ただし，E(Ci)=∑x∈Ci(d(x,ci))2 で ci はクラスタ Ci のセントロイド ∑x∈Cix/|Ci|．
Ward 法は，各対象から，その対象を含むクラスタのセントロイドまでの距離の二乗の総和を最小化する．
なお，最短距離法，最長距離法，及び，群平均法は任意の対象間の距離 d(xi,xj) が与えられている場合に適用でき，クラスタを併合した後の距離の更新は Lance-Williamsの更新式 [Lance 67] により定数時間で可能です．もし，対象が数値ベクトルで記述されている場合は，ベクトル間のユークリッド距離などを求めて適用します．Ward法は対象が数値ベクトルで与えられている場合には上記の式が直接適用でき，対象間の距離のみが与えられている場合では Lance-Williamsの更新式を使って距離の更新をします．
Lance-Williamsの更新式で定数時間で距離の更新が可能な一般の場合の計算量は O(N2logN) ですが，上記の距離更新手法には可約性 (reducibility) という性質があり，再近隣グラフの性質を活用することで O(N2) の時間で計算可能なアルゴリズム [Murtagh 83] が知られています．なお，スカラー・並列計算機上での計算量については [Olson 95] にまとめられています．
分割最適化手法は，非階層的手法の他，partitional や optimization など多くの呼び方があります．この手法は，分割の良さの評価関数を定め，その評価関数を最適にする分割を探索します．可能な分割の総数は N に対して指数的なので，実際は準最適解を求めることになります．代表的な k-means法（k平均法）は，セントロイド ci (クラスタの重心点)をクラスタの代表点とし，
∑i=1k∑x∈Ci(d(x,ci))2
の評価関数を最小化するように k 個のクラスタを分割します．最適解の探索は下記のように，対象のクラスタへの割り当てと代表点の再計算を交互に繰り返して行います．この手法は山登り法で，局所最適解しか求められないため，ランダムに初期値を変更するか，適宜互いに離れたデータ点を初期の代表点として選んで，評価関数を最小にする結果を選択するのが一般的です．
k 個の代表点 c1,…,ck をランダムに選択
X 中の全ての対象 x を c∗=argmincid(x,ci) なる代表点をもつクラスタ C∗ に割り当て
もし代表点への割り当てが変化しないならば終了し，そうでなければ各クラスタのセントロイドを代表点にしてステップ2へ
図2：k-means法
*Newman法
Modularityと呼ばれる「ネットワークのクラスタリングの結合度合い」を表す値を定義し、
それを最適化する手法。実際には、局所最適値を求める手法となる。
Modularityは、ごく簡単に述べると「クラスタ内のエッジ割合」ー「クラスタ間のエッジ割合」である。
なお、Newman法が登場して以降、Modularityを最適化する様々な手法が提案された点から考えて、
クラスタリングにおけるブレイクスルー手法である。
*Louvain法
現在（2014年4月)時点で、もっと高速かつ精度の良いModurality Optimizationアプローチのクラスタリング手法。
*NMF（Non-negative Matrix Factorizaton非負行列分解）
正もしくは０の値を要素として持つN×M行列をN×V行列とV×M行列に分解することでクラスタリングを実現する手法。
文書クラスタリングによく用いられる。
*スペクトラルクラスタリング
ネットワークを行列で表現し、そのスペクトル＝固有値と固有ベクトルを求めた後、
得られた固有ベクトルに通常のクラスタリング手法を適用する手法である。
これにより、元のネットワークより低い次元のネットワークでクラスタリングを行うことができるため、計算量の削減ができる。
言い換えれば、スペクトラルクラスタリングとは、通常のクラスタリング手法では異なる、
クラスタリングのための次元削減の手法であると言える。
最も重要な点は，クラスタリングは探索的 (exploratory) なデータ解析手法であって，分割は必ず何らかの主観や視点に基づいているということです．よって，クラスタリングした結果は，データの要約などの知見を得るために用い，客観的な証拠として用いてはなりません．この「データの要約」を直観的に理解するのに役立つように，Cutting らの研究 [Cutting 92] を紹介します．
データベースから明確な目的に適合する文書を検索する場合，キーワードを用いた文書検索手法は有効です．しかし，明確な目的がなく，データベース全体の傾向を知りたい場合はどうでしょうか？ この場合，具体的なキーワードを示すことは困難なので，文書検索手法の利用は不適当です．そこで，クラスタリングによって，その要約，すなわち，データベース中の主な話題を表すカテゴリーの一覧を取出します．Cutting らは，ニューヨーク・タイムス紙 1990 年 8 月の約 5,000 件の記事のデータベースの傾向を抽出する問題にクラスタリングを用いました．話題が類似している文書をまとめたクラスタを生成した結果，以下の話題を含むクラスタが発見されました．
教育, 国内, イラク, 芸術, スポーツ, 石油, ドイツ統合, 裁判
利用者は，内容が全く不明であった新聞記事のデータベースのおおまかな内容を，これらのクラスタから知ることができるでしょう．この要約は，一つのクラスタ，例えばイラクをさらに分割して，パキスタンやアフリカといったより詳細な要約を得たり，文書検索のためのキーワードを決める目的にも利用できます．クラスタリングは，このように，未知のデータベースの内容に見当をつける目的で利用できるため探索的であるといえます．
ここで注意すべき点は，この例では8個のクラスタに記事を分類し，データベースの「正しい」要約を得ることができました．しかし，イラクと石油はどちらも湾岸戦争に関する話題なので，これらをまとめても，データベースの「正しい」要約といえます．すなわち，どちらにも，それを正当化する視点が存在します．このように，クラスタリングの結果は絶対的でも，普遍的でも，客観的でもないので，分割結果は結論を導く証拠にはなりえません．例えば，教育と国内が違うクラスタに分類されていますが，これは実社会で二つの問題に関連性が皆無であることを意味しません．クラスタリング結果の妥当性は，その分割の利用目的など，外的な知識によって判断するしかありません． 例えば，新聞記事の話題の抽出という目的であれば，国内とドイツ統合を同じクラスタに分類していれば，妥当な要約とはいえないでしょう．ですが，同じ週に起きた事件をまとめるという目的ならば，これらをまとめるのも妥当かもしれません．クラスタリングの結果は，その利用目的などに応じて，妥当性を常に検証する必要があります．
ただし，均一に分布するデータを分割する行為は，多くの場合で妥当ではありません．この観点での妥当性については [Dubes 79] に詳しく議論されています．また，妥当性の問題に関連するものとして，クラスタ数の決定問題があります．本来，このクラスタ数も目的に応じて利用者が決めるべきものですし，『正しい』クラスタ数ということにも上記の議論があてはまるので，利用者が分割結果を解釈できれば「正しい」クラスタ数であるといえます．ですが，視覚的に非常によく分離されたクラスタ構造が存在する条件の下での，クラスタ数の決定基準を比較した研究 [Milligan 85] などはあります．
*GePhi
最近流行のツール。日本語化も進んでいる。
https://gephi.org/
*R
汎用的統計分析ツール。ネットワーク分析もできる
http://www.r-project.org/
http://www1.doshisha.ac.jp/~mjin/R/61/61.html
*NodeXL
Excel Templateなネットワーク分析ツール。
小規模ネットワーク分析ならこれで十分かも。
当然大規模ネットワークは厳しい。OSXのExcelで動くかどうかは不明。
http://nodexl.codeplex.com/
*UCINET
社会学者がよく使っている（いた）ツール。古いが、その分使い方の説明ページなどが多い。
https://sites.google.com/site/ucinetsoftware/
*NetworkX
Pythonでネットワーク分析を行うためのパッケージ。
1コマンドでいろんな事が出来るので便利。
http://networkx.github.io/
*Stanford Network Analysis Project
C++で書かれたネットワーク分析ライブラリ群。大規模データを高速に分析するのに適している。
良く出来ているが、使いこなすのはちょっと大変。
ただし、サンプルプログラムで一通りのことはできる。
http://snap.stanford.edu/
*Newman-Clauset Method
http://www.cs.unm.edu/~aaron/research/fastmodularity.htm
*Louvain Method
http://perso.uclouvain.be/vincent.blondel/research/louvain.html
*Bayon
http://code.google.com/p/bayon/wiki/Tutorial_ja
ネット上に公開されているデータから、ネットワークを構築した後、
いずれかの中心性を算出してください。
中心性の算出はプログラムを組む、ツールを使う、どちらでもかまいません。
課題１で構築したネットワークに対して、本チュートリアルで紹介したクラスタリング手法を用いて、
クラスタリングを実行してください。クラスタリングは，階層的クラスタリングの手法のいずれかとK-Meansクラスタリングの両方を適用してください。
Newman法 もしくは Louvain法を、いずれかのプログラミング言語で実装してください。
また、すでに公開されているプログラムと自分のプログラムの結果を比較し、
差異が有る場合は、その原因について考察してください。
（差異が無かった場合は、そのまま終了で構いません）