0_Networks.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CSS Lab: Networks\n",
    "This lab demonstrates how to use common tools to analyze the structure of several networks. Topics covered include visualization, centrality measures, shortest paths, and affiliation networks. At the end of the lab, you will be able to visualze and perform an analysis of your own social network.\n",
    "\n",
    "__NOTE:__ When running this lab in the course environment, click on your website address and remove \"/lab\" from the address to launch the notebook in Jupyter Notebook."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Contents\n",
    "\n",
    "1. [Background](#Section-1%3A-Background)\n",
    "2. [Setup](#Section-2%3A-Setup)\n",
    "3. [Build and Visualize a Network](#Section-3%3A-Build-and-Visualize-a-Network)\n",
    "    * [3.1 Load the Network](#3.1-Load-the-Network)\n",
    "    * [3.2 Visualize the Network](#3.2-Visualize-the-Network)\n",
    "4. [Centrality measures](#Section-4%3A-Centrality-Measures)\n",
    "    * [4.1 Load the Network](#4.1-Load-the-Network)\n",
    "    * [4.2 Visualize the Network](#4.2-Visualize-the-Network)\n",
    "    * [4.3 Find Centrality](#4.3-Find-Centrality)\n",
    "    * [4.4 Compare Centrality Measures](#4.4-Compare-Centrality-Measures)\n",
    "5. [Reflection](#Section-6%3A-Reflection)\n",
    "6. [References](#References)\n",
    "    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Section 1: Background\n",
    "Many types of social science data can be represented and analyzed as networks. This notebook looks at networks made that represent the relationships between people: social networks. Social networks play an important role in the spread of information across groups of people. One reason to study social networks is to better understand social movements, why they spread or fizzle out, and the structure of relationships that make up those movements. In this notebook, you will analyze two social networks from the American Revolution: one historical (New England revolutionary groups) (Healey2013), and one fictional (co-appearences in the musical _Hamilton_). You will also have a chance to analyze your own social network.\n",
    "\n",
    "## Section 2: Setup\n",
    "We import several libraries, including `networkx` for network algorithms, `pandas` for data processing, and `vis` for visualization. We also define some helper functions used by several of the sections in this notebook."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# %pylab inline\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "from IPython.display import display, Javascript, HTML\n",
    "import itertools\n",
    "import json\n",
    "import math\n",
    "import urllib.request\n",
    "import networkx as nx\n",
    "import networkx as networkx\n",
    "import networkx.algorithms as nxalg\n",
    "import networkx.algorithms.community as nxcom\n",
    "import networkx.readwrite as nxrw\n",
    "import pandas as pd\n",
    "import warnings\n",
    "warnings.filterwarnings('ignore')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Load vis.js \n",
    "The following cell import and test `vis.js`, the visualization library used by this lab.\n",
    "- If you get an error, `Javascript Error: require is not defined`, it is likely because you are running this notebook in `jupyter lab`. You need to click `Open in...` on the top right corner of the page, select `NbClassic` instead, and then rerun this notebook. This error should not happen in the classic `jupyter notebook`.  \n",
    "- Once you are running this file in NbClass, you should be able to see a color network diagram in the first cell.\n",
    "<div id=\"mynetwork\">You should see a network below after executing the next cell</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%javascript\n",
    "require.config({\n",
    "    paths: {\n",
    "        vis: 'https://cdnjs.cloudflare.com/ajax/libs/vis/4.21.0/vis'\n",
    "    }\n",
    "});\n",
    "\n",
    "require(['vis'], function(vis){\n",
    "var nodes = [{id: 1, label: 'Using', group: 'action'}, {id: 2, label: 'JavaScript', group: 'tool'},\n",
    "        {id: 3, label: 'Vis', group: 'tool'}, {id: 31, label: 'JS', group: 'tool'},\n",
    "        {id: 32, label: 'Network', group: 'tool'}, {id: 4, label: 'to display', group: 'action'},\n",
    "        {id: 5, label: 'graphs', group: 'data'}, {id: 6, label: 'networks', group: 'data'},\n",
    "        {id: 7, label: 'in', group: 'action'}, {id: 8, label: 'web pages', group: 'location'},\n",
    "        {id: 9, label: 'notebooks', group: 'location'},\n",
    "];\n",
    "var edges = [{from: 1, to: 2}, {from: 1, to: 3}, {from: 3, to: 31},\n",
    "    {from: 3, to: 32}, {from: 32, to: 4}, {from: 31, to: 4},\n",
    "    {from: 2, to: 4}, {from: 6, to: 4}, {from: 5, to: 4},\n",
    "    {from: 5, to: 7}, {from: 6, to: 7}, {from: 7, to: 8}, {from: 7, to: 9},\n",
    "];\n",
    "// create a network\n",
    "var data= {\n",
    "    nodes: nodes,\n",
    "    edges: edges,\n",
    "};\n",
    "var options = {\n",
    "    width: '800px',\n",
    "    height: '400px'\n",
    "};\n",
    "\n",
    "var container = document.getElementById('mynetwork');\n",
    "var network = new vis.Network(container, data, options);\n",
    "});"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Load custom CSS for `vis`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "HTML('<style>{}</style>'.format(open('custom.css').read()));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Helper functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     0
    ]
   },
   "outputs": [],
   "source": [
    "# Helper functions\n",
    "\n",
    "# Standardize a vector to 0 mean and unit variance\n",
    "def scale(v):\n",
    "    return (v - v.mean()) / v.std()\n",
    "\n",
    "# Return a data frame sorted by a node's centrality relative the mean of its centralities\n",
    "def rel_centrality(df, measure, labels=dict()):\n",
    "    name = 'rel_{}'.format(measure)\n",
    "    return pd.DataFrame({\n",
    "        name: scale(df[measure]) / df['mean_centrality'],\n",
    "        \"label\": [labels.get(x, x) for x in df.index]\n",
    "    })\n",
    "\n",
    "def get_colors():\n",
    "    phi = (1 + math.sqrt(5)) / 2\n",
    "    color = []\n",
    "    for i in range(1, 20):\n",
    "        theta = phi * i * math.pi * 2\n",
    "        x = 128 + math.floor(64*math.sin(theta))\n",
    "        y = 128 + math.floor(64*math.cos(theta))\n",
    "        color.append((x, x, y))\n",
    "    return color\n",
    "\n",
    "def visjs_network(\n",
    "        nodes_list,\n",
    "        edges_dict,\n",
    "        node_size_field=None,\n",
    "        node_size_multiplier=1,\n",
    "        edge_width_field=None,\n",
    "        edge_width=None,\n",
    "        edge_arrow_to=None,\n",
    "        edge_arrow_to_scale_factor=1,\n",
    "        edge_smooth_enabled=False,\n",
    "        edge_smooth_type=\"curvedCW\",\n",
    "        graph_id=\"vis-output\"):\n",
    "    \n",
    "    # Configure nodes\n",
    "    for node in nodes_list:\n",
    "        if node_size_field is not None:\n",
    "            node['size'] = node[node_size_field] * node_size_multiplier\n",
    "        node['title'] = node['label']\n",
    "        node['font'] = { 'size': 14 }\n",
    "        node['shadow'] = True\n",
    "    node_json = json.dumps(nodes_list)\n",
    "    \n",
    "    # Configure edges\n",
    "    for edge in edges_dict:\n",
    "        color = edge['color']\n",
    "        edge['color'] = {\n",
    "            'color': color\n",
    "        }\n",
    "    edge_json = json.dumps(edges_dict)\n",
    "\n",
    "    js = Javascript(\"\"\"\n",
    "(function(element) {{\n",
    "    require(['vis'], function(vis) {{\n",
    "      // create an array with nodes\n",
    "      var nodes = new vis.DataSet({});\n",
    "      console.log(nodes)\n",
    "\n",
    "      // create an array with edges\n",
    "      var edges = new vis.DataSet({});\n",
    "      console.log(edges)\n",
    "\n",
    "      // create a network\n",
    "      var id = 'container-' + {}\n",
    "      element.append('<div style=\"width:800px;height:800px\" id=\"' + id + '\">hi</div>')\n",
    "      var container = document.getElementById(id);\n",
    "      element.append(container)\n",
    "      var data = {{\n",
    "        nodes: nodes,\n",
    "        edges: edges\n",
    "      }};\n",
    "      var options = {{\n",
    "          physics: {{\n",
    "              enabled: false\n",
    "          }},\n",
    "          interaction: {{\n",
    "              hover: true\n",
    "          }}\n",
    "      }};\n",
    "      var network = new vis.Network(container, data, options);\n",
    "    }})\n",
    "}})(element);\n",
    "    \"\"\".format(node_json, edge_json, graph_id))\n",
    "    return js\n",
    "\n",
    "def visualize_visjs(\n",
    "        G, communities=None, colors=None, default_color=\"192,192,192\",\n",
    "        node_size_field=\"node_size\", layout=\"spring\", scale=500, pos=None,\n",
    "        groups=None, weight=None, labels=dict(), title=\"\"):\n",
    "    # Get list of nodes and edges\n",
    "    nodes = list(G.nodes())\n",
    "    edges = list(G.edges())\n",
    "    # Change node shapes for bipartite graph\n",
    "    if groups is None:\n",
    "        node_shapes = dict()\n",
    "        node_sizes = dict()\n",
    "        node_colors = dict()\n",
    "    else:\n",
    "        node_shapes = dict((n, \"square\") for n in groups)\n",
    "        node_sizes = dict((n, 15) for n in groups)\n",
    "        node_colors = dict((n, \"192,128,0\") for n in groups)\n",
    "    # Per-node properties\n",
    "    nodes_dict = dict((n, {\n",
    "        \"id\": n,\n",
    "        \"label\": labels.get(n, n),\n",
    "        \"node_size\": node_sizes.get(n, 5),\n",
    "        \"shape\": node_shapes.get(n, \"dot\")\n",
    "        }) for n in nodes)\n",
    "    # Generate a layout for the nodes\n",
    "    edge_smooth_enabled = False\n",
    "    edge_width = 4\n",
    "    edge_arrow_scale = 2\n",
    "    if communities is not None and pos is None:\n",
    "        # Generate initial positions based on community\n",
    "        phi = 3.14 / len(nodes)\n",
    "        community_node = []\n",
    "        # Create list of nodes and their communities\n",
    "        for i, com in enumerate(sorted(communities, key=lambda x: len(x), reverse=True)):\n",
    "            for node in com:\n",
    "                community_node.append((i, node))\n",
    "        # Sort by community and\n",
    "        community_node = sorted(community_node)\n",
    "        # Generate initial position by placing communities around a circle\n",
    "        pos = dict((d[1], (math.cos(i*phi), math.sin(i*phi))) for i, d in enumerate(community_node))\n",
    "    else:\n",
    "        pos = None\n",
    "    if layout == \"circle\":\n",
    "        pos = nx.circular_layout(G, scale=scale)\n",
    "    elif layout == \"spring\":\n",
    "        pos = nx.spring_layout(G, k=3/math.sqrt(len(nodes)), scale=scale, pos=pos)\n",
    "    else:\n",
    "        edge_smooth_enabled = True\n",
    "    # Assign position\n",
    "    for n in nodes:\n",
    "        nodes_dict[n][\"x\"] = pos[n][0]\n",
    "        nodes_dict[n][\"y\"] = pos[n][1]\n",
    "    # Calculate bounds for scaling\n",
    "    x_min = min(pos.values(), key=lambda x: x[0])[0]\n",
    "    x_max = max(pos.values(), key=lambda x: x[0])[0]\n",
    "    y_min = min(pos.values(), key=lambda x: x[1])[1]\n",
    "    y_max = max(pos.values(), key=lambda x: x[1])[1]\n",
    "    x_range = x_max - x_min\n",
    "    y_range = y_max - y_min\n",
    "    max_range = max(x_range, y_range)\n",
    "    # If we have communities, assign color based on community\n",
    "    if colors is None:\n",
    "        colors = [\"{},{},{}\".format(*c) for c in get_colors()]\n",
    "    if communities is not None:\n",
    "        for i, com in enumerate(sorted(communities, key=lambda x: len(x), reverse=True)):\n",
    "            for node in com:\n",
    "                try:\n",
    "                    nodes_dict[node][\"color\"] = \"rgba({},1)\".format(colors[i])\n",
    "                    nodes_dict[node][\"color_index\"] = i\n",
    "                except IndexError:\n",
    "                    nodes_dict[node][\"color\"] = \"rgba({},1)\".format(default_color)\n",
    "    # Update color for bipartite nodes\n",
    "    for node, node_attr in nodes_dict.items():\n",
    "        if node in node_colors:\n",
    "            node_attr[\"color\"] = \"rgba({},1)\".format(node_colors[node])\n",
    "    # Map node labels to contiguous ids\n",
    "    node_map = dict(zip(nodes,range(len(nodes))))\n",
    "    # Determine edge colors\n",
    "    edge_colors_idx = {}\n",
    "    for source, target in edges:\n",
    "        source_color = nodes_dict[source].get(\"color_index\", None)\n",
    "        target_color = nodes_dict[target].get(\"color_index\", None)\n",
    "        if source_color == target_color and source_color is not None:\n",
    "            edge_colors_idx[(source, target)] = source_color\n",
    "    edge_colors = dict(\n",
    "        (e,colors[c])\n",
    "        for e, c in edge_colors_idx.items() if c < len(colors))\n",
    "    # Per-edge properties, use contiguous ids to identify nodes\n",
    "    edge_scale = math.ceil(max_range / 200)\n",
    "    edges_dict = []\n",
    "    for source, target, data in G.edges(data=True):\n",
    "        edge = {\n",
    "            \"from\": source,\n",
    "            \"to\": target,\n",
    "            \"title\":'test',\n",
    "            \"color\": \"rgba({},0.3)\".format(edge_colors.get((source,target), default_color)),\n",
    "            \"edge_width_field\": \"value\",\n",
    "            \"value\": data.get(\"value\", 1) * edge_scale\n",
    "        }\n",
    "        edges_dict.append(edge)\n",
    "    # Convert nodes dict to node list\n",
    "    nodes_list = [nodes_dict[n] for n in nodes]\n",
    "    # Check for directed graph\n",
    "    if G.__class__ == nx.classes.digraph.DiGraph:\n",
    "        directed = True\n",
    "    else:\n",
    "        directed = False\n",
    "    # Call visjs\n",
    "    return visjs_network(\n",
    "        nodes_list, edges_dict,\n",
    "        node_size_field=\"node_size\",\n",
    "        node_size_multiplier=5.0,\n",
    "        edge_width_field=\"value\",\n",
    "        edge_width=edge_width,\n",
    "        edge_arrow_to=directed,\n",
    "        edge_arrow_to_scale_factor=edge_arrow_scale,\n",
    "        edge_smooth_enabled=edge_smooth_enabled,\n",
    "        edge_smooth_type=\"curvedCW\",\n",
    "        graph_id=hash(title))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Section 3: Build and Visualize a Network\n",
    "\n",
    "This section loads network data from a file and explores its basic properties. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": []
   },
   "outputs": [],
   "source": [
    "# Helper functions\n",
    "\n",
    "def load_hamilton_affiliation():\n",
    "    B = nxrw.adjlist.read_adjlist(\"external/hamilton.csv\", delimiter=\"; \", comments=\"%\")\n",
    "    return B\n",
    "\n",
    "def load_hamilton(threshold=None):\n",
    "    # Load the song-character affiliation network\n",
    "    B = load_hamilton_affiliation()\n",
    "    # Get list of songs from the file\n",
    "    songs = set()\n",
    "    with open(\"external/hamilton.csv\") as f:\n",
    "        f.readline()\n",
    "        for row in f:\n",
    "            songs.add(row.split(\"; \")[0])\n",
    "    # Deduce list of charactes\n",
    "    characters = set(B.nodes()) - songs\n",
    "    # Project the affiliation network onto the set of characters\n",
    "    G = nxalg.bipartite.projection.weighted_projected_graph(B, characters)\n",
    "    # Threshold\n",
    "    if threshold is not None:\n",
    "        for s, t, data in list(G.edges(data=True)):\n",
    "            if data[\"weight\"] < threshold:\n",
    "                G.remove_edge(s,t)\n",
    "    return G"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1 Load the Network\n",
    "\n",
    "The next cell loads data from a file using the `networkx` library,\n",
    "and displays a list of nodes in the network.\n",
    "This example uses characters from the play _Hamilton_."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G_hamilton = load_hamilton()\n",
    "sorted(G_hamilton.nodes())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that you know the labels of the nodes, you can see which nodes are connected by an edge.\n",
    "In this case, two nodes are connected by an edge if the corresponding characters have parts in at least one song together.\n",
    "The next cell chooses a single node and prints a list of all the other nodes it's connected to.\n",
    "These nodes are called its neighbors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted(G_hamilton.neighbors('E. Schuyler'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2 Visualize the Network\n",
    "In these visualizations, each circle represents a node.\n",
    "Edges between two nodes are represented by drawing a line between them.\n",
    "\n",
    "There are many ways to draw a network.\n",
    "One simple way is to space all the nodes evenly around a circle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "visualize_visjs(G_hamilton, layout=\"circle\", title=\"Circular Layout Example\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another common way to visualize a network is using a \"force-directed\" layout.\n",
    "In a force-directed layout, nodes push away from each other, but edges act like springs pulling them back together.\n",
    "As a result, nodes with many neighbors in common are pulled closer to each other."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "visualize_visjs(G_hamilton, scale=2000, title=\"Force-Directed Layout Example\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert-info\">\n",
    "\n",
    "#### Short Answer 1\n",
    "1. What is one advantage of circular layouts over force-directed? \n",
    "2. What is one advantage of force-directed layouts? \n",
    "3. Which would you use to identify groups of friends in a 10000-node college social network, and why? \n",
    "4. Which would you use to create a reference for who is friends with whom in a 20-person class, and why?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "🤔 Your answer here:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Section 4: Centrality Measures\n",
    "\n",
    "One benefit of representing data as a network is that the patterns of connections between nodes can reveal useful information.\n",
    "Many standard techniques for investigating the structure of networks have been developed.\n",
    "\n",
    "One of the simplest to consider is which nodes are most important.\n",
    "But first, \"importance\" has to be defined.\n",
    "There are several common ways to measure importance, or _centrality_, of nodes in a nework.\n",
    "This section examines several of the most popular.\n",
    "\n",
    "While the _Hamilton_ network in the previous section is simple enough to be illustrative,\n",
    "a historical data set better demonstrates how centrality measures can be applied to real-world networks.\n",
    "This section uses historical data on affilations between organizers of the American Revolution,\n",
    "taken from [Using Metadata to Find Paul Revere](https://kieranhealy.org/blog/archives/2013/06/09/using-metadata-to-find-paul-revere/). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you want to know more about Paul Revere, here's a YouTube video: https://www.youtube.com/watch?v=cLbc0NcToUI"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     0
    ]
   },
   "outputs": [],
   "source": [
    "# Helper functions\n",
    "\n",
    "def load_revere_affiliation(\n",
    "        url=\"https://raw.githubusercontent.com/kjhealy/revere/master/data/PaulRevereAppD.csv\"):\n",
    "    data = urllib.request.urlopen(url)\n",
    "    df = pd.read_csv(data).set_index(\"Unnamed: 0\")\n",
    "    people = list(df.index)\n",
    "    groups = list(df.columns)\n",
    "    #\n",
    "    B = nx.Graph()\n",
    "    for column in df.columns:\n",
    "        for row in df[df[column] == 1].index:\n",
    "            B.add_edge(column, row)\n",
    "    return people, groups, B\n",
    "\n",
    "def load_revere(\n",
    "        url=\"https://raw.githubusercontent.com/kjhealy/revere/master/data/PaulRevereAppD.csv\",\n",
    "        threshold=None, dual=False):\n",
    "    # Load the affiliation network\n",
    "    people, groups, B = load_revere_affiliation(url)\n",
    "    # Project the affiliation network onto the set of people\n",
    "    if dual:\n",
    "        G = nxalg.bipartite.projection.weighted_projected_graph(B, groups)\n",
    "    else:\n",
    "        G = nxalg.bipartite.projection.weighted_projected_graph(B, people)\n",
    "    # Threshold\n",
    "    if threshold is not None:\n",
    "        for s, t, data in list(G.edges(data=True)):\n",
    "            if data[\"weight\"] < threshold:\n",
    "                G.remove_edge(s,t)\n",
    "    # Copy \"weight\" data to \"value\" needed by visjs\n",
    "    w = nx.get_edge_attributes(G, \"weight\")\n",
    "    nx.set_edge_attributes(G, w, \"value\")\n",
    "    return G"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1 Load the Network\n",
    "The next cell begins by loading the data into a `networkx` graph. **In this network, there's an edge between two nodes if the corresponding pair of individuals were both members of at least one common organization**. As is, an analysis of the data will reveal Paul Revere to be highly central by all measures (Healey2013), so to make the example more interesting, let's assume Paul Revere had been on vacation and try to determine who might have notified the Massachusetts Provincial Congress of the impending attack in his place. To do so, we remove Paul Revere from the network. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G_revere = load_revere()\n",
    "people, groups, B_revere = load_revere_affiliation()\n",
    "G_revere.remove_node('Revere.Paul')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.2 Visualize the Network\n",
    "The next cell visualizes the network. You can zoom in and out and hover over nodes to see their labels."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "visualize_visjs(G_revere, scale=1500, title=\"American Revolution\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert-info\">\n",
    "\n",
    "#### Short Answer  2\n",
    "Looking at the visualization above, consider who in the network might be influential. \n",
    "    \n",
    "1. Based on their network position only, who do you think would be good at spreading news within a community (pick 3)? \n",
    "2. Who do you think would be good at spreading information quickly to many different groups of people (pick 3)? \n",
    "3. How might each of these properties relate to an individual’s role in a social movement such as the American Revolution?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "🤔 Your answer here:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.3 Find Centrality\n",
    "Now let's move on to examine the centralities. The next cell uses `networkx` to calculate node centralities and then stores them in a data frame. For each node we also calculate a mean centrality value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df = pd.DataFrame({\"id\": G_revere.nodes(), \"label\": G_revere.nodes()}).set_index(\"id\")\n",
    "df['degree'] = pd.Series(nx.degree_centrality(G_revere))\n",
    "df['betweenness'] = pd.Series(nx.betweenness_centrality(G_revere))\n",
    "df['closeness'] = pd.Series(nx.closeness_centrality(G_revere))\n",
    "df['eigenvector'] = pd.Series(nx.eigenvector_centrality(G_revere))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Calculate mean of all centrality measures\n",
    "df['mean_centrality'] = (\n",
    "    scale(df['degree'])\n",
    "    + scale(df['betweenness'])\n",
    "    + scale(df['closeness'])\n",
    "    + scale(df['eigenvector'])) / 4.0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Degree\n",
    "\n",
    "One very simple way to find important nodes is to count how many neighbors they have.\n",
    "This measure is called the degree centrality.\n",
    "This number is typically divided by the total number of other nodes in the network, so a value\n",
    "of 0.82 means that a node is connected to 82% of the other nodes.\n",
    "The next cell shows the nodes with the highest degree centralities.\n",
    "\n",
    "Note that some of the people have the same degree. In fact, if two people have exactly the same set of neighbors,\n",
    "all of their centrality scores will be the same."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "df.sort_values('degree', ascending=False).head(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Betweenness\n",
    "\n",
    "Rather than highly-connected nodes, you might want to find nodes that connect different parts of the network.\n",
    "These types of nodes are sometimes called bridges, or brokers.\n",
    "The betweenness centrality is based on finding the shortest path between nodes.\n",
    "The nodes on that path play the role of bridges, connecting the endpoints.\n",
    "So the betweenness is the fraction of all shortest paths in the network that pass through a given node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df.sort_values('betweenness', ascending=False).head(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Closeness\n",
    "\n",
    "A nodes might also be considered important if it is close to many other nodes.\n",
    "In other words, if the paths connecting it to other nodes are all very short.\n",
    "This measure is called closeness centrality."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df.sort_values('closeness', ascending=False).head(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Eigenvector\n",
    "\n",
    "The last centrality measure covered in this section measures not just how well-connected a node is, but how well-connected its neighbors are as well.\n",
    "This measure is the eigenvector centrality.\n",
    "The PageRank algorithm used by Google to find high quality websites is an extension of this algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df.sort_values('eigenvector', ascending=False).head(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert-info\">\n",
    "\n",
    "#### Short Answer 3\n",
    "Looking over the above centrality results, write a few sentences addressing the following questions. \n",
    "    \n",
    "1. Where do the high centrality individuals appear in visualization? \n",
    "2. For each type of centrality, are there any individuals who appear in that list but not in others? \n",
    "3. Which of the lists, if any, did your predictions from the previous question appear in?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "🤔 Your answer here:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.4 Compare Centrality Measures\n",
    "\n",
    "The following plot shows how different centrality measures are related to each other (in this network).\n",
    "Each graph compares two centrality measures corresponding to its row and column.\n",
    "In each graph, each point represents a single node in the network.\n",
    "\n",
    "Points are drawn with transparency so overlapping points are darker.\n",
    "If a group of people have the same centralities,\n",
    "possibly because they have the same set of neighbors,\n",
    "they appear as a single dark spot."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Store column names in array to keep order consistent\n",
    "measures = [\"degree\", \"betweenness\", \"eigenvector\", \"closeness\"]\n",
    "plt.figure(figsize=(10,10))\n",
    "# Loop through rows and columns\n",
    "# Even though we have 4 measures, we only need 3x3 to compare all\n",
    "for row in range(3):\n",
    "    for col in range(3):\n",
    "        # Each row column pair only needs to be plotted once\n",
    "        if row >= col:\n",
    "            # The longest row should correspond to the measure that\n",
    "            # does not appear on a column.\n",
    "            x, y = df[measures[row]], df[measures[(col-1) % 4]]\n",
    "            plt.subplot(3,3,1 + row*3 + col)\n",
    "            plt.plot(x, y, '.', alpha=0.3, markersize=10)\n",
    "            plt.xlim([0, x.max()]); plt.ylim([0, y.max()])\n",
    "        if row == 2:\n",
    "            plt.xlabel(measures[(col - 1) % 4])\n",
    "        if col == 0:\n",
    "            plt.ylabel(measures[row])\n",
    "plt.tight_layout()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert-info\">\n",
    "\n",
    "#### Short Answer 4\n",
    "\n",
    "Depending on the arrangement of nodes and their connections in a network, commonly referred to as the network structure, some nodes may have high value for one type of centrality while having a low value for another. Using the code in the next cell, try to construct a network in which  \n",
    "1. at least one node has **high degree centrality and low betweenness centrality**  \n",
    "and\n",
    "2. at least one node has **low degree centrality and high betweenness centrality**. \n",
    "    \n",
    "Which nodes in your network satisfy each condition? Breifly explain the strategy you used to come up with this network.\n",
    "Limit your networks to 5-10 nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nodes = [1,2,3,4,5] # add your nodes separated by commas. For example, nodes = [1,2,3,4,5]\n",
    "edges = [(1,2), (2,3), (3,4), (1,5)] # add edges between nodes as tuples. For example, edges = [(1,2), (2,3), (3,4), (1,5)]\n",
    "G_toy = nx.Graph()\n",
    "G_toy.add_nodes_from(nodes)\n",
    "G_toy.add_edges_from(edges)\n",
    "visualize_visjs(G_toy, scale=500)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.degree_centrality(G_toy)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.betweenness_centrality(G_toy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "🤔 Your answer here:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Section 5: Reflection\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert-warning\">\n",
    "\n",
    "#### Reflection Question 1\n",
    "\n",
    "Given some set of people and social interactions among them, a network representation can encode people as nodes and the presence of relationships among them as edges. \n",
    "    \n",
    "For example, in a friendship network, nodes represent people, and edges represent friendship between two person. The network representation makes it easy to see who are friends with whom. However, this leaves out a lot of information regarding people and their relationships that are arguably very important in contextualizing both. For instance, people's addresses are left out in the nextwork. If we want to investigate what are the key factors for people to become friends, one drawback of the nextwork representation is that we cannot see if people became friends because of location proximity. \n",
    "\n",
    "Another example would be University of Michigan course network. In this network, nodes represent different courses, and there is an edge between two courses if any student at our university has taken both courses in the same semester. This network is useful for students' course planning, as we can see which course combinations are feasible based on past experience. However, it left out information like what was the courseload for each node. As a student, we want to aviod taking two heavy courseload classes at the same time. \n",
    "\n",
    "\n",
    "In the section, please do the following:\n",
    "1. Define another social network not discussed above: what do the nodes and edges represent in the network?\n",
    "2. Give an example of a type of information that gets left out when constructing a social network. \n",
    "3. Construct a practical/empirical question that you can solve using this network. Explain one benefit or one drawback of leaving that information out."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "🤔 Your answer here:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert-warning\">\n",
    "\n",
    "#### Reflection Question 2\n",
    "Consider how your friendship network changes over time based on your actions. If you wanted to increase your degree centrality, what types of activities would you do? What if you wanted to increase your betweenness centrality?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "🤔 Your answer here:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "\n",
    "(Healey2013) Healy, K. 2013. \"Using Metadata to Find Paul Revere.\" https://kieranhealy.org/blog/archives/2013/06/09/using-metadata-to-find-paul-revere/"
   ]
  }
 ],
 "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.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}