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

• There are N vertices (nodes).
• Randomly select two points and connect them with an edge. This is repeated S times.
• What is the maximum size of the part connected by the sides (connected part)?

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

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

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

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. It can be seen that the size of max_cluster increases rapidly around S = 500.

Do the same with N = 10,000.

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