python-louvainでクラスタリング

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

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

論文はこちら
[Blondel, Vincent D., et al. "Fast unfolding of communities in large networks." Journal of statistical mechanics: theory and experiment 2008.10 (2008): P10008.](http://iopscience.iop.org/article/10.1088/1742-5468/2008/10/P10008/meta)

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

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

```py:pip-install
sudo pip install python-louvain
```

または
[ソースコード](https://bitbucket.org/taynaud/python-louvain)をダウンロードして

```py:install
python setup.py install
```

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

```py:import
import community
```

で行える

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


グラフをそのままplotすると以下のグラフになる.
![nomal.png](https://qiita-image-store.s3.amazonaws.com/0/82740/8e199ef0-69c4-63b9-568d-30373090ec55.png)


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

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

```

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

```py: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](https://qiita-image-store.s3.amazonaws.com/0/82740/6dd055ab-e1e0-1705-d8bc-1acd1c591aab.png)



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



#参考
[PythonとCytoScapeを使ってクラスタリングと可視化 - Qiita](http://qiita.com/ysekky/items/985cf01d21c742be92e3)