ネットワーク分析とは

ネットワーク分析の基礎知識として用語の簡単な解説。

＞＞もう統計で悩むのを終わりにしませんか？

↑1万人以上の医療従事者が購読中

ネットワーク分析とは？
ノードとは？
エッジとは？
ノードの指標
次数とは？
中心性とは？
ネットワークの指標
コミュニティとは？
- コミュニティの検出方法
まとめ
参考サイト

ネットワーク分析とは？

ネットワーク分析とは、社会学や通信ネットワークなどの分野で用いられる分析手法である。

脳画像を用いた脳内のネットワーク分析も行われている。

このネットワーク分析は、数学のグラフ理論に基礎をおいている。

ネットワークはノード (node) とエッジ (edge) で構成されている。

ノードとは？

ノード (node) とは、ネットワークの頂点のこと。

ソーシャルネットワークであれば、人や集団など。

通信や運輸ネットワークであれば、サーバ・端末や都市・空港など。

脳内ネットワークであれば、脳内の部位など。

こういう要素がノードになりうる。

グラフ（ネットワーク図をグラフと呼ぶ）では丸や点で書くことが多い。

＞＞もう統計で悩むのを終わりにしませんか？

↑1万人以上の医療従事者が購読中

エッジとは？

エッジ (edge) とは、ノードとノードをつなぐ枝・辺・線・リンクのこと。

エッジには方向性によって２種類あって、一つは方向性があるもの (directed) 、もう一つは方向性がないもの (undirected) である。

グラフでは、方向性がある場合は矢印で書き、方向性がない場合は線で書く。

ノードの指標

ノードにまつわる指標について代表的なものを簡単に記述する。

次数とは？

次数とは、ノードが持つエッジの数である。

英語ではdegreeと呼ばれる。

次数の分布（次数分布）とは、以下のとおり計算する。

$\displaystyle \begin{equation} 次数分布 = \frac{次数 k を持つノードの数}{全体のノードの数} \end{equation}$

中心性とは？

中心性 (centrality) とは、ネットワークにおける各ノードの重要性を評価したり、比較したりするための指標である。

次数中心性とは？

よく知られていて、わかりやすい中心性の一つが、次数中心性 (degree centrality) である。

これはエッジの多い（degreeが高い）ノードが重要という指標である。

他のノードとのつながりが多いということは、中心的な役割をしているイメージがわき、理解しやすい。

計算式は以下のようになる。

$\displaystyle \begin{equation} \frac{次数 k}{ノードの数 n - 1} \end{equation}$

近接中心性とは？

近接中心性（隣接中心性も同じ。closeness centrality）とは、他の点と距離が近いほど中心性が高いとするものである。

その他のノードに短い距離でつながるノードが重要とするもので、これも直感的にわかりやすい。

$\displaystyle \begin{equation} \frac{1}{あるノードとつながる他ノードとの距離の総和} \end{equation}$

媒介中心性とは？

媒介中心性 (betweenness centrality) とは、各ノード間の最短パスを考えるとき、よく通過するノードが重要と考える指標である。

この人がいないとうまく回らないとか物事が始まらないみたいな人というふうにイメージすると重要性が理解できると思う。

もっとも一般的でよくつかわれる指標である。

\begin{equation} \sum_{i \neq j \neq k} \frac{ノード_{j-k}間の最短パスにおいてノード_iを通る最短パスの数}{ノード_{j-k}間の最短パスの数} \end{equation}

固有ベクトル中心性とは？

固有ベクトル中心性とは、隣接行列の固有ベクトルを用いて、隣接するノードの中心性を反映させた中心性が得られることを利用して、絶対値が最大の固有値に対応する第1固有ベクトルを中心性指標としたもの。

例えば、「交友関係の広い友人を何人も持っている」ような人ということに対応する。

広い人脈を持つ人とつながりがあるといえば、中心的な人と思われる。

そういう中心性である。

隣接行列について、式で表すとすると以下のようになる。

\begin{equation} \boldsymbol c = \boldsymbol {Rc} \end{equation}

$\boldsymbol c$ は中心性、 $\boldsymbol R$ が隣接行列である。

これは以下の式をまとめたものである。

\begin{equation} c_i = r_{i1} c_1 + r_{i2} c_2 + \cdots + r_{in} c_n \end{equation}

ここで $c_i$ はノードi の中心性、 $r_{ij}$ はノードj から受けるノードi の影響力に対する係数として定義したときに、ノードi の中心性の総和を計算したものである。

そして、先ほどの $\boldsymbol c = \boldsymbol{Rc}$ の式に固有値 $\lambda$ を導入する。

\begin{equation} \lambda \boldsymbol c = \boldsymbol {Rc} \end{equation}

固有値・固有ベクトル問題に帰着させるときのお決りのやり方である。

例としては主成分分析が参考になる。

