ネットワーク分析
SNS
ソーシャルグラフ
DataMining

ネットワーク分析 : ネットワーク指標まとめ

ネットワーク分析の基礎指標となる値についてまとめます。

「これなんだっけ」となりがちだったので、直感的なメモとして。


  • 次数

  • 次数分布

  • 最短経路長

  • 平均経路長

  • 次数相関

  • クラスタ係数


次数

ある頂点に繋がっている辺の本数を、その頂点の次数という。

下図でいうと頂点4の次数は3

スクリーンショット 2018-09-28 8.51.01.png


次数分布

ネットワークに含まれる各ノードの次数がどのように分布しているかを表す次数。

ごく簡単に言えば

横軸に次数kにとり、縦軸にそのノード数をとったもの

下図のような感じ。

スクリーンショット 2018-09-28 9.01.17.png

ノード数が大量にある時、次数分布の形によってネットワークの特徴がわかる。

e.g.

下図の崖みたいに下がってるのがスケールフリーネットワーク、山なりになっているのがランダムネットワークの特徴である。

スクリーンショット 2018-09-28 9.03.22.png


最短経路長

あるノードとあるノードの間の最短経路のこと。

最短パス長ともいいます。

下図でいうと頂点6と頂点1の最短経路長は3

スクリーンショット 2018-09-28 8.51.01.png


平均経路長

ネットワークに含まれるノードの全ペアの最短経路長を平均した値。

平均最短距離・平均パス長・直径ともいいます。


次数相関

あるノードの次数と、そのノードが隣接するノードの次数がどのような相関を持つかの指標。

高い次数のノードが高い次数のノードとリンクを持ちやすい場合は次数相関性は正となり、

高い次数のノードが低い次数のノードとリンクを持ちやすい場合が次数相関性は負となる。

e.g.

SNSでおおくの友達を持つ人の友達が、同様におおくの友達を持っている場合は次数相関性が正と言えるでしょう。


クラスタ係数


あるノードに対するクラスタ係数

あるノードに対するクラスタ係数は、

あるノードの次数をvとして、

(あるノードと隣接するノード同士のリンクの数) / v(v-1) /2

となる。これだとよくわからない。

わかりやすく言えば、「SNSで自分の友達100人いたら、その友人たち100人の中での繋がりはいくつあるのだろうか」という話。

100人の中でつくり得る友達関係は、

100 * (100- 1)/2 = 4950 通り

この4950通りの中で、たとえば50通りの友達関係があるなら、クラスター係数は

 50 / 4950 = 0.0101...

となるので、0.01くらいである。


ネットワークのクラスタ係数

全ノードのクラスタ係数の平均がネットワークのクラスタ係数。

クラスタ係数が高いとネットワークの密度が高い。

小さなサークルの交友関係などの「全員が友人同士のネットワーク」は、クラスタ係数が1になるのは想像がつくと思う。


参考資料

https://gci.t.u-tokyo.ac.jp/tutorial/network/

https://www.nii.ac.jp/userdata/shimin/documents/H19/071113_6thlec.pdf

http://syrinx.q.t.u-tokyo.ac.jp/tori/lecture/complex/network2.pdf

https://ja.wikipedia.org/wiki/%E8%A4%87%E9%9B%91%E3%83%8D%E3%83%83%E3%83%88%E3%83%AF%E3%83%BC%E3%82%AF