Network Analysis I.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Intro to networks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Basics of drawing of a network using NetworkX**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Import necessary modules\n",
    "import matplotlib.pyplot as plt\n",
    "import networkx as nx\n",
    "\n",
    "# Draw the graph to screen\n",
    "nx.draw(T_sub)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Queries on a graph**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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'] < date(2010, 1, 1)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Specifying a weight on edges**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Set the weight of the edge\n",
    "T.edge[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.edge[u][v]['weight'] = 1.1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Checking whether there are self-loops in the graph**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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(data=False):\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",
    "assert T.number_of_selfloops() == len(find_selfloop_nodes(T))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Visualizing using Matrix plots**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Import nxviz\n",
    "import nxviz as nv\n",
    "\n",
    "# Create the MatrixPlot object: m\n",
    "m = nv.MatrixPlot(T)\n",
    "\n",
    "# Draw m to the screen\n",
    "m.draw()\n",
    "\n",
    "# Display the plot\n",
    "plt.show()\n",
    "\n",
    "# Convert T to a matrix format: A\n",
    "A = nx.to_numpy_matrix(T)\n",
    "\n",
    "# Convert A back to the NetworkX form as a directed graph: T_conv\n",
    "T_conv = nx.from_numpy_matrix(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**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Import necessary modules\n",
    "import matplotlib.pyplot as plt\n",
    "from nxviz import CircosPlot\n",
    "\n",
    "# Create the CircosPlot object: c\n",
    "c = CircosPlot(T)\n",
    "\n",
    "# Draw c to the screen\n",
    "c.draw()\n",
    "\n",
    "# Display the plot\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Visualizing using Arc plots**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Import necessary modules\n",
    "import matplotlib.pyplot as plt\n",
    "from nxviz import ArcPlot \n",
    "\n",
    "# Create the un-customized ArcPlot object: a\n",
    "a = ArcPlot(T)\n",
    "\n",
    "# Draw a to the screen\n",
    "a.draw()\n",
    "\n",
    "# Display the plot\n",
    "plt.show()\n",
    "\n",
    "# Create the customized ArcPlot object: a2\n",
    "a2 = ArcPlot(T, node_order = 'category', node_color='category')\n",
    "\n",
    "# Draw a2 to the screen\n",
    "a2.draw()\n",
    "\n",
    "# Display the plot\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Important nodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Compute number of neighbors for each node**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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(data=False):\n",
    "    \n",
    "        # Check if the number of neighbors of n matches m\n",
    "        if len(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": [
    "**Compute degree distribution**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The basic syntax for a list comprehension is [output expression for iterator variable in iterable]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Compute the degree of every node: degrees\n",
    "degrees = [len(T.neighbors(n)) for n in T.nodes()]\n",
    "\n",
    "# Print the degrees\n",
    "print(degrees)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Degree centrality distribution**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Import matplotlib.pyplot\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "# Compute the degree centrality of the Twitter network: deg_cent\n",
    "deg_cent = nx.degree_centrality(T)\n",
    "\n",
    "# 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": [
    "**Shortest Path I **"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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 cells 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**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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",
    "            # 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**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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": [
    "**NetworkX betweenness centrality on a social network**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Compute the betweenness centrality of T: bet_cen\n",
    "bet_cen = nx.betweenness_centrality(T)\n",
    "\n",
    "# Compute the degree centrality of T: deg_cen\n",
    "deg_cen = nx.degree_centrality(T)\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.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deep dive - Twitter network**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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(top_dc)\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**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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)\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)[node] == max(nx.betweenness_centrality(T).values())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Structures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Identifying triangle relationships**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from itertools import combinations\n",
    "\n",
    "# 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"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Finding nodes involved in triangles**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from itertools import combinations\n",
    "\n",
    "# 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",
    "            \n",
    "    return triangle_nodes\n",
    "    \n",
    "# Write the assertion statement\n",
    "assert len(nodes_in_triangle(T, 1)) == 35"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Finding open triangles**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from itertools import combinations\n",
    "\n",
    "# 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(data=False):\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(num_open_triangles)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Finding all maximal cliques of size \"n\"**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Define maximal_cliques()\n",
    "def maximal_cliques(G, size):\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) == size:\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,3)) == 33"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Subgraphs I**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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 G.subgraph(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(n)\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)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "**Subgraph II**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Extract the nodes of interest: nodes\n",
    "nodes = [n for n, d in T.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.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.subgraph(nodeset)\n",
    "\n",
    "# Draw T_sub to the screen\n",
    "nx.draw(T_sub)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Case study"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** ArcPlot**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Import necessary modules\n",
    "from nxviz.plots import ArcPlot\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "# Iterate over all the nodes in G, including the metadata\n",
    "for n, d in G.nodes(data=True):\n",
    "\n",
    "    # Calculate the degree of each node: G.node[n]['degree']\n",
    "    G.node[n]['degree'] = nx.degree(G, n)\n",
    "    \n",
    "# Create the ArcPlot object: a\n",
    "a = ArcPlot(graph=G, node_order='degree')\n",
    "\n",
    "# Draw the ArcPlot to the screen\n",
    "a.draw()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**CircosPlot**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Import necessary modules\n",
    "from nxviz import CircosPlot\n",
    "import matplotlib.pyplot as plt \n",
    " \n",
    "# Iterate over all the nodes, including the metadata\n",
    "for n, d in G.nodes(data=True):\n",
    "\n",
    "    # Calculate the degree of each node: G.node[n]['degree']\n",
    "    G.node[n]['degree'] = nx.degree(G, n)\n",
    "\n",
    "# Create the CircosPlot object: c\n",
    "c = CircosPlot(graph=G, node_order='degree', node_grouping='grouping', node_color='grouping')\n",
    "\n",
    "# Draw the CircosPlot object to the screen\n",
    "c.draw()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Finding cliques (I)**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Finding maximal clique**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Maximal clique - a clique that cannot be extented by adding another member to the group."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Import necessary modules\n",
    "import networkx as nx\n",
    "from nxviz import CircosPlot\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "# Find the author(s) that are part of the largest maximal clique: largest_clique\n",
    "largest_clique = sorted(nx.find_cliques(G), key=lambda x:len(x))[-1]\n",
    "\n",
    "# Create the subgraph of the largest_clique: G_lc\n",
    "G_lc = G.subgraph(largest_clique)\n",
    "\n",
    "# Create the CircosPlot object: c\n",
    "c = CircosPlot(G_lc)\n",
    "\n",
    "# Draw the CircosPlot to the screen\n",
    "c.draw()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Final tasks:**\n",
    "    \n",
    "1. Find important users - (degree of centrality)\n",
    "2. Find largest communities of collaborators - (maximal clique concept)\n",
    "3. Build a collaboration recommendation system - (open triangles)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Finding important users**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Compute the degree centralities of G: deg_cent\n",
    "deg_cent = nx.degree_centrality(G)\n",
    "\n",
    "# Compute the maximum degree centrality: max_dc\n",
    "max_dc = max(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(prolific_collaborators)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Characterizing editing communities**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Import necessary modules\n",
    "from nxviz import ArcPlot\n",
    "import matplotlib.pyplot as plt\n",
    " \n",
    "# Identify the largest maximal clique: largest_max_clique\n",
    "largest_max_clique = set(sorted(nx.find_cliques(G), key=lambda x: len(x))[-1])\n",
    "\n",
    "# Create a subgraph from the largest_max_clique: G_lmc\n",
    "G_lmc = G.subgraph(largest_max_clique)\n",
    "\n",
    "# Go out 1 degree of separation\n",
    "for node in G_lmc.nodes():\n",
    "    G_lmc.add_nodes_from(G.neighbors(node))\n",
    "    G_lmc.add_edges_from(zip([node]*len(G.neighbors(node)), node))\n",
    "\n",
    "# Record each node's degree centrality score\n",
    "for n in G_lmc.nodes():\n",
    "    G_lmc.node[n]['degree centrality'] = nx.degree_centrality(G_lmc)[n]\n",
    "        \n",
    "# Create the ArcPlot object: a\n",
    "a = ArcPlot(G_lmc, node_order='degree centrality')\n",
    "\n",
    "# Draw the ArcPlot to the screen\n",
    "a.draw()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Recommending co-editors who have yet to edit together**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Import necessary modules\n",
    "from itertools import combinations\n",
    "from collections import defaultdict\n",
    "\n",
    "# Initialize the defaultdict: recommended\n",
    "recommended = defaultdict(int)\n",
    "\n",
    "# Iterate over all the nodes in G\n",
    "for n, d in G.nodes(data=True):\n",
    "\n",
    "    # Iterate over all possible triangle relationship combinations\n",
    "    for n1, n2 in combinations(G.neighbors(n), 2):\n",
    "    \n",
    "        # Check whether n1 and n2 do not have an edge\n",
    "        if not G.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(top10_pairs)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}