[PYTHON] Zählen Sie mit NetworkX den maximal verketteten Teil eines zufälligen Diagramms

Ich habe von NetworkX, einer netten Grafikbibliothek für Python, erfahren und nach dem Üben mit "Wie groß ist der maximal verkettete Teil eines zufälligen Diagramms?" Experimentiert. (Das "Diagramm" hier ist kein Diagramm, das numerische Daten visualisiert, sondern ein Diagramm im Sinne eines Netzwerkdiagramms.)

Problemstellung

• Es gibt N Knoten.
• Wähle zufällig zwei Punkte aus und verbinde sie mit einer Kante. Dies wird S-mal wiederholt.
• Was ist die maximale Größe des seitlich verbundenen Teils (verbundenes Teil)?

Dieses Problem wird in S. Kauffmans Buch Die Logik der Selbstorganisation und Evolution behandelt = as2 & tag = yubais-22) ”In Kapitel 3 vorgestellt, erscheint es als Teil eines Modells, in dem Leben aus einer Mischung verschiedener Substanzen hervorgeht.

Code und Ausführung

Hierbei wird angenommen, dass networkx, numpy, matplotlib und pydot nicht verdeckt sind. Der Installationsvorgang wird am Ende angesprochen.

Schreiben Sie nach dem obigen Problem Code, der zufällig S = 20 Kanten zwischen N = 100 Knoten zeichnet.

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt

N = 100 # number of nodes
S = 20  # number of edges

G = nx.Graph()
G.add_nodes_from(range(N))
G.add_edges_from(np.random.randint(N, size=(S,2)))

# get max connected component
max_size = 0
for component in nx.connected_components(G):
        if len(component) > max_size:
                max_cluster = component
                max_size = len(max_cluster)
print max_cluster

# draw graph
plt.title("Nodes: {}, Edges: {}, max_cluster: {}".format(N, S, max_size))
nx.draw_graphviz(G, alpha=0.3, color='r', node_size=100)
nx.draw_graphviz(G, nodelist=max_cluster, alpha=0.8, color='b', node_size=100)
plt.show()

Wenn S = 20 ist, beträgt die maximale Anzahl verbundener Teile nur vier.

Wenn Sie S = 50 einstellen, wird ein ziemlich komplexer Cluster erstellt. Die maximale Größe beträgt 15.

Mit S = 80 gehört mehr als die Hälfte der Eckpunkte nicht mehr zu einem einzelnen Cluster.

Erhöhen Sie als nächstes N = 1.000 und untersuchen Sie die Korrelation zwischen S und dem maximalen Cluster. Es ist ersichtlich, dass die Größe von max_cluster um S = 500 schnell zunimmt.

Machen Sie dasselbe mit N = 10.000.

fast das gleiche. Es ist ersichtlich, dass der Cluster phasenübergreifend um S / N = 0,5 wächst.

Installation

NetworkX selbst ist mit pip einfach

# pip install networkx

Sie können mit insuko. Es ist besser, Graphviz zu verwenden, um die Visualisierung des Diagramms schön zu gestalten.

# pip install pydot

Ich kann dorthin gehen, aber aus irgendeinem Grund zur Laufzeit in meiner Umgebung

NameError: global name 'dot_parser' is not defined

Ich habe den Fehler bekommen. Wenn ich nachschaue http://stackoverflow.com/questions/15951748/pydot-and-graphviz-error-couldnt-import-dot-parser-loading-of-dot-files-will Es scheint, dass es nicht funktionieren wird, wenn die Version der Bibliothek namens pyparsing 2.x wird. Führen Sie die folgenden Schritte aus, um zu 1.5.7 zurückzukehren.

pip uninstall pyparsing
pip install -Iv https://pypi.python.org/packages/source/p/pyparsing/pyparsing-1.5.7.tar.gz#md5=9be0fcdcc595199c646ab317c1d9a709
pip install pydot