Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

python-louvainでクラスタリング

More than 3 years have passed since last update.

louvainアルゴリズムでクラスタリング

クラスタリングアルゴリズムで分割するコミュニティ数がわかっていない時にModularity "Q"を最大化する手法として,Girvan-Newmanアルゴリズムを始めとした手法がある.クラスタリングについてはNewman アルゴリズムによるソーシャルグラフのクラスタリング - slideshareがわかりやすい.

その中でも現在計算量が比較的少なくなるアルゴリズムとしてlouvainアルゴリズムがある.

論文はこちら
Blondel, Vincent D., et al. "Fast unfolding of communities in large networks." Journal of statistical mechanics: theory and experiment 2008.10 (2008): P10008.

louvainアルゴリズムのpythonでのライブラリpython-louvainを使い、networkxのグラフをクラスタリングをする.

インストール

自分の環境(Python 2.7.10、pip 8.1.2)ではpipでインストールできた.

pip-install
sudo pip install python-louvain

または
ソースコードをダウンロードして

install
python setup.py install

ライブラリのインポートは

import
import community

で行える

クラスタリング

今回は以前の記事で作成したインディーズアーティストのグラフで,クラスタリングを実施する.簡易化のために2015年のデータを対象とした.ノード数は8523個,エッジ本数は61619本で重み付き無向グラフである.詳しいクラスタ分析はしていないので,何でクラスタが構成されているかは把握されていないため,louvainアルゴリズムによって最適なクラスタ数を求めながらクラスタリングするのに最適であると思われる.

グラフをそのままplotすると以下のグラフになる.
nomal.png

python-louvainの基本的なクラスタリングの計算はcommunity.best_partition(nxGraph)で行える.以下のようなdict形式で返ってくる.

In [1]: community.best_partition(G)                                          
Out[1]: 
{'nodelabel': int(community),
'nodelabel': int(community),
'nodelabel': int(community),
...

グラフをクラスタリングしてplotしてみる.サンプルを参考にplotする関数を作成.

clustering.py
import networkx as nx
import community
def clusteringplot(G):
  partition = community.best_partition(G)                                                                                                           
  size = float(len(set(partition.values())))                                                                                                 
  pos = nx.spring_layout(G)                                                                                                                  
  count = 0.                                                                                                                                 
  for com in set(partition.values()):                                                                                                        
    count += 1.                                                                                                                              
    list_nodes = [nodes for nodes in partition.keys() if partition[nodes] == com]                                                            
    nx.draw_networkx_nodes(G, pos, list_nodes, node_size=150, node_color = str(count/size))                                                                                                                                 
  plt.show()

出力されたグラフは以下.クラスタ別に色をつけている.
cluserring.png

クラスタリングその後

ここで述べられているようにクラスタリングとはある種の恣意的なものであり,重要なのはそのクラスタが何で構成されているかの意味づけであるのは間違いない.louvainアルゴリズムによってクラスタ数および構成を明らかにした後は,その構成要素の分析をし,その意味づけをしていくことを忘れてはならない.

参考

PythonとCytoScapeを使ってクラスタリングと可視化 - Qiita

chike0905
ブロックチェーンを雰囲気で研究しています。
http://chike.xyz
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away