{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# EXERCISE SHEET 2, 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": [
    "#import the neccessary packages\n"
   ]
  },
  {
   "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
}