introduction-and-game-of-thrones-student.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Networks? Graphs?\n",
    "\n",
    "A mathematical structure used to model pairwise relations between objects, where the objects are usually called `nodes` and the relationship between them `edges`.\n",
    "\n",
    "G = (V, E)\n",
    "\n",
    "V = set of nodes/vetices\n",
    "\n",
    "E = set of (x, y) edges"
   ]
  },
  {
   "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 warnings\n",
    "warnings.filterwarnings(\"ignore\")\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw_circular(nx.erdos_renyi_graph(10, 0.4), with_labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Examples of Networks?\n",
    "\n",
    "Can you think of some real world networks?\n",
    "\n",
    "### Using `NetworkX`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Creating a graph/network object\n",
    "G = nx.Graph()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# accessing nodes\n",
    "G.nodes()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# accessing edges\n",
    "G.edges()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let's create a recipe network \n",
    "# G.add_node('Tomato')\n",
    "# G.add_node('Eggs')\n",
    "# G.add_node('Lamb')\n",
    "# G.add_node('Chicken')\n",
    "G.add_nodes_from(['Tomato', 'Eggs', 'Lamb', 'Chicken'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# G.add_edge('Tomato', 'Eggs')\n",
    "# G.add_edge('Lamb', 'Tomato')\n",
    "# G.add_edge('Chicken', 'Tomato')\n",
    "G.add_edges_from([('Tomato', 'Eggs'), ('Tomato', 'Lamb'), ('Tomato', 'Chicken')])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.nodes()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.edges()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(G, with_labels=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# any hashable object can be a node in the network\n",
    "G.add_node([1, 2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Let's work on a read world network.\n",
    "\n",
    "Arxiv GR-QC (General Relativity and Quantum Cosmology) collaboration network is from the e-print arXiv and covers scientific collaborations between authors papers submitted to General Relativity and Quantum Cosmology category. If an author i co-authored a paper with author j, the graph contains a undirected edge from i to j. If the paper is co-authored by k authors this generates a completely connected (sub)graph on k nodes.\n",
    "\n",
    "source: http://snap.stanford.edu/data/index.html#canets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# If six authors wrote a paper together, they will have a complete graph\n",
    "nx.draw(nx.complete_graph(6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create a author graph from the dataset\n",
    "import csv\n",
    "authors_graph = nx.Graph()\n",
    "with open('CA-GrQc.txt', 'r') as f:\n",
    "    reader = csv.reader(f, delimiter='\\t')\n",
    "    for row in reader:\n",
    "        authors_graph.add_edge(row[0], row[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(authors_graph.number_of_edges())\n",
    "print(authors_graph.number_of_nodes())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Can we find the most influential researcher in this network?\n",
    "\n",
    "Something which is not so much dependent on citations.\n",
    "\n",
    "##### How do we evaluate the importance of some individuals in a network?\n",
    "\n",
    "Within a social network, there will be certain individuals which perform certain important functions. For example, there may be hyper-connected individuals who are connected to many, many more people. They would be of use in the spreading of information. Alternatively, if this were a disease contact network, identifying them would be useful in stopping the spread of diseases. How would one identify these people?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise \n",
    "\n",
    "Create a list of (node, degree of node) tuples and find the node with maximum degree.\n",
    "\n",
    "degree of node = number of neighbors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The degree of a node translates to degree centrality (which is a normalised version of degree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.degree_centrality(authors_graph)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "Plot a histogram of degree centrality of authors_graph.\n",
    "\n",
    "Hint: plt.hist(list_of_values) will plot a histogram\n",
    "\n",
    "(count vs degree centrality)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Let's have a look at Connected Components of a graph.\n",
    "\n",
    "In graph theory, a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = nx.erdos_renyi_graph(10, 0.15, seed=1)\n",
    "nx.draw(G, with_labels=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print([len(c) for c in sorted(nx.connected_components(authors_graph), key=len, reverse=True)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "graphs = [c for c in sorted(nx.connected_component_subgraphs(authors_graph), key=len, reverse=True)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len(graphs[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(graphs[10])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Shortest Path in the network"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(nx.erdos_renyi_graph(10, 0.15, seed=1), with_labels=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(nx.shortest_path(graphs[0], '22504', '23991'))\n",
    "print(len(nx.shortest_path(graphs[0], '22504', '23991')))\n",
    "print(nx.shortest_path_length(graphs[0], '22504', '23991'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "##### Six degrees of separation, Erdos Number, Bacon Number!!\n",
    "\n",
    "Find the '22504' number of the graph authors_graph, if there is no connection between nodes then give it the number `-1`.\n",
    "Also plot a histogram of the '22504' number.\n",
    "\n",
    "Find the average shortest path length in the first component i.e. graphs[0]\n",
    "\n",
    "HINT: `nx.shortest_path_length`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d = {}\n",
    "for node in authors_graph.nodes():\n",
    "    try:\n",
    "        d[node] = _______________\n",
    "    except:\n",
    "        d[node] = -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.hist(list(d.values()))\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Let's change gears and talk about Game of thrones or shall I say Network of Thrones.\n",
    "\n",
    "It is suprising right? What is the relationship between a fatansy TV show/novel and network science or python(it's not related to a dragon).\n",
    "\n",
    "If you haven't heard of Game of Thrones, then you must be really good at hiding. Game of Thrones is the hugely popular television series by HBO based on the (also) hugely popular book series A Song of Ice and Fire by George R.R. Martin. In this notebook, we will analyze the co-occurrence network of the characters in the Game of Thrones books. Here, two characters are considered to co-occur if their names appear in the vicinity of 15 words from one another in the books."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/got.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Andrew J. Beveridge, an associate professor of mathematics at Macalester College, and Jie Shan, an undergraduate created a network from the book A Storm of Swords by extracting relationships between characters to find out the most important characters in the book(or GoT).\n",
    "\n",
    "The dataset is publicly avaiable for the 5 books at https://github.com/mathbeveridge/asoiaf. This is an interaction network and were created by connecting two characters whenever their names (or nicknames) appeared within 15 words of one another in one of the books. The edge weight corresponds to the number of interactions. \n",
    "\n",
    "Credits:\n",
    "\n",
    "Blog: https://networkofthrones.wordpress.com\n",
    "\n",
    "Math Horizons Article: https://www.maa.org/sites/default/files/pdf/Mathhorizons/NetworkofThrones%20%281%29.pdf"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "from matplotlib import cm\n",
    "import community\n",
    "import numpy as np\n",
    "import warnings\n",
    "warnings.filterwarnings('ignore')\n",
    "\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Let's load in the datasets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "book1 = pd.read_csv('data/asoiaf-book1-edges.csv')\n",
    "book2 = pd.read_csv('data/asoiaf-book2-edges.csv')\n",
    "book3 = pd.read_csv('data/asoiaf-book3-edges.csv')\n",
    "book4 = pd.read_csv('data/asoiaf-book4-edges.csv')\n",
    "book5 = pd.read_csv('data/asoiaf-book5-edges.csv')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The resulting DataFrame book1 has 5 columns: Source, Target, Type, weight, and book. Source and target are the two nodes that are linked by an edge. A network can have directed or undirected edges and in this network all the edges are undirected. The weight attribute of every edge tells us the number of interactions that the characters have had over the book, and the book column tells us the book number.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "book1.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once we have the data loaded as a pandas DataFrame, it's time to create a network. We create a graph for each book. It's possible to create one MultiGraph instead of 5 graphs, but it is easier to play with different graphs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G_book1 = nx.Graph()\n",
    "G_book2 = nx.Graph()\n",
    "G_book3 = nx.Graph()\n",
    "G_book4 = nx.Graph()\n",
    "G_book5 = nx.Graph()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's populate the graph with edges from the pandas DataFrame."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for row in book1.iterrows():\n",
    "    G_book1.add_edge(row[1]['Source'], row[1]['Target'], weight=row[1]['weight'], book=row[1]['book'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for row in book2.iterrows():\n",
    "    G_book2.add_edge(row[1]['Source'], row[1]['Target'], weight=row[1]['weight'], book=row[1]['book'])\n",
    "for row in book3.iterrows():\n",
    "    G_book3.add_edge(row[1]['Source'], row[1]['Target'], weight=row[1]['weight'], book=row[1]['book'])\n",
    "for row in book4.iterrows():\n",
    "    G_book4.add_edge(row[1]['Source'], row[1]['Target'], weight=row[1]['weight'], book=row[1]['book'])\n",
    "for row in book5.iterrows():\n",
    "    G_book5.add_edge(row[1]['Source'], row[1]['Target'], weight=row[1]['weight'], book=row[1]['book'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "books = [G_book1, G_book2, G_book3, G_book4, G_book5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's have a look at these edges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(G_book1.edges(data=True))[16]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(G_book1.edges(data=True))[400]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Finding the most important node i.e character in these networks.\n",
    "\n",
    "Is it Jon Snow, Tyrion, Daenerys, or someone else? Let's see! Network Science offers us many different metrics to measure the importance of a node in a network as we saw in the first part of the tutorial. Note that there is no \"correct\" way of calculating the most important node in a network, every metric has a different meaning.\n",
    "\n",
    "First, let's measure the importance of a node in a network by looking at the number of neighbors it has, that is, the number of nodes it is connected to. For example, an influential account on Twitter, where the follower-followee relationship forms the network, is an account which has a high number of followers. This measure of importance is called degree centrality.\n",
    "\n",
    "Using this measure, let's extract the top ten important characters from the first book (book[0]) and the fifth book (book[4])."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "deg_cen_book1 = nx.degree_centrality(books[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "deg_cen_book5 = nx.degree_centrality(books[4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted(deg_cen_book1.items(), key=lambda x:x[1], reverse=True)[0:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted(deg_cen_book5.items(), key=lambda x:x[1], reverse=True)[0:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Plot a histogram of degree centrality\n",
    "plt.hist(list(nx.degree_centrality(G_book4).values()))\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d = {}\n",
    "for i, j in dict(nx.degree(G_book4)).items():\n",
    "    if j in d:\n",
    "        d[j] += 1\n",
    "    else:\n",
    "        d[j] = 1\n",
    "x = np.log2(list((d.keys())))\n",
    "y = np.log2(list(d.values()))\n",
    "plt.scatter(x, y, alpha=0.9)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "Create a new centrality measure, weighted_degree(Graph, weight) which takes in Graph and the weight attribute and returns a weighted degree dictionary. Weighted degree is calculated by summing the weight of the all edges of a node and find the top five characters according to this measure."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def weighted_degree(G, weight):\n",
    "    result = dict()\n",
    "    for node in G.nodes():\n",
    "        weight_degree = 0\n",
    "        for n in G.edges([node], data=True):\n",
    "            weight_degree += ___________\n",
    "        result[node] = weight_degree\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.hist(list(weighted_degree(G_book1, 'weight').values()))\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted(weighted_degree(G_book1, 'weight').items(), key=lambda x:x[1], reverse=True)[0:10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Let's do this for Betweeness centrality and check if this makes any difference\n",
    "\n",
    "Haha, evil laugh"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# First check unweighted, just the structure\n",
    "\n",
    "sorted(nx.betweenness_centrality(G_book1).items(), key=lambda x:x[1], reverse=True)[0:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let's care about interactions now\n",
    "\n",
    "sorted(nx.betweenness_centrality(G_book1, weight='weight').items(), key=lambda x:x[1], reverse=True)[0:10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### PageRank\n",
    "The billion dollar algorithm, PageRank works by counting the number and quality of links to a page to determine a rough estimate of how important the website is. The underlying assumption is that more important websites are likely to receive more links from other websites."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# by default weight attribute in pagerank is weight, so we use weight=None to find the unweighted results\n",
    "sorted(nx.pagerank_numpy(G_book1, weight=None).items(), key=lambda x:x[1], reverse=True)[0:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted(nx.pagerank_numpy(G_book1, weight='weight').items(), key=lambda x:x[1], reverse=True)[0:10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Is there a correlation between these techniques?\n",
    "\n",
    "#### Exercise\n",
    "\n",
    "Find the correlation between these four techniques.\n",
    "\n",
    "- pagerank\n",
    "- betweenness_centrality\n",
    "- weighted_degree\n",
    "- degree centrality"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cor = pd.DataFrame.from_records([______, _______, _______, _______])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cor.T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cor.T.corr()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Evolution of importance of characters over the books"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "According to degree centrality the most important character in the first book is Eddard Stark but he is not even in the top 10 of the fifth book. The importance changes over the course of five books, because you know stuff happens ;)\n",
    "\n",
    "Let's look at the evolution of degree centrality of a couple of characters like Eddard Stark, Jon Snow, Tyrion which showed up in the top 10 of degree centrality in first book.\n",
    "\n",
    "We create a dataframe with character columns and index as books where every entry is the degree centrality of the character in that particular book and plot the evolution of degree centrality Eddard Stark, Jon Snow and Tyrion.\n",
    "We can see that the importance of Eddard Stark in the network dies off and with Jon Snow there is a drop in the fourth book but a sudden rise in the fifth book"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "evol = [nx.degree_centrality(book) for book in books]\n",
    "evol_df = pd.DataFrame.from_records(evol).fillna(0)\n",
    "evol_df[['Eddard-Stark', 'Tyrion-Lannister', 'Jon-Snow']].plot()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "set_of_char = set()\n",
    "for i in range(5):\n",
    "    set_of_char |= set(list(evol_df.T[i].sort_values(ascending=False)[0:5].index))\n",
    "set_of_char"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "\n",
    "Plot the evolution of weighted degree centrality of the above mentioned characters over the 5 books, and repeat the same exercise for betweenness centrality."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "evol_df[________].plot(figsize=(29,15))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "evol = [________ for graph in [G_book1, G_book2, G_book3, G_book4, G_book5]]\n",
    "evol_df = pd.DataFrame.from_records(evol).fillna(0)\n",
    "\n",
    "set_of_char = set()\n",
    "for i in range(5):\n",
    "    set_of_char |= set(list(evol_df.T[i].sort_values(ascending=False)[0:5].index))\n",
    "\n",
    "\n",
    "evol_df[_________].plot(figsize=(19,10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### So what's up with  Stannis Baratheon?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(nx.barbell_graph(5, 1), with_labels=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted(nx.degree_centrality(G_book5).items(), key=lambda x:x[1], reverse=True)[:5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted(nx.betweenness_centrality(G_book5).items(), key=lambda x:x[1], reverse=True)[:5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Community detection in Networks\n",
    "A network is said to have community structure if the nodes of the network can be easily grouped into (potentially overlapping) sets of nodes such that each set of nodes is densely connected internally.\n",
    "\n",
    "We will use louvain community detection algorithm to find the modules in our graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.figure(figsize=(15, 15))\n",
    "\n",
    "partition = community.best_partition(G_book1)\n",
    "size = (len(set(partition.values())))\n",
    "pos = nx.spring_layout(G_book1)\n",
    "count = 0\n",
    "colors = [cm.jet(x) for x in np.linspace(0, 1, size)]\n",
    "for com in set(partition.values()):\n",
    "    list_nodes = [nodes for nodes in partition.keys()\n",
    "                                if partition[nodes] == com]\n",
    "    nx.draw_networkx_nodes(G_book1, pos, list_nodes, node_size = 100, node_color=colors[count])\n",
    "    count = count + 1\n",
    "nx.draw_networkx_edges(G_book1, pos, alpha=0.2)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d = {}\n",
    "for character, par in partition.items():\n",
    "    if par in d:\n",
    "        d[par].append(character)\n",
    "    else:\n",
    "        d[par] = [character]\n",
    "d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(nx.subgraph(G_book1, d[3]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(nx.subgraph(G_book1, d[1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.density(G_book1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.density(nx.subgraph(G_book1, d[4]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.density(nx.subgraph(G_book1, d[4]))/nx.density(G_book1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise \n",
    "\n",
    "Find the most important node in the partitions according to degree centrality of the nodes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A bit about power law in networks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G_random = nx.erdos_renyi_graph(100, 0.1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(G_random)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G_ba = nx.barabasi_albert_graph(100, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(G_ba)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Plot a histogram of degree centrality\n",
    "plt.hist(list(nx.degree_centrality(G_random).values()))\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.hist(list(nx.degree_centrality(G_ba).values()))\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G_random = nx.erdos_renyi_graph(2000, 0.2)\n",
    "G_ba = nx.barabasi_albert_graph(2000, 20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d = {}\n",
    "for i, j in dict(nx.degree(G_random)).items():\n",
    "    if j in d:\n",
    "        d[j] += 1\n",
    "    else:\n",
    "        d[j] = 1\n",
    "x = np.log2(list((d.keys())))\n",
    "y = np.log2(list(d.values()))\n",
    "plt.scatter(x, y, alpha=0.9)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d = {}\n",
    "for i, j in dict(nx.degree(G_ba)).items():\n",
    "    if j in d:\n",
    "        d[j] += 1\n",
    "    else:\n",
    "        d[j] = 1\n",
    "x = np.log2(list((d.keys())))\n",
    "y = np.log2(list(d.values()))\n",
    "plt.scatter(x, y, alpha=0.9)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}