ネットワーク分析ならNetworkX

2019.10.31

機械学習

こんにちは。

最近、温度差が激しすぎて体調を崩しがちで非常に困っています。kzです。

今回はピープルアナリティクスというキーワードで行われるネットワーク分析のためのライブラリ、NetworkXというものを使ってみようと思います。僕も使いはじめなのでまだまだ使用が分かっていないんですがかっこいいPlotがたくさんあるのでやっていて楽しいです。

NetworkXとは？

https://networkx.github.io

めっちゃ綺麗なサイトだと思いませんか？まあそれは置いておいて、NetworkXはグラフ・ネットワークを扱うためのPythonライブラリです。数学で言うとグラフ理論という分野です。最短経路問題など扱います。キーワードで言いますと、

深さ優先探索（DFS）
広さ優先探索（BFS）
ダイクストラ法
オイラー経路
ハミルトングラフ

などですね。懐かしいです。とはいえ、身近な例、欲しいですよね。

日本の中心はどの県だ？グラフ理論（ネットワーク）の基本的な諸概念

この日本の都道府県をノードとしたネットワークは非常にわかりやすいので入門にオススメです。このようにネットワークは身近に多数存在します。そこで、LineやSlackも人をノード（県）、メッセージの向きをエッジ（繋がり）と思うとネットワークです。こうして分析したいネットワークを構成していろいろ分析していくことをネットワーク分析と言います。

ネットワーク分析の指標

指標というのは例えば、誰が重要かです。SNSのデータを使ったネットワークを例にしますと、いろんな人がいろんな話題で発言する中で、中心人物は誰だったり、会話に積極的な人は誰だったりというような「ある基準に対して誰がどのくらいそうなのか」を数値化したものです。ネットワーク分析ではその指標のことを「中心性」といい、具体的には例えば次のような指標があります。

次数中心性 (Degree)

これはあるノードが持つエッジの数です。つまり、Aさんがいろんな人に喋れば喋るほどAさんの次数中心性は高いです。一番単純かつ、直感的な指標だと思います。

近接中心性 (Closeness)

iさんの近接中心性はiさんと他の人との距離が近ければ近いほど高い指標です。ここで距離なんですが、SNEを例にとると例えば、発言数の逆数を使ったりします。式は次のとおりです。

$\frac{N-1}{\sum_{j=1 \atop j \neq i}^{N} d\left(v_{i}, v_{j}\right)}$

媒介中心性 (Betweenness)

言葉の通り、媒介すればするほど高い指標です。都道府県を例でいうと、任意の２都道府県を選んだ時に最も中継されやすい都道府県が高くなります。式はなかなか複雑です。

あるノードi（都道府県）以外の２都道府県を選び方は総数をNとすると(N-1)(N-2)/2ですね。
gは $i_s, i_t$ を結ぶ最短路でiを通るものの数。
Nは $i_s, i_t$ を結ぶ最短経路数。

$b_{i} = \frac{ \sum_{i_s = 1,i_s \neq i }^{N} \sum_{i_t = 1,i_t \neq i }^{i_s -1} \frac{ g_i^{(i_s i_t)}} { N_{i_s i_t}} }{(N-1)(N-2)/2}$