Newer
Older
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# EXERCISE SHEET 4, EXERCISE 2: Giant Component in ER-Model"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The goal of this exercise is to observe and verify the behaviour of the ER-Model under different parameter specifications."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# QUESTION 1:\n",
"Generate a function that samples instances of ER-$G(N,p)$ models. Given a simple graph G = (V,E), the probability that your function outputs G should be equal to $p^M (1-p)^{\\binom{N}{2}-M}$, where $M \\coloneqq |E|$.\n",
"\n",
"Your function could follows this sturcture:\n",
"- Take as inputs two paramters $N \\in \\mathbb{N}$ and $p \\in [0,1]$;\n",
"- Create an empty undirected networkx graph with $N$ nodes;\n",
"- Loop over each pair of nodes $(i,j)$ and with probability $p$, add an edge between $i$ and $j$;\n",
"- Return the graph.\n",
"\n",
"Generate a few test graphs, compute their average degree and plot their degree distributions. Verify that the results you obtain are consistent with what you expect from the analytical derivations of the lecture."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Answer 1:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# QUESTION 2:\n",
"In the second part of the exercise we want to generate various instances of ER-models. For each $n \\in \\{ 25, 100, 500, 2000 \\}$:\n",
"- Find (matemathically, not numerically) the critical values $\\tilde{p} \\in [0,1]$ at which $G(n, \\tilde{p})$ transitions from the regime with many small components to the regime with one giant component.\n",
"- Use your previously defined function to generate graphs in three regimes: below $\\tilde{p}$, at $\\tilde{p}$, and above $\\tilde{p}$ (avoid the trivial cases $p \\in \\{ 0,1 \\}$).\n",
"\n",
"In total you should have 12 graphs."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Answer 2:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# QUESTION 3:"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Plot the graphs as 4 by 3 subplots.\n",
"As a suggestion, put $N$ on the $x$ axis (increasing left to right); and the density regimes on the $y$ axis (increasing from top to bottom)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Answer 3:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# QUESTION 4:\n",
"What do you observe in your plots?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Answer 4:"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": []
}
],
"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.8.3"
},
"vscode": {
"interpreter": {
"hash": "3699540f6baed5bd29a193b0c2d028af3f2c80498e3cac18f2b44cdd848387e2"
}
}
},
"nbformat": 4,
"nbformat_minor": 2
}