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

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

s20.png

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

s50.png

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

s80.png

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. output.png On peut voir que la taille de max_cluster augmente rapidement autour de S = 500.

Faites de même avec N = 10 000.

n10k.png

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

Recommended Posts

Compter la partie concaténée maximale d'un graphe aléatoire avec NetworkX
Dessinez un graphique avec PyQtGraph Partie 5-Augmentez l'axe Y
Dessinez un graphique avec networkx
Mesurer l'importance des entités avec un outil de forêt aléatoire
Trouvez la valeur optimale de la fonction à l'aide d'un algorithme génétique (partie 2)
[Statistiques] Saisir l'image de la théorie de la limitation du pôle central avec un graphe
Créez un programme de jugement de compatibilité avec le module aléatoire de python.
Dessinez un graphique avec PyQtGraph Part 1-Drawing
Compter le nombre de caractères avec écho
Tweet les prévisions météo avec le bot Partie 2
Dessinez un graphique avec les paramètres PyQtGraph Partie 3-PlotWidget
Augmentez la taille de la police du graphique avec matplotlib
Dessinez un graphique avec les paramètres PyQtGraph Part 4-PlotItem
La base de la théorie des graphes avec l'animation matplotlib
Dessinez un graphique avec PyQtGraph Partie 6 - Affichage d'une légende
J'ai fait un graphique de nombres aléatoires avec Numpy
Obtenez le cours de l'action d'une entreprise japonaise avec Python et faites un graphique
Découpez une partie de la chaîne à l'aide d'une tranche Python
Prenez des captures d'écran LCD avec Python-LEGO Mindstorms
Visualisez le vocabulaire caractéristique d'un document avec D3.js
Dessinez un graphique avec PyQtGraph Partie 2 - Paramètres de tracé détaillés
Calculer le produit des matrices avec une expression de caractère?
Comment tracer beaucoup de légendes en changeant la couleur du graphique en continu avec matplotlib
Un diagramme de réseau a été créé avec les données du COVID-19.
Obtenez l'identifiant d'un GPU avec une faible utilisation de la mémoire
Obtenez UNIXTIME au début d'aujourd'hui avec une commande
Trouver l'index de la valeur maximale (valeur minimale) d'un tableau multidimensionnel
J'ai fait une image ponctuelle de l'image d'Irasutoya. (partie 1)
[Homologie] Comptez le nombre de trous dans les données avec Python
J'ai fait une image ponctuelle de l'image d'Irasutoya. (partie 2)
[Golang] Un programme qui détermine le tour avec des nombres aléatoires
Analysez le modèle thématique pour devenir romancier avec GensimPy3
L'histoire de la création d'un bot de boîte à questions avec discord.py
Composants liés du graphique
Que faire lorsqu'une partie de l'image d'arrière-plan devient transparente lorsque l'image transparente est combinée avec Oreiller
[Python] Un programme qui trouve le nombre maximum de jouets pouvant être achetés avec votre argent
Lire les coordonnées du tracé sur le graphe avec Python-matplotlib (super débutant)
Traitez le contenu du fichier dans l'ordre avec un script shell
Une histoire coincée avec l'installation de la bibliothèque de machine learning JAX
[python, ruby] sélénium-Obtenez le contenu d'une page Web avec le pilote Web
[Introduction à StyleGAN] J'ai joué avec "The Life of a Man" ♬
Si vous donnez une liste avec l'argument par défaut de la fonction ...
L'histoire de la création d'un pilote standard pour db avec python.
J'ai étudié avec Kaggle Start Book basé sur kaggle [Partie 1]
Obtenir l'URL du ticket JIRA créé par la bibliothèque jira-python
J'ai écrit le fonctionnement de base de Pandas dans Jupyter Lab (partie 1)
L'idée d'alimenter le fichier de configuration avec un fichier python au lieu de yaml
J'ai essayé d'exécuter la partie DNN d'OpenPose avec le processeur Chainer
Trouvez la valeur optimale de la fonction à l'aide d'un algorithme génétique (partie 1)
J'ai écrit le fonctionnement de base de Pandas dans Jupyter Lab (partie 2)
L'histoire de la création d'un module qui ignore le courrier avec python
Construction d'un environnement distribué avec la série Raspberry PI (Partie 1: Résumé de la disponibilité des clients sans disque par modèle)
Jouez avec une tortue avec des graphiques de tortue (partie 1)
Tracez un graphe avec Julia + PyQtGraph (2)
Extraire la valeur maximale avec les pandas.
Dessinez un graphique lâche avec matplotlib
Tracez un graphique avec Julia + PyQtGraph (1)
Dessinez un graphique avec Julia + PyQtGraph (3)
Graphique d'appel de sortie avec PyCallGraph
Dessinez un graphique avec des pandas + XlsxWriter