[PYTHON] Compter la partie concaténée maximale d'un graphe aléatoire avec NetworkX

J'ai découvert NetworkX, une belle bibliothèque de graphes pour Python, donc après avoir pratiqué, j'ai expérimenté "quelle est la taille de la partie concaténée maximale d'un graphe aléatoire?" (Le "graphe" ici n'est pas un diagramme qui visualise des données numériques, mais un graphe au sens d'un graphe en réseau)

Problème de réglage

• Il y a N nœuds.
• Sélectionnez au hasard deux points et connectez-les avec un bord. Ceci est répété S fois.
• Quelle est la taille maximale de la partie connectée par le côté (partie connectée)?

Ce problème est abordé dans le livre de S. Kauffman [The Logic of Self-Organization and Evolution](http://www.amazon.co.jp/gp/product/4480091246/ref=as_li_ss_tl?ie=UTF8&camp=247&creative=7399&creativeASIN=4480091246&linkCode = as2 & tag = yubais-22) »Introduit au chapitre 3, il apparaît comme faisant partie d'un modèle dans lequel la vie émerge d'un mélange de diverses substances.

Code et exécution

Ici, on suppose que networkx, numpy, matplotlib et pydot sont insérés. La procédure d'installation sera abordée à la fin.

Suite au problème ci-dessus, écrivez du code qui dessine au hasard S = 20 arêtes entre N = 100 nœuds.

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

Lorsque S = 20, le nombre maximum de pièces connectées n'est que de quatre.

Le réglage S = 50 crée un cluster assez complexe. La taille maximale est de 15.

Avec S = 80, plus de la moitié des sommets n'appartiennent plus à un seul cluster.

Ensuite, augmentez N = 1 000 et examinez la corrélation entre S et le cluster maximum. On peut voir que la taille de max_cluster augmente rapidement autour de S = 500.

Faites de même avec N = 10 000.

presque la même. On peut voir que le cluster croît en phase de transition autour de S / N = 0,5.

Installation

NetworkX lui-même est facile avec pip

# pip install networkx

Vous pouvez insuko avec. Il est préférable d'utiliser Graphviz pour rendre la visualisation du graphique belle.

# pip install pydot

Je peux y aller, mais pour une raison quelconque dans mon environnement au moment de l'exécution

NameError: global name 'dot_parser' is not defined

J'ai eu l'erreur. Quand je regarde http://stackoverflow.com/questions/15951748/pydot-and-graphviz-error-couldnt-import-dot-parser-loading-of-dot-files-will Il semble que cela ne fonctionnera pas lorsque la version de la bibliothèque appelée pyparsing deviendra 2.x. Suivez les étapes ci-dessous pour revenir à 1.5.7.

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