1_Network_Structure.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CSS Lab: Network Structure\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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Contents\n",
    "\n",
    "1. [Background](#Section-1%3a-Background)\n",
    "1. [Setup](#Section-2%3a-Setup)\n",
    "4. [Community Structure](#Section-3%3a-Community-Structure)\n",
    "6. [Affiliation Networks](#Section-4%3a-Affiliation-Networks)\n",
    "    * [4.1 Weighted Edges](#4.1-Weighted-Edges)\n",
    "5. [Paths](#Section-5%3a-Paths)\n",
    "    * [5.1 Find Path Lengths](#5.1-Find-Path-Lengths)\n",
    "    * [5.2 Bridges and Weak Ties](#5.2-Bridges-and-Weak-Ties)\n",
    "    * [5.3 Find Minimum Cut](#5.3-Find-Minimum-Cut)\n",
    "7. [Your Social Network](#Section-6%3a-Your-Social-Network)\n",
    "    * [6.1 Communities](#6.1-Communities)\n",
    "    * [6.2 Find Giant Component](#6.2-Find-Giant-Component)\n",
    "    * [6.3 Path Lengths](#6.3-Path-Lengths)\n",
    "    * [6.4 Find Bridges](#6.4-Find-Bridges)\n",
    "8. [Reflection](#Section-7%3a-Reflection)\n",
    "1. [References](#References)\n",
    "    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Section 1: Background\n",
    "Looking at the structure of a network takes a step back from the properties of individual nodes to identify larger-scale patterns. This notebook explores several ways of measuring network structure. This lab will continue using a data set of group memberships from the American Revolution (Healey2013). Additionally, this lab analyzes a fictional network of complex political relationships, namely the characters in George R.R. Martin's _A Storm of Swords_ (BS2016). The _Storm of Swords_ network was created by creating links between two characters if they are mentione at the same time.\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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "import itertools\n",
    "from IPython.display import display, Javascript, HTML\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 numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following cell imports `vis.js`, the visualization library used by this lab.\n",
    "\n",
    "**Note**: 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`. "
   ]
  },
  {
   "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",
    "});"
   ]
  },
  {
   "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": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": []
   },
   "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 path_histogram(G, log=False):\n",
    "    # Find shortest path length for each pair\n",
    "    path_lengths = list(itertools.chain(*[\n",
    "            [length for length in targets.values() if length > 0]\n",
    "        for source, targets in list(nxalg.shortest_path_length(G))]))\n",
    "    # Draw histogram with integer bins\n",
    "    bins = [0.5 + x for x in range(max(path_lengths)+1)]\n",
    "    counts, centers, patches = plt.hist(\n",
    "        path_lengths, bins=bins, rwidth=0.8)\n",
    "    if log:\n",
    "        plt.yscale('log', nonposy='clip')\n",
    "        ymax = np.power(10, np.ceil(np.log10(max(counts))))\n",
    "    else:\n",
    "        place = np.power(10, np.floor(np.log10(max(counts))))\n",
    "        ymax = np.ceil(max(counts) / place) * place\n",
    "    # Plot average shortest path length\n",
    "    mean_path = nxalg.average_shortest_path_length(G)\n",
    "    plt.plot([mean_path, mean_path], [1, ymax], label=\"mean\")\n",
    "    plt.ylim([1, ymax])\n",
    "    plt.xlabel(\"Path length\")\n",
    "    plt.ylabel(\"Count\")\n",
    "    plt.legend()\n",
    "    plt.tight_layout()\n",
    "\n",
    "def longest_geodesic(G):\n",
    "    paths = nxalg.shortest_path(G)\n",
    "    longest = 0\n",
    "    longest_path = []\n",
    "    for source, source_paths in paths.items():\n",
    "        for target, path in source_paths.items():\n",
    "            if len(path) > longest:\n",
    "                longest = len(path)\n",
    "                longest_path = path\n",
    "    return path\n",
    "\n",
    "# Helper functions\n",
    "\n",
    "def find_bridges(G, labels=None):\n",
    "    bridges = []\n",
    "    for v, w in G.edges():\n",
    "        H = G.copy()\n",
    "        H.remove_edge(v, w)\n",
    "        try:\n",
    "            d = nx.shortest_path_length(H, source=v, target=w)\n",
    "            if d <= 2:\n",
    "                continue\n",
    "        except nx.NetworkXNoPath:\n",
    "            d = float(\"Inf\")\n",
    "        if labels is None:\n",
    "            bridges.append((d, v, w))\n",
    "        else:\n",
    "            bridges.append((d, labels[v], labels[w]))\n",
    "    bridges = sorted(bridges, key=lambda x: x[0], reverse=True)\n",
    "    for b in bridges:\n",
    "        if b[0] == float(\"Inf\"):\n",
    "            print(\"Global bridge:\\t{} <-> {}\".format(b[1], b[2]))\n",
    "        else:\n",
    "            print(\"Local bridge, span {}:\\t{} <-> {}\".format(*b))\n",
    "            \n",
    "def find_global_bridges(G, labels=None):\n",
    "    bridges = nx.algorithms.bridges(G)\n",
    "    for b in bridges:\n",
    "        if labels is None:\n",
    "            v, w = b[0], b[1]\n",
    "        else:\n",
    "            v, w = labels[b[0]], labels[b[1]]\n",
    "        print(\"Global bridge:\\t{} <-> {}\".format(v, w))\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(), edge_width_field=\"value\", 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, 5) 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",
    "            \"color\": \"rgba({},0.3)\".format(edge_colors.get((source,target), default_color)),\n",
    "            \"edge_width_field\": edge_width_field,\n",
    "            \"value\": data.get(edge_width_field, 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=10.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))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Section 3: Community Structure\n",
    "\n",
    "People are often organized into groups where everyone is highly-connected: schools, workplaces, clubs, etc. What if you know the connections between individuals and want to discover the groups? This is the problem of _community detection_. There are many ways to find communities. The following cells find and visualize communities using a method that maximizes _modularity_ (CNM2004). Networks with high modularity have a high number of edges between nodes in the same community and a low number of edges across communities. One benefit of this method is that it automatically determines the best number of communities.\n",
    "\n",
    "We'll continue using the network from the previous lab, composed of organizations from the American Revolution. In the visualization below, different communities are shown in different colors."
   ]
  },
  {
   "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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "people, groups, B_revere = load_revere_affiliation()\n",
    "G_revere = load_revere()\n",
    "communities = list(nxcom.greedy_modularity_communities(G_revere))\n",
    "visualize_visjs(G_revere, communities=communities, scale=3000, title=\"Community Detection Example\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Following command will show one individual's affiliations provided in the dataset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(nx.neighbors(B_revere, \"Church.Benjamin\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Section 4: Affiliation Networks\n",
    "Sometimes it is useful to consider two different types of nodes.\n",
    "Often, this is the case when one type of node represents groups and the other represents members of those groups,\n",
    "with the edges representing membership.\n",
    "Such networks are called affiliation networks.\n",
    "\n",
    "The American Revolution data from before was created from an affiliation network.\n",
    "The cell below visualizes the full affiliation network.\n",
    "Notice that person nodes are only connected to group nodes (political organizations in American Revolution) and vice versa."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "peopele, groups, B_revere = load_revere_affiliation()\n",
    "visualize_visjs(B_revere, scale=3000, groups=groups, title=\"American Revolution Affiliation\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Previously, this affilation network was used to create a network connecting people to people.\n",
    "But we can just as easily create a network connecting groups to groups (if they have a common member) [Breiger1974]. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G_dual = load_revere(dual=True)\n",
    "visualize_visjs(G_dual, title=\"American Revolution Groups\", edge_width_field=None, groups=G_dual.nodes())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1 Weighted Edges\n",
    "In the above example, two groups have an edge between them if they have a common member.\n",
    "But some groups might have only one member in common, while others have many.\n",
    "These differences can be represented by adding a _weight_ do the edge.\n",
    "Edge weights can be used to represent many different properties, such as distance or similarity.\n",
    "In this case, weights represent how many members two groups have in common."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "visualize_visjs(G_dual, title=\"American Revolution Weighted\", groups=G_dual.nodes(), weight=\"weight\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert-info\">\n",
    "\n",
    "#### Short Answer 1\n",
    "Which of the following pairs of groups has the most number of members in common, and which has the least? Briefly explain.\n",
    "1. LondonEnemies and TeaParty\n",
    "2. LondonEnemies and NorthCaucus\n",
    "3. StAndrewsLodge and BostonCommittee"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "🤔 Your answer here:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Section 5: Paths\n",
    "\n",
    "It is also informative to consider the shortest paths of a network.\n",
    "For a pair of nodes, the shortest path is the path connecting them in the fewest number of hops.\n",
    "The example below uses a network of characters from the novel _A Storm of Swords_ (BS2016),\n",
    "with edges representing characters mentioned at the same time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": []
   },
   "outputs": [],
   "source": [
    "# Helper functions\n",
    "\n",
    "def load_asoiaf():\n",
    "    G = nx.Graph()\n",
    "    with open(\"external/stormofswords.csv\") as f:\n",
    "        f.readline()\n",
    "        rows = list(f)\n",
    "    \n",
    "    for row in rows:\n",
    "        source, target, weight = row.split(\",\")\n",
    "        G.add_edge(source, target, weight=int(weight), capacity=1)\n",
    "    return G"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, load and visualize the network."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "G_asoiaf = load_asoiaf()\n",
    "visualize_visjs(G_asoiaf, title=\"asoiaf\", scale=2000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.1 Path Lengths\n",
    "Next, plot a histogram of the path lengths as well as the mean path length. The diameter of a network is the length of the longest shortest path."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert-info\">\n",
    "\n",
    "#### Short Answer 2\n",
    "Look at the network below, find the longest shortest path and determine the diameter of the network."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "🤔 Your answer here:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nodes = [1,2,3,4,5]\n",
    "edges = [(1,2), (2,3), (3,4), (3,5), (1,4), (4,5)]\n",
    "G = nx.Graph()\n",
    "G.add_nodes_from(nodes)\n",
    "G.add_edges_from(edges)\n",
    "nx.draw_networkx(G, with_labels=True, font_weight='bold')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert-info\">\n",
    "\n",
    "#### Short Answer 3\n",
    "Write a few sentences about the distance (number of edges) between nodes in the _A Storm of Swords_ network `G_asoiaf`, considering the following:\n",
    "\n",
    "    \n",
    "1. How long would you guess the typical shortest path between two nodes is? \n",
    "2. How long would you guess the shortest path is between the two most distance nodes? \n",
    "    \n",
    "(No right or wrong answer!)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "🤔 Your answer here:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Finding Path Lengths \n",
    "Now we will calculate the actual distribution of path lengths."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "path_histogram(G_asoiaf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The cell above found the distribution of paths lengths, but it is also informative to look at individual paths. The following cell prints the shortest path between the two most distant nodes in the network. You might expect the endpoints to be very different in some way, perhaps separated geographically, or socially. Similarly the nodes in the middle are ones that connect distant parts of the network, and are likely to play an important role in the network."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(longest_geodesic(G_asoiaf))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next we will look at link connectivity with bridges"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.2 Bridges and Weak Ties\n",
    "We can also find edges which act as bridges between different parts of the network. An edge is a bridge if removing it disconnects two parts of a network.\n",
    "More generally, a local bridge connects two nodes that would otherwise be far apart.\n",
    "If removing an edge causes its endpoints to become distance _n_ apart,\n",
    "it is called a local bridge of span n.\n",
    "\n",
    "Bridges are often _weak ties_ (Granovetter1977) because individuals with a strong connection are likely to have common friends."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "find_global_bridges(G_asoiaf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are also the linear approach to find all dual-bridges in a two-connected graph by using algorithms to certify three-connectivity of the graphs. The definition of the dual-bridge is by its removal the residual graph will be disconnected. This is a special version of the minimum cut that finds two links in the cut."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.3 Find Minimum Cut\n",
    "Sometimes you might want to know where a network is most fragile.\n",
    "The minimum cut finds the fewest number of links that need to be removed to break a network into two pieces.\n",
    "In the beginning of the _A Song of Ice and Fire_ series, exiled princess Daenerys Targaryen and her brother Viserys seek to reclaim the throne from reigning king Robert Baratheon.\n",
    "You can use the minimum cut to find the links that separate characters connected to the Targaryens from those more closely connected to the Baratheons.\n",
    "\n",
    "First we find the minimum cut: the number of edges separating the two factions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mincut, cuts = nxalg.minimum_cut(G_asoiaf, 'Daenerys', 'Robert')\n",
    "mincut\n",
    "cuts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert-info\">\n",
    "\n",
    "#### Short Answer 4\n",
    "Now we can visualize the min cut. Who in the \"Robert\" cluster is closest to members of the \"Daenerys\" cluster? (Hint: there should be 4 people)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "visualize_visjs(G_asoiaf, communities=cuts, scale=2000, title=\"Mincut\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "🤔 Your answer here:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Section 6: Reflection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert-warning\">\n",
    "    \n",
    "#### Reflection Question 1\n",
    "\n",
    "There are many examples of afflication networks in real life. For example, a supermarket inventory data can be represented using an affiliation network. In this network, group nodes represent brands of goods, and member nodes represent goods. The edges between members and groups represent which good is made by which brand. \n",
    "    \n",
    "Give an example of another type of data that can be modeled as an affiliation network and identify the nodes and edges. (In such a network, what are the two types of nodes? What do edges between those nodes represent?)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "🤔 Your answer here:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert-warning\">\n",
    "\n",
    "#### Reflection Question 2\n",
    "\n",
    "Your ego network includes your friends, but not friends of your friends. \n",
    "\n",
    "These are the steps to construct your ego network:\n",
    "    1. list your friends as nodes (not including yourself)\n",
    "    2. draw edges between your friends who you know that they know each other\n",
    "    \n",
    "Consider two friends who have a high distance between them in your ego network. What is their \"true distance\" from each other in the full network if they have a friend in common who is not in your ego network? If we only look at your ego network, are we overestimating or underestimating the true distance between individuals?\n",
    "    \n",
    "Hint: This question has one correct answer. You may find this mini example helpful."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![My Ego Network](my_ego_network.png)"
   ]
  },
  {
   "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/\n",
    "\n",
    "(CNM2004) Clauset, A., Newman, M. E., & Moore, C. (2004). Finding community structure in very large networks. Physical review E, 70(6).\n",
    "\n",
    "(BS2016) A. Beveridge and J. Shan, \"Network of Thrones,\" Math Horizons Magazine, Vol. 23, No. 4 (2016), pp. 18-22\n",
    "\n",
    "(Breiger1974) Breiger, R. L. (1974). The duality of persons and groups. Social forces, 53(2), 181-190.\n",
    "\n",
    "(Granovetter1977) Granovetter, M. S. (1977). The strength of weak ties. In Social networks (pp. 347-367).\n",
    "\n",
    "(Gallagher2021) Gallagher, R. J., Young, J. G., & Welles, B. F. (2021). A clarified typology of core-periphery structure in networks. Science Advances, 7(12)."
   ]
  }
 ],
 "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
}