2020-05-21_intro_to_network_analysis_in_python.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Notebook Author: [Trenton McKinney][1]\n",
    "- Course: **[DataCamp: Introduction to Network Analysis in Python][2]**\n",
    " - This [notebook][3] was created as a reproducible reference.\n",
    " - The material is from the course\n",
    " - I completed the exercises\n",
    " - If you find the content beneficial, consider a [DataCamp Subscription][4].\n",
    " - I added a function (**`create_dir_save_file`**) to automatically download and save the required data (`data/2020-05-21_intro_to_network_analysis_in_python`) and image (`Images/2020-05-21_intro_to_network_analysis_in_python`) files.\n",
    "\n",
    "  [1]: https://trenton3983.github.io/\n",
    "  [2]: https://learn.datacamp.com/courses/introduction-to-network-analysis-in-python\n",
    "  [3]: https://github.com/trenton3983/DataCamp/blob/master/2020-05-21_intro_to_network_analysis_in_python.ipynb\n",
    "  [4]: https://www.datacamp.com/join-me/MjQwNzMyMg=="
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Course Description\n",
    "\n",
    "From on-line social networks such as Facebook and Twitter to transportation networks such as bike sharing systems, networks are everywhere. And knowing how to analyze them will open up a new world of possibilities for you as a data scientist. This course will equip you with the skills to analyze, visualize, and make sense of networks. You'll apply the concepts you learn to real-world network data using the powerful `NetworkX` library. With the knowledge gained in this course, you'll develop your network thinking skills and be able to look at your data with a fresh perspective."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "#### Note\n",
    "\n",
    "There have been significant changes to nxviz v0.7.4. The code in the notebook has been update to use the new function calls, but the original instructions have not been altered."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Imports"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pathlib import Path\n",
    "import requests\n",
    "import networkx as nx\n",
    "import nxviz as nv  # using v0.7.4\n",
    "from nxviz import annotate\n",
    "import matplotlib as mpl\n",
    "import matplotlib.pyplot as plt\n",
    "from datetime import datetime, date\n",
    "from pprint import pprint as pp\n",
    "from itertools import combinations\n",
    "import random\n",
    "from collections import Counter, defaultdict\n",
    "import pickle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(f'NetworkX version: {nx.__version__}')\n",
    "print(f'Matplotlib version: {mpl.__version__}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_dir_save_file(dir_path: Path, url: str):\n",
    "    \"\"\"\n",
    "    Check if the path exists and create it if it does not.\n",
    "    Check if the file exists and download it if it does not.\n",
    "    \"\"\"\n",
    "    if not dir_path.parents[0].exists():\n",
    "        dir_path.parents[0].mkdir(parents=True)\n",
    "        print(f'Directory Created: {dir_path.parents[0]}')\n",
    "    else:\n",
    "        print('Directory Exists')\n",
    "        \n",
    "    if not dir_path.exists():\n",
    "        r = requests.get(url, allow_redirects=True)\n",
    "        open(dir_path, 'wb').write(r.content)\n",
    "        print(f'File Created: {dir_path.name}')\n",
    "    else:\n",
    "        print('File Exists')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data_dir = Path('data/2020-05-21_intro_to_network_analysis_in_python')\n",
    "images_dir = Path('Images/2020-05-21_intro_to_network_analysis_in_python')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Datasets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "twitter = 'https://assets.datacamp.com/production/repositories/580/datasets/64cf6963a7e8005e3771ef3b256812a5797320f0/ego-twitter.p'\n",
    "github = 'https://assets.datacamp.com/production/repositories/580/datasets/69ada08d5cce7f35f38ffefe8f2291b7cfcd6000/github_users.p'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "datasets = [twitter, github]\n",
    "data_paths = list()\n",
    "\n",
    "for data in datasets:\n",
    "    file_name = data.split('/')[-1].replace('?raw=true', '')\n",
    "    data_path = data_dir / file_name\n",
    "    create_dir_save_file(data_path, data)\n",
    "    data_paths.append(data_path)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# .read_gpickle is no longer available\n",
    "# T = nx.read_gpickle(data_paths[0])\n",
    "# Gh = nx.read_gpickle(data_paths[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(data_paths[0], 'rb') as f:\n",
    "    T = pickle.load(f)\n",
    "\n",
    "with open(data_paths[1], 'rb') as f:\n",
    "    Gh = pickle.load(f)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction to networks\n",
    "\n",
    "In this chapter, you'll be introduced to fundamental concepts in network analytics while exploring a real-world Twitter network dataset. You'll also learn about [NetworkX][1], a library that allows you to manipulate, analyze, and model graph data. You'll learn about the different types of graphs and how to rationally visualize them.\n",
    "\n",
    "  [1]: https://networkx.github.io/documentation/stable/index.html"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Networks\n",
    "\n",
    "### Examples of Networks\n",
    "1. Social\n",
    " - In a social network, we're modeling the relationship between people.\n",
    "1. Transportation\n",
    " - In a transportation network, we're modeling the connectivity between locations, as determined by the roads or flight paths connection them.\n",
    "- Networks are a useful tool for modeling relationships between entities.\n",
    "\n",
    "### Insights\n",
    "1. Important entities: influencers in social networks\n",
    "1. Pathfinding: most efficient transportation path\n",
    "1. Clustering: finding communities\n",
    "- By modeling the data as a network, you can gain insight into what entities (or nodes) are important, such as broadcasters or influencers in a social network.\n",
    "- You can start to think about optimizing transportation between cities.\n",
    "- Leverage the network structure to find communities in the network.\n",
    "\n",
    "### Network Structure\n",
    "\n",
    "![network_structure][1]\n",
    "\n",
    "- Networks are described by two sets of items, which form a \"network\".\n",
    " - Nodes\n",
    " - Edges\n",
    "- In mathematical terms, this is a graph.\n",
    "- Nodes and edges can have metadata associated with them.\n",
    " - Lets say there are two friends, Hugo and myself, who met on May 21, 2016.\n",
    " - The nodes may be \"Hugo\" and myself, with metadata stored in a `key-value` pair as `id` and `age`.\n",
    " - The friendship is represented as a line between two nodes, and may have metadata such as `date`, which represents the date we first met.\n",
    " \n",
    "![social graph][2]\n",
    "\n",
    "### NetworkX\n",
    "\n",
    "- This python library allows us to manipulate, analyze, and model, graph data.\n",
    "- Using `nx.Graph()`, we initialize an empty graph, to which we can add nodes and edges\n",
    "- The integers 1, 2, and 3 can be entered as nodes, using the `add_nodes_from` method, passing in the list `[1, 2, 3]`, as an argument.\n",
    "- Use the `.nodes` method to see the nodes present in the graph.\n",
    "- Similarly, use `.add_edges` and `.edges` to add and see the edges present in the graph.\n",
    "- Edges between nodes are represented as a tuple, in which each tuple shows the nodes that are present on that edge.\n",
    "\n",
    "```python\n",
    "import networkx as nx\n",
    "\n",
    "G = nx.Graph()\n",
    "G.add_nodes_from([1, 2, 3])\n",
    "G.nodes()\n",
    ">>> [1, 2, 3]\n",
    "G.add_edge(1, 2)\n",
    "G.edges()\n",
    ">>> [(1, 2)]\n",
    "```\n",
    "\n",
    "- Metadata can be stored on the graph as well.\n",
    "- For example, I can add to the node `1`, a `label` key with the value `blue`, just as I would assign a value to the key of a dictionary.\n",
    "- The node list can be retrieved with `G.nodes()` and passing the `data=True` parameter.\n",
    " - This returns a list of tuples, in which the first element of each tuple is the node, and the second element is a dictionary, in which the `key-value` pairs correspond to the metadata.\n",
    "\n",
    "```python\n",
    "G.node[1]['label'] = 'blue'\n",
    "G.nodes(data=True)\n",
    ">>>[(1, {'label': 'blue}), (2, {}), (3, {})]\n",
    "```\n",
    "\n",
    "- `networkx` as provides basic drawing functionality, using the `nx.draw()` function, which takes in a graph `G` as an argument.\n",
    "- In the IPyhton shell, you'll also have to call `plt.show()` function in order to display the graph screen.\n",
    "- With this graph, the `nx.draw()` function will draw to screen what we call a **node-link diagram** rendering of the graph.\n",
    "\n",
    "```python\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "nx.draw(G)\n",
    "plt.show()\n",
    "```\n",
    "\n",
    "- The first set of exercises we'll be doing is essentially exploratory data analysis on graphs.\n",
    "\n",
    "### Other Resources\n",
    "1. [Wikipedia: Network Theory][3]\n",
    "\n",
    "\n",
    "  [1]: https://raw.githubusercontent.com/trenton3983/DataCamp/master/Images/2020-05-21_intro_to_network_analysis_in_python/network_structure_1.JPG\n",
    "  [2]: https://raw.githubusercontent.com/trenton3983/DataCamp/master/Images/2020-05-21_intro_to_network_analysis_in_python/network_structure_2.JPG\n",
    "  [3]: https://en.wikipedia.org/wiki/Network_theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What is a network?\n",
    "\n",
    "Let's think again about examples of networks. Which of the following data is least easily modeled as a network?\n",
    "\n",
    "- ~~Airplane transportation.~~\n",
    "- **Phone numbers in a telephone directory.**\n",
    "- ~~Co-authorship of papers.~~\n",
    "- ~~Atoms in a molecule.~~\n",
    "\n",
    "1. Compared to the other options, it would not be as easy to model phone numbers in a telephone directory as a network."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Basics of NetworkX API, using Twitter network\n",
    "\n",
    "To get you up and running with the NetworkX API, we will run through some basic functions that let you query a Twitter network that has been pre-loaded for you and is available in the IPython Shell as `T`. The Twitter network comes from [KONECT][1], and shows a snapshot of a subset of Twitter users. It is an anonymized Twitter network with metadata.\n",
    "\n",
    "You're now going to use the NetworkX API to explore some basic properties of the network, and are encouraged to experiment with the data in the IPython Shell.\n",
    "\n",
    "Wait for the IPython shell to indicate that the graph that has been preloaded under the variable name T (representing a Twitter network), and then answer the following question:\n",
    "\n",
    "What is the size of the graph `T`, the type of `T.nodes()`, and the data structure of the third element of the last edge listed in `T.edges(data=True)`? The `len()` and `type()` functions will be useful here. To access the last entry of `T.edges(data=True)`, you can use `list(T.edges(data=True))[-1]`.\n",
    "\n",
    "- **23369, `networkx.classes.reportviews.NodeView`, `dict`.**\n",
    "- ~~32369, `tuple`, `datetime`.~~\n",
    "- ~~23369, `networkx.classes.reportviews.NodeView`, `datetime`.~~\n",
    "- ~~22339, `dict`, `dict`.~~\n",
    "\n",
    "\n",
    "  [1]: http://konect.uni-koblenz.de/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(len(T))\n",
    "print(type(T.nodes()))\n",
    "print(list(T.edges(data=True))[-1])\n",
    "print(type(list(T.edges(data=True))[-1][2]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Basic drawing of a network using NetworkX\n",
    "\n",
    "NetworkX provides some basic drawing functionality that works for small graphs. We have selected a subset of nodes from the graph for you to practice using NetworkX's drawing facilities. It has been pre-loaded as `T_sub`.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Import `matplotlib.pyplot` as `plt` and `networkx` as `nx`.\n",
    "- Draw `T_sub` to the screen by using the `nx.draw()` function, and don't forget to also use `plt.show()` to display it.\n",
    "\n",
    "#### Creating `T_sub`\n",
    "- Use [DiGraph][1] instead of [Graph][2]\n",
    "- [Why don't edges added with G.add_edges_from(), match G.edges()?][3]\n",
    "\n",
    "\n",
    "  [1]: https://networkx.github.io/documentation/networkx-1.10/reference/classes.digraph.html#networkx.DiGraph\n",
    "  [2]: https://networkx.github.io/documentation/networkx-1.10/reference/classes.graph.html#networkx.Graph\n",
    "  [3]: https://stackoverflow.com/questions/62032404/why-dont-edges-added-with-g-add-edges-from-match-g-edges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "T_sub = nx.DiGraph()\n",
    "edges_from_T = [x for x in T.edges(list(range(50)), data=True) if x[0] in [1, 16, 18, 19, 28, 36, 37, 39, 42, 43, 45] if x[1] < 50]\n",
    "T_sub.add_edges_from(edges_from_T)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.figure(figsize=(8, 8))\n",
    "nx.draw(T_sub, with_labels=True)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Queries on a graph\n",
    "\n",
    "Now that you know some basic properties of the graph and have practiced using NetworkX's drawing facilities to visualize components of it, it's time to explore how you can query it for nodes and edges. Specifically, you're going to look for \"nodes of interest\" and \"edges of interest\". To achieve this, you'll make use of the `.nodes()` and `.edges()` methods that Eric went over in the video. The `.nodes()` method returns a list of nodes, while the `.edges()` method returns a list of tuples, in which each tuple shows the nodes that are present on that edge. Recall that passing in the keyword argument data=True in these methods retrieves the corresponding metadata associated with the nodes and edges as well.\n",
    "\n",
    "You'll write list comprehensions to effectively build these queries in one line. For a refresher on list comprehensions, refer to [Part 2][1] of DataCamp's Python Data Science Toolbox course. Here's the recipe for a list comprehension:\n",
    "\n",
    "`[` *output expression* `for` *iterator variable* `in` *iterable* `if` *predicate expression* `]`.\n",
    "\n",
    "You have to fill in the `_iterable_` and the `_predicate expression_`. Feel free to prototype your answer by exploring the graph in the IPython Shell before submitting your solution.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Use a list comprehension to get a **list of nodes** from the graph `T` that have the `'occupation'` label of `'scientist'`.\n",
    " - The _output expression_ `n` has been specified for you, along with the _iterator variables_ `n` and `d`. Your task is to fill in the _iterable_ and the _conditional expression_.\n",
    " - Use the `.nodes()` method of `T` access its nodes, and be sure to specify `data=True` to obtain the metadata for the nodes.\n",
    " - The iterator variable `d` is a dictionary. The key of interest here is `'occupation'` and value of interest is `'scientist'`.\n",
    "- Use a list comprehension to get a **list of edges** from the graph T that were formed for at least 6 years, i.e., from before **1 Jan 2010**.\n",
    " - Your task once again is to fill in the _iterable_ and _conditional expression_.\n",
    " - Use the `.edges()` method of `T` to access its edges. Be sure to obtain the metadata for the edges as well.\n",
    " - The dates are stored as `datetime.date` objects in the metadata dictionary `d`, under the key `'date'`. To access the date 1 Jan 2009, for example, the dictionary value would be `date(2009, 1, 1)`.\n",
    "\n",
    "\n",
    "  [1]: https://www.datacamp.com/courses/python-data-science-toolbox-part-2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Use a list comprehension to get the nodes of interest: noi\n",
    "noi = [n for n, d in T.nodes(data=True) if d['occupation'] == 'scientist']\n",
    "\n",
    "# Use a list comprehension to get the edges of interest: eoi\n",
    "eoi = [(u, v) for u, v, d in T.edges(data=True) if d['date'].year < 2010]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(noi[:10])\n",
    "print(eoi[:10])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Types of Graphs\n",
    "\n",
    "1. Undirected graphs\n",
    " - Facebook\n",
    " - They are comprised of edges that don't have any inherent directionality associated with them.\n",
    " - With Facebook, for example, when one user befriends another, the two are automatically connected with an edge.\n",
    " - This is commonly drawn as a line with no arrows between two circles.\n",
    " - Undirected graphs have the type `Graph`\n",
    " \n",
    "```python\n",
    "import networkx as nx\n",
    "\n",
    "G = nx.Graph()\n",
    "type(G)\n",
    ">>> networkx.classes.graph.Graph\n",
    "``` \n",
    "\n",
    "2. Directed graphs\n",
    " - Twitter\n",
    " - This is because of the nature of how users interact with one another.\n",
    " - For example, one user may follow another, but that other user may not follow back.\n",
    " - As such, there's an inherent directionality associated with the graph\n",
    " - Directed grasphs have the type `DiGraph`\n",
    " \n",
    "```python\n",
    "D = nx.DiGraph()\n",
    "type(D)\n",
    ">>> networkx.classes.digraph.DiGraph\n",
    "```\n",
    "\n",
    "3. Muti-edge (Directed) graphs\n",
    " - Graph in which there are multiple edges permitted between the nodes\n",
    " - For example, we may want to model trips between bike sharing stations\n",
    " - Each trip may be one edge between the pair of stations\n",
    " - Sometimes, for practical reasons, it may be too memory-intensive too model multiple edges per pair of nodes, and so one may choose to collapse the edges into a single edge that contains a metadata summary of the original.\n",
    "    - For example, we may want to collapse these three edges into a single one and give them a _weight_ metadata with the value _3_, indicating that it was originally 3 edges between the pair of nodes.\n",
    "\n",
    "![multi-edge][1]\n",
    "\n",
    "```python\n",
    "M = nx.MultiGraph\n",
    "type(M)\n",
    ">>> networkx.classes.multigraph.MultiGraph\n",
    "\n",
    "MD = nx.MultiDiGraph\n",
    "type(MD)\n",
    ">>> networkx.classes.multidigraph.MultiDiGraph\n",
    "```\n",
    "\n",
    "4. Self-loops\n",
    " - Self-loops can be used in certain scenarios, such as in bike sharing data, where a trip begins at a station and ends at the same station.\n",
    "\n",
    "\n",
    "  [1]: https://raw.githubusercontent.com/trenton3983/DataCamp/master/Images/2020-05-21_intro_to_network_analysis_in_python/multi-edge.JPG"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Checking the un/directed status of a graph\n",
    "\n",
    "In the video, Eric described to you different types of graphs. Which type of graph do you think the Twitter network data you have been working with corresponds to? Use Python's built-in `type()` function in the IPython Shell to find out. The network, as before, has been pre-loaded as `T`.\n",
    "\n",
    "Of the four below choices below, which one corresponds to the type of graph that `T` is?\n",
    "\n",
    "- ~~Undirected Graph.~~\n",
    "- **Directed Graph.**\n",
    "- ~~Undirected Multi-Edge Graph.~~\n",
    "- ~~Directed Multi-Edge Graph.~~"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Specifying a weight on edges\n",
    "\n",
    "Weights can be added to edges in a graph, typically indicating the \"strength\" of an edge. In NetworkX, the weight is indicated by the `'weight'` key in the metadata dictionary.\n",
    "\n",
    "Before attempting the exercise, use the IPython Shell to access the dictionary metadata of `T` and explore it, for instance by running the commands `T.edges[1, 10]` and then `T.edges[10, 1]`. Note how there's only one field, and now you're going to add another field, called `'weight'`.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Set the `'weight'` attribute of the edge between node `1` and `10` of `T` to be equal to `2`. Refer to the following template to set an attribute of an edge: `network_name.edges[node1, node2]['attribute'] = value`. Here, the `'attribute'` is `'weight'`.\n",
    "- Set the weight of every edge involving node `293` to be equal to `1.1`. To do this:\n",
    " - Using a `for` loop, iterate over all the edges of `T`, including the `metadata`.\n",
    " - If `293` is involved in the list of nodes `[u, v]`:\n",
    "    - Set the weight of the edge between `u` and `v` to be `1.1`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Set the weight of the edge\n",
    "T.edges[1, 10]['weight'] = 2\n",
    "\n",
    "# Iterate over all the edges (with metadata)\n",
    "for u, v, d in T.edges(data=True):\n",
    "\n",
    "    # Check if node 293 is involved\n",
    "    if 293 in [u, v]:\n",
    "\n",
    "        # Set the weight to 1.1\n",
    "        T.edges[u, v]['weight'] = 1.1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Checking whether there are self-loops in the graph\n",
    "\n",
    "As Eric discussed, NetworkX also allows edges that begin and end on the same node; while this would be non-intuitive for a social network graph, it is useful to model data such as trip networks, in which individuals begin at one location and end in another.\n",
    "\n",
    "It is useful to check for this before proceeding with further analyses, and NetworkX graphs provide a method for this purpose: `.number_of_selfloops().`\n",
    "\n",
    "In this exercise as well as later ones, you'll find the `assert` statement useful. An `assert`-ions checks whether the statement placed after it evaluates to True, otherwise it will throw an `AssertionError`.\n",
    "\n",
    "To begin, use the `.number_of_selfloops()` method on `T` in the IPython Shell to get the number of edges that begin and end on the same node. A number of self-loops have been synthetically added to the graph. Your job in this exercise is to write a function that returns these edges.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Define a function called `find_selfloop_nodes()` which takes one argument: `G`.\n",
    " - Using a `for` loop, iterate over all the edges in `G` (excluding the metadata).\n",
    " - If node `u` is equal to node `v`:\n",
    "   - Append `u` to the list `nodes_in_selfloops`.\n",
    "   - Return the list `nodes_in_selfloops`.\n",
    "- Check that the number of self loops in the graph equals the number of nodes in self loops. This has been done for you, so hit 'Submit Answer' to see the result!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define find_selfloop_nodes()\n",
    "def find_selfloop_nodes(G):\n",
    "    \"\"\"\n",
    "    Finds all nodes that have self-loops in the graph G.\n",
    "    \"\"\"\n",
    "    nodes_in_selfloops = []\n",
    "\n",
    "    # Iterate over all the edges of G\n",
    "    for u, v in G.edges():\n",
    "\n",
    "    # Check if node u and node v are the same\n",
    "        if u == v:\n",
    "\n",
    "            # Append node u to nodes_in_selfloops\n",
    "            nodes_in_selfloops.append(u)\n",
    "\n",
    "    return nodes_in_selfloops\n",
    "\n",
    "# Check whether number of self loops equals the number of nodes in self loops\n",
    "# number_of_selfloops() is deprecated\n",
    "assert len(list(nx.selfloop_edges(T))) == len(find_selfloop_nodes(T))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len(list(nx.selfloop_edges(T)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**There are 42 nodes in T that have self-loops.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Network Visualization\n",
    "\n",
    "1. Matrix plots\n",
    " - ![matrix_plots][1]\n",
    " - Nodes are the rows and columns of a matrix, and cells are filled in according to whether an edge exists between the pairs of nodes.\n",
    " - In an undirected graph, the matrix is symmetrical around the diagonal, which is highlighted in gray.\n",
    " - Figure 3: edge (A, B) is equivalent to edge (B, A).  Highlighted in yellow.\n",
    " - Figure 4: edge (A, C) is equivalent to edge (C, A), because there's no directionality associated with that edge.\n",
    " - With directed graphs, the matrix representation is not necessarily going to be symmetrical.\n",
    " - Figure 5: there's a bidirectional edge between A and C, but only an edge from A to B and not B to A.\n",
    "       - (A, B) will be filled in, but not (B, A)\n",
    " - If the nodes are ordered along the rows and columns, such that neighbors are listed close to one another, then a matrix plot can be used to visualized clusters, or communities, of nodes.\n",
    "1. Arc plots\n",
    " - ![arc_plots][2]\n",
    " - Are a transformation of the node-link diagram layout, in which nodes are ordered along one axis of the plot, and edges are drawn using circular arcs from one node to another.\n",
    " - If the nodes are ordered according to some sortable rule, such as age in a social network of users, or otherwise grouped together, by geographic location in map for a transportation network, then it will be possible to visualized the relationship between connectivity and the sorted (or grouped) property.\n",
    "  - Arc plots are a good starting point for visualizing a network, as it forms the basis of the later plots that we'll take a look at.\n",
    "1. Circos plots\n",
    " - ![circo_plot][3]\n",
    " - Are a transformation of the Arc Plot, such that two ends of the Arc Plot are joined together into a circle.\n",
    " - Were originally designed for use in genomics, and you can think of them as an aesthetic and compact alternative to Arc Plots.\n",
    "- You will be using [nxviz][4] to plot the graphs.\n",
    "\n",
    "```python\n",
    "import nxviz as nv\n",
    "import matplotlib.pyplot as plt\n",
    "ap = nv.ArcPlot(G)\n",
    "ap.draw()\n",
    "plt.show()\n",
    "```\n",
    "\n",
    "\n",
    "\n",
    "  [1]: https://raw.githubusercontent.com/trenton3983/DataCamp/master/Images/2020-05-21_intro_to_network_analysis_in_python/matrix_plots.JPG\n",
    "  [2]: https://raw.githubusercontent.com/trenton3983/DataCamp/master/Images/2020-05-21_intro_to_network_analysis_in_python/arc_plots.JPG\n",
    "  [3]: https://raw.githubusercontent.com/trenton3983/DataCamp/master/Images/2020-05-21_intro_to_network_analysis_in_python/circo_plots.JPG\n",
    "  [4]: https://github.com/ericmjl/nxviz"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Visualizing using Matrix plots\n",
    "\n",
    "It is time to try your first \"fancy\" graph visualization method: a matrix plot. To do this, `nxviz` provides a `MatrixPlot` object.\n",
    "\n",
    "`nxviz` is a package for visualizing graphs in a rational fashion. Under the hood, the `MatrixPlo`t utilizes `nx.to_numpy_matrix(G)`, which returns the matrix form of the graph. Here, each node is one column and one row, and an edge between the two nodes is indicated by the value 1. In doing so, however, only the `weight` metadata is preserved; all other metadata is lost, as you'll verify using an `assert` statement.\n",
    "\n",
    "A corresponding `nx.from_numpy_matrix(A)` allows one to quickly create a graph from a NumPy matrix. The default graph type is `Graph()`; if you want to make it a `DiGraph()`, that has to be specified using the `create_using` keyword argument, e.g. (`nx.from_numpy_matrix(A, create_using=nx.DiGraph`)).\n",
    "\n",
    "One final note, `matplotlib.pyplot` and `networkx` have already been imported as `plt` and `nx`, respectively, and the graph `T` has been pre-loaded. For simplicity and speed, we have sub-sampled only 100 edges from the network.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Import `nxviz` as `nv`.\n",
    "- Plot the graph `T` as a matrix plot. To do this:\n",
    " - Create the `MatrixPlot` object called `m` using the `nv.MatrixPlot()` function with `T` passed in as an argument.\n",
    " - Draw the `m` to the screen using the `.draw()` method.\n",
    " - Display the plot using `plt.show()`.\n",
    "- Convert the graph to a matrix format, and then convert the graph back to the NetworkX form from the matrix as a directed graph.\n",
    "- Check that the `category` metadata field is lost from each node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = [(13829, 1386, {'date': date(2012, 3, 13)}), (3086, 669, {'date': date(2009, 3, 1)}), (3086, 3100, {'date': date(2013, 8, 10)}), (3086, 3117, {'date': date(2007, 12, 20)}), (4111, 4133, {'date': date(2007, 10, 28)}), (4111, 12582, {'date': date(2013, 6, 1)}), (6163, 7331, {'date': date(2013, 2, 3)}), (6163, 7336, {'date': date(2007, 9, 12)}), (6163, 6168, {'date': date(2008, 4, 2)}), (6163, 1326, {'date': date(2009, 2, 16)}), (4636, 4666, {'date': date(2012, 3, 20)}), (543, 12123, {'date': date(2014, 8, 12)}), (36, 24, {'date': date(2009, 4, 23)}), (12836, 12856, {'date': date(2014, 2, 21)}), (10790, 10854, {'date': date(2009, 8, 11)}), (9262, 9338, {'date': date(2007, 11, 11)}), (4160, 4161, {'date': date(2012, 4, 14)}), (4160, 3681, {'date': date(2013, 8, 10)}), (7746, 3396, {'date': date(2007, 2, 23)}), (7746, 543, {'date': date(2011, 7, 14)}), (7746, 5073, {'date': date(2012, 2, 25)}), (7746, 1130, {'date': date(2013, 8, 4)}), (7746, 3265, {'date': date(2008, 11, 8)}), (19013, 21248, {'date': date(2009, 3, 21)}), (19013, 21253, {'date': date(2007, 8, 17)}), (14916, 14930, {'date': date(2012, 4, 10)}), (5717, 5752, {'date': date(2009, 2, 2)}), (3159, 3176, {'date': date(2011, 8, 15)}), (3159, 3177, {'date': date(2008, 2, 1)}), (3159, 3193, {'date': date(2014, 1, 2)}), (1627, 1648, {'date': date(2011, 11, 7)}), (19550, 19570, {'date': date(2009, 11, 13)}), (5215, 5217, {'date': date(2011, 1, 7)}), (4198, 16203, {'date': date(2014, 12, 1)}), (3177, 3159, {'date': date(2010, 6, 2)}), (3177, 3176, {'date': date(2014, 11, 10)}), (1134, 2406, {'date': date(2011, 7, 10)}), (1134, 543, {'date': date(2011, 10, 20)}), (4206, 21962, {'date': date(2014, 4, 17)}), (6770, 2671, {'date': date(2010, 5, 18)}), (11384, 4955, {'date': date(2007, 2, 12)}), (11384, 2406, {'date': date(2007, 10, 13)}), (11384, 11402, {'date': date(2009, 11, 27)}), (10877, 10917, {'date': date(2014, 7, 17)}), (10877, 7886, {'date': date(2009, 1, 4)}), (10877, 36, {'date': date(2008, 10, 25)}), (10877, 10936, {'date': date(2008, 12, 26)}), (10877, 1326, {'date': date(2012, 1, 19)}), (10373, 1386, {'date': date(2011, 4, 21)}), (10373, 2501, {'date': date(2012, 8, 13)}), (3213, 3214, {'date': date(2008, 4, 19)}), (3213, 3265, {'date': date(2007, 8, 8)}), (3213, 3266, {'date': date(2009, 1, 4)}), (5626, 16654, {'date': date(2011, 3, 5)}), (20122, 20177, {'date': date(2014, 12, 21)}), (667, 669, {'date': date(2014, 2, 3)}), (667, 747, {'date': date(2008, 2, 23)}), (161, 18159, {'date': date(2014, 9, 22)}), (7331, 6163, {'date': date(2012, 10, 15)}), (7331, 6168, {'date': date(2012, 3, 17)}), (7331, 7606, {'date': date(2008, 11, 7)}), (7331, 24, {'date': date(2009, 9, 21)}), (7331, 36, {'date': date(2010, 5, 26)}), (10917, 10877, {'date': date(2011, 9, 7)}), (10917, 24, {'date': date(2014, 10, 16)}), (10917, 7886, {'date': date(2011, 7, 13)}), (10917, 36, {'date': date(2013, 8, 8)}), (10917, 1326, {'date': date(2009, 5, 23)}), (22184, 22188, {'date': date(2012, 11, 3)}), (6318, 6301, {'date': date(2011, 4, 3)}), (8367, 8421, {'date': date(2012, 7, 10)}), (21167, 3931, {'date': date(2012, 7, 9)}), (3265, 4955, {'date': date(2012, 6, 6)}), (3265, 4811, {'date': date(2014, 9, 18)}), (3265, 3266, {'date': date(2008, 9, 24)}), (3266, 4811, {'date': date(2007, 2, 16)}), (3266, 1926, {'date': date(2008, 3, 16)}), (3266, 3265, {'date': date(2014, 5, 25)}), (4291, 4306, {'date': date(2014, 9, 9)}), (4291, 4310, {'date': date(2007, 9, 11)}), (4811, 4955, {'date': date(2007, 4, 19)}), (4811, 3265, {'date': date(2013, 8, 23)}), (4811, 3266, {'date': date(2008, 8, 25)}), (7886, 10877, {'date': date(2012, 9, 5)}), (7886, 10917, {'date': date(2008, 9, 19)}), (7886, 24, {'date': date(2014, 8, 17)}), (7886, 36, {'date': date(2012, 9, 21)}), (7886, 1326, {'date': date(2012, 3, 23)}), (6863, 14981, {'date': date(2012, 8, 7)}), (13012, 13017, {'date': date(2012, 3, 4)}), (16597, 24, {'date': date(2012, 5, 2)}), (16597, 36, {'date': date(2011, 4, 19)}), (16597, 16610, {'date': date(2011, 11, 11)}), (12507, 12523, {'date': date(2012, 3, 11)}), (16618, 16619, {'date': date(2013, 3, 3)}), (13036, 15161, {'date': date(2012, 4, 23)}), (3826, 669, {'date': date(2014, 11, 9)}), (3826, 3100, {'date': date(2009, 2, 24)}), (3826, 3860, {'date': date(2013, 7, 27)}), (3826, 3681, {'date': date(2013, 2, 14)}), (7410, 7437, {'date': date(2012, 5, 2)}), (15092, 2148, {'date': date(2014, 11, 11)}), (15092, 20816, {'date': date(2009, 4, 8)}), (2820, 2826, {'date': date(2011, 10, 1)}), (2820, 2871, {'date': date(2010, 3, 26)}), (2311, 2371, {'date': date(2008, 8, 26)}), (11020, 11042, {'date': date(2008, 5, 12)}), (13070, 13079, {'date': date(2009, 10, 15)}), (20755, 24, {'date': date(2010, 11, 26)}), (20755, 1326, {'date': date(2014, 5, 2)}), (20756, 669, {'date': date(2012, 9, 7)}), (20756, 3100, {'date': date(2013, 3, 17)}), (20756, 3681, {'date': date(2010, 12, 9)}), (14613, 14617, {'date': date(2009, 6, 2)}), (10004, 10030, {'date': date(2008, 3, 1)}), (10004, 10111, {'date': date(2011, 7, 15)}), (4892, 1130, {'date': date(2011, 12, 10)}), (4892, 4947, {'date': date(2012, 3, 6)}), (2871, 15372, {'date': date(2014, 4, 27)}), (6968, 669, {'date': date(2010, 2, 6)}), (6968, 1386, {'date': date(2012, 9, 20)}), (6968, 4133, {'date': date(2012, 9, 22)}), (3385, 3396, {'date': date(2008, 3, 4)}), (8001, 23190, {'date': date(2008, 6, 26)}), (19787, 13581, {'date': date(2012, 4, 3)}), (21325, 21371, {'date': date(2009, 8, 2)}), (16720, 16734, {'date': date(2007, 10, 26)}), (16720, 16739, {'date': date(2008, 10, 24)}), (12119, 24, {'date': date(2013, 6, 1)}), (12119, 36, {'date': date(2007, 5, 1)}), (22872, 22918, {'date': date(2014, 7, 15)}), (7519, 16041, {'date': date(2012, 7, 8)}), (12640, 18082, {'date': date(2007, 4, 20)}), (12640, 18086, {'date': date(2008, 7, 8)}), (5987, 4957, {'date': date(2010, 12, 4)}), (5987, 492, {'date': date(2009, 6, 25)}), (19316, 19344, {'date': date(2013, 3, 15)}), (19316, 2501, {'date': date(2011, 11, 15)}), (13690, 4955, {'date': date(2014, 4, 5)}), (12162, 15560, {'date': date(2011, 1, 4)}), (2443, 3564, {'date': date(2014, 1, 9)}), (401, 492, {'date': date(2010, 11, 25)}), (401, 502, {'date': date(2013, 6, 27)}), (9106, 9107, {'date': date(2012, 5, 4)}), (8598, 8616, {'date': date(2011, 2, 6)}), (21919, 4161, {'date': date(2007, 7, 18)}), (21919, 669, {'date': date(2011, 12, 12)}), (21919, 3100, {'date': date(2012, 10, 15)}), (21919, 3681, {'date': date(2011, 1, 14)}), (10143, 4306, {'date': date(2009, 5, 26)}), (4517, 6414, {'date': date(2008, 7, 15)}), (20906, 2406, {'date': date(2012, 9, 5)}), (20906, 492, {'date': date(2013, 8, 12)}), (6059, 20368, {'date': date(2008, 11, 20)}), (2501, 1386, {'date': date(2009, 5, 1)}), (2501, 10373, {'date': date(2012, 7, 15)}), (13257, 13286, {'date': date(2008, 11, 4)}), (1484, 1492, {'date': date(2008, 6, 5)}), (1484, 1499, {'date': date(2013, 8, 9)}), (1996, 6038, {'date': date(2012, 7, 28)}), (20947, 669, {'date': date(2011, 7, 19)}), (20947, 3100, {'date': date(2010, 11, 23)}), (20947, 3681, {'date': date(2008, 6, 20)}), (5590, 5601, {'date': date(2012, 8, 17)}), (5590, 5626, {'date': date(2013, 8, 18)}), (18917, 19012, {'date': date(2013, 12, 15)}), (18917, 19013, {'date': date(2014, 1, 17)}), (10730, 24, {'date': date(2010, 1, 21)}), (10730, 36, {'date': date(2014, 1, 11)}), (10730, 1326, {'date': date(2008, 11, 4)}), (23024, 669, {'date': date(2010, 6, 15)}), (23024, 3100, {'date': date(2012, 6, 1)}), (23024, 23091, {'date': date(2011, 5, 20)}), (5109, 5112, {'date': date(2007, 5, 10)}), (13306, 13334, {'date': date(2014, 5, 18)})]\n",
    "attr = {13829: {'category': 'D', 'occupation': 'celebrity'}, 15372: {'category': 'D', 'occupation': 'celebrity'}, 3086: {'category': 'P', 'occupation': 'scientist'}, 4111: {'category': 'D', 'occupation': 'scientist'}, 6163: {'category': 'P', 'occupation': 'scientist'}, 13334: {'category': 'P', 'occupation': 'scientist'}, 6168: {'category': 'P', 'occupation': 'celebrity'}, 24: {'category': 'P', 'occupation': 'politician'}, 3100: {'category': 'D', 'occupation': 'scientist'}, 4636: {'category': 'D', 'occupation': 'celebrity'}, 543: {'category': 'D', 'occupation': 'politician'}, 36: {'category': 'D', 'occupation': 'scientist'}, 12836: {'category': 'I', 'occupation': 'celebrity'}, 4133: {'category': 'D', 'occupation': 'scientist'}, 10790: {'category': 'D', 'occupation': 'scientist'}, 3117: {'category': 'P', 'occupation': 'politician'}, 9262: {'category': 'I', 'occupation': 'scientist'}, 23091: {'category': 'P', 'occupation': 'celebrity'}, 12856: {'category': 'D', 'occupation': 'politician'}, 4666: {'category': 'P', 'occupation': 'politician'}, 4160: {'category': 'P', 'occupation': 'politician'}, 4161: {'category': 'I', 'occupation': 'politician'}, 7746: {'category': 'P', 'occupation': 'scientist'}, 19012: {'category': 'D', 'occupation': 'politician'}, 19013: {'category': 'I', 'occupation': 'politician'}, 14916: {'category': 'I', 'occupation': 'politician'}, 14930: {'category': 'P', 'occupation': 'celebrity'}, 5717: {'category': 'P', 'occupation': 'politician'}, 3159: {'category': 'I', 'occupation': 'scientist'}, 1627: {'category': 'I', 'occupation': 'scientist'}, 19550: {'category': 'D', 'occupation': 'politician'}, 5215: {'category': 'P', 'occupation': 'politician'}, 5217: {'category': 'D', 'occupation': 'scientist'}, 3681: {'category': 'I', 'occupation': 'politician'}, 2148: {'category': 'D', 'occupation': 'politician'}, 4198: {'category': 'D', 'occupation': 'celebrity'}, 10854: {'category': 'D', 'occupation': 'politician'}, 3176: {'category': 'D', 'occupation': 'scientist'}, 3177: {'category': 'I', 'occupation': 'scientist'}, 1130: {'category': 'I', 'occupation': 'celebrity'}, 1134: {'category': 'P', 'occupation': 'scientist'}, 4206: {'category': 'I', 'occupation': 'scientist'}, 2671: {'category': 'P', 'occupation': 'scientist'}, 1648: {'category': 'P', 'occupation': 'politician'}, 19570: {'category': 'P', 'occupation': 'scientist'}, 6770: {'category': 'D', 'occupation': 'celebrity'}, 5752: {'category': 'D', 'occupation': 'scientist'}, 11384: {'category': 'D', 'occupation': 'politician'}, 3193: {'category': 'P', 'occupation': 'politician'}, 9338: {'category': 'I', 'occupation': 'politician'}, 10877: {'category': 'P', 'occupation': 'celebrity'}, 10373: {'category': 'I', 'occupation': 'politician'}, 14981: {'category': 'P', 'occupation': 'celebrity'}, 11402: {'category': 'I', 'occupation': 'politician'}, 3213: {'category': 'D', 'occupation': 'politician'}, 3214: {'category': 'P', 'occupation': 'celebrity'}, 5626: {'category': 'P', 'occupation': 'politician'}, 23190: {'category': 'P', 'occupation': 'celebrity'}, 20122: {'category': 'D', 'occupation': 'politician'}, 667: {'category': 'P', 'occupation': 'politician'}, 6301: {'category': 'I', 'occupation': 'scientist'}, 669: {'category': 'I', 'occupation': 'celebrity'}, 161: {'category': 'D', 'occupation': 'politician'}, 18082: {'category': 'I', 'occupation': 'celebrity'}, 7331: {'category': 'I', 'occupation': 'celebrity'}, 10917: {'category': 'P', 'occupation': 'scientist'}, 18086: {'category': 'D', 'occupation': 'scientist'}, 22184: {'category': 'P', 'occupation': 'scientist'}, 7336: {'category': 'D', 'occupation': 'scientist'}, 16041: {'category': 'P', 'occupation': 'scientist'}, 22188: {'category': 'I', 'occupation': 'scientist'}, 6318: {'category': 'P', 'occupation': 'politician'}, 8367: {'category': 'I', 'occupation': 'politician'}, 21167: {'category': 'D', 'occupation': 'celebrity'}, 10936: {'category': 'P', 'occupation': 'scientist'}, 3265: {'category': 'I', 'occupation': 'celebrity'}, 3266: {'category': 'P', 'occupation': 'politician'}, 4291: {'category': 'P', 'occupation': 'politician'}, 15560: {'category': 'P', 'occupation': 'celebrity'}, 4811: {'category': 'P', 'occupation': 'politician'}, 7886: {'category': 'P', 'occupation': 'politician'}, 6863: {'category': 'I', 'occupation': 'scientist'}, 20177: {'category': 'P', 'occupation': 'scientist'}, 4306: {'category': 'P', 'occupation': 'scientist'}, 13012: {'category': 'D', 'occupation': 'celebrity'}, 16597: {'category': 'P', 'occupation': 'celebrity'}, 4310: {'category': 'D', 'occupation': 'scientist'}, 13017: {'category': 'I', 'occupation': 'politician'}, 12507: {'category': 'I', 'occupation': 'politician'}, 16610: {'category': 'I', 'occupation': 'celebrity'}, 8421: {'category': 'I', 'occupation': 'politician'}, 16618: {'category': 'D', 'occupation': 'politician'}, 16619: {'category': 'I', 'occupation': 'celebrity'}, 13036: {'category': 'D', 'occupation': 'politician'}, 12523: {'category': 'P', 'occupation': 'politician'}, 747: {'category': 'D', 'occupation': 'politician'}, 18159: {'category': 'P', 'occupation': 'celebrity'}, 3826: {'category': 'P', 'occupation': 'politician'}, 7410: {'category': 'D', 'occupation': 'scientist'}, 15092: {'category': 'I', 'occupation': 'scientist'}, 21248: {'category': 'I', 'occupation': 'politician'}, 2820: {'category': 'I', 'occupation': 'celebrity'}, 21253: {'category': 'P', 'occupation': 'celebrity'}, 2311: {'category': 'I', 'occupation': 'politician'}, 2826: {'category': 'D', 'occupation': 'celebrity'}, 11020: {'category': 'D', 'occupation': 'politician'}, 7437: {'category': 'P', 'occupation': 'celebrity'}, 16654: {'category': 'I', 'occupation': 'scientist'}, 6414: {'category': 'D', 'occupation': 'scientist'}, 13070: {'category': 'I', 'occupation': 'politician'}, 13581: {'category': 'D', 'occupation': 'politician'}, 20755: {'category': 'D', 'occupation': 'celebrity'}, 20756: {'category': 'I', 'occupation': 'scientist'}, 14613: {'category': 'I', 'occupation': 'celebrity'}, 10004: {'category': 'I', 'occupation': 'politician'}, 3860: {'category': 'D', 'occupation': 'celebrity'}, 13079: {'category': 'D', 'occupation': 'celebrity'}, 14617: {'category': 'P', 'occupation': 'celebrity'}, 4892: {'category': 'P', 'occupation': 'celebrity'}, 11042: {'category': 'I', 'occupation': 'celebrity'}, 12582: {'category': 'P', 'occupation': 'politician'}, 1326: {'category': 'D', 'occupation': 'scientist'}, 10030: {'category': 'I', 'occupation': 'celebrity'}, 2871: {'category': 'P', 'occupation': 'scientist'}, 6968: {'category': 'P', 'occupation': 'celebrity'}, 3385: {'category': 'D', 'occupation': 'scientist'}, 15161: {'category': 'D', 'occupation': 'scientist'}, 8001: {'category': 'P', 'occupation': 'celebrity'}, 2371: {'category': 'D', 'occupation': 'scientist'}, 3396: {'category': 'P', 'occupation': 'scientist'}, 16203: {'category': 'D', 'occupation': 'politician'}, 19787: {'category': 'D', 'occupation': 'politician'}, 21325: {'category': 'P', 'occupation': 'scientist'}, 20816: {'category': 'I', 'occupation': 'scientist'}, 16720: {'category': 'I', 'occupation': 'scientist'}, 4947: {'category': 'I', 'occupation': 'celebrity'}, 12119: {'category': 'D', 'occupation': 'politician'}, 22872: {'category': 'I', 'occupation': 'politician'}, 12123: {'category': 'D', 'occupation': 'celebrity'}, 4955: {'category': 'P', 'occupation': 'celebrity'}, 4957: {'category': 'D', 'occupation': 'celebrity'}, 16734: {'category': 'D', 'occupation': 'politician'}, 7519: {'category': 'I', 'occupation': 'politician'}, 12640: {'category': 'P', 'occupation': 'celebrity'}, 3931: {'category': 'I', 'occupation': 'celebrity'}, 5987: {'category': 'D', 'occupation': 'scientist'}, 16739: {'category': 'I', 'occupation': 'celebrity'}, 2406: {'category': 'I', 'occupation': 'scientist'}, 1386: {'category': 'I', 'occupation': 'politician'}, 19316: {'category': 'I', 'occupation': 'politician'}, 13690: {'category': 'I', 'occupation': 'celebrity'}, 21371: {'category': 'P', 'occupation': 'scientist'}, 10111: {'category': 'I', 'occupation': 'celebrity'}, 12162: {'category': 'I', 'occupation': 'celebrity'}, 22918: {'category': 'I', 'occupation': 'celebrity'}, 1926: {'category': 'D', 'occupation': 'celebrity'}, 2443: {'category': 'I', 'occupation': 'scientist'}, 20368: {'category': 'I', 'occupation': 'politician'}, 19344: {'category': 'D', 'occupation': 'politician'}, 401: {'category': 'P', 'occupation': 'celebrity'}, 9106: {'category': 'P', 'occupation': 'scientist'}, 9107: {'category': 'D', 'occupation': 'celebrity'}, 6038: {'category': 'I', 'occupation': 'celebrity'}, 8598: {'category': 'P', 'occupation': 'politician'}, 21919: {'category': 'I', 'occupation': 'celebrity'}, 10143: {'category': 'P', 'occupation': 'celebrity'}, 4517: {'category': 'D', 'occupation': 'celebrity'}, 8616: {'category': 'D', 'occupation': 'celebrity'}, 20906: {'category': 'D', 'occupation': 'celebrity'}, 6059: {'category': 'D', 'occupation': 'scientist'}, 7606: {'category': 'P', 'occupation': 'scientist'}, 2501: {'category': 'P', 'occupation': 'scientist'}, 13257: {'category': 'D', 'occupation': 'celebrity'}, 21962: {'category': 'D', 'occupation': 'politician'}, 1484: {'category': 'I', 'occupation': 'politician'}, 1996: {'category': 'D', 'occupation': 'celebrity'}, 5073: {'category': 'P', 'occupation': 'celebrity'}, 20947: {'category': 'I', 'occupation': 'celebrity'}, 1492: {'category': 'D', 'occupation': 'celebrity'}, 5590: {'category': 'I', 'occupation': 'politician'}, 1499: {'category': 'P', 'occupation': 'celebrity'}, 5601: {'category': 'P', 'occupation': 'scientist'}, 18917: {'category': 'D', 'occupation': 'celebrity'}, 13286: {'category': 'I', 'occupation': 'scientist'}, 10730: {'category': 'D', 'occupation': 'celebrity'}, 492: {'category': 'I', 'occupation': 'politician'}, 3564: {'category': 'P', 'occupation': 'scientist'}, 23024: {'category': 'P', 'occupation': 'politician'}, 5109: {'category': 'I', 'occupation': 'politician'}, 502: {'category': 'P', 'occupation': 'scientist'}, 5112: {'category': 'I', 'occupation': 'celebrity'}, 13306: {'category': 'D', 'occupation': 'scientist'}}\n",
    "t_131 = nx.DiGraph()\n",
    "t_131.add_nodes_from(attr)\n",
    "t_131.add_edges_from(data)\n",
    "nx.set_node_attributes(t_131, attr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create the MatrixPlot object: m\n",
    "plt.figure(figsize=(10, 10))\n",
    "m = nv.matrix(t_131)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Convert T to a matrix format: A\n",
    "A = nx.to_numpy_array(t_131)\n",
    "\n",
    "# Convert A back to the NetworkX form as a directed graph: T_conv\n",
    "T_conv = nx.from_numpy_array(A, create_using=nx.DiGraph())\n",
    "\n",
    "# Check that the `category` metadata field is lost from each node\n",
    "for n, d in T_conv.nodes(data=True):\n",
    "    assert 'category' not in d.keys()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Visualizing using Circos plots\n",
    "\n",
    "Circos plots are a rational, non-cluttered way of visualizing graph data, in which nodes are ordered around the circumference in some fashion, and the edges are drawn within the circle that results, giving a beautiful as well as informative visualization about the structure of the network.\n",
    "\n",
    "In this exercise, you'll continue getting practice with the nxviz API, this time with the `CircosPlot` object. `matplotlib.pyplot` has been imported for you as `plt`.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Import `CircosPlot` from `nxviz`.\n",
    "- Plot the Twitter network `T` as a Circos plot without any styling. Use the `CircosPlot()` function to do this. Don't forget to draw it to the screen using `.draw()` and then display it using `plt.show()`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create the CircosPlot object: c\n",
    "plt.figure(figsize=(10, 10))\n",
    "ax = nv.circos(t_131)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Visualizing using Arc plots\n",
    "\n",
    "Following on what you've learned about the nxviz API, now try making an ArcPlot of the network. Two keyword arguments that you will try here are `node_order='keyX'` and `node_color='keyX'`, in which you specify a key in the node metadata dictionary to color and order the nodes by.\n",
    "\n",
    "`matplotlib.pyplot` has been imported for you as `plt`.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Import `ArcPlot` from `nxviz`.\n",
    "- Create an un-customized ArcPlot of `T`. To do this, use the `ArcPlot()` function with just `T` as the argument.\n",
    "- Create another ArcPlot of `T` in which the nodes are ordered and colored by the `'category'` keyword. You'll have to specify the `node_order` and `node_color` parameters to do this. For both plots, be sure to draw them to the screen and display them with `plt.show()`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create the un-customized ArcPlot object: a\n",
    "plt.figure(figsize=(10, 10))\n",
    "a = nv.arc(t_131)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create the customized ArcPlot object: a2\n",
    "plt.figure(figsize=(10, 10))\n",
    "ax = nv.arc(t_131, node_color_by='category', group_by='category')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Notice the node coloring in the customized ArcPlot compared to the uncustomized version. In the customized ArcPlot, the nodes in each of the categories - `'I'`, `'D'`, and `'P'` - have their own color. If it's difficult to see on your screen, you can expand the plot into a new window by clicking on the pop-out icon on the top-left next to 'Plots'.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Important nodes\n",
    "\n",
    "You'll learn about ways to identify nodes that are important in a network. In doing so, you'll be introduced to more advanced concepts in network analysis as well as the basics of path-finding algorithms. The chapter concludes with a deep dive into the Twitter network dataset which will reinforce the concepts you've learned, such as degree centrality and betweenness centrality."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Degree Centrality\n",
    "\n",
    "- How to determine which nodes are important\n",
    "- Which center node might be more important?\n",
    " - ![star_graph][1]\n",
    " - The center node of the left graph is more important because it is connected to more nodes.\n",
    " - Being connected to other nodes means other nodes are considered a neighbor of that node.\n",
    "- From the concept of neighbors, we can now introduce the concept of _degree centrality_\n",
    "1. Degree centrality\n",
    " - This is one of many metrics we can use to evaluate the importance of a node, and is simply defined as the number of neighbors that a node has divided by the total number of neighbors that the node could possible have: $\\frac{\\text{Number of Neighbors I Have}}{\\text{Number of Neighbors I could Possibly Have}}$\n",
    " - There are two scenarios possible here:\n",
    "       - if self-loops are allowed, such as in a network mapping of all bike trips in a bike sharing system, then the number of neighbors that I could possibly have, is every single node in the graph, including myself.\n",
    "       - if self-loops are not allowed, such as in the Twitter social network, where, by definition, my account cannot follow itself, the the number of neighbors I could possibly have is every other node in the graph, excluding myself.\n",
    " - In real life, example of nodes in a graph that have high degree centrality might be:\n",
    "       - Twitter broadcasters, that is, users that are followed by many other users\n",
    "       - Airport transportation hubs, such as New York, London or Tokyo\n",
    "       - Disease super-spreaders, who are the individuals that epidemiologists would want to track down to help stop the spread of a disease\n",
    "1. Betweenness centrality\n",
    "\n",
    "### Number of Neighbors\n",
    "\n",
    "```python\n",
    "G.edges()\n",
    ">>> [(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9)]\n",
    "\n",
    "G.neighbors(1)\n",
    ">>> [2, 3, 4, 5, 6, 7, 8, 9]\n",
    "\n",
    "G.neighbors(8)\n",
    ">>> [1]\n",
    "\n",
    "G.neighbors(10)\n",
    ">>> NetworkXError: The node 10 is not in the graph.\n",
    "```\n",
    "\n",
    "### Degree Centrality\n",
    "\n",
    "- self-loops are not considered\n",
    "\n",
    "```python\n",
    "nx.degree_centrality(G)\n",
    ">>> {1: 1.0,\n",
    "     2: 0.125,\n",
    "     3: 0.125,\n",
    "     4: 0.125,\n",
    "     5: 0.125,\n",
    "     6: 0.125,\n",
    "     7: 0.125,\n",
    "     8: 0.125,\n",
    "     9: 0.125}\n",
    "```\n",
    "\n",
    "  [1]: https://raw.githubusercontent.com/trenton3983/DataCamp/master/Images/2020-05-21_intro_to_network_analysis_in_python/star_graphs.JPG"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Compute number of neighbors for each node\n",
    "\n",
    "How do you evaluate whether a node is an important one or not? There are a few ways to do so, and here, you're going to look at one metric: the number of neighbors that a node has.\n",
    "\n",
    "Every NetworkX graph `G` exposes a `.neighbors(n)` method that returns a list of nodes that are the neighbors of the node `n`. To begin, use this method in the IPython Shell on the Twitter network `T` to get the neighbors of of node `1`. This will get you familiar with how the function works. Then, your job in this exercise is to write a function that returns all nodes that have `m` neighbors.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Write a function called `nodes_with_m_nbrs()` that has two parameters - `G` and `m` - and returns all nodes that have `m` neighbors. To do this:\n",
    " - Iterate over all nodes in `G` (**not** including the metadata).\n",
    " - Use the `len()` and `list()` functions together with the `.neighbors()` method to calculate the total number of neighbors that node `n` in graph `G` has.\n",
    "   - If the number of neighbors of node `n` is equal to `m`, add `n` to the set `nodes` using the `.add()` method.\n",
    " - After iterating over all the nodes in `G`, return the set `nodes`.\n",
    "- Use your `nodes_with_m_nbrs()` function to retrieve all the nodes that have 6 neighbors in the graph `T`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define nodes_with_m_nbrs()\n",
    "def nodes_with_m_nbrs(G, m):\n",
    "    \"\"\"\n",
    "    Returns all nodes in graph G that have m neighbors.\n",
    "    \"\"\"\n",
    "    nodes = set()\n",
    "\n",
    "    # Iterate over all nodes in G\n",
    "    for n in G.nodes():\n",
    "\n",
    "        # Check if the number of neighbors of n matches m\n",
    "        if len(list(G.neighbors(n))) == m:\n",
    "\n",
    "            # Add the node n to the set\n",
    "            nodes.add(n)\n",
    "\n",
    "    # Return the nodes with m neighbors\n",
    "    return nodes\n",
    "\n",
    "# Compute and print all nodes in T that have 6 neighbors\n",
    "six_nbrs = nodes_with_m_nbrs(T, 6)\n",
    "print(six_nbrs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**The number of neighbors a node has is one way to identify important nodes. It looks like 25 nodes in graph `T` have 6 neighbors.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Compute degree distribution\n",
    "\n",
    "The number of neighbors that a node has is called its \"degree\", and it's possible to compute the degree distribution across the entire graph. In this exercise, your job is to compute the degree distribution across `T`.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Use a list comprehension along with the `.neighbors(n)` method to get the degree of every node. The result should be a list of integers.\n",
    " - Use `n` as your _iterator variable_.\n",
    " - The _output expression_ of your list comprehension should be the number of neighbors that node `n` has - that is, its degree. Use the `len()` and `list()` functions together with the `.neighbors()` method to compute this.\n",
    " - The _iterable_ in your list comprehension is all the nodes in `T`, accessed using the `.nodes()` method.\n",
    "- Print the degrees."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "degrees = [len(list(T.neighbors(n))) for n in T.nodes()]\n",
    "degrees[:20]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Degree centrality distribution\n",
    "\n",
    "The degree of a node is the number of neighbors that it has. The degree centrality is the number of neighbors divided by all possible neighbors that it could have. Depending on whether self-loops are allowed, the set of possible neighbors a node could have could also include the node itself.\n",
    "\n",
    "The `nx.degree_centrality(G)` function returns a dictionary, where the keys are the nodes and the values are their degree centrality values.\n",
    "\n",
    "The degree distribution `degrees` you computed in the previous exercise using the list comprehension has been pre-loaded.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Compute the degree centrality of the Twitter network `T`.\n",
    "- Using `plt.hist()`, plot a histogram of the degree centrality distribution of `T`. This can be accessed using `list(deg_cent.values())`.\n",
    "- Plot a histogram of the degree distribution `degrees` of `T`. This is the same list you computed in the last exercise.\n",
    "- Create a scatter plot with `degrees` on the x-axis and the degree centrality distribution `list(deg_cent.values())` on the y-axis."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Compute the degree centrality of the Twitter network: deg_cent\n",
    "deg_cent = nx.degree_centrality(T)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Plot a histogram of the degree centrality distribution of the graph.\n",
    "plt.figure()\n",
    "plt.hist(list(deg_cent.values()))\n",
    "plt.show()\n",
    "\n",
    "# Plot a histogram of the degree distribution of the graph\n",
    "plt.figure()\n",
    "plt.hist(degrees)\n",
    "plt.show()\n",
    "\n",
    "# Plot a scatter plot of the centrality distribution and the degree distribution\n",
    "plt.figure()\n",
    "plt.scatter(degrees, list(deg_cent.values()))\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Given the similarities of their histograms, it should not surprise you to see a perfect correlation between the centrality distribution and the degree distribution.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graph Algorithms\n",
    "\n",
    "### Finding Paths\n",
    "- Pathfinding is important for:\n",
    " - Optimization:\n",
    "   - finding the shortest transportation path between two nodes\n",
    "   - shortest transport paths\n",
    " - Modeling:\n",
    "   - the spread of things\n",
    "   - disease spread\n",
    "   - information spread in a social network\n",
    "- How do we find out if there's a path between two nodes?\n",
    "- If there's a path, how do we find out what the shortest path is?\n",
    "- Algorithm: Breadth-first search\n",
    "- Developed in the 1950s as a way of finding the shortest path out of a maze.\n",
    "- Given the following network comprised of 11 nodes, and we want to find the shortest path between the yellow and red nodes.\n",
    "- If we start at the yellow node, we first ask for the yellow node's neighbors.\n",
    "- We then ask if the destination node is present in the set of yellow node's neighbors\n",
    "- If not, we continue on.\n",
    "- Going out a 2nd degree of separation, we ask for the neighbors of our neighbors.\n",
    "- The destination node is still not present, so we continue on.\n",
    "- On our 3rd degree of separation out, we see that the destination node is present.\n",
    "- At this point, we can stop and ignore the next degree of separation.\n",
    "- Note there was one other path possible, but it was longer.\n",
    "- As such, with the breadth-first search algorithm, we have achieved our goal of finding the _shortest_ path between the pair of nodes.\n",
    "- ![bfs][1]\n",
    "- If we do `G.neighbors(1)`, we get back a list containing the nodes that are neighbors of `1`\n",
    "- Let's go one degree out, to the first node in the list of node `1`'s neighbors, which is node `10`.\n",
    "- Let's check the neighbors of `10`: note that we have `1`, which is correct, and then `19`, and then a whole slew of other nodes.\n",
    "- Since `19`, our destination node, is present in the neighbors of node `10`, we can stop there.\n",
    "- If `19` wasn't there, we would go on to check the neighbors of node `5`, which was the next node in the list of node `1`'s neighbors.\n",
    "\n",
    "```python\n",
    "G\n",
    ">>> <networkx.classes.graph.Graph at 0x10cc08828>\n",
    "\n",
    "len(G.edges())\n",
    ">>> 57\n",
    "\n",
    "len(G.nodes())\n",
    ">>> 20\n",
    "\n",
    "list(G.neighbors(1))\n",
    ">>> [10, 5, 14, 7]\n",
    "\n",
    "list(G.neighborys(10))\n",
    ">>> [1, 19, 5, 17, 8, 9, 13, 14]\n",
    "```\n",
    "\n",
    "- This was a manual check, but in the exercises, you'll be implementing an automatic version of the breadth-first search algorithm.\n",
    "\n",
    "  [1]: https://raw.githubusercontent.com/trenton3983/DataCamp/master/Images/2020-05-21_intro_to_network_analysis_in_python/bfs.JPG"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Shortest Path I\n",
    "\n",
    "You can leverage what you know about finding neighbors to try finding paths in a network. One algorithm for path-finding between two nodes is the \"breadth-first search\" (BFS) algorithm. In a BFS algorithm, you start from a particular node and iteratively search through its neighbors and neighbors' neighbors until you find the destination node.\n",
    "\n",
    "Pathfinding algorithms are important because they provide another way of assessing node importance; you'll see this in a later exercise.\n",
    "\n",
    "In this set of 3 exercises, you're going to build up slowly to get to the final BFS algorithm. The problem has been broken into 3 parts that, if you complete in succession, will get you to a first pass implementation of the BFS algorithm.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Create a function called `path_exists()` that has 3 parameters - `G`, `node1`, and `node2` - and returns whether or not a path exists between the two nodes.\n",
    "- Initialize the queue of nodes to visit with the first node, `node1`. `queue` should be a list.\n",
    "- Iterate over the nodes in `queue`.\n",
    "- Get the neighbors of the node using the `.neighbors()` method of the graph `G`.\n",
    "- Check to see if the destination node `node2` is in the set of `neighbors`. If it is, return `True`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define path_exists()\n",
    "def path_exists(G, node1, node2):\n",
    "    \"\"\"\n",
    "    This function checks whether a path exists between two nodes (node1, node2) in graph G.\n",
    "    \"\"\"\n",
    "    visited_nodes = set()\n",
    "\n",
    "    # Initialize the queue of nodes to visit with the first node: queue\n",
    "    queue = [node1]\n",
    "\n",
    "    # Iterate over the nodes in the queue\n",
    "    for node in queue:\n",
    "\n",
    "        # Get neighbors of the node\n",
    "        neighbors = G.neighbors(node)\n",
    "\n",
    "        # Check to see if the destination node is in the set of neighbors\n",
    "        if node2 in neighbors:\n",
    "            print('Path exists between nodes {0} and {1}'.format(node1, node2))\n",
    "            return True\n",
    "            break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Shortest Path II\n",
    "\n",
    "Now that you've got the code for checking whether the destination node is present in neighbors, next up, you're going to extend the same function to write the code for the condition where the destination node is not present in the neighbors.\n",
    "\n",
    "All the code you need to write is in the `else` condition; that is, if `node2` is not in `neighbors`.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Using the `.add()` method, add the current node `node` to the set `visited_nodes` to keep track of what nodes have already been visited.\n",
    "- Add the _neighbors_ of the current node `node` that have not yet been visited to `queue`. To do this, you'll need to use the `.extend()` method of `queue` together with a list comprehension. The `.extend()` method appends all the items in a given list.\n",
    " - The _output expression_ and _iterator variable_ of the list comprehension are both `n`. The iterable is the list `neighbors`, and the conditional is if `n` is not in the visited nodes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def path_exists(G, node1, node2):\n",
    "    \"\"\"\n",
    "    This function checks whether a path exists between two nodes (node1, node2) in graph G.\n",
    "    \"\"\"\n",
    "    visited_nodes = set()\n",
    "    queue = [node1]\n",
    "\n",
    "    for node in queue:\n",
    "        neighbors = G.neighbors(node)\n",
    "        if node2 in neighbors:\n",
    "            print('Path exists between nodes {0} and {1}'.format(node1, node2))\n",
    "            return True\n",
    "          \n",
    "        else:\n",
    "            # Add current node to visited nodes\n",
    "            visited_nodes.add(node)\n",
    "\n",
    "            # Add neighbors of current node that have not yet been visited\n",
    "            queue.extend([n for n in neighbors if n not in visited_nodes])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Shortest Path III\n",
    "\n",
    "This is the final exercise of this trio! You're now going to complete the problem by writing the code that returns `False` if there's no path between two nodes.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Check to see if the queue has been emptied. You can do this by inspecting the last element of queue with `[-1]`.\n",
    "- Place the appropriate return statement for indicating whether there's a path between these two nodes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def path_exists(G, node1, node2):\n",
    "    \"\"\"\n",
    "    This function checks whether a path exists between two nodes (node1, node2) in graph G.\n",
    "    \"\"\"\n",
    "    visited_nodes = set()\n",
    "    queue = [node1]\n",
    "\n",
    "    for node in queue:\n",
    "        neighbors = G.neighbors(node)\n",
    "        if node2 in neighbors:\n",
    "            print('Path exists between nodes {0} and {1}'.format(node1, node2))\n",
    "            return True\n",
    "            break\n",
    "\n",
    "        else:\n",
    "            visited_nodes.add(node)\n",
    "            queue.extend([n for n in neighbors if n not in visited_nodes])\n",
    "\n",
    "        # Check to see if the final element of the queue has been reached\n",
    "        if node == queue[-1]:\n",
    "            print('Path does not exist between nodes {0} and {1}'.format(node1, node2))\n",
    "\n",
    "            # Place the appropriate return statement\n",
    "            return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Betweenness Centrality\n",
    "\n",
    "- Let's revisit our notions of what it means to be an _important node_, but leveraging what we know about paths\n",
    "- We're now going to learn about betweenness centrality, but before we talk about that, we need to extend our knowledge with one key concept - all shortest paths\n",
    "\n",
    "### All Shortest Paths\n",
    "- In the previous section, we learned about how to find the shortest path between any pair of nodes, using the breadth-first search algorithm.\n",
    "- Imagine now we used the BFS to find every shortest path between every pair of nodes.\n",
    "- What we would get back is the **set of _all shortest paths_** in a graph.\n",
    "- In other word, _all shortest paths_ are the set of paths in a graph, such that **each path is the shortest path between a given pair of nodes**, done **for all pairs of nodes**.\n",
    "\n",
    "### Betweenness Centrality\n",
    "- Definition: $\\frac{\\text{num. shortest paths through node}}{\\text{all possible shortest paths}}$\n",
    " - The number of shortest paths in a graph that pass through a node, divided by the number of shortest paths that exist between every pair of nodes in a graph.\n",
    " - This metric captures a different view of importance - in essence, it captures bottleneck nodes in a graph, rather that highly connected nodes; this will become much clearer as we go on.\n",
    "- Where might betweenness centrality be useful?\n",
    "- Application:\n",
    " - One example would be individuals that bridge between to communities\n",
    "   - An individual bridging liberal-leaning and conservative-leaning Twitter users\n",
    " - Alternatively, consider the Internet, where there are crucial links that bridge two network of computers.\n",
    " - If we removed those crucial nodes in the Internet, then information will not flow (or at least not as easily) between subnetworks.\n",
    " \n",
    "### Examples\n",
    "- Singapore: Raffles & Jurong East\n",
    " - Let's look at the Singapore subway system to make this more concrete\n",
    " - Take a look at two sets of stations that have been circled with purple.\n",
    " - In the south, there's a cluster of stations in the central business district that serve as connectors between different lines, but there's also this other station called Jurong East, which is only connected to three other stations, but serves as a major transit connector point between the red and green lines.\n",
    " - ![singapore_map][1]\n",
    "- Hight betweenness centrality, low degree centrality\n",
    "- We have a graph `G` that is a barbell graph, which can be created as in the following code cells.\n",
    "- `m1` is the number of nodes in the barbell ends, and `m2` is the number of nodes in the barbell bridge.\n",
    "- The `keys` are the nodes, and the `values` are the `betweenness centrality` scores.\n",
    "- Some values are `0` because they're located at the ends of the barbell graph and the nodes within each end are fully connected with one another.\n",
    "- With the exception of the bridge node and the two nodes it's connected to, there's no shortest path that has to run through any of those nodes to get to other nodes.\n",
    "\n",
    "\n",
    "  [1]: https://raw.githubusercontent.com/trenton3983/DataCamp/master/Images/2020-05-21_intro_to_network_analysis_in_python/singapore_station_map.jpg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = nx.barbell_graph(m1=5, m2=1)\n",
    "nx.betweenness_centrality(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(G)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### NetworkX betweenness centrality on a social network\n",
    "\n",
    "Betweenness centrality is a node importance metric that uses information about the shortest paths in a network. It is defined as the fraction of all possible shortest paths between any pair of nodes that pass through the node.\n",
    "\n",
    "NetworkX provides the `nx.betweenness_centrality(G)` function for computing the betweenness centrality of every node in a graph, and it returns a dictionary where the keys are the nodes and the values are their betweenness centrality measures.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Compute the betweenness centrality `bet_cen` of the nodes in the graph `T`.\n",
    "- Compute the degree centrality `deg_cen` of the nodes in the graph `T`.\n",
    "- Compare betweenness centrality to degree centrality by creating a scatterplot of the two, with `list(bet_cen.values())` on the x-axis and `list(deg_cen.values())` on the y-axis."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Compute the betweenness centrality of T: bet_cen\n",
    "bet_cen = nx.betweenness_centrality(t_131)\n",
    "\n",
    "# Compute the degree centrality of T: deg_cen\n",
    "deg_cen = nx.degree_centrality(t_131)\n",
    "\n",
    "# Create a scatter plot of betweenness centrality and degree centrality\n",
    "plt.scatter(list(bet_cen.values()), list(deg_cen.values()))\n",
    "\n",
    "# Display the plot\n",
    "plt.xlim(-0.00005, 0.0002)\n",
    "plt.xticks(rotation=45)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Deep dive - Twitter network\n",
    "\n",
    "You're going to now take a deep dive into a Twitter network, which will help reinforce what you've learned earlier. First, you're going to find the nodes that can broadcast messages very efficiently to lots of people one degree of separation away.\n",
    "\n",
    "NetworkX has been pre-imported for you as `nx`.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Write a function `find_nodes_with_highest_deg_cent(G)` that returns the node(s) with the highest degree centrality using the following steps:\n",
    " - Compute the degree centrality of `G`.\n",
    " - Compute the maximum degree centrality using the `max()` function on `list(deg_cent.values())`.\n",
    " - Iterate over the degree centrality dictionary, `deg_cent.items()`.\n",
    " - If the degree centrality value `v` of the current node `k` is equal to `max_dc`, add it to the set of nodes.\n",
    "- Use your function to find the node(s) that has the highest degree centrality in `T`.\n",
    "- Write an assertion statement that checks that the node(s) is/are correctly identified. This has been done for you, so hit 'Submit Answer' to see the result!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define find_nodes_with_highest_deg_cent()\n",
    "def find_nodes_with_highest_deg_cent(G):\n",
    "\n",
    "    # Compute the degree centrality of G: deg_cent\n",
    "    deg_cent = nx.degree_centrality(G)\n",
    "\n",
    "    # Compute the maximum degree centrality: max_dc\n",
    "    max_dc = max(list(deg_cent.values()))\n",
    "\n",
    "    nodes = set()\n",
    "\n",
    "    # Iterate over the degree centrality dictionary\n",
    "    for k, v in deg_cent.items():\n",
    "\n",
    "        # Check if the current value has the maximum degree centrality\n",
    "        if v == max_dc:\n",
    "\n",
    "            # Add the current node to the set of nodes\n",
    "            nodes.add(k)\n",
    "\n",
    "    return nodes\n",
    "\n",
    "# Find the node(s) that has the highest degree centrality in T: top_dc\n",
    "top_dc = find_nodes_with_highest_deg_cent(T)\n",
    "print(f'It looks like node {top_dc} has the highest degree centrality')\n",
    "\n",
    "# Write the assertion statement\n",
    "for node in top_dc:\n",
    "    assert nx.degree_centrality(T)[node] == max(nx.degree_centrality(T).values())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Deep dive - Twitter network part II\n",
    "\n",
    "Next, you're going to do an analogous deep dive on betweenness centrality! Just a few hints to help you along: remember that betweenness centrality is computed using `nx.betweenness_centrality(G)`.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Write a function `find_node_with_highest_bet_cent(G)` that returns the node(s) with the highest betweenness centrality.\n",
    " - Compute the betweenness centrality of `G`.\n",
    " - Compute the maximum betweenness centrality using the `max()` function on `list(bet_cent.values())`.\n",
    " - Iterate over the degree centrality dictionary, `bet_cent.items()`.\n",
    " - If the degree centrality value `v` of the current node `k` is equal to `max_bc`, add it to the set of nodes.\n",
    "- Use your function to find the node(s) that has the highest betweenness centrality in `T`.\n",
    "- Write an assertion statement that you've got the right node. This has been done for you, so hit 'Submit Answer' to see the result!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define find_node_with_highest_bet_cent()\n",
    "def find_node_with_highest_bet_cent(G):\n",
    "\n",
    "    # Compute betweenness centrality: bet_cent\n",
    "    bet_cent = nx.betweenness_centrality(G)\n",
    "\n",
    "    # Compute maximum betweenness centrality: max_bc\n",
    "    max_bc = max(list(bet_cent.values()))\n",
    "\n",
    "    nodes = set()\n",
    "\n",
    "    # Iterate over the betweenness centrality dictionary\n",
    "    for k, v in bet_cent.items():\n",
    "\n",
    "        # Check if the current value has the maximum betweenness centrality\n",
    "        if v == max_bc:\n",
    "\n",
    "            # Add the current node to the set of nodes\n",
    "            nodes.add(k)\n",
    "\n",
    "    return nodes\n",
    "\n",
    "# Use that function to find the node(s) that has the highest betweenness centrality in the network: top_bc\n",
    "top_bc = find_node_with_highest_bet_cent(t_131)\n",
    "print(f'Node {top_bc} has the highest betweenness centrality.')\n",
    "\n",
    "# Write an assertion statement that checks that the node(s) is/are correctly identified.\n",
    "for node in top_bc:\n",
    "    assert nx.betweenness_centrality(t_131)[node] == max(nx.betweenness_centrality(t_131).values())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Structures\n",
    "\n",
    "This chapter is all about finding interesting structures within network data. You'll learn about essential concepts such as cliques, communities, and subgraphs, which will leverage all of the skills you acquired in Chapter 2. By the end of this chapter, you'll be ready to apply the concepts you've learned to a real-world case study."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Communities & Cliques\n",
    "\n",
    "- We're now going to explore the concepts of structures and subgraphs, using NetworkX.\n",
    "- A lot of this is going to leverage what you've learned in the 2nd chapter, particularly on path finding and the use of neighbors.\n",
    "- Have your ever been in a clique?\n",
    "- How would you characterize the clique?\n",
    "- It probably was comprised of people who know everybody else in the group to a pretty strong degree, right?\n",
    "- Now imagine if there was another new person not originally part of the clique that joined in - now, in this group, it wouldn't feel like a _clique_, because the new person doesn't really know everybody else, and vise versa.\n",
    "- ![cliques][1]\n",
    "- In network theory, a _clique_ is essentially defined on the social version of a clique: \n",
    " - A set of nodes that are completely connected by an edge to every other node in the set.\n",
    " - It is, then, a completely connected graph.\n",
    "- What might be the _simplest clique_?\n",
    "- By the definition of a clique, an edge is the simplest clique possible.\n",
    "- Now, what would be the simplest _complex clique_?\n",
    " - 3 nodes fully connected, a triangle\n",
    "- What are some applications of finding _triangles_ in a network?\n",
    " - One example is a friend recommendation system.\n",
    " - If `A` knows `B` and `A` knows `C`, but `B` and `C` are not yet connected, then there's a good chance that `B` knows `C` as well, and may want to be connected online, by doing what we call triangle closures.\n",
    "\n",
    "### Clique Code\n",
    "- How might you write code that finds all triangles that a node is involved in?\n",
    "- That will be the exercise that you're going to go through.\n",
    "- Suppose you had a graph `G`, and you wanted to iterate over every pair of nodes, and not only every edge.\n",
    "- Rather than writing a nested for-loop, you might want to use the combinations function from the Python `itertool` module.\n",
    "- In this way, your for-loop can iterate over every pair of nodes in the network, by using the following code\n",
    "\n",
    "\n",
    "\n",
    "  [1]: https://raw.githubusercontent.com/trenton3983/DataCamp/master/Images/2020-05-21_intro_to_network_analysis_in_python/cliques.JPG"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t_131"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in list(combinations(t_131.nodes(), 2))[:10]:\n",
    "    print(n[0], n[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Identifying triangle relationships\n",
    "\n",
    "Now that you've learned about cliques, it's time to try leveraging what you know to find structures in a network. Triangles are what you'll go for first. We may be interested in triangles because they're the simplest complex clique. Let's write a few functions; these exercises will bring you through the fundamental logic behind network algorithms.\n",
    "\n",
    "In the Twitter network, each node has an `'occupation'` label associated with it, in which the Twitter user's work occupation is divided into `celebrity`, `politician` and `scientist`. One potential application of triangle-finding algorithms is to find out whether users that have similar occupations are more likely to be in a clique with one another.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Import `combinations` from `itertools`.\n",
    "- Write a function `is_in_triangle()` that has two parameters - `G` and `n` - and checks whether a given node is in a triangle relationship or not.\n",
    " - `combinations(iterable, n)` returns combinations of size `n` from `iterable`. This will be useful here, as you want combinations of size `2` from `G.neighbors(n)`.\n",
    " - To check whether an edge exists between two nodes, use the `.has_edge(node1, node2)` method. If an edge exists, then the given node is in a triangle relationship, and you should return `True`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define is_in_triangle()\n",
    "def is_in_triangle(G, n):\n",
    "    \"\"\"\n",
    "    Checks whether a node `n` in graph `G` is in a triangle relationship or not.\n",
    "\n",
    "    Returns a boolean.\n",
    "    \"\"\"\n",
    "    in_triangle = False\n",
    "\n",
    "    # Iterate over all possible triangle relationship combinations\n",
    "    for n1, n2 in combinations(G.neighbors(n), 2):\n",
    "\n",
    "        # Check if an edge exists between n1 and n2\n",
    "        if G.has_edge(n1, n2):\n",
    "            in_triangle = True\n",
    "            break\n",
    "    return in_triangle\n",
    "\n",
    "is_in_triangle(T, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for node in sorted(list(T.nodes())[:60]):\n",
    "    x = is_in_triangle(T, node)\n",
    "    if x == True:\n",
    "        print(f'{node}: {x}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Finding nodes involved in triangles\n",
    "\n",
    "NetworkX provides an API for counting the number of triangles that every node is involved in: `nx.triangles(G)`. It returns a dictionary of nodes as the keys and number of triangles as the values. Your job in this exercise is to modify the function defined earlier to extract all of the nodes involved in a triangle relationship with a given node.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Write a function `nodes_in_triangle()` that has two parameters - `G` and `n` - and identifies all nodes in a triangle relationship with a given node.\n",
    " - In the `for` loop, iterate over all possible triangle relationship combinations.\n",
    " - Check whether the nodes `n1` and `n2` have an edge between them. If they do, add both nodes to the set ``triangle_nodes``.\n",
    "- Use your function in an `assert` statement to check that the number of nodes involved in a triangle relationship with node `1` of graph `T` is equal to `35`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Write a function that identifies all nodes in a triangle relationship with a given node.\n",
    "def nodes_in_triangle(G, n):\n",
    "    \"\"\"\n",
    "    Returns the nodes in a graph `G` that are involved in a triangle relationship with the node `n`.\n",
    "    \"\"\"\n",
    "    triangle_nodes = set([n])\n",
    "\n",
    "    # Iterate over all possible triangle relationship combinations\n",
    "    for n1, n2 in combinations(G.neighbors(n), 2):\n",
    "\n",
    "        # Check if n1 and n2 have an edge between them\n",
    "        if G.has_edge(n1, n2):\n",
    "\n",
    "            # Add n1 to triangle_nodes\n",
    "            triangle_nodes.add(n1)\n",
    "\n",
    "            # Add n2 to triangle_nodes\n",
    "            triangle_nodes.add(n2)\n",
    "    return triangle_nodes\n",
    "\n",
    "# Write the assertion statement\n",
    "assert len(nodes_in_triangle(T, 1)) == 23"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Finding open triangles\n",
    "\n",
    "Let us now move on to finding open triangles! Recall that they form the basis of friend recommendation systems; if \"A\" knows \"B\" and \"A\" knows \"C\", then it's probable that \"B\" also knows \"C\".\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Write a function `node_in_open_triangle()` that has two parameters - `G` and `n` - and identifies whether a node is present in an open triangle with its neighbors.\n",
    " - In the `for` loop, iterate over all possible triangle relationship combinations.\n",
    " - If the nodes `n1` and `n2` do not have an edge between them, set `in_open_triangle` to `True`, break out from the `if` statement and return `in_open_triangle`.\n",
    "- Use this function to count the number of open triangles that exist in `T`.\n",
    " - In the `for` loop, iterate over all the nodes in `T`.\n",
    " - If the current node `n` is in an open triangle, increment `num_open_triangles`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define node_in_open_triangle()\n",
    "def node_in_open_triangle(G, n):\n",
    "    \"\"\"\n",
    "    Checks whether pairs of neighbors of node `n` in graph `G` are in an 'open triangle' relationship with node `n`.\n",
    "    \"\"\"\n",
    "    in_open_triangle = False\n",
    "\n",
    "    # Iterate over all possible triangle relationship combinations\n",
    "    for n1, n2 in combinations(G.neighbors(n), 2):\n",
    "\n",
    "        # Check if n1 and n2 do NOT have an edge between them\n",
    "        if not G.has_edge(n1, n2):\n",
    "\n",
    "            in_open_triangle = True\n",
    "\n",
    "            break\n",
    "\n",
    "    return in_open_triangle\n",
    "\n",
    "# Compute the number of open triangles in T\n",
    "num_open_triangles = 0\n",
    "\n",
    "# Iterate over all the nodes in T\n",
    "for n in T.nodes():\n",
    "\n",
    "    # Check if the current node is in an open triangle\n",
    "    if node_in_open_triangle(T, n):\n",
    "\n",
    "        # Increment num_open_triangles\n",
    "        num_open_triangles += 1\n",
    "\n",
    "print(f'{num_open_triangles} nodes in graph T are in open triangles.')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Maximal Cliques\n",
    "\n",
    "- ![maximal_cliques][1]\n",
    "- They are a clique, but that clique can't be extended by adding another node in the graph.\n",
    "- For example, the sub-clique of the 3 green nodes can be extended by one blue node to form a large clique.\n",
    "- As such, these 3 green nodes do not form a _maximal clique_ in the graph.\n",
    "- The 4 nodes connected as a clique together cannot be extended and still remain a clique, as the remaining node is not fully connected to the other four nodes.\n",
    "- As such, these four nodes constitute a _maximal clique_.\n",
    "\n",
    "### Communities\n",
    "- The concept of _maximal cliques_ has its uses in community finding algorithms.\n",
    "- Without going into the myriad of details possible, I hope to define, at a basic level, what a community is.\n",
    "- Cliques form a good starting point for finding communities, as they are fully connected subgraphs within a larger graph.\n",
    "- By identifying these _maximal cliques_, one naive way of identifying communities might be identifying the unions of maximal cliques that share some number of members, but are also of some minimum size.\n",
    "\n",
    "### NetworkX API\n",
    "- NetworkX provides a function for finding all maximal cliques, which is the `find_clique` function.\n",
    " - Works for `Graph`, but doesn't work for `DiGraph`\n",
    "- `find_cliqeus` will not just find any clique, but the set of _maximal cliques_.\n",
    "- There are two _maximal cliques_ of size 5 in the graph.\n",
    "- There are also two _maximal cliques_ of size 2 - these are the edges between nodes `4` and `5`, and nodes `5` and `6`.\n",
    "- Recall that edges are also a clique.\n",
    "\n",
    "\n",
    "  [1]: https://raw.githubusercontent.com/trenton3983/DataCamp/master/Images/2020-05-21_intro_to_network_analysis_in_python/max_cliques.JPG"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = nx.barbell_graph(m1=5, m2=1)\n",
    "nx.find_cliques(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gl = list(nx.find_cliques(G))\n",
    "print(gl)\n",
    "nx.draw(G, with_labels=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G2 = nx.barbell_graph(m1=5, m2=2)\n",
    "gl2 = list(nx.find_cliques(G2))\n",
    "print(gl2)\n",
    "nx.draw(G2, with_labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Finding all maximal cliques of size \"n\"\n",
    "\n",
    "Now that you've explored triangles (and open triangles), let's move on to the concept of maximal cliques. Maximal cliques are cliques that cannot be extended by adding an adjacent edge, and are a useful property of the graph when finding communities. NetworkX provides a function that allows you to identify the nodes involved in each maximal clique in a graph: `nx.find_cliques(G)`. Play around with the function by using it on `T` in the IPython Shell, and then try answering the exercise.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Write a function `maximal_cliques()` that has two parameters - `G` and `size` - and finds all maximal cliques of size `n`.\n",
    " - In the `for` loop, iterate over all the cliques in `G` using the `nx.find_cliques()` function.\n",
    " - If the current clique is of size `size`, append it to the list `mcs`.\n",
    "- Use an assert statement and your `maximal_cliques()` function to check that there are `33` maximal cliques of size `3` in the graph `T`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nodes = {1: {'category': 'I', 'occupation': 'politician'}, 3: {'category': 'D', 'occupation': 'celebrity'}, 4: {'category': 'I', 'occupation': 'politician'}, 5: {'category': 'I', 'occupation': 'scientist'}, 6: {'category': 'D', 'occupation': 'politician'}, 7: {'category': 'I', 'occupation': 'politician'}, 8: {'category': 'I', 'occupation': 'celebrity'}, 9: {'category': 'D', 'occupation': 'scientist'}, 10: {'category': 'D', 'occupation': 'celebrity'}, 11: {'category': 'I', 'occupation': 'celebrity'}, 12: {'category': 'I', 'occupation': 'celebrity'}, 13: {'category': 'P', 'occupation': 'scientist'}, 14: {'category': 'D', 'occupation': 'celebrity'}, 15: {'category': 'P', 'occupation': 'scientist'}, 16: {'category': 'P', 'occupation': 'politician'}, 17: {'category': 'I', 'occupation': 'scientist'}, 18: {'category': 'I', 'occupation': 'celebrity'}, 19: {'category': 'I', 'occupation': 'scientist'}, 20: {'category': 'P', 'occupation': 'scientist'}, 21: {'category': 'I', 'occupation': 'celebrity'}, 22: {'category': 'D', 'occupation': 'scientist'}, 23: {'category': 'D', 'occupation': 'scientist'}, 24: {'category': 'P', 'occupation': 'politician'}, 25: {'category': 'I', 'occupation': 'celebrity'}, 26: {'category': 'P', 'occupation': 'celebrity'}, 27: {'category': 'D', 'occupation': 'scientist'}, 28: {'category': 'P', 'occupation': 'celebrity'}, 29: {'category': 'I', 'occupation': 'celebrity'}, 30: {'category': 'P', 'occupation': 'scientist'}, 31: {'category': 'D', 'occupation': 'scientist'}, 32: {'category': 'P', 'occupation': 'politician'}, 33: {'category': 'I', 'occupation': 'politician'}, 34: {'category': 'D', 'occupation': 'celebrity'}, 35: {'category': 'P', 'occupation': 'scientist'}, 36: {'category': 'D', 'occupation': 'scientist'}, 37: {'category': 'I', 'occupation': 'scientist'}, 38: {'category': 'P', 'occupation': 'celebrity'}, 39: {'category': 'D', 'occupation': 'celebrity'}, 40: {'category': 'I', 'occupation': 'celebrity'}, 41: {'category': 'I', 'occupation': 'celebrity'}, 42: {'category': 'P', 'occupation': 'scientist'}, 43: {'category': 'I', 'occupation': 'celebrity'}, 44: {'category': 'I', 'occupation': 'politician'}, 45: {'category': 'D', 'occupation': 'scientist'}, 46: {'category': 'I', 'occupation': 'politician'}, 47: {'category': 'I', 'occupation': 'celebrity'}, 48: {'category': 'P', 'occupation': 'celebrity'}, 49: {'category': 'P', 'occupation': 'politician'}}\n",
    "edges = [(1, 3, {'date': date(2012, 11, 16)}), (1, 4, {'date': date(2013, 6, 7)}), (1, 5, {'date': date(2009, 7, 27)}), (1, 6, {'date': date(2014, 12, 18)}), (1, 7, {'date': date(2010, 10, 18)}), (1, 8, {'date': date(2012, 4, 18)}), (1, 9, {'date': date(2007, 10, 14)}), (1, 10, {'date': date(2012, 9, 8)}), (1, 11, {'date': date(2010, 1, 6)}), (1, 12, {'date': date(2012, 12, 27)}), (1, 13, {'date': date(2008, 12, 18)}), (1, 14, {'date': date(2014, 5, 25)}), (1, 15, {'date': date(2009, 11, 12)}), (1, 16, {'date': date(2008, 8, 6)}), (1, 17, {'date': date(2007, 8, 11)}), (1, 18, {'date': date(2009, 10, 7)}), (1, 19, {'date': date(2008, 7, 24)}), (1, 20, {'date': date(2013, 11, 18)}), (1, 21, {'date': date(2011, 3, 28)}), (1, 22, {'date': date(2013, 3, 4)}), (1, 23, {'date': date(2012, 4, 20)}), (1, 24, {'date': date(2009, 6, 6)}), (1, 25, {'date': date(2013, 6, 18)}), (1, 26, {'date': date(2014, 11, 20)}), (1, 27, {'date': date(2007, 4, 28)}), (1, 28, {'date': date(2014, 3, 28)}), (1, 29, {'date': date(2014, 1, 23)}), (1, 30, {'date': date(2007, 10, 9)}), (1, 31, {'date': date(2009, 2, 17)}), (1, 32, {'date': date(2009, 10, 14)}), (1, 33, {'date': date(2010, 5, 19)}), (1, 34, {'date': date(2009, 12, 21)}), (1, 35, {'date': date(2014, 11, 16)}), (1, 36, {'date': date(2010, 2, 25)}), (1, 37, {'date': date(2010, 9, 23)}), (1, 38, {'date': date(2007, 4, 28)}), (1, 39, {'date': date(2007, 4, 8)}), (1, 40, {'date': date(2010, 5, 15)}), (1, 41, {'date': date(2009, 8, 12)}), (1, 42, {'date': date(2013, 3, 9)}), (1, 43, {'date': date(2011, 11, 14)}), (1, 44, {'date': date(2013, 4, 6)}), (1, 45, {'date': date(2010, 1, 18)}), (1, 46, {'date': date(2011, 8, 20)}), (1, 47, {'date': date(2014, 8, 3)}), (1, 48, {'date': date(2010, 3, 15)}), (1, 49, {'date': date(2007, 9, 2)}), (5, 19, {'date': date(2013, 6, 12)}), (5, 28, {'date': date(2010, 12, 4)}), (5, 36, {'date': date(2013, 4, 7)}), (7, 28, {'date': date(2011, 11, 21)}), (8, 19, {'date': date(2010, 11, 5)}), (8, 28, {'date': date(2007, 6, 26)}), (11, 19, {'date': date(2012, 4, 16)}), (11, 28, {'date': date(2011, 6, 21)}), (13, 19, {'date': date(2012, 12, 13)}), (14, 28, {'date': date(2013, 12, 18)}), (15, 19, {'date': date(2008, 12, 13)}), (15, 28, {'date': date(2014, 6, 3)}), (16, 18, {'date': date(2008, 8, 5)}), (16, 35, {'date': date(2014, 6, 4)}), (16, 36, {'date': date(2008, 10, 10)}), (16, 48, {'date': date(2014, 1, 27)}), (17, 19, {'date': date(2007, 11, 11)}), (17, 28, {'date': date(2012, 10, 11)}), (18, 24, {'date': date(2009, 2, 4)}), (18, 35, {'date': date(2008, 12, 1)}), (18, 36, {'date': date(2013, 2, 6)}), (19, 20, {'date': date(2008, 11, 9)}), (19, 21, {'date': date(2007, 7, 23)}), (19, 24, {'date': date(2013, 12, 13)}), (19, 30, {'date': date(2012, 6, 6)}), (19, 31, {'date': date(2011, 1, 27)}), (19, 35, {'date': date(2014, 3, 3)}), (19, 36, {'date': date(2007, 10, 22)}), (19, 37, {'date': date(2008, 4, 20)}), (19, 48, {'date': date(2010, 12, 23)}), (20, 28, {'date': date(2012, 4, 15)}), (21, 28, {'date': date(2014, 4, 27)}), (24, 28, {'date': date(2013, 1, 27)}), (24, 36, {'date': date(2009, 4, 23)}), (24, 37, {'date': date(2008, 6, 27)}), (24, 39, {'date': date(2007, 1, 27)}), (24, 43, {'date': date(2014, 2, 12)}), (25, 28, {'date': date(2014, 5, 9)}), (27, 28, {'date': date(2007, 8, 9)}), (28, 29, {'date': date(2012, 4, 3)}), (28, 30, {'date': date(2007, 12, 2)}), (28, 31, {'date': date(2008, 6, 1)}), (28, 35, {'date': date(2012, 11, 16)}), (28, 36, {'date': date(2012, 9, 26)}), (28, 37, {'date': date(2014, 11, 12)}), (28, 44, {'date': date(2007, 11, 18)}), (28, 48, {'date': date(2008, 5, 25)}), (28, 49, {'date': date(2011, 12, 19)}), (29, 43, {'date': date(2014, 6, 4)}), (33, 39, {'date': date(2011, 9, 5)}), (35, 36, {'date': date(2008, 12, 1)}), (35, 37, {'date': date(2014, 5, 7)}), (35, 39, {'date': date(2007, 6, 17)}), (35, 43, {'date': date(2009, 6, 10)}), (36, 37, {'date': date(2014, 5, 13)}), (36, 39, {'date': date(2014, 12, 6)}), (36, 43, {'date': date(2013, 12, 17)}), (37, 43, {'date': date(2012, 1, 22)}), (38, 39, {'date': date(2009, 5, 15)}), (39, 40, {'date': date(2011, 6, 3)}), (39, 41, {'date': date(2009, 10, 5)}), (39, 45, {'date': date(2011, 1, 12)}), (41, 45, {'date': date(2009, 9, 7)}), (43, 47, {'date': date(2014, 12, 21)}), (43, 48, {'date': date(2013, 1, 28)})]\n",
    "\n",
    "t_321 = nx.Graph()\n",
    "t_321.add_nodes_from(nodes)\n",
    "t_321.add_edges_from(edges)\n",
    "nx.set_node_attributes(t_321, nodes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define maximal_cliques()\n",
    "def maximal_cliques(G, n):\n",
    "    \"\"\"\n",
    "    Finds all maximal cliques in graph `G` that are of size `size`.\n",
    "    \"\"\"\n",
    "    mcs = []\n",
    "    for clique in nx.find_cliques(G):\n",
    "        if len(clique) == n:\n",
    "            mcs.append(clique)\n",
    "    return mcs\n",
    "\n",
    "# Check that there are 33 maximal cliques of size 3 in the graph T\n",
    "assert len(maximal_cliques(t_321, 3)) == 33"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Subgraphs\n",
    "\n",
    "- When you have a large graph, and you want to visualize just a small portion of it, it can be helpful to extract those nodes and their associated edges as a separate graph object.\n",
    "- For example, you might want to visualized a particular path through the network, or you might want to visualized a particular community or clique.\n",
    "- Alternatively, you might just want to explore the structure of the graph around a node out of a number of degrees of separation.\n",
    "- In all of these scenarios, it's useful to be able to \"slice out\" the nodes and edges of interest, and visualize them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "random.seed(121)\n",
    "G = nx.erdos_renyi_graph(n=20, p=0.2)\n",
    "G.nodes()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(G, with_labels=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nodes = list(G.neighbors(8))\n",
    "nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nodes.append(8)\n",
    "G_eight = G.subgraph(nodes)\n",
    "G_eight.edges()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "display(G_eight)\n",
    "display(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(G_eight, with_labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Subgraphs I\n",
    "\n",
    "There may be times when you just want to analyze a subset of nodes in a network. To do so, you can copy them out into another graph object using `G.subgraph(nodes)`, which returns a new `graph` object (of the same type as the original graph) that is comprised of the iterable of `nodes` that was passed in.\n",
    "\n",
    "`matplotlib.pyplot` has been imported for you as `plt`.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Write a function `get_nodes_and_nbrs(G, nodes_of_interest)` that extracts the subgraph from graph `G` comprised of the `nodes_of_interest` and their neighbors.\n",
    " - In the first `for` loop, iterate over `nodes_of_interest` and append the current node `n` to `nodes_to_draw`.\n",
    " - In the second `for` loop, iterate over the neighbors of `n`, and append all the neighbors `nbr` to `nodes_to_draw`.\n",
    "- Use the function to extract the subgraph from `T` comprised of nodes 29, 38, and 42 (contained in the pre-defined list `nodes_of_interest`) and their neighbors. Save the result as `T_draw`.\n",
    "- Draw the subgraph `T_draw` to the screen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nodes_of_interest = [29, 38, 42]\n",
    "\n",
    "# Define get_nodes_and_nbrs()\n",
    "def get_nodes_and_nbrs(G, nodes_of_interest):\n",
    "    \"\"\"\n",
    "    Returns a subgraph of the graph `G` with only the `nodes_of_interest` and their neighbors.\n",
    "    \"\"\"\n",
    "    nodes_to_draw = []\n",
    "\n",
    "    # Iterate over the nodes of interest\n",
    "    for n in nodes_of_interest:\n",
    "\n",
    "        # Append the nodes of interest to nodes_to_draw\n",
    "        nodes_to_draw.append(n)\n",
    "\n",
    "        # Iterate over all the neighbors of node n\n",
    "        for nbr in G.neighbors(n):\n",
    "\n",
    "            # Append the neighbors of n to nodes_to_draw\n",
    "            nodes_to_draw.append(nbr)\n",
    "\n",
    "    return G.subgraph(nodes_to_draw)\n",
    "\n",
    "# Extract the subgraph with the nodes of interest: T_draw\n",
    "T_draw = get_nodes_and_nbrs(T, nodes_of_interest)\n",
    "\n",
    "# Draw the subgraph to the screen\n",
    "nx.draw(T_draw, with_labels=True)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Subgraphs II\n",
    "\n",
    "In the previous exercise, we gave you a list of nodes whose neighbors we asked you to extract.\n",
    "\n",
    "Let's try one more exercise in which you extract nodes that have a particular metadata property and their neighbors. This should hark back to what you've learned about using list comprehensions to find nodes. The exercise will also build your capacity to compose functions that you've already written before.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Using a list comprehension, extract nodes that have the metadata `'occupation'` as `'celebrity'` alongside their neighbors:\n",
    " - The _output expression_ of the list comprehension is `n`, and there are two _iterator variables_: `n` and `d`. The iterable is the list of nodes of `T` (including the metadata, which you can specify using `data=True`) and the conditional expression is if the `'occupation'` key of the metadata dictionary `d` equals `'celebrity'`.\n",
    "- Place them in a new subgraph called `T_sub`. To do this:\n",
    " - Iterate over the nodes, compute the neighbors of each node, and add them to the set of nodes `nodeset` by using the `.union()` method. This last part has been done for you.\n",
    " - Use `nodeset` along with the `T.subgraph()` method to calculate `T_sub`.\n",
    "- Draw `T_sub` to the screen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Extract the nodes of interest: nodes\n",
    "nodes = [n for n, d in t_321.nodes(data=True) if d['occupation'] == 'celebrity']\n",
    "\n",
    "# Create the set of nodes: nodeset\n",
    "nodeset = set(nodes)\n",
    "\n",
    "# Iterate over nodes\n",
    "for n in nodes:\n",
    "\n",
    "    # Compute the neighbors of n: nbrs\n",
    "    nbrs = t_321.neighbors(n)\n",
    "\n",
    "    # Compute the union of nodeset and nbrs: nodeset\n",
    "    nodeset = nodeset.union(nbrs)\n",
    "\n",
    "# Compute the subgraph using nodeset: T_sub\n",
    "T_sub = t_321.subgraph(nodeset)\n",
    "\n",
    "# Draw T_sub to the screen\n",
    "nx.draw(T_sub, with_labels=True)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bringing it all together\n",
    "\n",
    "In this final chapter of the course, you'll consolidate everything you've learned through an in-depth case study of GitHub collaborator network data. This is a great example of real-world social network data, and your newly acquired skills will be fully tested. By the end of this chapter, you'll have developed your very own recommendation system to connect GitHub users who should collaborate together."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Case Study\n",
    "\n",
    "### Data\n",
    "- This dataset is a GitHub user collaboration network.\n",
    "- GitHub is a social coding site, where users can collaborate on code repositories.\n",
    "- In this network, nodes are users, and edges indicate that two users are collaborators on at least one GitHub repository.\n",
    "- What you'll be accomplishing by the end of the exercises is the following:\n",
    " - You will have analyzed the structure of the graph, including its basic properties.\n",
    " - You will visualize the graph using `nxviz`\n",
    " - You will build a simple recommendation system.\n",
    "   - A recommendation system in social networks recommends users to \"connect\" with one another in some fashion.\n",
    "   - In the GitHub context, we will try writing a recommender that suggests users that should collaborate together.\n",
    "\n",
    "### Graph properties\n",
    "- Recall from the first chapter about some basic functions for getting a graph's size."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "random.seed(121)\n",
    "G = nx.erdos_renyi_graph(n=20, p=0.2)\n",
    "print(len(G.edges()))\n",
    "print(len(G.nodes()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Are you able to recall what the function names are for computing the degree and betweenness centralities of each node in the graph?\n",
    " - `nx.degree_centrality(G)`\n",
    " - `nx.betweenness_centrality(G)`\n",
    " - In both cases, the key is the node name and the value is the centrality score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pp(nx.degree_centrality(G))\n",
    "print('\\n')\n",
    "pp(nx.betweenness_centrality(G))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Characterizing the network (I)\n",
    "To start out, let's do some basic characterization of the network, by looking at the number of nodes and number of edges in a network. It has been pre-loaded as `G` and is available for exploration in the IPython Shell. Your job in this exercise is to identify how many nodes and edges are present in the network. You can use the functions `len(G.nodes())` and `len(G.edges())` to calculate the number of nodes and edges respectively.\n",
    "\n",
    "- ~~72900 nodes, 56519 edges.~~\n",
    "- **56519 nodes, 72900 edges.**\n",
    "- ~~47095 nodes, 65789 edges.~~\n",
    "- ~~63762 nodes, 71318 edges.~~"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = nx.Graph(Gh)\n",
    "print(len(G.nodes()))\n",
    "print(len(G.edges()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Characterizing the network (II)\n",
    "\n",
    "Let's continue recalling what you've learned before about node importances, by plotting the degree distribution of a network. This is the distribution of node degrees computed across all nodes in a network.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Plot the degree distribution of the GitHub collaboration network `G`. Recall that there are four steps involved here:\n",
    " - Calculating the degree centrality of `G`.\n",
    " - Using the `.values()` method of `G` and converting it into a list.\n",
    " - Passing the list of degree distributions to `plt.hist()`.\n",
    " - Displaying the histogram with `plt.show()`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Plot the degree distribution of the GitHub collaboration network\n",
    "plt.hist(list(nx.degree_centrality(G).values()))\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Characterizing the network (III)\n",
    "\n",
    "The last exercise was on degree centrality; this time round, let's recall betweenness centrality!\n",
    "\n",
    "A small note: if executed correctly, this exercise may need about 5 seconds to execute.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Plot the betweenness centrality distribution of the GitHub collaboration network. You have to follow exactly the same four steps as in the previous exercise, substituting `nx.betweenness_centrality()` in place of `nx.degree_centrality()`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nodes = {'u41': {'bipartite': 'users', 'grouping': 0}, 'u69': {'bipartite': 'users', 'grouping': 0}, 'u96': {'bipartite': 'users', 'grouping': 0}, 'u156': {'bipartite': 'users', 'grouping': 0}, 'u297': {'bipartite': 'users', 'grouping': 0}, 'u298': {'bipartite': 'users', 'grouping': 0}, 'u315': {'bipartite': 'users', 'grouping': 0}, 'u322': {'bipartite': 'users', 'grouping': 0}, 'u435': {'bipartite': 'users', 'grouping': 0}, 'u440': {'bipartite': 'users', 'grouping': 0}, 'u640': {'bipartite': 'users', 'grouping': 0}, 'u655': {'bipartite': 'users', 'grouping': 0}, 'u698': {'bipartite': 'users', 'grouping': 0}, 'u821': {'bipartite': 'users', 'grouping': 0}, 'u863': {'bipartite': 'users', 'grouping': 0}, 'u901': {'bipartite': 'users', 'grouping': 0}, 'u914': {'bipartite': 'users', 'grouping': 0}, 'u1254': {'bipartite': 'users', 'grouping': 0}, 'u1407': {'bipartite': 'users', 'grouping': 0}, 'u1468': {'bipartite': 'users', 'grouping': 0}, 'u1908': {'bipartite': 'users', 'grouping': 0}, 'u2022': {'bipartite': 'users', 'grouping': 0}, 'u2066': {'bipartite': 'users', 'grouping': 0}, 'u2137': {'bipartite': 'users', 'grouping': 0}, 'u2289': {'bipartite': 'users', 'grouping': 0}, 'u2482': {'bipartite': 'users', 'grouping': 0}, 'u2552': {'bipartite': 'users', 'grouping': 0}, 'u2643': {'bipartite': 'users', 'grouping': 0}, 'u2737': {'bipartite': 'users', 'grouping': 0}, 'u2906': {'bipartite': 'users', 'grouping': 0}, 'u3083': {'bipartite': 'users', 'grouping': 0}, 'u3174': {'bipartite': 'users', 'grouping': 0}, 'u3231': {'bipartite': 'users', 'grouping': 0}, 'u3243': {'bipartite': 'users', 'grouping': 0}, 'u3271': {'bipartite': 'users', 'grouping': 0}, 'u3658': {'bipartite': 'users', 'grouping': 0}, 'u3974': {'bipartite': 'users', 'grouping': 0}, 'u3979': {'bipartite': 'users', 'grouping': 0}, 'u4159': {'bipartite': 'users', 'grouping': 0}, 'u4199': {'bipartite': 'users', 'grouping': 0}, 'u4329': {'bipartite': 'users', 'grouping': 0}, 'u4412': {'bipartite': 'users', 'grouping': 0}, 'u4513': {'bipartite': 'users', 'grouping': 0}, 'u4710': {'bipartite': 'users', 'grouping': 0}, 'u4761': {'bipartite': 'users', 'grouping': 0}, 'u4953': {'bipartite': 'users', 'grouping': 0}, 'u5082': {'bipartite': 'users', 'grouping': 0}, 'u5337': {'bipartite': 'users', 'grouping': 0}, 'u5693': {'bipartite': 'users', 'grouping': 0}, 'u5993': {'bipartite': 'users', 'grouping': 0}, 'u6081': {'bipartite': 'users', 'grouping': 0}, 'u7418': {'bipartite': 'users', 'grouping': 0}, 'u7623': {'bipartite': 'users', 'grouping': 0}, 'u7963': {'bipartite': 'users', 'grouping': 0}, 'u8135': {'bipartite': 'users', 'grouping': 0}, 'u9866': {'bipartite': 'users', 'grouping': 0}, 'u9869': {'bipartite': 'users', 'grouping': 0}, 'u9997': {'bipartite': 'users', 'grouping': 0}, 'u10090': {'bipartite': 'users', 'grouping': 0}, 'u10340': {'bipartite': 'users', 'grouping': 0}, 'u10500': {'bipartite': 'users', 'grouping': 0}, 'u10603': {'bipartite': 'users', 'grouping': 0}, 'u14964': {'bipartite': 'users', 'grouping': 1}}\n",
    "edges = [('u41', 'u2022', {}), ('u41', 'u69', {}), ('u41', 'u5082', {}), ('u41', 'u298', {}), ('u41', 'u901', {}), ('u69', 'u315', {}), ('u69', 'u4513', {}), ('u69', 'u5082', {}), ('u69', 'u901', {}), ('u69', 'u298', {}), ('u69', 'u2022', {}), ('u96', 'u315', {}), ('u96', 'u2482', {}), ('u96', 'u10500', {}), ('u96', 'u2022', {}), ('u96', 'u863', {}), ('u96', 'u9997', {}), ('u96', 'u297', {}), ('u96', 'u698', {}), ('u96', 'u2066', {}), ('u96', 'u7963', {}), ('u96', 'u156', {}), ('u96', 'u2906', {}), ('u96', 'u2552', {}), ('u156', 'u315', {}), ('u156', 'u2482', {}), ('u156', 'u10500', {}), ('u156', 'u863', {}), ('u156', 'u2022', {}), ('u156', 'u297', {}), ('u156', 'u9997', {}), ('u156', 'u698', {}), ('u156', 'u2066', {}), ('u156', 'u7963', {}), ('u156', 'u2906', {}), ('u156', 'u2552', {}), ('u297', 'u315', {}), ('u297', 'u2482', {}), ('u297', 'u863', {}), ('u297', 'u2022', {}), ('u297', 'u9997', {}), ('u297', 'u698', {}), ('u297', 'u10500', {}), ('u297', 'u2066', {}), ('u297', 'u7963', {}), ('u297', 'u2906', {}), ('u297', 'u2552', {}), ('u298', 'u5082', {}), ('u298', 'u901', {}), ('u298', 'u2022', {}), ('u315', 'u2482', {}), ('u315', 'u10500', {}), ('u315', 'u2022', {}), ('u315', 'u863', {}), ('u315', 'u9997', {}), ('u315', 'u698', {}), ('u315', 'u2066', {}), ('u315', 'u7963', {}), ('u315', 'u2906', {}), ('u315', 'u4513', {}), ('u315', 'u2552', {}), ('u322', 'u3174', {}), ('u322', 'u3974', {}), ('u322', 'u7623', {}), ('u322', 'u8135', {}), ('u322', 'u2022', {}), ('u322', 'u4953', {}), ('u322', 'u640', {}), ('u322', 'u4412', {}), ('u322', 'u10340', {}), ('u322', 'u4159', {}), ('u322', 'u1908', {}), ('u322', 'u3979', {}), ('u322', 'u435', {}), ('u322', 'u821', {}), ('u322', 'u9869', {}), ('u322', 'u9866', {}), ('u322', 'u10603', {}), ('u322', 'u3083', {}), ('u322', 'u4710', {}), ('u435', 'u7623', {}), ('u435', 'u8135', {}), ('u435', 'u2022', {}), ('u435', 'u10603', {}), ('u435', 'u10340', {}), ('u435', 'u9866', {}), ('u440', 'u5693', {}), ('u440', 'u2643', {}), ('u440', 'u10090', {}), ('u440', 'u3271', {}), ('u640', 'u1908', {}), ('u640', 'u3174', {}), ('u640', 'u3979', {}), ('u640', 'u3974', {}), ('u640', 'u821', {}), ('u640', 'u4953', {}), ('u640', 'u4412', {}), ('u640', 'u9869', {}), ('u640', 'u4159', {}), ('u640', 'u4710', {}), ('u640', 'u3083', {}), ('u655', 'u2643', {}), ('u655', 'u2906', {}), ('u655', 'u2137', {}), ('u655', 'u914', {}), ('u655', 'u4513', {}), ('u698', 'u10500', {}), ('u698', 'u2066', {}), ('u698', 'u2906', {}), ('u698', 'u2552', {}), ('u698', 'u9997', {}), ('u698', 'u7963', {}), ('u698', 'u2482', {}), ('u698', 'u863', {}), ('u698', 'u2022', {}), ('u821', 'u3174', {}), ('u821', 'u3974', {}), ('u821', 'u4953', {}), ('u821', 'u4412', {}), ('u821', 'u4159', {}), ('u821', 'u1908', {}), ('u821', 'u3979', {}), ('u821', 'u9869', {}), ('u821', 'u4710', {}), ('u821', 'u3083', {}), ('u863', 'u10500', {}), ('u863', 'u2022', {}), ('u863', 'u7963', {}), ('u863', 'u2906', {}), ('u863', 'u2482', {}), ('u863', 'u9997', {}), ('u863', 'u2552', {}), ('u863', 'u2066', {}), ('u901', 'u2022', {}), ('u901', 'u5082', {}), ('u914', 'u2022', {}), ('u914', 'u3231', {}), ('u1254', 'u2737', {}), ('u1254', 'u2289', {}), ('u1254', 'u2643', {}), ('u1254', 'u4329', {}), ('u1254', 'u4761', {}), ('u1407', 'u2643', {}), ('u1407', 'u6081', {}), ('u1407', 'u3658', {}), ('u1468', 'u5993', {}), ('u1468', 'u2643', {}), ('u1468', 'u2022', {}), ('u1468', 'u7418', {}), ('u1468', 'u5337', {}), ('u1468', 'u9869', {}), ('u1908', 'u3174', {}), ('u1908', 'u3979', {}), ('u1908', 'u3974', {}), ('u1908', 'u4953', {}), ('u1908', 'u4412', {}), ('u1908', 'u9869', {}), ('u1908', 'u4159', {}), ('u1908', 'u4710', {}), ('u1908', 'u3083', {}), ('u2022', 'u2482', {}), ('u2022', 'u5993', {}), ('u2022', 'u7623', {}), ('u2022', 'u8135', {}), ('u2022', 'u10500', {}), ('u2022', 'u10340', {}), ('u2022', 'u9997', {}), ('u2022', 'u3231', {}), ('u2022', 'u2643', {}), ('u2022', 'u2906', {}), ('u2022', 'u5082', {}), ('u2022', 'u4199', {}), ('u2022', 'u9869', {}), ('u2022', 'u2066', {}), ('u2022', 'u9866', {}), ('u2022', 'u7418', {}), ('u2022', 'u7963', {}), ('u2022', 'u5337', {}), ('u2022', 'u10603', {}), ('u2022', 'u2552', {}), ('u2066', 'u10500', {}), ('u2066', 'u7963', {}), ('u2066', 'u2906', {}), ('u2066', 'u2482', {}), ('u2066', 'u9997', {}), ('u2066', 'u2552', {}), ('u2137', 'u2643', {}), ('u2137', 'u4513', {}), ('u2289', 'u4329', {}), ('u2289', 'u4761', {}), ('u2289', 'u2643', {}), ('u2289', 'u2737', {}), ('u2482', 'u10500', {}), ('u2482', 'u7963', {}), ('u2482', 'u2906', {}), ('u2482', 'u9997', {}), ('u2482', 'u2552', {}), ('u2552', 'u10500', {}), ('u2552', 'u9997', {}), ('u2552', 'u2906', {}), ('u2552', 'u7963', {}), ('u2643', 'u10090', {}), ('u2643', 'u5993', {}), ('u2643', 'u5693', {}), ('u2643', 'u4329', {}), ('u2643', 'u4761', {}), ('u2643', 'u9869', {}), ('u2643', 'u6081', {}), ('u2643', 'u2737', {}), ('u2643', 'u3658', {}), ('u2643', 'u3243', {}), ('u2643', 'u7418', {}), ('u2643', 'u5337', {}), ('u2643', 'u4513', {}), ('u2643', 'u3271', {}), ('u2737', 'u4329', {}), ('u2737', 'u4761', {}), ('u2906', 'u10500', {}), ('u2906', 'u9997', {}), ('u2906', 'u7963', {}), ('u3083', 'u3174', {}), ('u3083', 'u3974', {}), ('u3083', 'u4953', {}), ('u3083', 'u4412', {}), ('u3083', 'u4159', {}), ('u3083', 'u3979', {}), ('u3083', 'u9869', {}), ('u3083', 'u4710', {}), ('u3174', 'u3974', {}), ('u3174', 'u4953', {}), ('u3174', 'u4412', {}), ('u3174', 'u4159', {}), ('u3174', 'u3979', {}), ('u3174', 'u9869', {}), ('u3174', 'u4710', {}), ('u3231', 'u4159', {}), ('u3243', 'u3271', {}), ('u3271', 'u10090', {}), ('u3271', 'u5693', {}), ('u3658', 'u6081', {}), ('u3974', 'u4953', {}), ('u3974', 'u4412', {}), ('u3974', 'u4159', {}), ('u3974', 'u3979', {}), ('u3974', 'u9869', {}), ('u3974', 'u4710', {}), ('u3979', 'u4953', {}), ('u3979', 'u4412', {}), ('u3979', 'u4159', {}), ('u3979', 'u9869', {}), ('u3979', 'u4710', {}), ('u4159', 'u4412', {}), ('u4159', 'u9869', {}), ('u4159', 'u4710', {}), ('u4159', 'u4953', {}), ('u4329', 'u4761', {}), ('u4412', 'u4953', {}), ('u4412', 'u9869', {}), ('u4412', 'u4710', {}), ('u4710', 'u4953', {}), ('u4710', 'u9869', {}), ('u4953', 'u9869', {}), ('u5337', 'u5993', {}), ('u5337', 'u7418', {}), ('u5337', 'u9869', {}), ('u5693', 'u10090', {}), ('u5993', 'u7418', {}), ('u5993', 'u9869', {}), ('u7418', 'u9869', {}), ('u7623', 'u8135', {}), ('u7623', 'u10603', {}), ('u7623', 'u10340', {}), ('u7623', 'u9866', {}), ('u7963', 'u10500', {}), ('u7963', 'u9997', {}), ('u8135', 'u10603', {}), ('u8135', 'u10340', {}), ('u8135', 'u9866', {}), ('u9866', 'u10603', {}), ('u9866', 'u10340', {}), ('u9997', 'u10500', {}), ('u10340', 'u10603', {})]\n",
    "\n",
    "g_413 = nx.Graph()\n",
    "g_413.add_nodes_from(nodes)\n",
    "g_413.add_edges_from(edges)\n",
    "nx.set_node_attributes(g_413, nodes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Plot the degree distribution of the GitHub collaboration network\n",
    "plt.hist(list(nx.betweenness_centrality(g_413).values()))\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Case Study: Visualization\n",
    "\n",
    "- Practicing drawing Circos, Hive and Arc plots\n",
    "\n",
    "### Connected component subgraphs\n",
    "- The following figure contains two connected component subgraphs\n",
    "- The one on the left, containing the yellow node, and the one on the right containing the purple node.\n",
    "- There are no edges connecting the left graph to the right graph.\n",
    "- A connected component subgraph is a set of nodes connected to one another by some path in the subgraph, and not connected to other nodes in the larger graph.\n",
    "- ![connected_component_subgraph][1]\n",
    "\n",
    "  [1]: https://raw.githubusercontent.com/trenton3983/DataCamp/master/Images/2020-05-21_intro_to_network_analysis_in_python/con_com_sub.JPG"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "random.seed(121)\n",
    "G = nx.erdos_renyi_graph(n=20, p=0.3)\n",
    "ax = nv.circos(g_413)  # node_color_by='key', group_by='key')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "random.seed(60)\n",
    "G = nx.erdos_renyi_graph(n=100, p=0.03)\n",
    "nx.connected_components(G)  # connected_componet_subgraphs() is deprecated"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "subgraphs = [G.subgraph(c) for c in nx.connected_components(G)]\n",
    "subgraphs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for sg in subgraphs:\n",
    "    print(f'Subgraph has {len(sg.nodes())} nodes')\n",
    "    nx.draw(sg, with_labels=True)\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### MatrixPlot\n",
    "\n",
    "Let's now practice making some visualizations. The first one will be the MatrixPlot. In a MatrixPlot, the matrix is the representation of the edges.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Make a MatrixPlot visualization of the largest connected component subgraph, with authors grouped by their user group number.\n",
    " - First, calculate the largest connected component subgraph by using the` nx.connected_component_subgraphs(G)` inside the provided `sorted()` function. Python's built-in [sorted()][1] **function** takes an iterable and returns a sorted list (in ascending order, by default). Therefore, to access the largest connected component subgraph, the statement is sliced with `[-1]`.\n",
    " - Create the `MatrixPlot` object `h`. You have to specify the parameters `graph` and `node_grouping` to be the largest connected component subgraph and `'grouping'`, respectively.\n",
    " - Draw the `MatrixPlot` object to the screen and display the plot.\n",
    " \n",
    " \n",
    "  [1]: https://docs.python.org/2/library/functions.html#sorted"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "subgraphs = [g_413.subgraph(c) for c in nx.connected_components(g_413)]\n",
    "subgraphs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Calculate the largest connected component subgraph: largest_ccs\n",
    "largest_ccs = sorted(subgraphs, key=lambda x: len(x))[-1]\n",
    "\n",
    "# Create the customized MatrixPlot object: h\n",
    "ax = nv.matrix(largest_ccs, group_by='grouping', )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Recall that in a MatrixPlot, nodes are the rows and columns of the matrix, and cells are filled in according to whether an edge exists between the pairs of nodes.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.figure(figsize=(10, 10))\n",
    "nx.draw(largest_ccs, with_labels=True)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ArcPlot\n",
    "\n",
    "Next up, let's use the ArcPlot to visualize the network. You're going to practice sorting the nodes in the graph as well.\n",
    "\n",
    "Note: this exercise may take about 4-7 seconds to execute if done correctly.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Make an ArcPlot of the GitHub collaboration network, with authors sorted by degree. To do this:\n",
    " - Iterate over all the nodes in `G`, including the metadata (by specifying `data=True`).\n",
    " - In each iteration of the loop, calculate the degree of each node `n` with `nx.degree()` and set its `'degree'` attribute. `nx.degree()` accepts two arguments: A graph and a node.\n",
    " - Create the `ArcPlot` object `a` by specifying two parameters: the `graph`, which is `G`, and the `node_order`, which is `'degree'`, so that the nodes are sorted.\n",
    " - Draw the `ArcPlot` object to the screen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Iterate over all the nodes in G, including the metadata\n",
    "for n, d in g_413.nodes(data=True):\n",
    "\n",
    "    # Calculate the degree of each node: G.node[n]['degree']\n",
    "    g_413.nodes[n]['degree'] = nx.degree(g_413, n)\n",
    "\n",
    "# Create the ArcPlot object: a\n",
    "plt.figure(figsize=(10, 10))\n",
    "ax = nv.arc(g_413, sort_by='degree', group_by='grouping', node_color_by='grouping')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### CircosPlot\n",
    "\n",
    "Finally, you're going to make a CircosPlot of the network!\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Make a CircosPlot of the network, again, with GitHub users sorted by their degree, and grouped and `coloured` by their 'grouping' key. To do this:\n",
    " - Iterate over all the nodes in `G`, including the metadata (by specifying `data=True`).\n",
    " - In each iteration of the loop, calculate the degree of each node `n` with `nx.degree()` and set its `'degree'` attribute.\n",
    " - Create the `CircosPlot` object `c` by specifying three parameters in addition to the graph `G`: the `node_order`, which is `'degree'`, the `node_grouping` and the `node_color`, which are both `'grouping'`.\n",
    " - Draw the `CircosPlot` object to the screen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Iterate over all the nodes in G, including the metadata\n",
    "for n, d in g_413.nodes(data=True):\n",
    "\n",
    "    # Calculate the degree of each node: G.node[n]['degree']\n",
    "    g_413.nodes[n]['degree'] = nx.degree(g_413, n)\n",
    "\n",
    "# Create the ArcPlot object: a\n",
    "plt.figure(figsize=(10, 10))\n",
    "a = nv.circos(g_413, sort_by='degree', group_by='grouping', node_color_by='grouping')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**This CircosPlot provides a compact alternative to the ArcPlot. It is easy to see in this plot that most users belong to one group.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Case Study: Cliques\n",
    "\n",
    "- A group of nodes that are fully connected to one another.\n",
    "- The simplest clique is an edge and the simplest \"complex\" clique is a triangle.\n",
    "- A maximal clique is a clique that cannot be extended by adding another node in the graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = nx.erdos_renyi_graph(n=100, p=0.15)\n",
    "print(nx.find_cliques(G))\n",
    "\n",
    "clique_lens = Counter([len(clique) for clique in nx.find_cliques(G)])\n",
    "clique_lens"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Finding cliques (I)\n",
    "\n",
    "You're now going to practice finding cliques in `G`. Recall that cliques are \"groups of nodes that are fully connected to one another\", while a maximal clique is a clique that cannot be extended by adding another node in the graph.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Count the number of maximal cliques present in the graph and print it.\n",
    " - Use the `nx.find_cliques()` function of `G` to find the maximal cliques.\n",
    " - The `nx.find_cliques()` function returns a generator object. To count the number of maximal cliques, you need to first convert it to a list with `list()` and then use the `len()` function. Place this inside a `print()` function to print it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cliques = sorted([len(cl) for cl in nx.find_cliques(g_413)], reverse=True)\n",
    "print(cliques)\n",
    "print(f'There are {len(cliques)} cliques.')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Finding cliques (II)\n",
    "\n",
    "Let's continue by finding a particular maximal clique, and then plotting that clique.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Find the author(s) that are part of the largest maximal clique, and plot the subgraph of that/one of those clique(s) using a CircosPlot. To do this:\n",
    " - Use the `nx.find_cliques()` function to calculate the maximal cliques in `G`. Place this within the provided `sorted()` function to calculate the largest maximal clique.\n",
    " - Create the subgraph consisting of the largest maximal clique using the `.subgraph()` method and `largest_clique`.\n",
    " - Create the `CircosPlot` object using the subgraph `G_lc` (without any other arguments) and plot it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Find the author(s) that are part of the largest maximal clique: largest_clique\n",
    "largest_clique = sorted(nx.find_cliques(g_413), key=lambda x:len(x))[-1]\n",
    "\n",
    "# Create the subgraph of the largest_clique: G_lc\n",
    "G_lc = g_413.subgraph(largest_clique)\n",
    "\n",
    "for n, d in G_lc.nodes(data=True):\n",
    "    # add the node as a key - value pair in the data, so the key can be used to annotate in the new API\n",
    "    G_lc.nodes[n]['node'] = n\n",
    "    print(n, d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create the CircosPlot object: c\n",
    "plt.figure(figsize=(10, 10))\n",
    "c = nv.circos(G_lc)\n",
    "annotate.circos_group(G_lc, group_by='node', radius_offset=1, midpoint=False)\n",
    "\n",
    "# Draw the CircosPlot to the screen\n",
    "print(f'The largest maximal clique consists of {len(largest_clique)} users')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Case Study: Final Tasks\n",
    "\n",
    "- Find important GitHub users based on their collaborative relationships\n",
    " - Look for GitHub users that share collaborations with the most number of other users.\n",
    " - _degree centrality_\n",
    "- Find the largest communities of collaborators.\n",
    " - You'll be looking for the largest communities of collaborators.\n",
    " - _maximal clique_\n",
    "- Guild a recommendation system for GitHub users based on the concept of open triangles.\n",
    " - _open triangles_: I'm connected to two people who are not connected to one another"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Finding important collaborators\n",
    "\n",
    "You'll now look at important nodes once more. Here, you'll make use of the `degree_centrality()` and `betweenness_centrality()` functions in NetworkX to compute each of the respective centrality scores, and then use that information to find the \"important nodes\". In other words, your job in this exercise is to find the user(s) that have collaborated with the most number of users.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Compute the degree centralities of `G`. Store the result as `deg_cent`.\n",
    "- Compute the maximum degree centrality. Since `deg_cent` is a dictionary, you'll have to use the `.values()` method to get a list of its values before computing the maximum degree centrality with `max()`.\n",
    "- Identify the most prolific collaborators using a list comprehension:\n",
    " - Iterate over the degree centrality dictionary `deg_cent` that was computed earlier using its `.items()` method. What condition should be satisfied if you are seeking to find user(s) that have collaborated with the most number of users? _Hint_: It has do to with the maximum degree centrality.\n",
    "- Hit 'Submit Answer' to see who the most prolific collaborator(s) is/are!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Compute the degree centralities of G: deg_cent\n",
    "deg_cent = nx.degree_centrality(g_413)\n",
    "\n",
    "# Sorting the dictionary\n",
    "deg_cent = {k: v for k, v in sorted(deg_cent.items(), key=lambda item: item[1], reverse=True)}\n",
    "\n",
    "# Compute the maximum degree centrality: max_dc\n",
    "max_dc = max(list(deg_cent.values()))\n",
    "\n",
    "# Find the user(s) that have collaborated the most: prolific_collaborators\n",
    "prolific_collaborators = [n for n, dc in deg_cent.items() if dc == max_dc]\n",
    "\n",
    "# Print the most prolific collaborator(s)\n",
    "print(f'The most prolific collaborator(s): {prolific_collaborators}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "max_dc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "deg_cent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Characterizing editing communities\n",
    "\n",
    "You're now going to combine what you've learned about the BFS algorithm and concept of maximal cliques to visualize the network with an ArcPlot.\n",
    "\n",
    "The largest maximal clique in the Github user collaboration network has been assigned to the subgraph `G_lmc`. Note that for `NetworkX` version 2.x and later, `G.subgraph(nodelist)` returns only an immutable view on the original graph. We must explicitly ask for a `.copy()` of the graph to obtain a mutatable version.\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Go out 1 degree of separation from the clique, and add those users to the subgraph. Inside the first `for` loop:\n",
    "- Add nodes to `G_lmc` from the neighbors of `G` using the `.add_nodes_from()` and `.neighbors()` methods.\n",
    "- Using the `.add_edges_from()`, method, add edges to `G_lmc` between the current node and all its neighbors. To do this, you'll have create a list of tuples using the `zip()` function consisting of the current node and each of its neighbors. The first argument to `zip()` should be `[node]*len(list(G.neighbors(node)))`, and the second argument should be the neighbors of `node`.\n",
    "- Record each node's degree centrality score in its node metadata.\n",
    "- Do this by assigning `nx.degree_centrality(G_lmc)[n]` to `G_lmc.node[n]['degree centrality']` in the second `for` loop.\n",
    "- Visualize this network with an ArcPlot sorting the nodes by degree centrality (you can do this using the keyword argument `node_order='degree centrality'`).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Identify the largest maximal clique: largest_max_clique\n",
    "largest_max_clique = set(sorted(nx.find_cliques(g_413), key=lambda x: len(x))[-1])\n",
    "print(largest_max_clique)\n",
    "\n",
    "# Create a subgraph from the largest_max_clique: G_lmc\n",
    "G_lmc = g_413.subgraph(largest_max_clique).copy()\n",
    "display(G_lmc)\n",
    "\n",
    "# Go out 1 degree of separation\n",
    "for node in list(G_lmc.nodes()):\n",
    "    G_lmc.add_nodes_from(g_413.neighbors(node))\n",
    "    G_lmc.add_edges_from(zip([node]*len(list(g_413.neighbors(node))), g_413.neighbors(node)))\n",
    "    \n",
    "# Record each node's degree centrality score\n",
    "for n in G_lmc.nodes():\n",
    "    G_lmc.nodes[n]['degree centrality'] = nx.degree_centrality(G_lmc)[n]\n",
    "\n",
    "# Create the ArcPlot object: a\n",
    "a = nv.arc(G_lmc, sort_by='degree centrality')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Recommending co-editors who have yet to edit together\n",
    "\n",
    "Finally, you're going to leverage the concept of open triangles to recommend users on GitHub to collaborate!\n",
    "\n",
    "**Instructions**\n",
    "\n",
    "- Compile a list of GitHub users that should be recommended to collaborate with one another. To do this:\n",
    " - In the first `for` loop, iterate over all the nodes in `G`, including the metadata (by specifying `data=True`).\n",
    " - In the second `for` loop, iterate over all the possible triangle `combinations`, which can be identified using the combinations() function with a `size` of `2`.\n",
    " - If `n1` and `n2` **do not** have an edge between them, a collaboration between these two nodes (users) **should** be recommended, so increment the `(n1), (n2)` value of the `recommended` dictionary in this case. You can check whether or not `n1` and `n2` have an edge between them using the `.has_edge()` method.\n",
    "- Using a list comprehension, identify the top 10 pairs of users that should be recommended to collaborate. The _iterable_ should be the key-value pairs of the `recommended` dictionary (which can be accessed with the `.items()` method), while the conditional should be satisfied if `count` is _greater_ than the top 10 in `all_counts`. Note that `all_counts` is sorted in ascending order, so you can access the top 10 with `all_counts[-10]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = nx.Graph(Gh)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Initialize the defaultdict: recommended\n",
    "recommended = defaultdict(int)\n",
    "\n",
    "# Iterate over all the nodes in G\n",
    "for n, d in g_413.nodes(data=True):\n",
    "\n",
    "    # Iterate over all possible triangle relationship combinations\n",
    "    for n1, n2 in combinations(g_413.neighbors(n), 2):\n",
    "\n",
    "        # Check whether n1 and n2 do not have an edge\n",
    "        if not g_413.has_edge(n1, n2):\n",
    "\n",
    "            # Increment recommended\n",
    "            recommended[((n1), (n2))] += 1\n",
    "\n",
    "# Identify the top 10 pairs of users\n",
    "all_counts = sorted(recommended.values())\n",
    "top10_pairs = [pair for pair, count in recommended.items() if count > all_counts[-10]]\n",
    "print(f'Pairs of users who should collaborate: {top10_pairs}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.figure(figsize=(15, 15))\n",
    "nx.draw(g_413, with_labels=True)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What You've Learned\n",
    "\n",
    "- The basics of networks and network analysis\n",
    "- How to find important nodes\n",
    "- How to identify communities of nodes\n",
    "- How to apply these concepts in case studies\n",
    "- How to use the NetworkX and nxviz packages to model, analyze and visualized network data.\n",
    "- How to write algorithms that operate on networks to do useful things like finding paths.\n",
    "- You've seen practical application of network analysis, and even tried your hand at implementing them."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Certificate\n",
    "\n",
    "![certificate](https://raw.githubusercontent.com/trenton3983/DataCamp/master/Images/2020-05-21_intro_to_network_analysis_in_python/2020-05-31_DataCamp_intro_to_network_analysis_in_python.jpg)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.5"
  },
  "toc-autonumbering": true
 },
 "nbformat": 4,
 "nbformat_minor": 4
}