ネットワーク分析1　基礎知識

[Aidemy](https://aidemy.net/)　2020/12/8
#はじめに
　こんにちは、んがょぺです！バリバリの文系ですが、AIの可能性に興味を持ったのがきっかけで、AI特化型スクール「Aidemy」に通い、勉強しています。ここで得られた知識を皆さんと共有したいと思い、Qiitaでまとめています。以前のまとめ記事も多くの方に読んでいただけてとても嬉しいです。ありがとうございます！
　今回は、ネットワーク分析の一つ目の投稿になります。どうぞよろしくお願いします。

＊本記事は「Aidemy」での学習内容を「自分の言葉で」まとめたものになります。表現の間違いや勘違いを含む可能性があります。ご了承ください。

今回学ぶこと
・ネットワーク分析について
・基本用語
・グラフの作成

#ネットワーク分析について
##ネットワーク分析とは
・__ネットワーク分析__とは、__グラフを用いてさまざまな事象と事象の関係について調べる__という分析手法である。ここでいう__「ネットワーク」__とは、いわゆるコンピューターネットワークに限らず、広く__「複数の点がなんらかの関係で繋がっている（線になっている）」__物を指す。例えば、人と人をそれぞれ点とすれば、それを繋げば__「人間関係」__となる。ちなみに、友人関係、血縁関係といった人間関係は__「社会ネットワーク」__と呼ばれる。このネットワークを可視化したものが__「グラフ」__となる。このグラフも、一般的な意味とは必ずしも一致しないため、注意する。
・ネットワーク分析の応用例として、__ネットワークの中心性__を分析して影響力のある人物を特定する__「ソーシャルネットワーク」__、企業間の取引データから業種の分類などを行う__「企業間ネットワーク」__などがある。
・今回は、__networkx__というネットワーク分析用ライブラリを使い、ネットワークの__「クラスタリング」__や__「中心的なノードの発見法」__を学んでいく。Chapter1では__このライブラリの関数の説明__を行う。Chapter2では__karateclub__というデータセットを使って、実際にデータ分析を行う。

##グラフの描画例
・Chapter1では、__networkx__ライブラリの使い方の中でも、特に__グラフの記述__についてを学んでいく。グラフは__点と線からなる関係構造を可視化したもの__、ということができる。
・グラフの作成はこのnetworkxで行うが、表示については今までと同様に__「plt.show()」__で行う。以下は実際にグラフを作成し、表示したものである。（コードについては後述する。）

![スクリーンショット 2020-12-03 20.22.29.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/3de6e4ec-810a-7e10-76cb-265827ff7090.png)


#グラフ理論の基礎
##基本用語
・前項のような、__グラフを数学的に扱う分野__を__「グラフ理論」__という。
・基本用語について、グラフを構成する各点を__「頂点（ノード）」__という。そして、この頂点同士を結んだ線を__「辺（エッジ）」__という。
・ベクトルのように__「矢印の向き」__がある辺を含むグラフのことを__「有向グラフ」__といい、全ての辺に向きがないグラフを__「無向グラフ」__という。
・そして、この__点と辺を連続で辿ったもの__を、文字通り__「道（path）」__という。有向グラフの場合は、辺の向きが進む方向と一致していなければ、道とはならない。また、一般的に「道」というときは、同じ頂点は二度と通らない物を指す。
![スクリーンショット 2020-12-03 20.43.05.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/0ad4e19d-ac52-e7fd-6468-ab806c2e5447.png)

##その他の用語（応用）
・「辺」に数字が書いてあるものを、__「重み付きグラフ」__といい、その数字のことを__「重み」__という。ニューラルネットワークでよく見られる。また、ある頂点から頂点に移動する道を考えるとき、通過する__重みの合計が最小になるもの__を__「最短経路」__という。
・道のうち、循環になっている（一回りすると最初の頂点に戻る）物を__「閉路」__という。
![スクリーンショット 2020-12-03 20.53.31.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/2b45c885-b981-173c-7644-79cdc755d262.png)

・また、閉路を持たないグラフのことを__「木」__という。そして、木の一番上の頂点を__「根」__、一番下の頂点を__「葉」__という。自分より上位にある頂点を__「親」__、下位にある頂点を__「子」__という。
・木の特徴として、辺の数の合計が__「頂点の数-1」__で求められることが挙げられる。
![スクリーンショット 2020-12-03 21.00.14.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/0ad1b13e-f821-bbb3-21de-ce616e49d236.png)

・他のグラフとしては、__「二部グラフ」__というものがある。これは、頂点を__2グループに分け__て、各グループ同士では辺をつくらず、違うグループ同士でのみ辺を作るものを指す。以下の図では、赤いグループと青いグループで分け、同じグループ内では辺が作られていないことがわかる。
![スクリーンショット 2020-12-03 22.02.40.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/a2be50e9-b479-5e63-12f6-c4f7f5adc686.png)

##用語（発展）
・有向グラフにおいて、__方向を無視しないで__どの頂点との間にも道が存在するものを__「強連結」__という。一方で、__方向を無視した場合__（無効グラフとして見た場合）に任意の二点間に道が存在するものを__「弱連結」__という。

![スクリーンショット 2020-12-04 0.20.06.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/e4a61baa-382e-98a2-7817-24e3caab2d1c.png)

・次に、__隣接行列__について見ていく。以下は、上記グラフのうちの一つ目（強連結の有向グラフ）の隣接行列である。![スクリーンショット 2020-12-04 0.25.38.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/78b605da-7ed8-0109-d247-f3ae19d4ae52.png)

・それぞれの行についてみてみる。まず一行目については__2列目と5列目が「1」__となっている。これは、__頂点「1」から頂点「2」と「5」への辺が存在している__ことを表す。逆に「0」の部分は頂点1からの辺が存在していないことを表す。また、自分自身（頂点「1」）への辺は存在していないものとして扱う。それ以降の行についても同様に考えることができる。
・そして、以下がこのグラフの__隣接リスト__と呼ばれるものである。![スクリーンショット 2020-12-04 0.29.53.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/8b674779-a08c-16e4-1899-fe3acf7c64d6.png)

・これは、i番目のリストには、頂点iから辺が出ている頂点が格納されている。基本的には隣接行列から得られる情報と変わりはないが、それぞれ以下のような特徴がある。
　・隣接行列の方が計算で扱いやすい。
　・隣接リストの方が消費メモリが少ない。
　・頂点iからどの頂点への辺が出ているかを確認するとき、隣接リストの方が参照数は少ない。

・最後に、ある頂点につながっている辺の数を__「次数」__という。特に有向グラフについて、その頂点に入ってくるような辺の数を__「入次数」__、出ていくような辺の数を__「出次数」__という。

#networkxについて
##グラフの描画の実装
・以下は、最初に作成したグラフの描画のコード例である。このコードについて、詳しく説明していく。
![スクリーンショット 2020-12-04 0.40.18.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/ca98d7b0-d1e7-bc2d-65d1-5459642b058f.png)

・まず、__「G=nx.path_graph(5)」__について、これは__「nx.path_graph()」__によって「G」という__無向グラフ__を作成していることを示す。引数で、頂点の数を指定する。頂点は後から追加できるので、この値は厳密に決める必要はない。今回の例で言えば、5と指定しているので、それぞれラベルが「0~4」の5つの頂点が一繋ぎの辺となって作成されている。ちなみに、__「nx.Graph()」__とすることで、まっさらなグラフを作成できる。
・__「G.add_edge()」__で、指定した頂点を結ぶ__辺を追加__している。この段階で存在していない頂点が指定された場合は__自動的に追加される__。
・__「pos = nx.spring_layout(G)」__で、Fruchterman-Reingold force-directed algorithmという力学モデルの描画アルゴリズムで、__頂点を描画する位置__を決めている。この部分はなくても構わない。
・__「nx.draw_networkx(G)」__で、作成した__グラフGを描画__する。これを__「plt.show()」__とすることで、__表示できる__。

##有向グラフの描画
・__有向グラフ__については、グラフの作成時に__「nx.DiGraph()」__とすれば良い。あとは基本的には同じ。
・有向グラフに限らず、まとめて辺を作成したいときは__「G.add_edges_from()」__に、__辺のリスト__を渡せば良い。有向グラフの場合、辺の指定は__(入力点,出力点)__とする。例えば(0,1)なら頂点0から頂点1に向かう辺が作成され、(1,0)なら頂点1から頂点0に向かう辺が作成される。このように__指定順で意味が異なる__ので注意する。
また、頂点をまとめて追加したい時は__「G.add_nodes_from()」__に、同じように頂点のリストをまとめれば良い。

![スクリーンショット 2020-12-04 1.13.35.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/3a444afa-100f-7c10-d837-4ea5b2533294.png)

##頂点と辺の描画
・__「draw_networkx_nodes()」__で頂点を、__「draw_networkx_edges()」__で辺を、それぞれ__色や大きさを指定して__描画することができる。
・各引数について、__「G」「pos」__はこれまでと同様に指定する。ちなみに、ここでの__posは必須__となる。
・__「nodelist」__で、描画したい頂点をリストで渡して指定する。__「node_color」__で頂点の色を指定でき、__「node_size」__で大きさを指定できる。この3つについては「node」の部分を__「edge」__とすれば辺についても同じように指定できる。
・頂点について、__「alpha」__で透過度を指定できる。0〜1の値を取る。また、辺については__「width」__で太さを指定できる。

・コード![スクリーンショット 2020-12-04 1.28.45.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/ebe38522-61e9-0a35-7213-bca97a52ac7a.png)


・結果![スクリーンショット 2020-12-04 1.29.02.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/b7a315cc-ef13-d5dd-1f40-5d590409fe37.png)

##グラフに重みを加える
・グラフGに、__「add_weighted_edges_from()」__というメソッドを使うと、__重みを付け加える__ことができる。引数には__「(頂点1,頂点2,重み)」__をまとめたリストを渡す。
![スクリーンショット 2020-12-04 10.04.48.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/ecd03569-0daa-eb3b-da2e-d5c2b9725a72.png)

・これを使って作成した以上のグラフについて、networkxのメソッドを試していく。
・__「nx.info(G)」__とすると、グラフGの基本情報が出力される。
![スクリーンショット 2020-12-04 10.06.35.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/bfb35ee7-388d-23a6-c7ac-61883bd295da.png)

・__Type__はグラフの種類、__Number of nodes(edges）__は頂点(辺)の数、__Average degree__は全ての頂点から出ている辺の平均数である。
・__「G.nodes()」__というようにすると、頂点をリスト型で取得できる。同様に、__「G.edge()」__とすると辺を構成する頂点をリスト型で取得できる。
・また、__「G.degree()」__とすると、すべての点における次数（隣接する点の数）が取得できる。
・__「nx.adjacency_matrix(G)」__とすることで、Gの__隣接行列__が取得できる。ただし、返り値はリストではないので、そのままでは扱えない。以下では、重み付きグラフGについて、隣接行列を取得し、その各要素（頂点）について、__i行j列目（頂点iとj）の辺の重みが0でなければ道が存在する__ということになるので、その部分の辺について、重みを取得して、隣接リストadj_listに格納している。

・コード（Gの作成〜隣接行列の取得まで）![スクリーンショット 2020-12-04 11.25.21.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/ae46b834-7e31-13d1-7ddf-9968f28a9740.png)

・結果![スクリーンショット 2020-12-04 11.25.34.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/36a18ac3-aade-081a-ef4c-3d1cd6e930a9.png)

・これを見ると、__「adj_matrix」__には__「頂点1,頂点2,重み」__というような隣接行列が作成されていることがわかる。

・コード（隣接リストの作成と表示）![スクリーンショット 2020-12-04 11.28.42.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/571cfa1b-0daf-25d9-5e1d-970c0299af9b.png)

・結果![スクリーンショット 2020-12-04 11.28.53.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/8794f7dd-6dc0-c3fc-d1a6-8f2c98ad1f28.png)

・__「adj_matrix[(i, j)]」__で、頂点(i, j)間の辺の重みが取得できる。辺が存在しなければ0を返す、それ以外の値であれば、その値を重みとする辺が存在するということになる。よって、隣接リスト「adj_list」の「i」番目について、__(j, adj_matrix[(i,j)])__として格納することで、例えばadj_list[0]の値が(1,5)であれば、「頂点0から頂点1の辺の重みは5である」という意味を持つリストが作成できる。

##networkxのその他のメソッド（応用）
・他のメソッドとしては、グラフを__連結成分__で分割する__「nx.connected_component_subgraphs(G)」__がある。__「連結成分」__については、次のChapterで説明する。以下では、__「0~4の線」__と__「5~6の線」__を連結し、これで分割したものをリスト化して、前者はG[0]、後者はG[1]と、分けて描画している。
![スクリーンショット 2020-12-04 11.55.08.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/f91ee081-d01f-6d16-f602-2659a340c75e.png)

・結果![スクリーンショット 2020-12-04 11.55.22.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/bdb1c68c-ebbb-9fa1-b7bc-ceb478dd6a2d.png)

・次のメソッドは__「nx.all_pairs_dijksta_path(G)」__で、これは、__「ダイクストラ法」__というもので、頂点間の__最短経路を求める__ことができる。最短経路は__「重みが最も小さくなるような道」__のことである。よって、前に行った方法で重み付きグラフを作成し、それをGとしてこのメソッドを使い、辞書型で取得すると、__{i:{j:[最短経路の時に通る頂点のリスト]}}__という辞書で、iからjまでの最短経路を取得できる。以下では、この最短経路の距離（重みの合計）も算出している。
・距離の求め方について、辺の重みは__「edge_labels[i,j]」__で求められる。これを応用して、距離を足し合わせている。

![スクリーンショット 2020-12-04 12.18.14.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/8572ceeb-9934-5637-6b55-d986349e2863.png)

・結果（一部のみ）![スクリーンショット 2020-12-04 12.19.01.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/698700/852030fd-bcc2-7b70-d590-86440e36fcea.png)


#まとめ
・__ネットワーク分析__とは、__グラフ__を使ってさまざまな事象の関係について調べる分析手法である。この時のグラフ上でのそれぞれの事象を__頂点（node）__、繋がりを__辺（edge）__という。
・ネットワーク分析では、__networkx__というライブラリを使用する。グラフもこれを使って作成する。__無向グラフ__は__「nx.path_graph()」__で作成できる。__有向グラフ__は__「nx.DiGraph()」__で作成でき、__「nx.Graph()」__は条件のないグラフが作成される。
・このグラフに頂点や辺を追加していくことでグラフを作成していく。作成したグラフの描画は__「nx.draw_networkx(G)」__のように行う。
・グラフの辺に__重み__を付け加える時は__「add_weighted_edges_from()」__を使うことで行える。また、この重みについて、__隣接行列__や__隣接リスト__に変換することで、計算などにも使えるようになる。

今回は以上です。最後まで読んでいただき、ありがとうございました。