Implementation.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Implementation.ipynb",
      "version": "0.3.2",
      "provenance": [],
      "collapsed_sections": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "accelerator": "GPU"
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/ptleskin/GraphAlgorithmImplementation/blob/master/Implementation.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "DVCvfAKvN8dg",
        "colab_type": "text"
      },
      "source": [
        "Install dependencies"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "zK7UbftdN8d0",
        "colab_type": "code",
        "outputId": "7d61198b-a8a6-4316-ae7d-73307ffbc2f2",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 69
        }
      },
      "source": [
        "!pip install numpy networkx"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Requirement already satisfied: numpy in /usr/local/lib/python3.6/dist-packages (1.16.4)\n",
            "Requirement already satisfied: networkx in /usr/local/lib/python3.6/dist-packages (2.3)\n",
            "Requirement already satisfied: decorator>=4.3.0 in /usr/local/lib/python3.6/dist-packages (from networkx) (4.4.0)\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tktJjT8TN8eT",
        "colab_type": "text"
      },
      "source": [
        "Import libraries"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "a6N87O1kN8eY",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import collections\n",
        "import networkx as nx\n",
        "import numpy as np\n",
        "import random\n",
        "from itertools import product\n",
        "from math import exp"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4MutQWT9N8eq",
        "colab_type": "text"
      },
      "source": [
        "\n",
        "Equation (4) for estimating D_n for a z-regular random network:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "PBtQzrY5N8et",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def calculate_regular(G):\n",
        "    N = G.number_of_nodes()\n",
        "    p_k = getDD(G)\n",
        "    \n",
        "    z = sum([k*p for k,p in p_k.items()])\n",
        "    \n",
        "    D_n = [0.0]\n",
        "    iters = 32\n",
        "    \n",
        "    for n in range(1,iters):\n",
        "        \n",
        "        d_n = D_exp(n-1, N, z) - D_exp(n, N, z)\n",
        "        \n",
        "        D_n.append(d_n)\n",
        "    \n",
        "    sumd = sum(D_n)\n",
        "    expD = sum([n*d/sumd for n,d in enumerate(D_n)])\n",
        "    return expD\n",
        "\n",
        "def D_exp(n,N,z):\n",
        "    return exp(-(z*((z-1)**n) -2)/(N*(z-2)))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WOHpV2TrN8e9",
        "colab_type": "text"
      },
      "source": [
        "Implementation of calculations in Section IV: p_k-theory"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "GdWbjQs8N8fA",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def calculate_random(G):\n",
        "    N = G.number_of_nodes()\n",
        "    p_k = getDD(G)\n",
        "    pk = list(p_k.keys())\n",
        "    \n",
        "    z = sum([k*p for k,p in p_k.items()])\n",
        "    \n",
        "    iters = 32\n",
        "    rho, q = [], []\n",
        "    q_bar = {}\n",
        "    \n",
        "    for n in range(iters):\n",
        "        \n",
        "        rho.append(dict([((k,_k), 0.0) for k,_k in product(pk,pk)]))\n",
        "        q.append(dict([((k,_k), 0.0) for k,_k in product(pk,pk)]))\n",
        "        \n",
        "        if n==0:\n",
        "            \n",
        "            for k in pk:\n",
        "                rho_0 = 1/(N*p_k[k])\n",
        "                rho[0][(k,k)] = rho_0\n",
        "                q[0][(k,k)] = rho_0\n",
        "            \n",
        "            q_bar = dict([(_k,0.0) for _k in pk])\n",
        "            for (k,_k), _q in q[n].items():\n",
        "                q_bar[_k] += k*p_k[k]*_q\n",
        "            \n",
        "            for _k in q_bar.keys():\n",
        "                q_bar[_k] /= z\n",
        "        else:\n",
        "            \n",
        "            j = n-1\n",
        "            \n",
        "            rho[n] = dict([((k,_k),1-(1-rho[0][(k,_k)])*((1-q_bar[_k])**k)) \n",
        "                        for k,_k in q[j].keys()])\n",
        "            q[n] = dict([((k,_k),1-(1-rho[0][(k,_k)])*((1-q_bar[_k])**(k-1))) \n",
        "                        for k,_k in q[j].keys()])\n",
        "            \n",
        "            q_bar = dict([(_k,0.0) for _k in pk])\n",
        "            for (k,_k), _q in q[n].items():\n",
        "                q_bar[_k] += k*p_k[k]*_q\n",
        "            \n",
        "            for _k in q_bar.keys():\n",
        "                q_bar[_k] /= z\n",
        "            \n",
        "            \n",
        "    \n",
        "    D_n = [0.0]\n",
        "    for n in range(1,iters):\n",
        "        D_nkk = dict([ (\n",
        "                    (k,_k),\n",
        "                    (_d-rho[n-1][(k,_k)])/rho[-1][(k,_k)] ) \n",
        "                    for (k,_k), _d in rho[n].items() ])\n",
        "        d_n = sum([p_k[k]*p_k[_k]*_d for (k,_k), _d in D_nkk.items()] )\n",
        "        D_n.append(d_n)\n",
        "    \n",
        "    sumd = sum(D_n)\n",
        "    expD = sum([n*d/sumd for n,d in enumerate(D_n)])\n",
        "    \n",
        "    return expD"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YZfEyvNIN8fQ",
        "colab_type": "text"
      },
      "source": [
        "Implementation of calculations in Section V: P(k,k')-theory"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3PBqjV2pN8gS",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def calculate_ByJDD(G):\n",
        "    N = G.number_of_nodes()\n",
        "    p_k = getDD(G)\n",
        "    \n",
        "    Pkk = getJDD(G)\n",
        "    pk = list(set([x for x,_ in Pkk.keys()]+[x for _,x in Pkk.keys()]))\n",
        "    \n",
        "    iters = 32\n",
        "    rho, q = [], []\n",
        "    q_bar = {}\n",
        "    \n",
        "    for n in range(iters):\n",
        "        \n",
        "        rho.append(dict([((k,_k), 0.0) for k,_k in Pkk.keys()]))\n",
        "        q.append(dict([((k,_k), 0.0) for k,_k in Pkk.keys()]))\n",
        "        \n",
        "        if n==0:\n",
        "            \n",
        "            for k in pk:\n",
        "                rho_0 = 1/(N*p_k[k])\n",
        "                rho[0][(k,k)] = rho_0\n",
        "                q[0][(k,k)] = rho_0\n",
        "                \n",
        "        else:\n",
        "            \n",
        "            j = n-1\n",
        "            \n",
        "            q_bar = dict([((k,_k), [0.0, 0.0]) for k,_k in Pkk.keys()])\n",
        "            \n",
        "            for (k,_k), _p in Pkk.items():\n",
        "                for k2 in pk:\n",
        "                    try:\n",
        "                        q_bar[(k,_k)][1] += Pkk[(k,k2)]\n",
        "                        q_bar[(k,_k)][0] += Pkk[(k,k2)]*q[j][(k2,_k)]\n",
        "                    except KeyError:\n",
        "                        pass\n",
        "                    \n",
        "            for k,_k in Pkk.keys():\n",
        "                if q_bar[(k,_k)][1]>0:\n",
        "                    q_bar[(k,_k)][0] /= q_bar[(k,_k)][1]\n",
        "            \n",
        "            rho[n] = dict([((k,_k),1-(1-rho[0][(k,_k)])*((1-q_bar[(k,_k)][0])**k)) \n",
        "                        for k,_k in Pkk.keys()])\n",
        "            q[n] = dict([((k,_k),1-(1-rho[0][(k,_k)])*((1-q_bar[(k,_k)][0])**(k-1))) \n",
        "                        for k,_k in Pkk.keys()])\n",
        "            \n",
        "            \n",
        "            if False:\n",
        "                sum_rho = sum(rho[n].values())\n",
        "                sum_q = sum(q[n].values())\n",
        "                print(\"n {}\".format(n))\n",
        "                print(\"Sum rho {}\".format(sum_rho))\n",
        "                print(\"Sum q {}\".format(sum_q))\n",
        "    \n",
        "    D_n = [0.0]\n",
        "    \n",
        "    for n in range(1,iters):\n",
        "        D_nkk = dict([ (\n",
        "                    (k,_k),\n",
        "                    (_d-rho[n-1][(k,_k)])/rho[-1][(k,_k)] ) \n",
        "                    for (k,_k), _d in rho[n].items() ])\n",
        "        \n",
        "        d_n = sum([p_k[k]*p_k[_k]*_d for (k,_k), _d in D_nkk.items()] )\n",
        "        D_n.append(d_n)\n",
        "        \n",
        "    sumd = sum(D_n)\n",
        "    expD = sum([n*d/sumd for n,d in enumerate(D_n)])\n",
        "    \n",
        "    return expD\n",
        "\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Nf2CMFuaN8g4",
        "colab_type": "text"
      },
      "source": [
        "Define some useful tools:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Hapd8o6WN8g8",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# calcullate estimate for input graph G\n",
        "def analyzeGraph(G):    \n",
        "    N = G.number_of_nodes()\n",
        "    print(\"Number of nodes: {}\".format(N))\n",
        "    E = G.number_of_edges()\n",
        "    print(\"Average degree: {}\".format(2.0*E/N))\n",
        "    d_bar = nx.average_shortest_path_length(G)\n",
        "    \n",
        "    expD = calculate_random(G)\n",
        "    print(\"Average shortest path length: {:.4f}\".format(d_bar))\n",
        "    print(\"Expected D with p_k\\t{:.4f}\".format(expD))\n",
        "    print(\"Relative error\\t{:.4f}\\n\".format(relative_error(d_bar, expD)))\n",
        "    \n",
        "    \n",
        "    expD = calculate_ByJDD(G)\n",
        "    print(\"Expected D with P(k,k')\\t{:.4f}\".format(expD))\n",
        "    print(\"Relative error\\t{:.4f}\\n\".format(relative_error(d_bar, expD)))\n",
        "    \n",
        "    D_rrg = calculate_regular(G)\n",
        "    print(\"Regular degree estimate\\t{:.4f}\".format(D_rrg))\n",
        "    print(\"Relative error\\t{:.4f}\".format(relative_error(d_bar, D_rrg)))\n",
        "    \n",
        "# calculate joint degree-degree distribution of input network G\n",
        "def getJDD(G):\n",
        "    M = nx.degree_mixing_matrix(G.to_directed(), normalized=True)\n",
        "    Pkk = dict([((k,k_),x) for k,row in enumerate(M) for k_,x in enumerate(row) if x>0])\n",
        "    return Pkk\n",
        "\n",
        "# calculate degree distribution of input network G\n",
        "def getDD(G):\n",
        "    degree_sequence = sorted([d for n, d in G.degree()], reverse=True)  # degree sequence\n",
        "    degrees = collections.Counter(degree_sequence)\n",
        "    N = sum(degrees.values())\n",
        "    return dict([(x,y/N) for x,y in degrees.items()])\n",
        "\n",
        "# calculate relative error of v_approx to v\n",
        "def relative_error(v,v_approx):\n",
        "    return abs((v-v_approx)/v)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Y1fgfCk8N8hG",
        "colab_type": "text"
      },
      "source": [
        "First run a test with a random 4-regular graph with N=500"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "b_PXk_U0N8hJ",
        "colab_type": "code",
        "outputId": "a97f7d9a-3d28-4927-fd53-37a8174ca9bb",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 208
        }
      },
      "source": [
        "G = nx.random_regular_graph(n=500,d=4)\n",
        "\n",
        "analyzeGraph(G)"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Number of nodes: 500\n",
            "Average degree: 4.0\n",
            "Average shortest path length: 5.0119\n",
            "Expected D with p_k\t5.0214\n",
            "Relative error\t0.0019\n",
            "\n",
            "Expected D with P(k,k')\t5.0214\n",
            "Relative error\t0.0019\n",
            "\n",
            "Regular degree estimate\t5.0223\n",
            "Relative error\t0.0021\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "phpHs3IJHjzO",
        "colab_type": "text"
      },
      "source": [
        " Test with a random 10-regular graph with N=500"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "pa9OWVLnrHlv",
        "colab_type": "code",
        "outputId": "166c6ea5-d61a-4a76-a057-47526a4634a9",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 208
        }
      },
      "source": [
        "G = nx.random_regular_graph(n=500,d=10)\n",
        "analyzeGraph(G)"
      ],
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Number of nodes: 500\n",
            "Average degree: 10.0\n",
            "Average shortest path length: 2.9445\n",
            "Expected D with p_k\t2.9605\n",
            "Relative error\t0.0054\n",
            "\n",
            "Expected D with P(k,k')\t2.9605\n",
            "Relative error\t0.0054\n",
            "\n",
            "Regular degree estimate\t2.9610\n",
            "Relative error\t0.0056\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9yO4pB4GZjte",
        "colab_type": "text"
      },
      "source": [
        "A larger random 4-regular graph with N=10000"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "xLAr3DHgZktY",
        "colab_type": "code",
        "outputId": "04097d97-bf72-4e3a-8d85-66daf3ea59bc",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 208
        }
      },
      "source": [
        "G = nx.random_regular_graph(n=10000,d=4)\n",
        "\n",
        "analyzeGraph(G)"
      ],
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Number of nodes: 10000\n",
            "Average degree: 4.0\n",
            "Average shortest path length: 7.7291\n",
            "Expected D with p_k\t7.7288\n",
            "Relative error\t0.0000\n",
            "\n",
            "Expected D with P(k,k')\t7.7288\n",
            "Relative error\t0.0000\n",
            "\n",
            "Regular degree estimate\t7.7288\n",
            "Relative error\t0.0000\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Ik3ROiE5dw_0",
        "colab_type": "text"
      },
      "source": [
        "A larger random 10-regular graph with N=10000"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "OAk1-f8bdxm2",
        "colab_type": "code",
        "outputId": "d901dff0-0ebe-4a04-b80a-5f216de10953",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 208
        }
      },
      "source": [
        "G = nx.random_regular_graph(n=10000,d=10)\n",
        "\n",
        "analyzeGraph(G)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Number of nodes: 10000\n",
            "Average degree: 10.0\n",
            "Average shortest path length: 4.3421\n",
            "Expected D with p_k\t4.3431\n",
            "Relative error\t0.0002\n",
            "\n",
            "Expected D with P(k,k')\t4.3431\n",
            "Relative error\t0.0002\n",
            "\n",
            "Regular degree estimate\t4.3431\n",
            "Relative error\t0.0002\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "W7phoZI1N8hS",
        "colab_type": "text"
      },
      "source": [
        "Then a Erdos-Renyi graph with N=500, p=0.02"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vb5kYG1IN8hT",
        "colab_type": "code",
        "outputId": "c73aa0a1-59a8-48a1-c6ac-780204a06180",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 208
        }
      },
      "source": [
        "G = nx.erdos_renyi_graph(500,0.02)\n",
        "analyzeGraph(G)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Number of nodes: 500\n",
            "Average degree: 9.932\n",
            "Average shortest path length: 2.9425\n",
            "Expected D with p_k\t2.9592\n",
            "Relative error\t0.0056\n",
            "\n",
            "Expected D with P(k,k')\t2.9598\n",
            "Relative error\t0.0059\n",
            "\n",
            "Regular degree estimate\t2.9696\n",
            "Relative error\t0.0092\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "aJ1Wda5_rma4",
        "colab_type": "code",
        "outputId": "9ec3a6ba-6974-4815-dea3-ce674133ff89",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 208
        }
      },
      "source": [
        "G = nx.erdos_renyi_graph(10000,0.001)\n",
        "analyzeGraph(G)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Number of nodes: 10000\n",
            "Average degree: 9.9766\n",
            "Average shortest path length: 4.2633\n",
            "Expected D with p_k\t4.2623\n",
            "Relative error\t0.0002\n",
            "\n",
            "Expected D with P(k,k')\t4.2627\n",
            "Relative error\t0.0002\n",
            "\n",
            "Regular degree estimate\t4.3474\n",
            "Relative error\t0.0197\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "mq_637M1N8hh",
        "colab_type": "text"
      },
      "source": [
        "Then C.elegans Neural network\n",
        "\n",
        "source: https://www.complex-networks.net/datasets.html#c_elegans"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "zIhWl2vMN8hi",
        "colab_type": "code",
        "outputId": "180e12a8-2ca7-4e70-baed-7367b9429804",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 419
        }
      },
      "source": [
        "!wget https://raw.githubusercontent.com/ptleskin/GraphAlgorithmImplementation/master/data/c_elegans_undir.net?raw=true\n",
        "!mv c_elegans_undir.net\\?raw\\=true c_elegans_undir.net\n",
        "\n",
        "G=nx.read_weighted_edgelist(\"c_elegans_undir.net\", nodetype=int)\n",
        "analyzeGraph(G)"
      ],
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "--2019-08-11 10:09:52--  https://raw.githubusercontent.com/ptleskin/GraphAlgorithmImplementation/master/data/c_elegans_undir.net?raw=true\n",
            "Resolving raw.githubusercontent.com (raw.githubusercontent.com)... 151.101.0.133, 151.101.64.133, 151.101.128.133, ...\n",
            "Connecting to raw.githubusercontent.com (raw.githubusercontent.com)|151.101.0.133|:443... connected.\n",
            "HTTP request sent, awaiting response... 200 OK\n",
            "Length: 16186 (16K) [text/plain]\n",
            "Saving to: ‘c_elegans_undir.net?raw=true’\n",
            "\n",
            "\r          c_elegans   0%[                    ]       0  --.-KB/s               \rc_elegans_undir.net 100%[===================>]  15.81K  --.-KB/s    in 0s      \n",
            "\n",
            "2019-08-11 10:09:53 (81.6 MB/s) - ‘c_elegans_undir.net?raw=true’ saved [16186/16186]\n",
            "\n",
            "Number of nodes: 279\n",
            "Average degree: 16.39426523297491\n",
            "Average shortest path length: 2.4356\n",
            "Expected D with p_k\t2.3318\n",
            "Relative error\t0.0426\n",
            "\n",
            "Expected D with P(k,k')\t2.2932\n",
            "Relative error\t0.0585\n",
            "\n",
            "Regular degree estimate\t2.3245\n",
            "Relative error\t0.0456\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6-g3rTU5Wasr",
        "colab_type": "text"
      },
      "source": [
        "500 US Airports network\n",
        "\n",
        "source: https://www.complex-networks.net/datasets.html#airports"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7y4wMSTEN8hr",
        "colab_type": "code",
        "outputId": "faab0754-689a-44bf-d2df-7c6744deb7b4",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 419
        }
      },
      "source": [
        "!wget https://raw.githubusercontent.com/ptleskin/GraphAlgorithmImplementation/master/data/US_airports.net?raw=true\n",
        "!mv US_airports.net\\?raw\\=true US_airports.net\n",
        "\n",
        "G=nx.read_weighted_edgelist(\"US_airports.net\", nodetype=int)\n",
        "analyzeGraph(G)"
      ],
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "--2019-08-11 10:10:09--  https://raw.githubusercontent.com/ptleskin/GraphAlgorithmImplementation/master/data/US_airports.net?raw=true\n",
            "Resolving raw.githubusercontent.com (raw.githubusercontent.com)... 151.101.0.133, 151.101.64.133, 151.101.128.133, ...\n",
            "Connecting to raw.githubusercontent.com (raw.githubusercontent.com)|151.101.0.133|:443... connected.\n",
            "HTTP request sent, awaiting response... 200 OK\n",
            "Length: 39832 (39K) [text/plain]\n",
            "Saving to: ‘US_airports.net?raw=true’\n",
            "\n",
            "\rUS_airports.net?raw   0%[                    ]       0  --.-KB/s               \rUS_airports.net?raw 100%[===================>]  38.90K  --.-KB/s    in 0.001s  \n",
            "\n",
            "2019-08-11 10:10:09 (55.4 MB/s) - ‘US_airports.net?raw=true’ saved [39832/39832]\n",
            "\n",
            "Number of nodes: 500\n",
            "Average degree: 11.92\n",
            "Average shortest path length: 2.9910\n",
            "Expected D with p_k\t2.8022\n",
            "Relative error\t0.0631\n",
            "\n",
            "Expected D with P(k,k')\t2.8559\n",
            "Relative error\t0.0452\n",
            "\n",
            "Regular degree estimate\t2.7729\n",
            "Relative error\t0.0729\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yCV2Bff9N8h1",
        "colab_type": "text"
      },
      "source": [
        ""
      ]
    }
  ]
}