Clustering avec python-louvain

Clustering avec l'algorithme de Louvain

Pour maximiser la modularité «Q» lorsque le nombre de communautés à diviser par l’algorithme de clustering est inconnu, il existe des méthodes telles que l’algorithme Girvan-Newman. http://www.slideshare.net/komiyaatsushi/newman-6670300) est facile à comprendre.

Parmi eux, il y a l'algorithme de Louvain en tant qu'algorithme qui nécessite actuellement une quantité relativement faible de calcul.

Cliquez ici pour lire l'article Blondel, Vincent D., et al. "Fast unfolding of communities in large networks." Journal of statistical mechanics: theory and experiment 2008.10 (2008): P10008.

Clustering des graphes networkx à l'aide de python-louvain, une bibliothèque d'algorithmes de Louvain en python.

Installation

J'ai pu installer avec pip dans mon environnement (Python 2.7.10, pip 8.1.2).

pip-install

sudo pip install python-louvain

Ou Télécharger Code source

install

python setup.py install

Importer la bibliothèque

import

import community

Peut être fait avec

Clustering

Cette fois, nous allons effectuer un clustering avec le graphique de l'artiste indépendant créé dans Article précédent. Par souci de simplicité, nous avons ciblé les données de 2015. Le nombre de nœuds est de 8523 et le nombre d'arêtes est de 61 619, ce qui correspond à un graphe non orienté pondéré. Aucune analyse détaillée des clusters n'ayant été effectuée, on ne sait pas de quoi les clusters sont composés, le nombre optimal de clusters est donc déterminé par l'algorithme de louvain. Cela semble être le meilleur pour le regroupement lors de la recherche.

Si vous tracez le graphique tel quel, vous obtiendrez le graphique suivant.

Les calculs de clustering de base pour python-louvain peuvent être effectués avec community.best_partition (nxGraph). Il sera renvoyé au format dict suivant.

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

Regroupez le graphique et essayez de tracer. Créez une fonction à tracer en vous référant à l'échantillon.

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()

Le graphique de sortie est ci-dessous.

Clustering alors

Comme indiqué dans here, le clustering est une sorte de chose arbitraire, et ce qui est important, c'est de quoi le cluster est composé. Il ne fait aucun doute qu'il s'agit d'un sens.Après avoir clarifié le nombre de clusters et la configuration par l'algorithme de louvain, il ne faut pas oublier d'analyser les composants et d'en faire le sens.

référence

Clustering et visualisation à l'aide de Python et CytoScape-Qiita