{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Lab5-6 (Student version): standard graph models\n",
"\n",
"We can use the following libraries."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"3.8.10 (default, Sep 28 2021, 16:10:42) \n",
"[GCC 9.3.0]\n"
]
}
],
"source": [
"import matplotlib.pyplot as plt\n",
"import math\n",
"import sys\n",
"import random\n",
"print(sys.version)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This lab work will spread over sessions 5 and 6."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercise 1: Preliminary work"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Question 1\n",
"\n",
"Download the graph http://lioneltabourier.fr/documents/as_caida.txt and load it in memory as a dictionary of lists (as usual). This graph is a partial map of the Internet at the AS level as obtained using BGP tables during the CAIDA project in 2007. It will be used during the rest of this practical work. \n",
"\n",
"Apply the codes seen in the previous labs to:\n",
"- count its number of nodes and links, \n",
"- plot its degree distribution,\n",
"- compute its number of triangles,\n",
"- give an approximation of its diameter.\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercise 2: Erdös-Rényi model"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Question 2\n",
"\n",
"Create an Erdös-Rényi graph with the same number of nodes and links as the original graph."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Question 3\n",
"\n",
"Compare its degree distribution, its number of triangles, its approximate diameter (of the largest component) to the one of the original graph."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercise 2: Barabasi-Albert model\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Question 4\n",
"\n",
"Create a Barabasi-Albert graph with a number of links and nodes comparable to the original graph. We remind that in a BA model with $n$ nodes, the number of links $m$ is roughly equal to $\\alpha n$ where $ \\alpha $ is the parameter of the model. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Question 5\n",
"\n",
"Compare its degree distribution, its number of triangles, its approximate diameter (of the largest component) to the one of the original graph."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercise 3: Watts-Strogatz model"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Question 6\n",
"\n",
"Create a regular graph with a number of nodes $n$ equals to the one of the initial CAIDA graph. We have these constraints:\n",
"\n",
"* all nodes of a regular graph have the same degree $k$, choose $k$ so that the number $m$ of edges is close to the one of the CAIDA graph,\n",
"\n",
"* each node is connected to the nodes with the closest index, for example, if $k=6$, node $i$ will be connected to nodes $ i-1 $, $ i-2 $, $ i-3$ and $ i+1 $, $ i+2 $, $ i+3 $. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Question 7\n",
"\n",
"Starting from the graph created in the previous question, generate Watts-Strogatz models with several values of the parameter $p$: 0.01, 0.1, 0.3."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Question 8\n",
"\n",
"Compare their degree distribution, their number of triangles, their approximate diameter (of the largest component) to the one of the original graph."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercise 5: configuration model\n",
"\n",
"For this exercise, use two different datasets:\n",
"\n",
"CAIDA: http://lioneltabourier.fr/documents/as_caida.txt\n",
"\n",
"INET: http://lioneltabourier.fr/documents/inet.txt"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Question 9\n",
"\n",
"Create a Configuration Model of the graph with the same degree sequence as the original graph.\n",
"\n",
"Unfortunately, the version \"with rejection\" runs too slowly to be used here, so implement the version \"with loops and multi-edges deletion\" seen in the course."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Question 10\n",
"\n",
"For both CAIDA and INET graphs:\n",
"\n",
"* Compare the initial degree distribution to the configuration model degree distribution. To do so, compute the fraction of nodes which degree in the model is different from their degree in the original distribution: $ \\frac{n_{mod}}{n} $.\n",
"\n",
"* Compare the number of triangles of the configuration model to the one of the original graph. In which case does it correspond to the result of the course? In the other case, can you propose an explanation?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"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.10"
}
},
"nbformat": 4,
"nbformat_minor": 2
}