assignment_centrality_measures/assignment.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Assignment — Centrality measures"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "from typing import Dict, List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this assignment, we will use Moscow Metro underground stations dataset taken from [Moscow Subway Optimal* Complete Route](https://medium.com/altsoph/moscow-subway-optimal-complete-route-ac98796dd652) research. Let us download and take a look at the data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "station_url = 'https://raw.githubusercontent.com/netspractice/ml-on-graphs/main/datasets/stations_data.txt'\n",
    "routes_url = 'https://raw.githubusercontent.com/netspractice/ml-on-graphs/main/datasets/routes_data.txt'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "stations = pd.read_csv(station_url)\n",
    "routes = pd.read_csv(routes_url)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "stations.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "routes.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1. Metro graph (0.8 points)\n",
    "\n",
    "Before we start analyzing centrality, let us build a graph of stations.\n",
    "\n",
    "Write a function `metro_graph` that takes datasets `stations` and `routes` and returns a graph with all stations and routes of any type. Labels of nodes are in column `stations.id`. Nodes in `G.nodes` viewer should be in ascending order. All nodes should have attributes `station_name` and `line_name`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "8c54e6021de80068147963f12353dcfe",
     "grade": false,
     "grade_id": "cell-96fa1082742a036a",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def metro_graph(stations: pd.DataFrame, routes: pd.DataFrame) -> nx.Graph:\n",
    "    \"\"\"\n",
    "    Build a graph with metro stations and routes\n",
    "    \n",
    "    :param stations: dataframe with undeground stations (nodes) description, column id is used for node id in the nx.Graph\n",
    "    :param routes: edgelist for undeground graph. id_from is source and id_to is target nodes.\n",
    "    :return: graph of Moscow undeground\n",
    "    \"\"\"\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "55438a2455b649635105743e0e6613cd",
     "grade": true,
     "grade_id": "cell-c6f1237f3a4eaaa9",
     "locked": true,
     "points": 0.2,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "'''Check ordering of nodes, number of nodes, names of stations and lines'''\n",
    "G = metro_graph(stations, routes)\n",
    "assert (np.array(list(G.nodes)) == np.arange(194)).sum() == 194\n",
    "assert G.number_of_edges() == 228\n",
    "assert G.nodes[100]['station_name'] == 'Shabolovskaya'\n",
    "assert G.nodes[100]['line_name'] == 'Kaluzhsko-Rizhskaya'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us draw the graph with default spring layout."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.figure(figsize=(10, 8))\n",
    "nx.draw(G, \n",
    "        width=0.5,\n",
    "        node_size=60)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So far it does not look like a metro map. Let us specify a distance based layout using information from the dataset `stations`.\n",
    "\n",
    "Write a function `metro_layout` that takes the dataset `stations` and returns a dictionary with nodes as keys and positions as values:\n",
    "```\n",
    "{node_id: [longitude, latitude]}\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "b3a33086e68d835c9a3b1f97e4c635c9",
     "grade": false,
     "grade_id": "cell-7ca2e105bb2493b1",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def metro_layout(stations: pd.DataFrame) -> Dict[int, List[float]]:\n",
    "    \"\"\"\n",
    "    Build a distance based layout of the metro graph\n",
    "    \n",
    "    :param stations: dataframe with undeground stations (nodes) description, column id is used for node id in the nx.Graph.\n",
    "        lat and lon is geo coordinates of station.\n",
    "    :return: geo layout of Moscow undeground\n",
    "    \"\"\"\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "a57c2143dec62da961f61c172550573f",
     "grade": true,
     "grade_id": "cell-b5e28f603eaba3a6",
     "locked": true,
     "points": 0.4,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "'''Check a type and positions of some random nodes'''\n",
    "pos = metro_layout(stations)\n",
    "assert type(pos) == dict\n",
    "assert len(pos) == 194\n",
    "assert pos[100] == [37.6078018, 55.71882329]\n",
    "assert pos[172] == [37.72840065, 55.69297728]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us draw the graph with the distance based layout."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.figure(figsize=(10, 8))\n",
    "nx.draw(G, \n",
    "        pos,\n",
    "        width=0.5,\n",
    "        node_size=60)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The final preprocessing step, let us colorize stations by their lines.\n",
    "\n",
    "Write a function `station_color` that takes a graph `G` and returns a dictionary with nodes as keys and color as values. Colors are given in the `line_color` dictionary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "line_color = {\n",
    "    'Sokolnicheskaya': 'tab:red',\n",
    "    'Zamoskvoretskaya': 'tab:green',\n",
    "    'Arbatsko-Pokrovskaya': 'tab:blue',\n",
    "    'Filevskaya': 'deepskyblue',\n",
    "    'Koltsevaya': 'tab:brown',\n",
    "    'Kaluzhsko-Rizhskaya': 'tab:orange',\n",
    "    'Tagansko-Krasnopresnenskaya': 'tab:purple', \n",
    "    'Kalininskaya': 'gold',\n",
    "    'Serpuhovsko-Timiryazevskaya': 'gray', \n",
    "    'Lyublinsko-Dmitrovskaya': 'yellowgreen',\n",
    "    'Kahovskaya': 'paleturquoise', \n",
    "    'Butovskaya': 'lightblue', \n",
    "    'Monorels': 'royalblue'\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "583a8477b61ed7a7793c690f13b99e5d",
     "grade": false,
     "grade_id": "cell-2f1d4177661a9582",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def station_color(G: nx.Graph, line_color: Dict[str, str] = line_color) -> Dict[int, str]:\n",
    "    \"\"\"\n",
    "    Defines color of stations\n",
    "    \n",
    "    :param G: graph of Moscow undeground\n",
    "    :param line_color: mapping of undeground lines to colors\n",
    "    :return: mapping of node ids to its colors \n",
    "    \"\"\"\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "09e08fcbd17722b3dd2357cf78c2485e",
     "grade": true,
     "grade_id": "cell-8777de6843545b61",
     "locked": true,
     "points": 0.2,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "'''Check a type and colors of some random nodes'''\n",
    "nx.set_node_attributes(G, station_color(G), 'color')\n",
    "assert type(station_color(G)) == dict\n",
    "assert len(station_color(G)) == 194\n",
    "assert station_color(G)[9] == 'tab:red'\n",
    "assert station_color(G)[193] == 'royalblue'\n",
    "assert station_color(G)[119] == 'tab:purple'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us draw the graph with the distance based layout and stations colors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.figure(figsize=(10, 8))\n",
    "nx.draw(\n",
    "    G, \n",
    "    pos,\n",
    "    width=0.5,\n",
    "    node_color=list(nx.get_node_attributes(G, 'color').values()),\n",
    "    node_size=60,\n",
    ")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2. Degree, closeness, betweenness centralities (0.8 point)\n",
    "\n",
    "Let us look at centrality measures of the metro stations graph. First, use networkx to calculate degree, closeness, betweenness centralities.\n",
    "\n",
    "Write a function `centralities` that takes a graph `G` and returns a dictionary with keys `degree`, `closeness`, `betweenness`. The values are np.arrays with values of each centrality."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "9d4d2c85577e5707ea38c40285fe67f2",
     "grade": false,
     "grade_id": "cell-8ef9147d12ad6ac4",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def centralities(G: nx.Graph) -> Dict[str, np.array]:\n",
    "    \"\"\"\n",
    "    Calculate degree, closeness, betweenness centralities of the graph\n",
    "    \n",
    "    :param G: Moscow undeground graph\n",
    "    :return: mapping of centrality names (degree, closeness, betweenness) to np.array of its values\n",
    "    \"\"\"\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "9784c402574e34dd8d7567fbc066b6ce",
     "grade": true,
     "grade_id": "cell-dd093037fa7756f4",
     "locked": true,
     "points": 0.4,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "'''Check some random values of centralities'''\n",
    "c = centralities(G)\n",
    "assert c['degree'].shape[0] == 194\n",
    "assert c['degree'][193] == 0.0051813471502590676\n",
    "assert c['closeness'][94] == 0.12107904642409034\n",
    "assert c['betweenness'][49] == 0.0991400402993669"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, let us create a table with top 10 nodes for each centrality.\n",
    "\n",
    "Write a function `top10_centralities` that takes a graph `G` and returns a dictionary with keys `degree`, `closeness`, `betweenness`. The values are pd.DataFrames with columns:\n",
    "* `station` — station name\n",
    "* `line` — line name\n",
    "* `centrality` — value of a centrality\n",
    "\n",
    "Each dataframe contains 10 rows with highest centrality values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "05481e356ffebb1abfb97780f5e7ef4b",
     "grade": false,
     "grade_id": "cell-3dad4de0a9186415",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def top10_centralities(G: nx.Graph) -> Dict[str, pd.DataFrame]:\n",
    "    \"\"\"\n",
    "    Create table of top 10 nodes by degree, closeness, betweenness centralities\n",
    "    \n",
    "    :param G: graph of Moscow undeground\n",
    "    :return: mapping of station name to the dataframe with columns (station, line, centrality)\n",
    "    \"\"\"\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "372a08d1ef0b1c88298ec165815b62ca",
     "grade": true,
     "grade_id": "cell-0bfea33ff1fcf96c",
     "locked": true,
     "points": 0.4,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "'''Check that some random nodes are in the top 10 tables'''\n",
    "top_dfs = top10_centralities(G)\n",
    "assert 'Biblioteka imeni Lenina' in top_dfs['degree']['station'].to_list()\n",
    "assert 'Serpuhovskaya' in top_dfs['betweenness']['station'].to_list()\n",
    "assert 'Teatralnaya' in top_dfs['closeness']['station'].to_list()\n",
    "assert 'Arbatsko-Pokrovskaya' in top_dfs['closeness']['line'].to_list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Following code makes a visualization: for each centrality it prints a top 10 table and graph, where the node size and color correspond to the centrality value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cases = [['degree', 5000, 0, 'Degree centrality'], \n",
    "         ['closeness', 700, 0, 'Closeness centrality'], \n",
    "         ['betweenness', 900, 20, 'Betweenness centrality']]\n",
    "for c_key, scale, bias, title in cases:\n",
    "    print(title)\n",
    "    display(top_dfs[c_key])\n",
    "    plt.figure(figsize=(10, 8))\n",
    "    nx.draw(G, \n",
    "            pos,\n",
    "            width=0.5,\n",
    "            linewidths=0.5,\n",
    "            edgecolors='black',\n",
    "            cmap=plt.cm.hot,\n",
    "            node_size=c[c_key]*scale + bias,\n",
    "            node_color=c[c_key])\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 3. Center of the graph (0.8 points)\n",
    "\n",
    "In the next section we will slightly modify the initial graph — truncate all stations that located outside of Sadovoye ring.\n",
    "Sadovoye ring is the region that includes all stations on the Koltsevaya line, all stations of radial lines that intersect Koltsevaya line and all stations that contains inside the circle.\n",
    "\n",
    "Write a function `metro_graph_center` that takes a metro graph `G` and returns a subgraph with stations inside Sadovoye ring."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "ae8d4807aedbca53789540f5e2cb4ce2",
     "grade": false,
     "grade_id": "cell-7e22abcc984c16d2",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def metro_graph_center(G: nx.Graph) -> nx.Graph:\n",
    "    \"\"\"\n",
    "    Build a subgraph with stations inside the Sadovoye ring\n",
    "    \n",
    "    :param G: graph of Moscow undeground\n",
    "    :return: subgraph of Moscow undeground stations that is located inside Sadovoye ring.\n",
    "    \"\"\"\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "ca71b5c47feb05fd21d56e46fdb42950",
     "grade": true,
     "grade_id": "cell-da2bb8cea6d1507c",
     "locked": true,
     "points": 0.8,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "'''Check the number of nodes and edges and some random stations'''\n",
    "subG = metro_graph_center(G)\n",
    "assert len(subG.nodes) == 57\n",
    "assert len(subG.edges) == 85\n",
    "assert 149 in list(subG.nodes)\n",
    "assert 82 in list(subG.nodes)\n",
    "assert 137 in list(subG.nodes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us draw the center of the metro graph with station names and colors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.figure(figsize=(10, 8))\n",
    "nx.draw(subG, \n",
    "        pos,\n",
    "        width=0.5,\n",
    "        node_color=list(nx.get_node_attributes(subG, 'color').values()),\n",
    "        labels=nx.get_node_attributes(subG, 'station_name'),\n",
    "        font_size=10)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 4. Centralization (2 point)\n",
    "\n",
    "The center of the metro graph looks a bit like a circular graph. We can see that a circular graph has the lowest centralization since\n",
    "\n",
    "$$\\text{Centralization} = \\frac{\\sum_i^N[C_x(p_*) - C_x(p_i)]}{\\max\\sum_i^N[C_x(p_*) - C_x(p_i)]}$$\n",
    "\n",
    "where \n",
    "* $C_x$ — some centrality measure\n",
    "* $p_i$ — $i$-th node\n",
    "* $p_*$ — node with the largest centrality value\n",
    "* $\\max$ — maximum over all possible graphs with the same number of nodes (a star graph for degree, betweenness, closeness centralities).\n",
    "\n",
    "Let us check how centralization changes during transformation our truncated graph into a pure circular graph.\n",
    "\n",
    "Write a function `centralization_seq` that takes the truncated graph `G` and deletes stations inside Koltsevaya line one-by-one in ascending order (i.e. result of `sorted` function). In each step the centralization is calculated. The function returns a dictionary with keys `degree`, `closeness`, `betweenness` and values — np.arrays with centralization values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "ae6772cd16504af992abfe90e8184b5e",
     "grade": false,
     "grade_id": "cell-599d21555a10592f",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def centralization_seq(G: nx.Graph) -> (Dict[str, np.array], List[str]):\n",
    "    \"\"\"\n",
    "    Delete stations and calculate centralization for degree, closeness, betweenness\n",
    "    \n",
    "    :param G: graph of Moscow undeground inside the Sadovoye ring\n",
    "    :return: to elements (tuple):\n",
    "        1. mapping of centrality name to array of centralization values for subgraphs\n",
    "           without each node (iteratively) that does not correspond to Koltsevaya line\n",
    "        2. list of station ids to remove\n",
    "    \"\"\"\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "aca57acceb5e961e56c979a7f59974c5",
     "grade": true,
     "grade_id": "cell-19b3b60a79fa0348",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "'''Check the output shape and some random centralization values'''\n",
    "cent, order = centralization_seq(subG)\n",
    "assert cent['degree'].shape == (45,)\n",
    "assert cent['closeness'].shape == (45,)\n",
    "assert cent['betweenness'].shape == (45,)\n",
    "assert cent['degree'][-1] == cent['betweenness'][-1] == cent['closeness'][-1]\n",
    "assert cent['degree'][41].round(4) == 0.0824\n",
    "assert cent['degree'][2].round(4) == 0.0406\n",
    "assert cent['closeness'][11].round(4) == 0.0785\n",
    "assert cent['closeness'][9].round(4) == 0.0814\n",
    "assert cent['betweenness'][14].round(4) == 0.1178"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us draw how the centralization changes when the graph tends to a circular graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.figure(figsize=(7, 5))\n",
    "plt.plot(cent['degree'], label='Degree')\n",
    "plt.plot(cent['closeness'], label='Closeness')\n",
    "plt.plot(cent['betweenness'], label='Betweenness')\n",
    "plt.ylabel('Centralization')\n",
    "plt.xlabel('Number of deleted nodes')\n",
    "plt.axvline(16, linestyle='--', color='C4', alpha=0.5)\n",
    "plt.axvline(30, linestyle='--', color='C4', alpha=0.5)\n",
    "plt.axvline(37, linestyle='--', color='C4', alpha=0.5)\n",
    "plt.axvline(41, linestyle='--', color='C4', alpha=0.5)\n",
    "plt.legend()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can see the several peaks in centralization for betweenness centrality. Higher centralization means that centrality measures unevenly distributed over nodes. Betweenness centrality for specific node indocates how much shortest paths pass through this node.\n",
    "\n",
    "Peaks signalize that we break some shortests paths after node deletion, so new shortest paths should go through a little number of specific nodes.\n",
    "\n",
    "Let us visualize graph before and after deletion of node under index `37` (Tsvetnoy bulvar), to understand this effect."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_truncated_graph(subG, order, idx, ax, highlight=True, title=\"\"):\n",
    "    s = subG.copy()\n",
    "    s.remove_nodes_from(order[:idx + 1])\n",
    "    betw = nx.betweenness_centrality(s)\n",
    "    nx.draw(\n",
    "        s,\n",
    "        pos,\n",
    "        width=0.5,\n",
    "        node_color=list('red' if (i == order[idx + 1] and highlight) else j\n",
    "                        for i, j in nx.get_node_attributes(s, 'color').items()),\n",
    "        node_size=[j * 1000 for i, j in betw.items()],\n",
    "        labels=nx.get_node_attributes(s, 'station_name'),\n",
    "        font_size=10,\n",
    "        ax=ax\n",
    "    )\n",
    "    ax.set_title(title)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "f = plt.figure(figsize=(16, 8))\n",
    "ax = f.subplots(1, 2)\n",
    "plot_truncated_graph(subG, order, 36, ax[0], title=\"Before deletion of node Tsvetnoy bulvar\")\n",
    "plot_truncated_graph(subG, order, 37, ax[1], highlight=False, title=\"After deletion of node Tsvetnoy bulvar\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tsvetnoy bulvar is a node targeted for deletion on the next step.\n",
    "\n",
    "On the first graph we can see, that exists a cycle of gray and light green line, so all nodes on that lines can easily access each other via shortest path.\n",
    "\n",
    "However, after deletion of Tsvetnoy bulvar, the cycle is broken. So to connect stations between gray and light green lines, it is required to pass through line intersection with Koltsevaya and some stations on it. It raises the value of betwenness centrality for such nodes (e.g. Serpuhovskaya, Paveletskaya, Taganskaya), keeping the old values for rest of graph. So it leads to the increase of overall graph centralization for betwenness centrality."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 5. Katz centrality (3 points)\n",
    "\n",
    "Katz centrality is based on the number of all paths (not only shortest) passing through a node. By the way, how to quickly calculate the total number of fixed length paths between two nodes?\n",
    "\n",
    "Write a function `number_of_paths` that takes graph `G`, nodes `i`, `j` and the length of paths `n`. The function returns the number of paths."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "b3cab80e268cce0a16d3f46beee4568f",
     "grade": false,
     "grade_id": "cell-99d5119d30c4e079",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def number_of_paths(G: nx.Graph, i: int, j: int, n: int) -> int:\n",
    "    \"\"\"\n",
    "    Calculate number of paths of length n\n",
    "    \n",
    "    :param G: graph of Moscow underground inside the Sadovoye ring\n",
    "    :param i: the starting node of paths\n",
    "    :param j: the target node of paths\n",
    "    :param n: the size of paths\n",
    "    :return: the number of paths between input nodes of size n\n",
    "    \"\"\"\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "06abee78761d0abdc30afcb9515bcd71",
     "grade": true,
     "grade_id": "cell-0f40f6090975a9d5",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "'''Check some paths in the city center'''\n",
    "# Paveletskaya (Koltsevaya) - Ohotny ryad. Length 4\n",
    "# Single path: Paveletskaya (Koltsevaya) -> Paveletskaya (Zamoskvoretskaya) \n",
    "# -> Novokuznetskaya -> Teatralnaya -> Ohotny ryad\n",
    "assert number_of_paths(subG, 78, 9, 4) == 1\n",
    "# Novoslobodskaya - Pushkinskaya. Length 4\n",
    "# 1st path: Novoslobodskaya -> Belorusskaya -> Krasnopresnenskaya\n",
    "# -> Barrikadnaya -> Pushkinskaya\n",
    "# 2nd path: Novoslobodskaya -> Mendeleevskaya -> Tsvetnoy bulvar\n",
    "# -> Chehovskaya -> Pushkinskaya\n",
    "assert number_of_paths(subG, 83, 120, 4) == 2\n",
    "# Novoslobodskaya - Pushkinskaya. Length 7. Many paths.\n",
    "assert number_of_paths(subG, 83, 120, 7) == 31"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can apply similar approach in calculation Katz centrality. The formula is\n",
    "\n",
    "$$k_i = \\beta\\sum_j A_{ij} + \\beta^2\\sum_j A_{ij}^2 + \\beta^3\\sum_j A_{ij}^3 + \\dots$$\n",
    "\n",
    "where $\\beta$ is an attenuation factor with restriction \n",
    "\n",
    "$$\\beta < \\frac{1}{\\lambda}$$\n",
    "\n",
    "where $\\lambda$ is a largest eigenvalue of a matrix $A$.\n",
    "\n",
    "Write a function `katz_centrality` that takes a graph `G`, number of iterations `n`, attenuation factor `beta` and returns a np.array of centrality values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "5032b14e2f76650745f5931950fa8ede",
     "grade": false,
     "grade_id": "cell-c8319e7048861c63",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def katz_centrality(G: nx.Graph, n: int, beta: float) -> np.array:\n",
    "    \"\"\"\n",
    "    Calculate Katz centrality\n",
    "    \n",
    "    :param G: graph of Moscow undeground\n",
    "    :param n: number of iterations in Katz centrality calcultation\n",
    "    :param beta: attenuation factor\n",
    "    :return: array of centrality values for each node\n",
    "    \"\"\"\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "37986ad73517c4c47a361f46de4ad295",
     "grade": true,
     "grade_id": "cell-1ebe7a8d0b3a8b75",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "'''Check the restriction on beta and networkx implementation'''\n",
    "beta = 1 / 3\n",
    "try:\n",
    "    katz = katz_centrality(G, 1, beta)\n",
    "except:\n",
    "    pass\n",
    "else:\n",
    "    raise AssertionError(\"Did not raise an exception\")\n",
    "beta = 1 / 5\n",
    "assert 0.9999 < np.corrcoef(katz_centrality(G, 1, beta), c['degree'])[0][1] <= 1\n",
    "nxkatz = np.array([val for val in nx.katz_centrality(G, beta).values()])\n",
    "assert 0.9999 < np.corrcoef(katz_centrality(G, 20, beta), nxkatz)[0][1] <= 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us draw the graph with Katz centrality visualization."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "katz_c = katz_centrality(subG, 20, 1/4)\n",
    "katz_c = katz_c / katz_c.max()\n",
    "plt.figure(figsize=(8, 6))\n",
    "nx.draw(subG, \n",
    "        pos,\n",
    "        width=0.5,\n",
    "        linewidths=0.5,\n",
    "        edgecolors='black',\n",
    "        cmap=plt.cm.hot,\n",
    "        node_size=katz_c*300,\n",
    "        node_color=katz_c)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we can see how Katz centrality converges by the number of iterations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.figure(figsize=(7, 5))\n",
    "convergence = []\n",
    "old_katz = katz_centrality(G, 1, 0.2)\n",
    "step_space = np.arange(2, 21)\n",
    "for i in step_space:\n",
    "    katz = katz_centrality(G, i, 0.2)\n",
    "    convergence.append(np.linalg.norm(katz - old_katz))\n",
    "    old_katz = katz.copy()\n",
    "plt.plot(step_space, convergence)\n",
    "plt.ylabel('Difference, Euclidean norm')\n",
    "plt.xlabel('Step')\n",
    "plt.title('Convergence of Katz centrality')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 6. Eigenvector centrality (2 points)\n",
    "\n",
    "Let us implement eigenvector centrality that can be interpreted as influence of a node. A centrality value of a node takes into account centrality values of its neighbors, that is\n",
    "\n",
    "$$v_i = \\frac{1}{\\lambda}\\sum_j A_{ij} v_j$$\n",
    "\n",
    "or in the matrix form\n",
    "\n",
    "$$Av = \\lambda v$$\n",
    "\n",
    "where $\\lambda$ is the largest eigenvalue.\n",
    "\n",
    "Write a function `eigenvector_centrality` that takes an adjacency matrix `A` and returns a np.array with centrality values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "e5b7dbbd61bb895fdd07417076bc6d5f",
     "grade": false,
     "grade_id": "cell-8dc712b03819afba",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def eigenvector_centrality(A: np.array) -> np.array:\n",
    "    \"\"\"\n",
    "    Calculate eigenvector centrality\n",
    "    \n",
    "    :param A: adjacency matric of graph\n",
    "    :return: array of eigenvector centralities\n",
    "    \"\"\"\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "bb7cdaf17213c8cd0148fa2aaf40b62e",
     "grade": true,
     "grade_id": "cell-15a0fcb2c488608e",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "'''Check some random values'''\n",
    "eig_c = eigenvector_centrality(nx.to_numpy_array(subG))\n",
    "assert eig_c.shape == (57, )\n",
    "assert eig_c[0].round(4) == 0.0244\n",
    "assert eig_c[-1].round(4) == 0.0701\n",
    "assert eig_c[25].round(4) == 0.1198"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us draw the graph with eigenvector centrality visualization."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.figure(figsize=(8, 6))\n",
    "nx.draw(subG, \n",
    "        pos,\n",
    "        width=0.5,\n",
    "        linewidths=0.5,\n",
    "        edgecolors='black',\n",
    "        cmap=plt.cm.hot,\n",
    "        node_size=eig_c/eig_c.max()*400,\n",
    "        node_color=eig_c)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 7. Correlations (0.6 point)\n",
    "\n",
    "Finally, let us see the relation between centralities. Calculate Pearson correlation coefficient and then we will draw scatter plots on pairs of centralities.\n",
    "\n",
    "Write a function `pearson_correlation` that takes two np.arrays and returns Person correlation coefficient."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "58019c3876fbee707e3c0ee0b8cb7ff3",
     "grade": false,
     "grade_id": "cell-b5e6459a752a958b",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def pearson_correlation(i_vals: np.array, j_vals: np.array) -> float:\n",
    "    \"\"\"\n",
    "    Calculate Pearson correlation coefficient\n",
    "    \n",
    "    :param i_vals: array of centralities\n",
    "    :param j_vals: array of centralities\n",
    "    :return: Pearson's correlation\n",
    "    \"\"\"\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "d55082d16d3009d2c2b7f2e46e2f8afc",
     "grade": true,
     "grade_id": "cell-2689d32a2c28cd6f",
     "locked": true,
     "points": 0.6,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "'''Check some coefficients'''\n",
    "centvals = [\n",
    "    ('Degree', list(nx.degree_centrality(G).values())),\n",
    "    ('Closeness', list(nx.closeness_centrality(G).values())),\n",
    "    ('Betweenness', list(nx.betweenness_centrality(G).values())),\n",
    "    ('Katz', katz_centrality(G, 20, 1/5)), \n",
    "    ('Eigenvector', eigenvector_centrality(nx.to_numpy_array(G)))\n",
    "]\n",
    "assert pearson_correlation(centvals[0][1], centvals[0][1]) == 1\n",
    "assert round(pearson_correlation(centvals[4][1], centvals[2][1]), 4) == 0.3358\n",
    "assert round(pearson_correlation(centvals[4][1], centvals[3][1]), 4) == 0.9169\n",
    "assert round(pearson_correlation(centvals[0][1], centvals[1][1]), 4) == 0.7211\n",
    "assert round(pearson_correlation(centvals[3][1], centvals[4][1]), 4) == 0.9169"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.figure(figsize=(2*5, 5*5))\n",
    "plt.subplots_adjust(hspace=0.4, wspace=0.4)\n",
    "k = 1\n",
    "for i in range(len(centvals)):\n",
    "    for j in range(i + 1, len(centvals)):\n",
    "        i_label, i_vals = centvals[i]\n",
    "        j_label, j_vals = centvals[j]\n",
    "        correlation = pearson_correlation(i_vals, j_vals)\n",
    "        plt.subplot(5, 2, k)\n",
    "        plt.scatter(i_vals, j_vals, s=5)\n",
    "        plt.title('Correlation: {:.4f}'.format(correlation))\n",
    "        plt.xlabel(i_label)\n",
    "        plt.ylabel(j_label)\n",
    "        k += 1"
   ]
  },
  {
   "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}