Clustering mit Python-Louvain

Clustering mit dem Louvain-Algorithmus

Als Methode zur Maximierung der Modularität "Q", wenn die Anzahl der durch den Clustering-Algorithmus zu teilenden Communities unbekannt ist, gibt es Methoden wie den Girvan-Newman-Algorithmus. Für das Clustering Social Graph Clustering durch den Newman-Algorithmus --slideshare ist leicht zu verstehen.

Unter diesen gibt es den Louvain-Algorithmus als einen Algorithmus, der derzeit einen relativ geringen Rechenaufwand erfordert.

Klicken Sie hier für das Papier Blondel, Vincent D., et al. "Fast unfolding of communities in large networks." Journal of statistical mechanics: theory and experiment 2008.10 (2008): P10008.

Clustering von networkx-Diagrammen mit Python-Louvain, einer Bibliothek von Louvain-Algorithmen in Python.

Installation

Ich konnte mit pip in meiner Umgebung installieren (Python 2.7.10, pip 8.1.2).

pip-install

sudo pip install python-louvain

Oder Laden Sie [Quellcode] herunter (https://bitbucket.org/taynaud/python-louvain)

install

python setup.py install

Bibliothek importieren

import

import community

Kann mit gemacht werden

Clustering

Dieses Mal werden wir Clustering mit dem Diagramm des Indie-Künstlers durchführen, das in Vorheriger Artikel erstellt wurde. Der Einfachheit halber haben wir die Daten für 2015 als Ziel ausgewählt. Die Anzahl der Knoten beträgt 8523 und die Anzahl der Kanten beträgt 61.619. Dies ist ein gewichteter ungerichteter Graph. Da keine detaillierte Clusteranalyse durchgeführt wurde, ist nicht bekannt, woraus die Cluster bestehen, sodass die optimale Anzahl von Clustern durch den Louvain-Algorithmus bestimmt wird. Es scheint am besten für Clustering während der Suche zu sein.

Wenn Sie das Diagramm so zeichnen, wie es ist, erhalten Sie das folgende Diagramm.

Grundlegende Clusterberechnungen für Python-Louvain können mit community.best_partition (nxGraph) durchgeführt werden. Sie werden im folgenden Diktatformat zurückgegeben.

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

Gruppieren Sie das Diagramm und versuchen Sie es mit dem Plotten. Erstellen Sie eine Funktion zum Plotten, indem Sie sich auf das Beispiel beziehen.

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

Das Ausgabediagramm ist unten dargestellt. Nach Cluster gefärbt.

Clustering dann

Wie in hier angegeben, ist Clustering eine willkürliche Sache, und wichtig ist, woraus der Cluster besteht. Es besteht kein Zweifel, dass es sich um eine Bedeutung handelt. Nachdem wir die Anzahl der Cluster und die Konfiguration durch den Louvain-Algorithmus geklärt haben, dürfen wir nicht vergessen, die Komponenten zu analysieren und die Bedeutung zu bestimmen.

Referenz

Clustering und Visualisierung mit Python und CytoScape-Qiita