Graph Analytics with Python -Graph Visualization and Centrality-
Tags: python, datascience, graph, networkx
Published: 2021-01-18 02:23:30

<!--この記事では，グラフ分析について説明を行う．ここで言うグラフとは，棒グラフや円グラフのことではなく，ノードとエッジの集合で構成されるグラフ理論の意味合いでのグラフを指す．身近なグラフの例としては，ソーシャルネットワークにおけるユーザとツイート関係や論文の引用関係，そしてWebページ間のハイパーリンク関係等が挙げられる．他にもグラフ形式のデータに変換することで，ノードやエッジの予測やグラフ伝播の流れを可視化することができる．この記事ではPythonとNotebookを用いて簡単なグラフ分析を行う-->
In this article, I will explain about graph analysis. The term "graph" here does not refer to bar graphs or pie charts, but to graphs in the sense of graph theory, which are composed of a set of nodes and edges. 
Familiar examples of graphs include the relationship between users and tweets in twitter networks, citation relationships in papers, and hyperlink relationships between web pages. 
By converting the data into a graph format, we can predict nodes and edges and visualize the flow of graph propagation. In this article, I will use Python and Networkx to perform a simple graph analysis.

# Load Graph Data

<!--まずはlesmis.gmlをダウンロードして読み込む．file.upload()を使うことで簡単にデータを読み込ませられる．-->
First, download and load lesmis.gml. 
file.upload() makes it easy to load the data.

```Python
import networkx as nx
from google.colab import files
uploaded = files.upload()
```

<!--uploadedに格納したlesmisのグラフを可視化する．可視化にはnetworkxを用いて行う．-->
Visualize the graph of lesmis stored in uploaded data by Networkx.

```Python
for fn in uploaded.keys():
  print("User uploaded file '{name}' with length {length} bytes".format(name=fn, length=len(uploaded[fn])))
  G = nx.readwrite.gml.read_gml(fn)
  nx.draw_spring(G, node_size=200, node_color="#00C98D", with_labels=True)
```

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/0nzj58giz9hi54dye13f.png)

<!--グラフの形式には他にもあるので，リンクを参考にして他のも試してみて欲しい-->
There are other types of graphs, so please refer to the links and try the other ones.

[Networkx: Drawing](https://networkx.org/documentation/stable//reference/drawing.html)

# Centrality

<!--グラフ分析では，どの頂点が中心的であるかを調査することがある．論文の引用関係では基礎技術に関わる論文は数多く引用されることが多く，そのような論文が万が一欠損してしまうと引用関係グラフが分裂してしまう．そのような場合，その論文は引用関係グラフにおける中心だと考えられ，この中心性には次数中心性，固有ベクトル中心性，近接中心性，媒介中心性等が挙げられる．-->
In graph analysis, we sometimes investigate which vertices are central. In the citation relation of papers, papers related to basic technology are often cited a lot, and if such a paper is missing, the citation relation graph will be split. 
In such a case, the paper is considered to be the center of the citation relation graph. 
There are some graph metrics to quantify centrality, degree centrality, eigenvector centrality, proximity centrality, mediation centrality, etc.

<!--まずは各グラフごとにヒートマップをプロットする関数を作成する-->
First, I will create a function to plot a heat map for each graph.

```Python
def draw_heatmap(G, pos, measures, measure_name):
  nodes = nx.draw_networkx_nodes(G, pos, node_size=250,
                                 cmap = plt.cm.plasma,
                                 node_color = list(measures.values()),
                                 nodelist=list(measures.keys()))
  nodes.set_norm(mcolors.SymLogNorm(linthresh=0.01, linscale=1))
  edges = nx.draw_networkx_labels(G, pos)
  plt.title(measure_name)
  plt.colorbar(nodes)
  plt.axis("off")
  plt.show()
```

<!--次に次数中心性を計算およびヒートマップとしてプロットする．次数中心性は多くの頂点とつながっている頂点を中心としてみなすグラフメトリクスである．-->
Next, we compute degree centrality and plot it as a heatmap. Degree centrality is a graph metric that considers a vertex connected to many other vertices as the center.

```Python
pos = nx.spring_layout(G)
draw_heatmap(G, pos, nx.degree_centrality(G), "Degree Centrality")
```

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/hqqkqrkpb93fargtn80h.png)

<!--次に固有ベクトル中心性を計算およびヒートマップとしてプロットする．固有ベクトル中心性は周囲の頂点の中心性も加味して，多くの中心的な頂点とつながっている頂点を中心的とみなすグラフメトリクスである．-->
Next one is Eigenvector centrality. 
Eigenvector centrality is a graph metric that considers a vertex to be central if it is connected to many other central vertices, taking into account the centrality of surrounding vertices.

```Python
pos = nx.spring_layout(G)
draw_heatmap(G, pos, nx.eigenvector_centrality(G), "Eigenvector Centrality")
```

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/kx27oz5j0h3c8yny6txv.png)

<!--次に近接中心性を計算およびヒートマップとしてプロットする．近接中心性はグラフ中の他の頂点へ短い距離で到達できる頂点を中心的としてみなすグラフメトリクスである．-->
Next, we compute the closeness centrality and plot it as a heatmap. closeness centrality is a graph metric that considers as central a vertex that can be reached in a short distance to other vertices in the graph.

```Python
pos = nx.spring_layout(G)
draw_heatmap(G, pos, nx.closeness_centrality(G), "Closeness Centrality")
```

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/8g1ymfbcden0h664hwr8.png)

<!--最後に媒介中心性を計算およびヒートマップとしてプロットする．媒介中心性はその頂点が欠損してしまうと多くの経路が分断されてしまうような頂点を中心的としてみなすグラフメトリクスである．-->
Finally, the betweenness centrality is calculated and plotted as a heat map. Betweenness centrality is a graph metric that considers a vertex as central, such that the loss of that vertex would cause many paths to be fragmented.

```Python
pos = nx.spring_layout(G)
draw_heatmap(G, pos, nx.betweenness_centrality(G), "Betweenness Centrality")
```

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/jsnmtlws5bzv11aygy8m.png)

<!--他にもnx以降の部分を書き換えることで，様々な中心性を計算することが可能となっている．-->
It is also possible to compute various other types of centrality by rewriting the parts after nx.

[Networkx: Centrality](https://networkx.org/documentation/networkx-1.10/reference/algorithms.centrality.html)

# Conclusion

<!--この記事では，グラフ分析においてまず最初のグラフのロードと，それらの可視化，最後に中心性について説明を行った．-->
In this article, I explained first the loading of graphs in graph analysis, then their visualization, and finally their centrality.