1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
{
"cells": [
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"%matplotlib inline"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n# Giant Component\n\nThis example illustrates the sudden appearance of a\ngiant connected component in a binomial random graph.\n\nThis example needs Graphviz and PyGraphviz.\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import math\n\nimport matplotlib.pyplot as plt\nimport networkx as nx\n\nn = 150 # 150 nodes\n# p value at which giant component (of size log(n) nodes) is expected\np_giant = 1.0 / (n - 1)\n# p value at which graph is expected to become completely connected\np_conn = math.log(n) / n\n\n# the following range of p values should be close to the threshold\npvals = [0.003, 0.006, 0.008, 0.015]\n\nfig, axes = plt.subplots(2, 2)\nfor p, ax, seed in zip(pvals, axes.ravel(), range(len(pvals))):\n #### generate graph ####\n G = nx.binomial_graph(n, p, seed=seed)\n # identify connected/disconnected nodes\n connected = [n for n, d in G.degree() if d > 0]\n disconnected = list(set(G.nodes()) - set(connected))\n # identify largest connected component\n Gcc = sorted(nx.connected_components(G), key=len, reverse=True)\n G0 = G.subgraph(Gcc[0])\n #### draw graph ####\n pos = nx.nx_agraph.graphviz_layout(G)\n ax.set_title(f\"p = {p:.3f}\")\n # draw largest connected component\n options = {\"ax\": ax, \"edge_color\": \"tab:red\"}\n nx.draw_networkx_edges(G0, pos, width=6.0, **options)\n # draw other connected components\n for Gi in Gcc[1:]:\n if len(Gi) > 1:\n nx.draw_networkx_edges(G.subgraph(Gi), pos, alpha=0.3, width=5.0, **options)\n # draw connected/disconnected nodes\n options = {\"ax\": ax, \"node_size\": 30, \"edgecolors\": \"white\"}\n nx.draw(G, pos, nodelist=connected, **options)\n nx.draw(G, pos, nodelist=disconnected, alpha=0.25, **options)\nfig.tight_layout()\nplt.show()"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.9.16"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
|