toukeier.hatenablog.com

この固有値問題を解いて、絶対値最大の固有値に対応する固有ベクトルを中心性の指標とするものである。

詳細は以下の論文を参照。

ボナチッチの２つの中心性概念について

ネットワークの指標

密度とは？

密度 (network density) は、可能性のあるつながりが分母で、実際のつながりが分子としたときの比で表される値。

ネットワークの粗・密を表す指標。

式で書くと以下の通り。

エッジに方向性がない場合

$\displaystyle \begin{equation} \frac{2m}{n(n-1)} \end{equation}$

エッジに方向性がある場合

$\displaystyle \begin{equation} \frac{m}{n(n-1)} \end{equation}$

$m$ はエッジの数、 $n$ はノードの数である。

R のigraphパッケージでは、graph.density()関数で計算できる。

推移性とは？

推移性 (network transitivity) は、ある３つの頂点が相互につながっている場合、この関係性を推移的と言う。

例えば、あなたの友達の友達は、あなたの友達でもある、というような関係。

この推移的な３点が形成する「三角形」が、ネットワーク内にどれだけあるかを示す指標で、transitivity()関数で、type="global" と指定することで求めることができる。

クラスタ係数とは？

クラスタ係数 (clustering coefficient) は、ノードのクラスタ係数と、グラフのクラスタ係数がある。

ノードのクラスタ係数は、あるノードから見て、隣接するノードからなるサブグラフを考え、そのサブグラフの密度 (density) を求めたものである。

igraphパッケージでは、transitivity() で type="local" を指定する。

式で書くと以下のようになる。

$\displaystyle \begin{equation} \frac{あるノードを含む三角形の数}{k(k-1)/2} \end{equation}$

$k$ は、あるノードの次数 (degree) = エッジの数である。

グラフのクラスタ係数は、ノードのクラスタ係数を平均した値である。

igraphパッケージでは、transitivity() で type="average" を指定する。

式で書くと以下のようになる。

$\displaystyle \begin{equation} \frac{1}{n} \sum \frac{あるノードを含む三角形の数}{k(k-1)/2} \end{equation}$

$n$ は、ネットワーク内に存在するノードの数である。

相互性とは？

相互性 (reciprocity) は、向きがあるエッジのうち、双方向のエッジがどれだけあるかを表す指標。

グラフ全体において、「両想い」がどのくらいの割合を占めているか？と見ればわかりやすい。

双方向以外は、aからb (一方向１)、bからa (一方向２) の２つの一方向のエッジがあり、合計３種類ある。

相互性は以下のように計算できる。

$\displaystyle \begin{equation} \frac{双方向}{双方向＋一方向１＋一方向２} \end{equation}$

R では、reciprocity()関数で計算できる。

コミュニティとは？

コミュニティとは、ネットワーク全体の中で、密につながったグループのことを言う。

ネットワークは、均一に散らばってつながっているよりも、密につながっているグループが存在することが多い。

また、そのような比較的密に連結した部分があって、疎に連結しているような部分がある構造を見つけ出すことで、ネットワークの特徴を知ることができる。

大きな規模の複雑なネットワークを、俯瞰的に理解ができるという利点がある。

塊を見出し、理解が深まる、ということだ。

コミュニティの検出方法

コミュニティの検出方法は多岐にわたっていて、一つ一つ理解するのが大変時間がかかりそうである。

必要に応じて再度学ぶとして、いったん網羅的に解説している参考になるウェブサイトを掲載するにとどめる。

R の igraph パッケージで計算できるものが中心である。

Rとigraphを使ったネットワーク解析と可視化

セクション８．２のコミュニティの検出に記載がある。

コミュニティの検出 | R+igraph

コミュニティには、Non-overlappingとOverlappingがある。

新サイトは以下のサイト。

Takemoto Lab - R+igraph

ネットワーク分析をもうちょっと勉強 - でたぁっ感動と失敗の備忘録

igraph で利用可能なコミュニティ検出法を網羅して紹介している。

eb <- edge.betweenness.community(g) # 辺媒介性媒介性の高い辺を削除して分割
rw <- walktrap.community(g) # ランダムウォークに基くアルゴリズム
fg <- fastgreedy.community(g) # 貪欲アルゴリズム Q値が高くなるいようにペアをまとめていく
le <- leading.eigenvector.community(g) # スペクトラル最適化法グラフラプラシアンを使ってQ値が最大となるような分割を探す
ml <- multilevel.community(g) # 多段階最適アルゴリズム
sp <- spinglass.community(g) # 焼きなまし法グラフラプラシアンを使ってQ値が最大となるような分割を探す
op <- optimal.community(g) # 全探索（時間がかかるため小さなネットワークのみ有効）
ネットワーク分析をもうちょっと勉強 - でたぁっ感動と失敗の備忘録