Graph Modularität networkx in python

Habe ich einen Graphen in python lib NetorwkX und ich möchten, implementieren Sie eine Modularität Algorithmus, um cluster-Knoten meines Graphen. Ich kam über den folgenden code:

import community
import matplotlib.pyplot as plt
import networkx as nx

G = nx.Graph()

G = nx.read_weighted_edgelist('graphs/fashionGraph_1.edgelist')
nx.transitivity(G)

# Find modularity
part = community.best_partition(G)
mod = community.modularity(part,G)

# Plot, color nodes using community structure
values = [part.get(node) for node in G.nodes()]
nx.draw_spring(G, cmap=plt.get_cmap('jet'), node_color = values, node_size=30, with_labels=False)
plt.show()

Mein graph hat 4267 und 3692 Kanten. Der daraus resultierende plot ist:

Graph Modularität networkx in python

Ich bin ein bisschen verwirrt, wie die Knoten des Graphen gruppiert ist. Das sind genau die Logik der Farben?

Was sind für Sie die Berechnung mod?

InformationsquelleAutor snake plissken | 2015-04-27

  1. 4

    Aus der Dokumentation:

    Knoten Farbe. Kann eine einzelne Farbe, format-string, oder eine Reihe von Farben mit der gleichen Länge wie der nodelist. Wenn numerische Werte angegeben sind, werden Sie zugeordnet werden Farben mithilfe der cmap und vmin,vmax Parameter. Sehen matplotlib.scatter für mehr details.

    part = community.best_partition(G) weist eine Gemeinschaft zu der jeder Knoten - part ist ein dict, und part[node] ist die Gemeinschaft der Knoten gehört (jeder bekommt eine Zahl). Später values = [part.get(node) for node in G.nodes()] erstellt eine Liste mit der Gemeinschaft Anzahl für jeden Knoten in der Reihenfolge der Knoten im G.nodes().

    Dann in der Plot-Befehl verwenden, wird die Gemeinde zahlen, um zu bestimmen, die Farbe der Knoten. Alle Knoten, die zugewiesen wurden, um die gleiche Gemeinschaft, die gleiche Farbe.

    Die physikalischen Standorte der Knoten zugeordnet sind, durch die Feder layout. Sie können sehen, dass der Frühling layout scheint zu sein, den Knoten in Positionen, die nahelegen, dass einige Gemeinden, die unterschiedlich sind von dem, was community.best_partition findet. Dies ist vielleicht leicht überraschend, aber sicherlich nichts verhindert. Es macht mich denken, dass der Algorithmus, den Sie verwendet haben, nicht entsprechend Rechnung für alle von der Struktur des Netzes. Die Dokumentation für best_partition gibt einige Erläuterung des zugrunde liegenden Algorithmus.

    Welche version von community waren Sie mit? Meine community (heute installiert) nur hat die folgenden Attribute/Methoden: ['__builtins__', '__doc__', '__file__', '__name__', '__package__', '__path__']
    Ich eigentlich nicht haben community auf meinem computer - ich habe nicht verwendet es selbst. Diese Frage könnte(?) helfen stackoverflow.com/questions/24255143/graph-theory-in-networkx
    Ich denke eher das das Paket beschädigt ist und nicht gepflegt mehr: die Installationen sind unvollständig, links sind veraltet, E-Mail-accounts tot.

    InformationsquelleAutor Joel

  2. 1

    Grob gesprochen, die Knoten sind unterteilt in Gemeinschaften, so dass das Verhältnis von intra-community verbindungen zu inter-Gemeinschaften-verbindungen (Modularität Messen) optimiert ist.

    Eine genaue definition der Modularität von wikipedia:

    Modularität ist der Anteil der Kanten, die fallen, innerhalb der vorgegebenen Gruppen minus erwartet, wie der Bruchteil wenn die Kanten wurden verteilt nach dem Zufallsprinzip. Der Wert der Modularität liegt im Bereich [-1/2,1). Es ist positiv, wenn die Anzahl der Kanten innerhalb von Gruppen übersteigt die Zahl voraussichtlich auf der basis der chance. Für eine division des Netzwerk-Knoten in einige Module, Modularität spiegelt die Konzentration von Kanten innerhalb von Modulen im Vergleich mit zufälliger Verteilung von verbindungen zwischen allen Knoten unabhängig von Modulen.

    Den Algorithmus implementiert, durch die Gemeinschaft Paket findet näherungsweise Lösung (Trennung der Gemeinschaften) unter Verwendung iterativer Prozess, der zu Beginn definieren Sie die einzelnen Knoten als Gemeinschaft, und hält die Zusammenlegung bis Modularität optimiert.

    Genauere Infos finden Sie in dem Papier beschreibt den Algorithmus:

    Schnelle Entfaltung von Gemeinschaften in großen Netzwerken.
    VD Blondel, Guillaume JL, R Lambiotte, E Lefebvre
    Journal of statistical mechanics: theory and experiment 2008 (10), P10008

    (Ich war in der Lage, zum abrufen und installieren Sie es auf windows aus https://pypi.python.org/pypi/python-louvain)

    InformationsquelleAutor schiffli

Schreibe einen Kommentar