Pythonでグラフ理論するには？

NetworkXを使うらしい。コミュニティ検出にはpython-louvain

なんてことを、８月３日、

グラフ理論・ネットワーク分析の仕組みの解説とハンズオン
https://liberal-arts-beginners.connpass.com/event/139583/

で習ってきたのでメモ

ちなみに、セミナーの前に前もって、NetworkXのインストール
pip install networkx

---

■講義

なぜグラフ理論が必要か？
・多変量解析：データセットの傾向までを探る
　→構成要素のつながりが重要になってきている：Amazon
・グラフを用いると、世の中の、ある要素同士のつながりを表現できる

グラフの定義
・頂点：ノード　Vertex(ばーてっくす）　　　V：ノードの集合
・辺：頂点をつなぐ。エッジ　link（りんく） E：エッジの集合
・グラフ：ノードの集合とエッジの集合の組 G={V,E}
　　注意：エッジの集合だけでは、
　　　　　　どのノードにもつながっていないノード
　　　　　　→エッジない孤立したノードを表現できない
　　エッジには、向き、重さを付けられる

有向か否か
・無向グラフ：向きがない。双方向的
・有向グラフ：向きがある（一方通行）一方的なつながり→(from,to)であらわす

グラフに重み
・重み：つながりの強さ→有値グラフ
→有向有値のグラフを作れる

グラフの表現
・隣接行列：メモリくう。嫌われる
　　→Aで書くこと多い
　　　　　aij：ノードiからノードjへのエッジ→行列をかく
　　　　　要素に０が多い：疎（Sparse)

・辺リスト：メモリ問題回避
　　　　エッジを列挙する(1,2),(1,3)等
　　　　（無向グラフの時、(1,2)を書いたら(2,1)はいらない）

・隣接リスト：メモリは食わないけど、プログラミングの処理厄介
　　　from to
　　　　1 2,3,4
　　　　2 1
　　　　3 1,4
　　　　4 1,3
　　→行によって大きさが異なる


次数
・次数（入次数、出次数）ノードについて計算される
　　入次数：→が自分に入ってくる
　　出次数：→が何本出ていくか
→次数が大きい：つながり多い→ハブ？
　　入次数が大きい：注目を集めるノード？
　　出次数が大きい：アクティブなノード？

ネットワーク分析：ノードの中心性
・ネットワーク→グラフのこと（重み付きグラフ）
　　図り方：中心性　何種類も図り方がある
　　　１．次数中心性:(aの次数)/(全ノード数-1)
　　　２．媒介中心性：ほかのノードのつながりを媒介するノードを高く評価
　　　３．ページランク
　　中心性：ノードに対しての数
・リンク
　　ページランクの考え方
　　　多くのノードからリンクされているノードは重要
　　　重要なノードからリンクされるノードは重要
　　　リンクを乱発しているノードからのリンクはあまり重要でない

コミュニティ検出

　pip install python-louvain

派閥を検出したいときに使う
　派閥→コミュニティ：グラフの一部
　　　派閥でない：少ないつながり
　　　派閥　　　：多いつながり

→グラフの中でコミュニティを見つける
　　モジュラリティQ
　　　ボトムアップのクラスタリング
　　　Qを増加させるように、ノードをコミュニティに追加


■はんずおん

グラフ
import networkx as nx

描画
import matplotlib.pyplot as plt

空手クラブ：サンプルのデータ

隣接行列を入力
G=nx.Graph()
　→ノードもエッジもない無向グラフを生成
G=nx.DiGraph()
　→ノードもエッジもない有向グラフを生成
G.add_node('name')　　ノード追加
G.add_edge('A','B')　　ノード追加
G.add_nodes_from,G.add_edges_fromでリストをまとめて追加できる

中心性
betweeness centrality 媒介中心性

ランダムグラフ：２点に対して確率ｐで辺を張る

コミュニティ検出
community.best_partition(G)

中心性は０～１の間をとる
　　０に近いほど重要性は低く
　　１に近いほど重要

非連結なGを入れるとコミュニティ検出がエラーになる