[PYTHON] Count the maximum concatenated part of a random graph with NetworkX

I found out about NetworkX, a nice graph library for Python, so after practicing, I experimented with "what is the size of the maximum connected part of a random graph?" (The "graph" here is not a diagram that visualizes numerical data, but a graph in the sense of a network graph)

Problem setting

This issue is addressed by S. Kauffman's book [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) ”Introduced in Chapter 3, it appears as part of the model of life emergent from a mixture of various substances.

Code and execution

Here, it is assumed that networkx, numpy, matplotlib, and pydot are inscored. The installation procedure will be touched upon at the end.

Following the above problem, write code that randomly draws S = 20 edges between N = 100 nodes.

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

When S = 20, the maximum number of connected parts is only four.

s50.png

Setting S = 50 creates a fairly complex cluster. The maximum size is 15.

s80.png

With S = 80, more than half of the vertices no longer belong to a single cluster.

Next, increase it to N = 1,000 and examine the correlation between S and the maximum cluster. output.png It can be seen that the size of max_cluster increases rapidly around S = 500.

Do the same with N = 10,000.

n10k.png

almost the same. It can be seen that the cluster becomes huge in a phase transition around S / N = 0.5.

Installation

NetworkX itself is easy with pip

# pip install networkx

You can insuko with. It is better to use Graphviz to make the visualization of the graph beautiful, which is

# pip install pydot

I can go there, but for some reason in my environment at runtime

NameError: global name 'dot_parser' is not defined

I got the error. When I look it up http://stackoverflow.com/questions/15951748/pydot-and-graphviz-error-couldnt-import-dot-parser-loading-of-dot-files-will It seems that it will not work when the version of the library called pyparsing becomes 2.x. Follow the steps below to return to 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

Count the maximum concatenated part of a random graph with NetworkX
Draw a graph with PyQtGraph Part 5-Increase the Y-axis
Draw a graph with networkx
Measure the importance of features with a random forest tool
Find the optimal value of a function with a genetic algorithm (Part 2)
[Statistics] Grasp the image of the central limit theorem with a graph
Create a compatibility judgment program with the random module of python.
Draw a graph with PyQtGraph Part 1-Drawing
Count the number of characters with echo
Tweet the weather forecast with a bot Part 2
Draw a graph with PyQtGraph Part 3-PlotWidget settings
Increase the font size of the graph with matplotlib
Draw a graph with PyQtGraph Part 4-PlotItem settings
The basis of graph theory with matplotlib animation
Draw a graph with PyQtGraph Part 6-Displaying a legend
I made a random number graph with Numpy
Get the stock price of a Japanese company with Python and make a graph
Cut a part of the string using a Python slice
Take a screenshot of the LCD with Python-LEGO Mindstorms
Visualize the characteristic vocabulary of a document with D3.js
Draw a graph with PyQtGraph Part 2--Detailed plot settings
Calculate the product of matrices with a character expression?
How to plot a lot of legends by changing the color of the graph continuously with matplotlib
A network diagram was created with the data of COVID-19.
Get the id of a GPU with low memory usage
Get UNIXTIME at the beginning of today with a command
Find the index of the maximum value (minimum value) of a multidimensional array
I made a dot picture of the image of Irasutoya. (part1)
[Homology] Count the number of holes in data with Python
I made a dot picture of the image of Irasutoya. (part2)
[Golang] A program that determines the turn with random numbers
Analyze the topic model of becoming a novelist with GensimPy3
The story of making a question box bot with discord.py
Connected components of the graph
What to do when a part of the background image becomes transparent when the transparent image is combined with Pillow
[Python] A program that finds the maximum number of toys that can be purchased with your money
Read the coordinates of the plot on the graph with Python-matplotlib (super beginner)
Process the contents of the file in order with a shell script
A story stuck with the installation of the machine learning library JAX
Save the result of the life game as a gif with python
[python, ruby] fetch the contents of a web page with selenium-webdriver
[Introduction to StyleGAN] I played with "The Life of a Man" ♬
If you give a list with the default argument of the function ...
The story of making a standard driver for db with python.
I studied with Kaggle Start Book on the subject of kaggle [Part 1]
Get the URL of a JIRA ticket created with the jira-python library
I wrote the basic operation of Pandas with Jupyter Lab (Part 1)
The idea of feeding the config file with a python file instead of yaml
I tried running the DNN part of OpenPose with Chainer CPU
Finding the optimum value of a function using a genetic algorithm (Part 1)
I wrote the basic operation of Pandas with Jupyter Lab (Part 2)
The story of making a module that skips mail with python
Building a distributed environment with the Raspberry PI series (Part 1: Summary of availability of diskless clients by model)
Play with a turtle with turtle graphics (Part 1)
Draw a graph with Julia + PyQtGraph (2)
Extract the maximum value with pandas.
Draw a loose graph with matplotlib
Draw a graph with Julia + PyQtGraph (1)
Draw a graph with Julia + PyQtGraph (3)
Output the call graph with PyCallGraph
Draw a graph with pandas + XlsxWriter