labs/minimum_cut/minimum_cut_lab_key.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e8e14fa6",
   "metadata": {},
   "source": [
    "# Min Cut Lab\n",
    "**Objectives:**\n",
    "- Understand the formulation of a min cut instance, in particular\n",
    "    - using infinite capacity edges\n",
    "    - finding an s-t cut \n",
    "    - using it to solve the Tool Selection problem\n",
    "    - using it to solve the Densest Subgraph problem"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "14028177",
   "metadata": {},
   "source": [
    "## Part 1: The Densest Subgraph Problem\n",
    "In the first part of this lab, we will introduce the densest subgraph problem and model it by reducing it to an instance of the Minimum Cut problem. This problem is used frequently in social network analysis as it helps us identify communities within a certain network and helps us separate meaningful data among a large network by decreasing our sample size of significant data points. We will explore some applications of the problem in the latter part of this lab.\n",
    "\n",
    "Let's first go through some notation: the density of a graph is defined by the number of edges induced in the graph (fully contained inside the graph) divided by the number of nodes in the graph. Let us denote the graph and density with $$G = (V, E), d = \\frac{|E|}{|V|}.$$\n",
    "\n",
    "Suppose we are given the following graph and the subgraph with vertices $S = \\{1, 2, 5\\}$ shown in red. Then the edges induced by the subgraph are precisely the ones outlined in yellow:\n",
    "\n",
    "![title](images-lab/density_ex.png)\n",
    "\n",
    "The density of the subgraph defined by the vertices in $S$ is then $\\frac{|E|}{|V|} = \\frac{3}{3} = 1$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "24a45c76",
   "metadata": {},
   "source": [
    "Now, answer the following questions about this graph with $S = \\{1, 2, 4\\}$:\n",
    "\n",
    "![title](images-lab/density_q.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "24c8c352",
   "metadata": {},
   "source": [
    "**Q:** Which edges are induced (completely contained) by the subgraph given by the vertices in red? Hint: there should only be one.\n",
    "\n",
    "**A:** <font color='blue'> the edge (1,2) </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2fd7ad60",
   "metadata": {},
   "source": [
    "**Q:** What is the density of this subgraph?\n",
    "\n",
    "**A:** <font color='blue'> $\\frac{|E|}{|V|} = \\frac{1}{3} = .33$ </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "64bb9115",
   "metadata": {},
   "source": [
    "**Q:** You'll notice that this is not the densest subgraph we could have chosen. What vertices do you think would make up the densest subgraph in this case? Hint: its density should be 1.25\n",
    "\n",
    "**A:** <font color='blue'> 1, 2, 3, 5.</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "19a2c161",
   "metadata": {},
   "source": [
    "Now, we will first focus on the non-optimization aspect of the densest subgraph problem. That is, we want to answer the question: does there exist a subset of nodes S such that the density of the subgraph it makes up is at least $\\lambda$?\n",
    "\n",
    "**Q:** Write an equation that if satisfied, proves the existence of such a subset $S$. Let $E(S)$ be the edge set induced by the nodes in $S$ (edges going from a node in $S$ to another node in $S$). Write your answer in terms of $\\lambda$, $|E(S)|$, and $|S|$. Hint: it should represent an inequality that says \"the density of the subgraph is greater than or equal to a certain value\"\n",
    "\n",
    "**A:** <font color='blue'> $\\frac{|E(S)|}{|S|} \\geq \\lambda$ </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9e66b5ff",
   "metadata": {},
   "source": [
    "**Q:** Rewrite the equation such that we have an equation of the form $a - b*c \\geq 0$.\n",
    "\n",
    "**A:** <font color='blue'> $|E(S)| - \\lambda |S| \\geq 0$ </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "42178669",
   "metadata": {},
   "source": [
    "So, if we want to prove that there exists some subset of nodes S that has density at least $\\lambda$, we just need to find one such $S$ that satisfies the equation above. Since the relationship is greater than or equal to, we can try to maximize the LHS such that if our maximum value is $\\geq 0$ then we know we have found a set $S$ that satisfies this property. Thus, our goal is $$maximize |E(S)| - \\lambda |S|$$ and we want to see if that value is $\\geq 0$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1b3b83fd",
   "metadata": {},
   "source": [
    "Notice that there are two components to this equation. **The first part can be interpreted as receiving one unit of benefit for each edge induced by the set $S$ we are choosing. The second part can be interpreted as paying $\\lambda$ units of cost for every node that we include in our set $S$.** Is this starting to sound familiar?\n",
    "\n",
    "This is exactly similar to the tool selection problem! In that problem, we wanted to find a subset of tasks to complete given that we gain a certain amount of revenue for each task finished, but have to pay a certain cost to use the tools needed for each task. Luckily enough, that problem also had the optimization of finding such a subset such that our overall profit was positive. *If you are unfamiliar with this problem, there is a walkthrough of the reduction for it at the end of this notebook. Feel free to go through it before continuing.*\n",
    "\n",
    "Let's model the densest subgraph instance as a tool selection problem! Since we gain benefit from including edges, let the edge set of the graph, $E$, take the role of the tasks in the model. Similarly, let the vertex set of the graph, $V$, take the role of the tools in the model.\n",
    "\n",
    "Rather than choosing tools so that certain tasks can be completed, we can think of this as *choosing nodes such that certain edges are induced by our subset $S$.*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5a47372b",
   "metadata": {},
   "source": [
    "Let's say we are given the following graph (same as before), and we want to see if there is a subgraph with density at least 1.2.\n",
    "\n",
    "![title](images-lab/graph_1.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fb22c2aa",
   "metadata": {},
   "source": [
    "**Q:** Draw the min cut instance for the above graph. Hint: there should be a \"layer\" for nodes representing edges in the original graph, and another \"layer\" for vertex nodes.\n",
    "\n",
    "**A:** ![title](images-key/reduction_graph_1.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f86d081e",
   "metadata": {},
   "source": [
    "Given that the objective function of the tool selection problem was really `maximize b - c` where $b$ was the total benefit of all the tasks completed and $c$ was the total cost of all the tools used, the \"equivalent\" objective function of the minimum cost reduction was to minimize just the total cost, which was measured by the opportunity cost of jobs not taken added with the cost of using tools for the jobs we did take."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d891545e",
   "metadata": {},
   "source": [
    "**Q:** In plain English, what are the two costs that we want to minimize for the densest subgraph problem?\n",
    "\n",
    "**A:** <font color='blue'> the opportunity cost of not inducing an edge and the cost of including more vertices in our subgraph </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "519c923d",
   "metadata": {},
   "source": [
    "Let the edge set from the original graph be $E = E(S) \\cup \\overline{E(S)}$, where $E(S)$ is the set of all edges induced by the subgraph and $\\overline{E(S)}$ is the set of all edges not induced. Let the vertex set be $V = S \\cup T$, where $S$ is the set of all vertices included in our subgraph and $T$ is the set of vertices not included.  \n",
    "\n",
    "If you answered Q7 correctly, the equivalent objective function for your answer should be $$ minimize |\\overline{E(S)}| + \\lambda|S|.$$\n",
    "\n",
    "Let's take a closer look at this objective function to see the parallels:\n",
    "\n",
    "**Q:** For every edge we do not induce in our subgraph, what is the opportunity cost?\n",
    "\n",
    "**A:** <font color='blue'> 1 (the coefficient in front of the term $|\\overline{E(S)}|$ is 1) </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ca2afb0e",
   "metadata": {},
   "source": [
    "**Q:** For every vertex we add to our subgraph, what is the cost?\n",
    "\n",
    "**A:** <font color='blue'> $\\lambda$ (the coefficient in front of the term $|S|$ is $\\lambda$) </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0d044c77",
   "metadata": {},
   "source": [
    "Now, it may not be immediately apparent, but this is exactly the objective function we said we wanted to use at the beginning of the lab! Let's see how that is. We first need to change it into a maximization function.\n",
    "\n",
    "**Q:** What is the maximization equivalent of the minimization objective function we were looking at above?\n",
    "\n",
    "**A:** <font color='blue'> *maximize* $-|\\overline{E(S)}| - \\lambda|S|$  </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b9d827ea",
   "metadata": {},
   "source": [
    "**Q:** You should have ended up with an equation in terms of only $|\\overline{E(S)}|$, $|S|$, and $\\lambda$. We can rewrite $|\\overline{E(S)}|$ in terms of $|E|$ and $|E(S)|$. Substitute $|\\overline{E(S)}|$ from the previous question and write the new maximization function below.\n",
    "\n",
    "**A:** <font color='blue'> *maximize* $-(|E| - |E(S)|) - \\lambda|S|$ or *maximize* $-|E| + |E(S)| - \\lambda|S|$ </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "83177b91",
   "metadata": {},
   "source": [
    "Notice that $|E|$ is a property of the original graph and is independent of any subgraph we may choose, thus it is a constant that we can remove it from the objective function since constants contribute the same value to any solution. Finally, we end up with the function: *maximize* $|E(S)| - \\lambda|S|$ which is exactly what we wanted! Essentially, nodes inside the cut represent the edges induced and vertices making up the subgraph we have chosen.\n",
    "\n",
    "We've now successfully formulated a min cut instance from the densest subgraph problem!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "500f5b24",
   "metadata": {},
   "source": [
    "## Part 2: Using Python"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2bea2bea",
   "metadata": {},
   "source": [
    "In this part of the lab, we will be using python to help us solve some instances of the densest subgraph problem. We first define the graph that we want to analyze. Run the following code to see an illustration of the graph we will be using for this part of the lab."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "78da083f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Don't forget to run this cell to load all the packages!\n",
    "from max_flow import *\n",
    "import pickle\n",
    "import numpy as np\n",
    "from social_network import *\n",
    "\n",
    "# Uncomment the following line of code and run this cell again if you get an error when running the next cell of code. \n",
    "# pip install decorator==5.0.7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "debedcf5",
   "metadata": {},
   "outputs": [],
   "source": [
    "# define the input graph\n",
    "G = nx.Graph()\n",
    "edgeList = [(1,1), (2,4), (3,4), (4,5), (4,6), (4,7), (5,6), (5,7), (6,7)]\n",
    "G.add_edges_from(edgeList)\n",
    "nx.draw(G,with_labels=True, font_weight='bold')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3934f128",
   "metadata": {},
   "source": [
    "**Q:** What do you expect to be the maximum density for this graph upon inspection?\n",
    "\n",
    "**A:** <font color='blue'> 1.5 </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6bcc6a27",
   "metadata": {},
   "source": [
    "**Q:** What vertices do you expect to be inside subgraph with the density you answered above?\n",
    "\n",
    "**A:** <font color='blue'> 4,5,6,7 </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7bf0876d",
   "metadata": {},
   "source": [
    "The following code will generate the min-cut instance of the graph given above. It will then execute Ford-Fulkerson on the formulated graph and print out the max flow value as well as the list of nodes in the s side of the minimum cut. Fill in the missing pieces of code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9d1bf62f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def gen_max_density(G, edges, d):\n",
    "    \"\"\"Returns the graph of the min cut instance of the maximum density problem with the given graph [G], graph edges [edges] and given density [d].\"\"\"\n",
    "    dirG = nx.DiGraph()\n",
    "    sink_edges = []\n",
    "    \n",
    "    #add vertex nodes\n",
    "    for i in G.nodes:\n",
    "        \n",
    "        # TODO: Assign a value for the capacity of the edges going into the sink node. Hint: use a given parameter.\n",
    "        # sink_edges.append((i, 't', XXX))\n",
    "        ### BEGIN SOLUTION\n",
    "        sink_edges.append((i, 't', d))\n",
    "        ### END SOLUTION\n",
    "        \n",
    "        \n",
    "    source_edges = []\n",
    "    etv_edges = []  #edge to vertex edges\n",
    "    edge_nodes = [] #list of all the edge nodes we need to add\n",
    "    #total number of edges in the original graph that are not self loops\n",
    "    total_edges = 0\n",
    "    #add source to edge node edges and edge to vertex node edges\n",
    "    for e in edges:\n",
    "        if e[0] != e[1]:\n",
    "            edge_nodes.append(str(e))\n",
    "            \n",
    "            # TODO: Assign a value for the capacity of the edges coming from the source node.\n",
    "            # source_edges.append(('s',str(e), XXX))\n",
    "            ### BEGIN SOLUTION\n",
    "            source_edges.append(('s', str(e), 1))\n",
    "            ### END SOLUTION\n",
    "            \n",
    "            etv_edges.append((str(e), e[0], math.inf))\n",
    "            etv_edges.append((str(e), e[1], math.inf))\n",
    "            total_edges += 1\n",
    "    dirG.add_weighted_edges_from(sink_edges, 'cap' )\n",
    "    dirG.add_weighted_edges_from(source_edges, 'cap' )\n",
    "    dirG.add_weighted_edges_from(etv_edges, 'cap' )\n",
    "    #assign positions to nodes\n",
    "    for i in G.nodes:\n",
    "        dirG.nodes[i]['pos'] = (40, 100-i*10)\n",
    "    count = 0\n",
    "    for i in edge_nodes:\n",
    "        dirG.nodes[i]['pos'] = (20, 100-count*10)\n",
    "        count +=1\n",
    "    dirG.nodes['t']['pos'] = (60, len(edge_nodes)*10)\n",
    "    dirG.nodes['s']['pos'] = (0, len(edge_nodes)*10)\n",
    "\n",
    "    return dirG\n",
    "\n",
    "\n",
    "def solve_min_cut(G):\n",
    "    \"\"\"Solves the given graph [G] that represents a min-cut instance. Prints out the flow and min-cut. \"\"\"\n",
    "    #solve the min cut instance\n",
    "    ex= max_flow(G)\n",
    "    ex.plot_graph()\n",
    "    ex.ford_fulkerson(s='s', t='t', show=False)\n",
    "    print(\"Max flow value: \" + str(ex.get_flow_value(t='t')))\n",
    "    ex.plot_flow()\n",
    "    # ex.label(s='s', auto=True, show=False)\n",
    "    value, cut = nx.minimum_cut(G, 's', 't', capacity = 'cap')\n",
    "    s_cut, t_cut = cut\n",
    "    ex.label_from_t(s_cut)\n",
    "    print(\"Minimum s-t cut: \" + str(ex.get_checked_nodes()))\n",
    "    ex.plot_checked(residual=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5a0f2ebb",
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO: Test this block of code with different values to find the maximum density.\n",
    "# d = XXX\n",
    "### BEGIN SOLUTION\n",
    "d = 1.5\n",
    "### END SOLUTION\n",
    "dirG = gen_max_density(G, edgeList, d)\n",
    "solve_min_cut(dirG)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "32e84e0f",
   "metadata": {},
   "source": [
    "**Q:** What was the maximum density subgraph you found?\n",
    "\n",
    "**A:** <font color='blue'> 1.5 </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7236868f",
   "metadata": {},
   "source": [
    "**Q:** What nodes are part of the subgraph that makes up this density?\n",
    "\n",
    "**A:** <font color='blue'> 4,5,6,7 </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a1a20188",
   "metadata": {},
   "source": [
    "## Part 3: Taxi Pickup Application"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d6c71c04",
   "metadata": {},
   "source": [
    "In this part of the lab, we will apply the densest subgraph problem to the taxi data we previously saw with the MST approach. We can use this application to try to identify clusters in the data by determining a measure such that only dates \"similar\" enough to each other share an edge in the original graph.\n",
    "\n",
    "The following code cell will load the taxi data and define some functions we will use to measure similarity. Here, we turn each day into a 96-element vector (representing 15 minute intervals) and take the norm (magnitude) of the vector calculated by the difference between two dates to represent how similar they are. Don't worry too much about this terminology, but know that we have a calculated measure of similarity between any two dates."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5976e03b",
   "metadata": {},
   "outputs": [],
   "source": [
    "#Load the data\n",
    "taxi_count = pickle.load(\n",
    "        open( \"data-lab/taxi_count_dict.pickle\", \"rb\"))\n",
    "\n",
    "#Functions to convert the data so that each element of the vector represents the proportion of total riders on a day\n",
    "def total(i):\n",
    "    data = taxi_count['count_vector'][i]\n",
    "    sum = 0\n",
    "    for val in data:\n",
    "        sum += val\n",
    "    return sum\n",
    "\n",
    "def normalize(i):\n",
    "    data = taxi_count['count_vector'][i]\n",
    "    sum = total(i)\n",
    "    normalized_data = list()\n",
    "    for val in data:\n",
    "        normalized_data.append(val/sum)\n",
    "    return normalized_data\n",
    "\n",
    "#Function that calculates distance between two days using the 2-norm\n",
    "def get_distance(i, j):\n",
    "     return np.linalg.norm(np.array(normalize(i)) - np.array(normalize(j)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "77e7865d",
   "metadata": {},
   "source": [
    "Next, we will use this code to generate a graph and return the number of occurrences of each weekday inside the subgraph found using the densest subgraph problem. We can define the parameter `distance` as the value such that all nodes that have a similarity measure less than it will share an edge in our graph. The parameter `density` is similar to Part 2 of this lab where it is the density of the subgraph we are looking for."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "49f3cb44",
   "metadata": {},
   "outputs": [],
   "source": [
    "def taxi_density(distance, density, show=False):\n",
    "    \"\"\"Generates a graph from the taxi data and finds a minimum cut given that only dates with norm differences of [distance]\n",
    "    away from each other share an edge. [density] is the density of the subgraph we wish to find.\"\"\"\n",
    "    G = nx.Graph()\n",
    "    nodesList = []\n",
    "    for i in range(365):\n",
    "        nodesList.append(i)\n",
    "    G.add_nodes_from(nodesList)\n",
    "\n",
    "    edgeList = []\n",
    "    for i in range(364):\n",
    "        for j in range(i+1, 365):\n",
    "            if get_distance(i, j) < distance:\n",
    "                edgeList.append((i, j))\n",
    "\n",
    "    G = nx.Graph()\n",
    "    G.add_edges_from(edgeList)\n",
    "    #illustrate the graph\n",
    "    if show:\n",
    "        plt.figure(figsize=(15, 10), tight_layout=True)\n",
    "        nx.draw_networkx(G, with_labels = True, node_size = 300, font_size = 10)\n",
    "        plt.show()\n",
    "    print('Number of nodes: ' + str(G.number_of_nodes()))\n",
    "    print('Max distance: '+ str(distance))\n",
    "    print('Density: ' + str(density))\n",
    "    \n",
    "    #create a min-cut instance\n",
    "    dirG = create_max_density(G, edgeList, density)\n",
    "    #solve for a minimum cut\n",
    "    value, cut = nx.minimum_cut(dirG, 's', 't', capacity = 'cap')\n",
    "    s_cut, t_cut = cut\n",
    "    dates = []\n",
    "    days = []\n",
    "    str_days = []\n",
    "    num_to_day = {0:'Mon', 1: 'Tues', 2:'Wed', 3:'Thur', 4:'Fri', 5:'Sat', 6:'Sun'}\n",
    "    for i in s_cut:\n",
    "        if isinstance(i, int):\n",
    "            dates.append(i)\n",
    "            days.append(taxi_count['weekday'][i])\n",
    "            str_days.append(num_to_day[taxi_count['weekday'][i]])\n",
    "            \n",
    "    #count the number of times each weekday occurs in the cut\n",
    "    count = {}\n",
    "    for i in range(7):\n",
    "        count[num_to_day[i]] = days.count(i)\n",
    "    print(count)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3a619556",
   "metadata": {},
   "source": [
    "**Q:** What kind of clustering do you expect us to uncover and why?\n",
    "\n",
    "**A:** <font color='blue'> weekends and weekdays, days of the week, etc. </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1791fc3f",
   "metadata": {},
   "source": [
    "Run the following block of code to see if you can identify a cluster. Feel free to change the values to experiment with the possible clusters you may uncover!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a6b0bb0e",
   "metadata": {},
   "outputs": [],
   "source": [
    "distance = .01\n",
    "density = 20\n",
    "taxi_density(distance, density, True)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f33ca969",
   "metadata": {},
   "source": [
    "**Q:** What kind clustering were you able to identify?\n",
    "\n",
    "**A:** <font color='blue'> weekends and weekdays </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1b0e3c7b",
   "metadata": {},
   "source": [
    "Run the following block of code to see some interesting behavior..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "159770fe",
   "metadata": {},
   "outputs": [],
   "source": [
    "distance = .01\n",
    "density = 35\n",
    "taxi_density(distance, density)\n",
    "\n",
    "distance = .01\n",
    "density = 47\n",
    "taxi_density(distance, density)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b67eba35",
   "metadata": {},
   "source": [
    "You'll notice that specifically two of the weekdays seem to contribute less and less to the cluster as we increase the density of the subgraph.\n",
    "\n",
    "**Q:** Which weekdays decrease significantly in occurrences in the cut that we found and why do you think this may be the case?\n",
    "\n",
    "**A:** <font color='blue'> Monday and Friday. Fridays sometimes have patterns that follow more similarly to weekends, so that may be why it \"dropped\" out of the subgraph first. Mondays are also sometimes slightly different than the other weekdays as they are the start of a new work week and thus may exhibit different behavior. </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b3c81a6d",
   "metadata": {},
   "source": [
    "You might be thinking: this is very cool and all, but there doesn't seem to be a reason for us to cluster this specific set of data. Of course weekends are going to have different schedules than weekdays! While that may be true, using data with pretty clear expectations of behavior can help us verify the credibility of our algorithm. We just used a min cut problem to concretely find two distinct patterns! The taxi application may have seemed a bit artificial, but we can apply this to a variety of different sets of data, one of which is explored in the next part of this lab. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f4113120",
   "metadata": {},
   "source": [
    "## Part 4: Social Network Application"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "84a6b2f6",
   "metadata": {},
   "source": [
    "In part 4 of this lab, we will take a look at how the densest subgraph problem can help us in analyzing social networks. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06acdb6f",
   "metadata": {},
   "source": [
    "### Facebook Friend Network\n",
    "We will analyze a graph that represents friendships through Facebook. Each node represents a person and each edge represents two people being friends with one another. Suppose we are interested in finding different communities within a social network, a subgroup of people that are hyperconnected to each other within the data we are given. We can see the similarities between finding such a subgroup with finding a subgraph with a very high density, as ideally we will have many edges concentrated between a subset of nodes representing many mutual friendships among the subgroup we have found.\n",
    "\n",
    "The social network we will look at today consists of 4039 people and 88234 friendships. Below is a picture of what the social network looks like:\n",
    "\n",
    "![title](images-lab/fb_network.png)\n",
    "\n",
    "Run the following code to find the densest subgraph on this network (it may take a few minutes to finish executing):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "885a0540",
   "metadata": {},
   "outputs": [],
   "source": [
    "density = 77.3\n",
    "fb, edge_list = generate_fb(show = False)\n",
    "solve_network(fb, edge_list, density, display_color = False, display_community = False)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3587e47c",
   "metadata": {},
   "source": [
    "**Q:** How many people were in the community you just found?\n",
    "\n",
    "**A:** <font color='blue'> 202 </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "28d93299",
   "metadata": {},
   "source": [
    "Here is a (rough) picture of what the network looks like with the community you just found in red:\n",
    "\n",
    "![title](images-lab/fb_community_in_network.png)\n",
    "\n",
    "*Since the runtime per execution of the algorithm is a bit long, we've given you the highest density value already (77.3). If you're interested in how this was determined, it can be found using binary search on the density value. However, with a small enough sample, you could also find this value experimentally similar to what we did at the beginning of this lab.*\n",
    "\n",
    "The community itself looks like:\n",
    "\n",
    "![title](images-lab/fb_community.png)\n",
    "\n",
    "Notice how dense this community is! If we think closely about this, the density of a subgraph is twice the average number of friends that each person in that subset has within that subgraph. Thus, we have just found a community where the average number of friends from person to person is about 39 (given our maximum density value of 77.3). Unfortunately, since this data is anonymous, we can't decipher much about it's meaning just yet. But, we've just narrowed down our data from about 4000 vertices to only about 200. Finding these dense subgraphs can help us better understand messy graphs and discover trends that we might not have anticipated, and they allow us to focus our analysis on clusters of people related to the data we are trying to learn more about!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a7340bd8",
   "metadata": {},
   "source": [
    "### Marvel Superhero Network\n",
    "Now, let's analyze a social network you may be more familiar with: the Marvel superhero universe! Our graph will represent the following: each vertex represents a hero and each edge represents two heroes appearing in the same comic book together. Additionally, the weight of each edge represents how many times the two heroes have appeared together. You may be wondering, could this data even possibly point to anything representative of the real world? Surprisingly, yes! In fact, a few studies have been done on the Marvel network and they found that it behaves very similar to a real social network. \n",
    "\n",
    "To quote the authors of the research paper \"Marvel Universe looks almost like a real social network\": *...most pairs of characters that have jointly appeared in the same comic book have fought shoulder to shoulder or each other, or have had some other strong relationship, like family ties or kidnapping. Thus, it shares, in its artificial way, the true social nature of scientific collaboration networks...*\n",
    "\n",
    "The original dataset contains 6,486 heroes, but today we'll be using a condensed data set of 327 heroes and 9891 connections to speed up the analysis. The heroes contained in our data set were chosen because they had the most connections in the network. Here is what the graph looks like:\n",
    "\n",
    "![title](images-lab/hero_network.png)\n",
    "\n",
    "Because we have weighted edges, we can use a similar tool of analysis as we did for the taxi pickup data by setting a minimum threshold such that if any edges have weights less than that, we won't include that edge in our graph instance. Run the following block of code to identify a community. Feel free to change the `min_weight` and `density` values to see if you can find other clusters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6241e9d2",
   "metadata": {},
   "outputs": [],
   "source": [
    "min_weight = 70\n",
    "density = 7\n",
    "marvel, edge_list = generate_marvel(min_weight, show = False)\n",
    "solve_network(marvel, edge_list, density, display_color = False, display_community = False)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0b6f898b",
   "metadata": {},
   "source": [
    "**Q:** Using min_weight = 70 and density = 7, how many people were in the community you just found?\n",
    "\n",
    "**A:** <font color='blue'> 24 </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a9605312",
   "metadata": {},
   "source": [
    "How awesome is that? We just found a cluster of heroes that are some of the most well-known heroes from the Marvel universe. On first glance, we have characters from \n",
    "- the cinematic universe of the *Avengers*: Quicksilver, Thor, Scarlet Witch, Jarvis, Hawk(eye), Black Widow, Captain America, Iron Man, Ant-man, Vision, Hulk, Spider-man, the Wasp, and Black Panther. \n",
    "- the *Fantastic Four*: the Thing, Invisible Woman, Mr. Fantastic, and Human Torch\n",
    "\n",
    "(please excuse our limited Marvel knowledge)\n",
    "\n",
    "Here is the what that subgraph looks like in the whole graph:\n",
    "\n",
    "![title](images-lab/hero_community_network.png)\n",
    "\n",
    "Here is what the subgraph edges look like (the graph itself is formatted a bit differently here):\n",
    "\n",
    "![title](images-lab/hero_community_edges.png)\n",
    "\n",
    "Also, if we zoom in on some vertices in the cluster, we'll see that they are all highly connected characters:\n",
    "\n",
    "![title](images-lab/marvel_community_zoomin.png)\n",
    "\n",
    "An initial thought you might have is that this yields the cluster of heroes with the top 24 number of connections in the network. Running some tests, we found the following stats:\n",
    "\n",
    "- ordering heroes by the sum of the weights of edges they were connected to in the graph:\n",
    "    - 9 out of the top 10 heroes are in our subgraph\n",
    "    - the heroes in our subgraph are in the top 46\n",
    "- ordering heroes by the number of edges they were connected to in the graph:\n",
    "    - 8 out of the top 10 heroes are in our subgraph\n",
    "    - the heroes in our subgraph are in the top 52\n",
    "\n",
    "Whereas the meaning behind the community we found in the anonymous Facebook network was hard to decipher, our Marvel network has allowed us to identiify a pretty neat and meaningful cluster. Hopefully, you're beginning to see the usefulness behind the densest subgraph problem!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a1cad341",
   "metadata": {},
   "source": [
    "### Erdos Number Network\n",
    "Finally, let's take a look at the Erdos Number network. Similar to Bacon numbers which exist in the realm of movies and actors, Erdos numbers describe how \"far apart\" you are from publishing a paper with the famous mathematician, Paul Erdos. Erdos himself has an Erdos number of 0, people who have directly collaborated with Erdos have Erdos number 1, people who have collaborated with an author who has Erdos number 1 have Erdos number 2, and so on. We'll use the densest subgraph problem to see if we can identify a meaningful community in this network.\n",
    "\n",
    "Below is the graph of all people who have an Erdos number of 2 or less as of 2002. Unfortunately, we weren't able to find a complete graph that had edges between authors of Erdos number 2, but this graph has an edge between Erdos and people with Erdos number 1, edges between Erdos number 1 authors, and edges between Erdos number 1 and 2 authors if they published a paper together. There are 6927 authors (one of which is our very own Professor David Shmoys!) and 11850 edges.\n",
    "\n",
    "![title](images-lab/erdos2_full.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4d9b8d54",
   "metadata": {},
   "source": [
    "**Q:** Which Erdos number(s) do you expect to be most prominent in the community we find and why?\n",
    "\n",
    "**A:** <font color='blue'> Erdos number 0 (because everyone with Erdos number 1 has an edge connecting them to Erdos) and/or Erdos number 1 (because it is reasonable to expect the subgraph to not just consist of Erdos himself and Erdos number 1 authors can be expected to have more edges in general compared to Erdos number 2 authors) </font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "47bc81be",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Run this block of code to find the community\n",
    "density = 7.8\n",
    "erdos, edge_list = generate_erdos(show = False)\n",
    "community = solve_network(erdos, edge_list, density, display_color = False, display_community = False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8b7f1ad5",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Now run this block of code to print a list of the names of the authors in the community\n",
    "authors = erdos_dict()\n",
    "print('\\nAuthors in the community found: ')\n",
    "print(list(map(lambda x:authors[x], community)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9445a430",
   "metadata": {},
   "source": [
    "Here is what the community looks like with the following color codes:\n",
    "\n",
    "- Erdos number 0 => yellow\n",
    "- Erdos number 1 => red\n",
    "- Erdos number 2 => magenta\n",
    "\n",
    "![title](images-lab/erdos2_edges.png)\n",
    "\n",
    "What we notice is that first, Paul Erdos himself is indeed in the community (hopefully this does not surprise you, afterall the network is centered around him), and second, the majority of people in our densest subgraph have Erdos number 1. In fact, we ran the Densest Subgraph problem on a network of only Erdos number 1 authors (511 authors total) and found a cluster of 50 people. All but one person in that cluster were included in our overall Erdos sommunity. \n",
    "\n",
    "Here is the makeup of our 78 person community:\n",
    "\n",
    "- 1 is Erdos 0 (Paul Erdos)\n",
    "- 65 are Erdos 1\n",
    "- 12 are Erdos 2\n",
    "\n",
    "*If you want to take a look at the community we found from the Erdos number 1 authors or the list of Erdos number 1 authors itself, they are located in the data-lab folder associated with this lab.*\n",
    "\n",
    "Again, we're starting to see that the communities we can find using the Densest Subgraph can reflect common characteristics or display certain behaviors. Here, we can continue to ask more questions if we want to find more underlying meanings such as: what fields of mathematics did this community publish papers in, did all of these authors publish papers with one common coauthor, etc. Ultimately, we can use the minimum cut reduction to help us solve all sorts of problems, one of which we've shown today through the Densest Subgraph problem and social network analysis."
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}