Graph Analytics with Python -Graph Partition and Community Extraction-
Tags: python, datascience, graph, networkx
Published: 2021-01-21 01:23:27

<!--グラフからグループや派閥を抽出することで，複数の部分グラフに分割することができる．分割には，グラフ分割とコミュニティ抽出が存在し，この記事ではこの二つについてコード付きで説明を行う．まずは本記事で使用するNetworkxのライブラリをロードする．-->
By extracting groups and factions from a graph, it is possible to partition it into multiple subgraphs. There are two types of partitioning, graph partitioning and community extraction, and in this article, we will explain these two types with code. First, load the Networkx library to be used in this article.

```Python
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
from networkx.algorithms.community import kernighan_lin_bisection
from networkx.algorithms.community import greedy_modularity_communities
from networkx.algorithms.community import label_propagation_communities
```

# Graph Partitioning

<!--グラフ分割の基本的なアルゴリズムとして，Kernighan-Linアルゴリズムが挙げられる．Kernighan-Linアルゴリズムでは，与えられたグラフを二つのグループに分割し，各グループから二つの頂点を選択して所属グループを交換した際に，グループ間の辺の数がもっと減少するような二頂点を交換するアルゴリズムである．詳細な説明は以下の論文や記事が参考になるので，目を通して欲しい．-->
One of the basic algorithms for graph partitioning is the Kernighan-Lin algorithm, which divides a given graph into two groups and selects two vertices from each group to exchange the groups to which they belong, such that the number of edges between the groups is The algorithm exchanges two vertices such that the number of edges between the groups decreases more. For detailed explanation, please refer to the following papers and articles.

