ネットワークのクラスタリング - Louvain - 備忘録

#概要
コミュニティのクラスタリングがいずれ仕事にも使えそうなので、お試ししてみた備忘録を残す。

• 実施期間: 2021年8月
• 環境：Ubuntu20.04 LTS
• パケージ：python-louvain, networkxなど

##1. 準備
パケージをインストールする。他はインストール済みとする。

pip install python-louvain

今回使用するパケージをすべてimportする。
また、お試しのデータセットはのはkarateを使用する。
クラスタリングするときゴミノードをremoveするのでG_clsにグラフをコピー（深い）しておく

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
import community
import collections
from collections import Counter
from sklearn import preprocessing, metrics

G = nx.karate_club_graph()
G_cls = G.copy()  # クラスタリング結果用
print(nx.info(G))

# GraphRicciCurvatureからお借りしたhelper関数
# clustering_labelに対し、自動で色付けしてくださる。
def draw_graph(G, clustering_label="club"):
    """
    A helper function to draw a nx graph with community.
    """
    complex_list = nx.get_node_attributes(G, clustering_label)

    le = preprocessing.LabelEncoder()
    node_color = le.fit_transform(list(complex_list.values()))

    # nx.draw_spring(G, nodelist=G.nodes(),
    nx.draw_circular(G, nodelist=G.nodes(),
                   node_color=node_color,
                   cmap=plt.cm.rainbow,
                   alpha=0.8, with_labels=True)

# defaultで入っている属性club('Mr. Hi', 'Officer')で色分け
draw_graph(G, "club")

Name: Zachary's Karate Club
Type: Graph
Number of nodes: 34
Number of edges: 78
Average degree: 4.5882

##2. Centrality
ネットワークにおいてどのnodeが重要なのかcentralityという指標で表すことができる。文字通り中心nodeを探すわけである。
コミュニティを解析するのであれば、eigenvector_centralityやpagerankといった自分につながっているnodesの重要性も考慮した指標がいいように思う。
netowkxに実装されているcentralityは下記を参照。全部で30個近くあるのでよく調べて使うこと。

df = pd.DataFrame(columns=[i for i in range(len(G.nodes))])
df.loc['degree_centrality'] = [v for k, v in nx.algorithms.centrality.degree_centrality(G).items()]
df.loc['eigenvector_centrality'] = [v for k, v in nx.algorithms.centrality.eigenvector_centrality(G).items()]
df.loc['betweenness_centrality'] = [v for k, v in nx.algorithms.centrality.betweenness_centrality(G).items()]
df.loc['load_centrality'] = [v for k, v in nx.algorithms.centrality.load_centrality(G).items()]
df.loc['pagerank_scipy'] = [v for k, v in nx.pagerank_scipy(G, alpha=0.9).items()]

node=0, 33がどのcentralityでも上昇しているのは、karateにおいて両者が'Mr. Hi'、'Officer'の中心人物であることを示している。いわゆるインフルエンサーか。

df_t = df.T
df_t.plot()
# print(df_t.describe())

##3. Louvainでクラスタリング
Louvainのアルゴリズムは各nodesの末端から距離が近いものどうしをグルーピングする手法で、デンドログラムを描く手法
理屈を知りたければいつもお世話になっているProf. Leskovecのレクチャー拝聴のこと。どの講義もわかりやすく助かる。

今回使用するパケージであるcommunityのドキュメントはCommunity detection for NetworkX’s documentation参照
この"community"はpython-louvainパケージをインストールすると使えるようになる。
APIの使い方はcommunity API参照

流れは、
第1層目(引数:1)のデンドロをfirstPartitionに描いてもらい、
この中で小さなクラスタに属しているゴミnodesをremoveする
（計算処理に使うのはG_clsの方である点、注意）
その後再度クラスタリング(best_partition())して精度を上げる
なおremoveしたnodesも表示したいので、表示には元のGを使用する。
新しく"cls"属性をGに追加しそこにクラスタを色で登録したが、draw_graph()で描画するのであればこの色は使われない。

# ゴミnodesの削除
dendrogram = community.generate_dendrogram(G_cls)
firstPartition = community.partition_at_level(dendrogram, 1)

minCommSize=6
sparseComm = set([k for k,v in Counter(firstPartition.values()).items() if v<minCommSize])
nodes = [node for node in G_cls.nodes() if firstPartition[node] in sparseComm]
print(sparseComm)
print(f'removed: {nodes}')

G_cls.remove_nodes_from(nodes)
for i in range(len(nodes)):
    # 表示にはremoveしたnodeも灰色で表示したいのでGを使う
    G.nodes[nodes[i]]['cls'] = -1   # gray

# 本番クラスタリング
partition = community.best_partition(G_cls, resolution=0.8, random_state=30)

# 'cls'属性に色を登録（ちょっとダサい）　描画用なのでGの方
k_lst = list(partition.keys())
v_lst = list(partition.values())
color = {-1: 'gray', 0: 'r', 1: 'g', 2:'b', 3:'c', 4:'m', 5:'y'}

clr = []
for i in range(len(k_lst)):
    ii = k_lst[i]
    G.nodes[ii]['cls'] = v_lst[i]
    clr.append(color[v_lst[i]])

# 属性を確認
for i in range(len(G.nodes)):
    print(f'{i}: {G.nodes[i]}')

# 描画
draw_graph(G, "cls")
# nx.draw_networkx(G,
#                  node_size=300,
#                  node_color=clr, with_labels=True
#                  )

removed: [4, 5, 6, 10, 16]

0: {'club': 'Mr. Hi', 'cls': 1}
1: {'club': 'Mr. Hi', 'cls': 1}
2: {'club': 'Mr. Hi', 'cls': 1}
3: {'club': 'Mr. Hi', 'cls': 1}
4: {'club': 'Mr. Hi', 'cls': -1} 以下略

紫がremoveされたnodesとなる。その他のnodesは3クラスに分けられたが、ground-truthの'club'にとても一致していない。

そこでremoveしないようにminCommSize=0、デンドロの深さはbest_partition()のresolutionで調整するのでこれを1.5に変更
再度描画すると下図となる。1.準備で描いたものと比べ、node 9をnode 8にミスジャッジしている程度で、その他は正解となった。
ネットワークの規模がとても小さいのでそもそも前処理でnode削除など必要なかった。
でも規模が数千、数万nodesになったときには必要な処理と思われるので、決して無駄ではない。

次回はGraphRicciCurvatureでkarateをクラスタリングする。

以上