Original Paper: [An efficient heuristic procedure for partitioning graphs](http://xilinx.asia/_hdl/4/eda.ee.ucla.edu/EE201A-04Spring/kl.pdf)

Slide about Kernighan-Lin Algorithm: [A Fundamental Bi-partition Algorithm of Kernighan-Lin ](https://www.slideserve.com/howell/a-fundamental-bi-partition-algorithm-of-kernighan-lin)

```Python
G = nx.karate_club_graph()
colors = ["#00C98D", "#5030C0", "#50F0F0"]
pos = nx.spring_layout(G)

init_nodes = np.array_split(G.nodes(), 2)
init_partition = [set(init_nodes[0]), set(init_nodes[1])]
print(init_partition)

color_map_i = ["black"] * nx.number_of_nodes(G)
counter = 0
for c in init_partition:
  for n in c:
    color_map_i[n] = colors[counter]
  counter = counter +1
nx.draw_networkx_edges(G, pos)
nx.draw_networkx_nodes(G, pos, node_color=color_map_i)
nx.draw_networkx_labels(G, pos)
plt.axis("off")
plt.show()

lst_b = kernighan_lin_bisection(G, partition=init_partition)
color_map_b = ["black"] * nx.number_of_nodes(G)
counter = 0
for c in lst_b:
  for n in c:
    color_map_b[n] = colors[counter]
  counter = counter + 1
nx.draw_networkx_edges(G, pos)
nx.draw_networkx_nodes(G, pos, node_color=color_map_b)
nx.draw_networkx_labels(G, pos)
plt.axis("off")
plt.show()
```

<!--ここではZachary's karate clubネットワークをモデルとしたグラフをKernighan-Linアルゴリズムによって分割した場合の初期状態と最終状態の両方をプロットした．-->
Here, we plot both the initial and final states of a graph modeled after Zachary's karate club network, partitioned by the Kernighan-Lin algorithm.

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

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

# Community Extraction

<!--グラフ分割とは異なり，分割数や分割後のサイズを決めることなく密な部分を抽出するアプローチをコミュニティ抽出という．ここではコミュニティ抽出の代表的な方法としてLouvain法とラベル伝搬を扱う．-->
In contrast to graph partitioning, community extraction is an approach to extract dense parts of a graph without determining the number of partitions or the size of the partitions. In this paper, we discuss the Louvain method and label propagation as representative methods of community extraction.

### Louvain Method

<!--Louvain法とは，貪欲法によってModularityを高速に求めることで，コミュニティ抽出を行う手法である．
追加で説明しておくと，Modularity は大規模なグラフ構造から高速にコミュニティを抽出する手法として，近年最も注目を集めている指標の一つであるModularity は，切り出した部分グラフがランダムグラフから異なるほど良い値となる指標である．切り出した部分グラフのModularity が高ければ，それは適切にコミュニティを抽出していることを示す．抽出したコミュニティ集合をC，コミュニティi からコミュニティj へ接続されているエッジ数をeij，グラフ構造全体に含まれるエッジの総数をm とすると，Modularity は次のように定義される．-->
The Louvain method is a method for extracting communities by rapidly computing Modularity using the greedy method. As an additional explanation, Modularity is one of the most popular metrics in recent years as a method for fast community extraction from large graph structures. Modularity is a metric that becomes better the more the cut subgraph differs from the random graph. The higher the Modularity of the extracted subgraph, the better the community is extracted. If the extracted community set is C, the number of edges connected from community i to community j is eij, and the total number of edges in the entire graph structure is m, then Modularity is defined as follows.

{% katex %}
Modularity = \frac{1}{2m}\sum_{ij}(A_{ij}-\frac{k_ik_j}{2m})\delta(c_i,c_j)
{% endkatex %}

<!--数式に説明が冗長なのもあり理解は難しいかもしれないが，要するに貪欲法でコミュニティ抽出を行うだけなので実装は非常に簡単である．Networkxには貪欲法を実装するためのgreedy_modularity_communityが用意されているのでこちらを用いるだけである．-->
It may be difficult to understand due to the redundant explanations in the formulas, but it is very easy to implement since it only uses the greedy method to extract the community.
Networkx provides a greedy_modularity_community to implement the greedy method, so we just need to use it.

```Python
G = nx.karate_club_graph()
colors = ["#00C98D", "#5030C0", "#50F0F0"]
pos = nx.spring_layout(G)

lst_m = greedy_modularity_communities(G)
color_map_b = ["black"] * nx.number_of_nodes(G)
counter = 0
for c in lst_m:
  for n in c:
    color_map_b[n] = colors[counter]
  counter = counter + 1
nx.draw_networkx_edges(G, pos)
nx.draw_networkx_nodes(G, pos, node_color=color_map_b)
nx.draw_networkx_labels(G, pos)
plt.axis("off")
plt.show()
```

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

### Label Propagation

<!--次はラベル伝搬によるコミュニティ抽出である．ラベル伝搬はすべての頂点が別々のコミュニティのラベルを持った状態を初期状態として仮定し，各頂点が周囲の頂点に合わせて自身の所属コミュニティを変更する処理を繰り返すことで，コミュニティを決定する手法である．ラベル伝搬は高速な処理が可能だが，一方で得られるコミュニティの質が高くないという問題点も存在する．実装にはNetworkxに用意されているlapel_propagation_communitiesを用いれば簡単である．-->
The next step is community extraction by label propagation. Label propagation assumes that all vertices have different community labels as the initial state, and each vertex repeatedly changes its own community according to the surrounding vertices to determine the community. Label propagation is fast, but the quality of the resulting communities is not high. It is easy to implement by using the label_propagation_communities provided in Networkx.

```Python
lst_l = label_propagation_communities(G)
color_map_b = ["black"] * nx.number_of_nodes(G)
counter = 0
for c in lst_l:
  for n in c:
    color_map_b[n] = colors[counter]
  counter = counter + 1
nx.draw_networkx_edges(G, pos)
nx.draw_networkx_nodes(G, pos, node_color=color_map_b)
nx.draw_networkx_labels(G, pos)
plt.axis("off")
plt.show()
```

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

# Conclusion

<!--本記事ではグラフ分割とコミュニティ抽出についての説明とNetworkxを使用して実装まで行った．グラフは様々な分野への応用が可能であり，こうした分割や抽出技術に関する研究は数多くされているので，下記リンクも参照してほしい．-->
This article describes graph partitioning and community extraction, and implements them using Networkx. Graphs can be applied to a variety of fields, and there is a lot of research on such partitioning and extraction techniques.

・[Streaming Graph Partitioning: An Experimental Study](https://dl.acm.org/doi/pdf/10.14778/3236187.3236208)