sim-dist-exp.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Graphical Models: Similarity Distribution Experimentation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import necessary libraries\n",
    "import networkx as nx\n",
    "from networkx.algorithms import approximation\n",
    "from networkx.algorithms.approximation import independent_set, clique\n",
    "import matplotlib.pyplot as plt\n",
    "from matplotlib.pyplot import figure\n",
    "import random, itertools as it\n",
    "from scipy.special import comb\n",
    "import pandas as pd\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Similarity Implementations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### General Methods"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# get all children in a dictionary including their respective weights (chains taken into account)\n",
    "def get_all_children(graph, parent, children_dict={}, carry=1):\n",
    "    weights = nx.get_edge_attributes(graph, 'weight')\n",
    "    for i in graph.out_edges(parent):\n",
    "        children_dict[i[1]] = carry*weights[i]\n",
    "        get_all_children(graph, i[1], children_dict=children_dict, carry=weights[i])\n",
    "    return children_dict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# (Adapted from function above)\n",
    "# Get all children in a dictionary including their respective weights (chains taken into account)\n",
    "def get_descendants(graph, parent, children_dict={}, carry=1):\n",
    "    weights = nx.get_edge_attributes(graph, 'weight')\n",
    "    \n",
    "    for i in graph.out_edges(parent):\n",
    "        children_dict[i[1]] = carry*weights[i]\n",
    "        get_descendants(graph, i[1], children_dict=children_dict, carry=weights[i])\n",
    "    \n",
    "    return children_dict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Returns children of a single node\n",
    "def get_children(gm, parent):\n",
    "    children_weights = {}\n",
    "    weights = nx.get_edge_attributes(gm, 'weight')\n",
    "    \n",
    "    for i in gm.out_edges(parent):\n",
    "        children_weights[i[1]] = weights[i]\n",
    "\n",
    "    return children_weights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_node_children_subgraph(graph, snode, childgraph):\n",
    "    cnodes = graph.neighbors(snode)\n",
    "    edges = nx.edges(graph)\n",
    "    for i in cnodes:\n",
    "        childgraph.add_node(i)\n",
    "        childgraph.add_edge(snode, i)\n",
    "        childgraph = find_node_children_subgraph(graph, i, childgraph)\n",
    "    return childgraph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Jaccard Index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_intersection(graph, children_a, children_b):\n",
    "    inter = 0\n",
    "    for i in children_a:\n",
    "        if i in children_b:\n",
    "            if children_a[i] < children_b[i]:\n",
    "                inter += children_a[i]\n",
    "            else:\n",
    "                inter += children_b[i]\n",
    "    return inter  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# helper func to calculate the union\n",
    "def calculate_union(graph, children_a, children_b):\n",
    "    union = 0\n",
    "    for i in children_a:\n",
    "        if not i in children_b:\n",
    "            union += 1\n",
    "        else:\n",
    "            union += children_a[i]\n",
    "    for i in children_b:\n",
    "        if not i in children_a:\n",
    "            union += 1\n",
    "        else:\n",
    "            union += children_b[i]\n",
    "    union -= calculate_intersection(graph, children_a, children_b)\n",
    "    return union"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# calculate the similarity, compares both methods\n",
    "def calculate_similarity(graph, node_a, node_b):\n",
    "    children_a = get_all_children(graph, node_a, {})\n",
    "    children_b = get_all_children(graph, node_b, {})\n",
    "    \n",
    "    intersection = calculate_intersection(graph, children_a, children_b)\n",
    "    union = calculate_union(graph, children_a, children_b)\n",
    "    \n",
    "    results = 0\n",
    "    if union != 0:\n",
    "        results = intersection/union\n",
    "            \n",
    "    return results"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Edit-Distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Edit-distance similarity implementation based only on a node's children."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Returns the similarity of node B compared to node A, based on children\n",
    "def get_immediate_similarity(gm, A, B):\n",
    "    cost = 0.0\n",
    "    A_children = get_children(gm, A)\n",
    "    B_children = get_children(gm, B)\n",
    "    \n",
    "    if len(A_children) > 0:\n",
    "        for child in A_children:\n",
    "            if child in B_children:\n",
    "                diff = abs(A_children[child] - B_children[child])\n",
    "                cost += diff\n",
    "            else:\n",
    "                cost += 1\n",
    "\n",
    "        return cost / len(A_children)\n",
    "    \n",
    "    else:\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Returns the node that is most similar to the input node\n",
    "def find_most_immediate_similar(gm, A):\n",
    "    nodes = list(gm.nodes)\n",
    "    nodes.remove(A)\n",
    "    \n",
    "    max_similarity = get_immediate_similarity(gm, A, nodes[0])\n",
    "    max_sim_node = nodes[0]\n",
    "    \n",
    "    for node in nodes:\n",
    "        node_similarity = get_immediate_similarity(gm, A, node)\n",
    "        \n",
    "        if node_similarity < max_similarity:\n",
    "            max_sim_node = node\n",
    "            max_similarity = node_similarity\n",
    "    \n",
    "    return max_sim_node"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Edit-distance similarity implementation based on all descendants of a node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Returns the similarity of node B compared to node A\n",
    "def get_full_similarity(gm, A, B):\n",
    "    cost = 0.0\n",
    "    A_children = get_descendants(gm, A, {}, 1)\n",
    "    B_children = get_descendants(gm, B, {}, 1)\n",
    "    \n",
    "    if len(A_children) > 0:\n",
    "        for child in A_children:\n",
    "            if child in B_children:\n",
    "                diff = abs(A_children[child] - B_children[child])\n",
    "                cost += diff\n",
    "            else:\n",
    "                cost += 1\n",
    "        return 1-(cost / len(A_children))\n",
    "    else:\n",
    "        return 1\n",
    "\n",
    "# Optional print line in for loop for debugging: \n",
    "# print(child, A_children[child], B_children[child])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# get_full_similarity(dg, 1, 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# dg = nx.DiGraph()\n",
    "# dg.add_node(1)\n",
    "# dg.add_node(2)\n",
    "# dg.add_node(3)\n",
    "# dg.add_node(4)\n",
    "# dg.add_node(5)\n",
    "# dg.add_edge(1, 3, weight=1)\n",
    "# dg.add_edge(2, 3, weight=1)\n",
    "# dg.add_edge(3, 4, weight=1)\n",
    "# dg.add_edge(4, 5, weight=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# nx.draw_networkx(dg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Returns the node that is most similar to the input node\n",
    "def find_most_similar(gm, A):\n",
    "    nodes = list(gm.nodes)\n",
    "    nodes.remove(A)\n",
    "    \n",
    "    max_similarity = get_full_similarity(gm, A, nodes[0])\n",
    "    max_sim_node = nodes[0]\n",
    "    for node in nodes:\n",
    "        node_similarity = get_full_similarity(gm, A, node)\n",
    "        \n",
    "        if node_similarity < max_similarity:\n",
    "            max_sim_node = node\n",
    "            max_similarity = node_similarity\n",
    "    \n",
    "    return max_sim_node"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### NetworkX: Edit-Distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "# nx.graph_edit_distance(Graph1, Graph2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### NetworkX: SimRank"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "# nx.algorithms.similarity.simrank_similarity(graph, source=\"node_a\", target=\"node_b\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Generating Random Directed Graphs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def addNodes(gm, num_nodes):\n",
    "    node_list = []\n",
    "    \n",
    "    for i in range(num_nodes):\n",
    "        gm.add_node(i)\n",
    "\n",
    "    return gm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "# NOTE: This function does not have functionality implemented yet that \n",
    "# prevents cycles from occurring\n",
    "def addEdges(gm, num_nodes, num_edges):\n",
    "    for i in range(num_edges):\n",
    "        parent = random.randrange(num_nodes)\n",
    "        child = random.randrange(num_nodes)\n",
    "        \n",
    "        conditional_prob = random.uniform(0, 1)\n",
    "        gm.add_edge(parent, child, weight=conditional_prob)\n",
    "            \n",
    "        if not nx.is_directed_acyclic_graph(gm):\n",
    "            gm.remove_edge(parent, child)\n",
    "        \n",
    "    return gm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def makeDirectedGraph(num_nodes, num_edges):\n",
    "    dg = nx.DiGraph() # creates directed graph\n",
    "    dg = addNodes(dg, num_nodes)\n",
    "    dg = addEdges(dg, num_nodes, num_edges)\n",
    "    return dg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Randomizes edge weights\n",
    "def makeDirectedPath(num_nodes):\n",
    "    pdg = nx.path_graph(num_nodes, create_using=nx.DiGraph())\n",
    "    for i in pdg.edges():\n",
    "        pdg.edges[i[0], i[1]]['weight'] = weight=random.uniform(0, 1)\n",
    "    return pdg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Sets all edge weights to 1\n",
    "def makeDirectedPathOne(num_nodes):\n",
    "    pdg = nx.path_graph(num_nodes, create_using=nx.DiGraph())\n",
    "    for i in pdg.edges():\n",
    "        pdg.edges[i[0], i[1]]['weight'] = 1\n",
    "    return pdg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "def makeDirectedStarGraph(num_nodes):\n",
    "    sdg = nx.DiGraph()\n",
    "    sdg.add_node(0)\n",
    "    for i in range(1, num_nodes+1):\n",
    "        sdg.add_node(i)\n",
    "        sdg.add_edge(0, i, weight=random.uniform(0, 1))\n",
    "    return sdg"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Running Experiments"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Distribution of Similarity Over Random Graphs of Constant Size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "def getSimilarityData(gm):\n",
    "    node_list = list(gm.nodes)\n",
    "    node_pairs = list(it.combinations(node_list, 2))\n",
    "\n",
    "    ed_imm_sim, ed_full_sim, ji_sim = [], [], []\n",
    "\n",
    "    for pair in node_pairs:\n",
    "        ed_imm_sim.append(get_immediate_similarity(gm, pair[0], pair[1]))\n",
    "        ed_imm_sim.append(get_immediate_similarity(gm, pair[1], pair[0]))\n",
    "\n",
    "        ed_full_sim.append(get_full_similarity(gm, pair[0], pair[1]))\n",
    "        ed_full_sim.append(get_full_similarity(gm, pair[1], pair[0]))\n",
    "\n",
    "        ji_sim.append(calculate_similarity(gm, pair[0], pair[1]))\n",
    "        ji_sim.append(calculate_similarity(gm, pair[1], pair[0]))\n",
    "\n",
    "    similarity_data = {\"Edit-Distance Immediate Similarity\": ed_imm_sim, \n",
    "                       \"Edit-Distance Full Similarity\": ed_full_sim,\n",
    "                       \"Jaccard Index Similarity\": ji_sim}\n",
    "        \n",
    "    return similarity_data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def getCliqueData(gm):\n",
    "    node_list = list(gm.nodes)\n",
    "    num_rows = len(list(it.combinations(node_list, 2))) * 2\n",
    "    \n",
    "    longest_max_indep_set = len(independent_set.maximum_independent_set(gm))\n",
    "    max_cliques = list(clique.clique_removal(gm)[1]) * num_rows\n",
    "    num_max_cliques = len(max_cliques)\n",
    "    longest_max_clique = len(max_cliques[0])\n",
    "    \n",
    "    clique_data = {\"Longest Maximum Independent Set\": [longest_max_indep_set] * num_rows,\n",
    "                   \"Number of Maximum Cliques\": [num_max_cliques] * num_rows, \n",
    "                   \"Longest Maximum Clique\": [longest_max_clique] * num_rows}\n",
    "    \n",
    "    return clique_data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "def getGraphSimilarityList(num_graphs, num_nodes, num_edges): \n",
    "    graph_sim_list = []\n",
    "    \n",
    "    for i in range(num_graphs):\n",
    "        dg = makeDirectedGraph(num_nodes, num_edges)\n",
    "        \n",
    "        similarity_data = getSimilarityData(dg)\n",
    "        clique_data = getCliqueData(dg) \n",
    "        similarity_data.update(clique_data)\n",
    "                        \n",
    "        graph_sim = pd.DataFrame(data = similarity_data)\n",
    "        graph_sim_list.append(graph_sim)\n",
    "    \n",
    "    return graph_sim_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "# similarity_dist = getGraphSimilarityList(2, 10, 15)\n",
    "# similarity_dist"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Condensing Data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "column_list = [\"Edit-Distance Immediate Similarity\", \"Edit-Distance Full Similarity\", \n",
    "                 \"Jaccard Index Similarity\",\n",
    "                 \"Longest Maximum Independent Set\",\n",
    "                 \"Number of Maximum Cliques\",\n",
    "                 \"Longest Maximum Clique\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "metrics = [\"mean\", \"50%\", \"std\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "# def getLists(experiment_data):\n",
    "#     metric_values = []\n",
    "    \n",
    "#     for metric in metrics:\n",
    "#         ed_imm_sim, ed_full_sim, ji_sim = [], [], []\n",
    "#         longest_max_ind_set, num_max_cliques, longest_max_clique = [], [], []\n",
    "\n",
    "#         similarity_lists = [ed_imm_sim, ed_full_sim, ji_sim, longest_max_ind_set,\n",
    "#                             num_max_cliques, longest_max_clique]\n",
    "\n",
    "#         for graph_df in experiment_data:\n",
    "#             summary = graph_df.describe(include = \"all\")\n",
    "            \n",
    "#             for index in range(len(column_list)):\n",
    "#                 similarity_lists[index].append(summary[column_list[index]][metric])\n",
    "        \n",
    "#         metric_values.append(similarity_lists)\n",
    "    \n",
    "#     return metric_values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "def getGraphSummaryRow(graph_summary): \n",
    "    graph_summary_row = []\n",
    "    \n",
    "    for column in column_list:\n",
    "        graph_summary_row.append(graph_summary[column][\"mean\"])\n",
    "        graph_summary_row.append(graph_summary[column][\"50%\"])\n",
    "        graph_summary_row.append(graph_summary[column][\"std\"])\n",
    "    \n",
    "    return tuple(graph_summary_row)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "def getCondensedSimilarityDistribution(graph_dist_list):\n",
    "    cols = pd.MultiIndex.from_product([column_list, metrics])\n",
    "    similarity_dist = pd.DataFrame(index = [\"Graph Number\"], columns = cols)\n",
    "    \n",
    "    index = 0\n",
    "    for graph_similarity in graph_dist_list:\n",
    "        graph_summary = graph_similarity.describe(include=\"all\")\n",
    "        graph_summary_row = getGraphSummaryRow(graph_summary)\n",
    "    \n",
    "        similarity_dist.loc[index,:] = graph_summary_row\n",
    "        index += 1\n",
    "    \n",
    "    return similarity_dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "# condensed_similarity_dist = getCondensedSimilarityDistribution(similarity_dist)\n",
    "# condensed_similarity_dist"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Distribution Over Varying Graph Sizes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "column_list = [\"Edit-Distance Immediate Similarity\", \"Edit-Distance Full Similarity\", \n",
    "                 \"Jaccard Index Similarity\",\n",
    "                 \"Longest Maximum Independent Set\",\n",
    "                 \"Number of Maximum Cliques\",\n",
    "                 \"Longest Maximum Clique\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "# def getUpdatedColumnList(column_list):\n",
    "#     updated_column_list = []\n",
    "    \n",
    "#     for column in column_list:\n",
    "#         updated_column_list.append(column + \" [Average]\")\n",
    "#         updated_column_list.append(column + \" [Median]\")\n",
    "#         updated_column_list.append(column + \" [STD]\")\n",
    "    \n",
    "#     return updated_column_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "nodes_to_edges_factor = 1.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "def getNewRow(graph_distribution): \n",
    "    new_row = []\n",
    "    \n",
    "    for column in column_list:\n",
    "        similarities = graph_distribution[column][\"mean\"]\n",
    "        new_row.append(similarities.mean())\n",
    "        new_row.append(similarities.median())\n",
    "        new_row.append(similarities.std())\n",
    "\n",
    "    return tuple(new_row)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "def getGraphSizeDistribution(num_graphs, start_num_nodes, end_num_nodes, step):    \n",
    "    cols = pd.MultiIndex.from_product([column_list, metrics])\n",
    "    graph_size_dist = pd.DataFrame(index = [[\"Number of Nodes Per Graph\"], [\"Number of Graphs\"]], columns = cols)\n",
    "\n",
    "    for num_nodes in range(start_num_nodes, end_num_nodes, step):\n",
    "        num_edges = int(num_nodes * nodes_to_edges_factor)\n",
    "        \n",
    "        graph_similarity_list = getGraphSimilarityList(num_graphs, num_nodes, num_edges)\n",
    "        graph_distribution = getCondensedSimilarityDistribution(graph_similarity_list)\n",
    "        \n",
    "        new_row = getNewRow(graph_distribution)\n",
    "        graph_size_dist.loc[(num_nodes, num_graphs),:] = new_row\n",
    "\n",
    "    return graph_size_dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "# similarity_list = getGraphSimilarityList(25, 40, 60)\n",
    "# similarity_dist = getCondensedSimilarityDistribution(similarity_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exporting Data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "# condensed_similarity_dist.to_csv(\"Data/similarity-distribution.csv\", index=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "# graph_size_dist.to_csv(\"Data/graph-size-distrubtion-5-10-41-10.csv\", index=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Analysis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Distribution Over Varying Graph Sizes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "ename": "FileNotFoundError",
     "evalue": "[Errno 2] File Data/graph-size-distrubtion-5-10-41-10.csv does not exist: 'Data/graph-size-distrubtion-5-10-41-10.csv'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mFileNotFoundError\u001b[0m                         Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-44-9affd2142eb5>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mgraph_dist\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mpd\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mread_csv\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Data/graph-size-distrubtion-5-10-41-10.csv\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      2\u001b[0m \u001b[0mgraph_dist\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mhead\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/opt/anaconda3/envs/amistad/lib/python3.7/site-packages/pandas/io/parsers.py\u001b[0m in \u001b[0;36mparser_f\u001b[0;34m(filepath_or_buffer, sep, delimiter, header, names, index_col, usecols, squeeze, prefix, mangle_dupe_cols, dtype, engine, converters, true_values, false_values, skipinitialspace, skiprows, skipfooter, nrows, na_values, keep_default_na, na_filter, verbose, skip_blank_lines, parse_dates, infer_datetime_format, keep_date_col, date_parser, dayfirst, cache_dates, iterator, chunksize, compression, thousands, decimal, lineterminator, quotechar, quoting, doublequote, escapechar, comment, encoding, dialect, error_bad_lines, warn_bad_lines, delim_whitespace, low_memory, memory_map, float_precision)\u001b[0m\n\u001b[1;32m    674\u001b[0m         )\n\u001b[1;32m    675\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 676\u001b[0;31m         \u001b[0;32mreturn\u001b[0m \u001b[0m_read\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mfilepath_or_buffer\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkwds\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    677\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    678\u001b[0m     \u001b[0mparser_f\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m__name__\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mname\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/opt/anaconda3/envs/amistad/lib/python3.7/site-packages/pandas/io/parsers.py\u001b[0m in \u001b[0;36m_read\u001b[0;34m(filepath_or_buffer, kwds)\u001b[0m\n\u001b[1;32m    446\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    447\u001b[0m     \u001b[0;31m# Create the parser.\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 448\u001b[0;31m     \u001b[0mparser\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mTextFileReader\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mfp_or_buf\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0mkwds\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    449\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    450\u001b[0m     \u001b[0;32mif\u001b[0m \u001b[0mchunksize\u001b[0m \u001b[0;32mor\u001b[0m \u001b[0miterator\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/opt/anaconda3/envs/amistad/lib/python3.7/site-packages/pandas/io/parsers.py\u001b[0m in \u001b[0;36m__init__\u001b[0;34m(self, f, engine, **kwds)\u001b[0m\n\u001b[1;32m    878\u001b[0m             \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0moptions\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m\"has_index_names\"\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mkwds\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m\"has_index_names\"\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    879\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 880\u001b[0;31m         \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_make_engine\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mengine\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    881\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    882\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0mclose\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/opt/anaconda3/envs/amistad/lib/python3.7/site-packages/pandas/io/parsers.py\u001b[0m in \u001b[0;36m_make_engine\u001b[0;34m(self, engine)\u001b[0m\n\u001b[1;32m   1112\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0m_make_engine\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mengine\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;34m\"c\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1113\u001b[0m         \u001b[0;32mif\u001b[0m \u001b[0mengine\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m\"c\"\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 1114\u001b[0;31m             \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_engine\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mCParserWrapper\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mf\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0moptions\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   1115\u001b[0m         \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1116\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mengine\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m\"python\"\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/opt/anaconda3/envs/amistad/lib/python3.7/site-packages/pandas/io/parsers.py\u001b[0m in \u001b[0;36m__init__\u001b[0;34m(self, src, **kwds)\u001b[0m\n\u001b[1;32m   1889\u001b[0m         \u001b[0mkwds\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m\"usecols\"\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0musecols\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1890\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 1891\u001b[0;31m         \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_reader\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mparsers\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mTextReader\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0msrc\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0mkwds\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   1892\u001b[0m         \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0munnamed_cols\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_reader\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0munnamed_cols\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1893\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32mpandas/_libs/parsers.pyx\u001b[0m in \u001b[0;36mpandas._libs.parsers.TextReader.__cinit__\u001b[0;34m()\u001b[0m\n",
      "\u001b[0;32mpandas/_libs/parsers.pyx\u001b[0m in \u001b[0;36mpandas._libs.parsers.TextReader._setup_parser_source\u001b[0;34m()\u001b[0m\n",
      "\u001b[0;31mFileNotFoundError\u001b[0m: [Errno 2] File Data/graph-size-distrubtion-5-10-41-10.csv does not exist: 'Data/graph-size-distrubtion-5-10-41-10.csv'"
     ]
    }
   ],
   "source": [
    "graph_dist = pd.read_csv(\"Data/graph-size-distrubtion-5-10-41-10.csv\")\n",
    "graph_dist.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'graph_dist' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-43-f19832434102>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mwidth\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m0.27\u001b[0m       \u001b[0;31m# the width of the bars\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      8\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 9\u001b[0;31m \u001b[0med_imm_sim\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mgraph_dist\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m\"Edit-Distance Immediate Similarity\"\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     10\u001b[0m \u001b[0med_f_sim\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mgraph_dist\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m\"Edit-Distance Full Similarity\"\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m \u001b[0mji_sim\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mgraph_dist\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m\"Jaccard Index Similarity (Method 1)\"\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mNameError\u001b[0m: name 'graph_dist' is not defined"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAD8CAYAAAB0IB+mAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+j8jraAAANgElEQVR4nO3ccYjfd33H8efLxE6mtY7lBEmi7Vi6Gsqg7ug6hFnRjbR/JP8USaC4SmnArQ5mETocKvWvKUMQsmm2iVPQWv1DD4nkD1fpECO50lmalMAtOnNE6Fm7/lO0Znvvj99P77hcct/e/e4u3vv5gMDv+/t9fr9758PdM798f/f7paqQJG1/r9rqASRJm8PgS1ITBl+SmjD4ktSEwZekJgy+JDWxavCTfC7Jc0meucLtSfLpJHNJnk7ytsmPKUlaryHP8D8PHLjK7XcB+8Z/jgL/tP6xJEmTtmrwq+oJ4GdXWXII+EKNnALekORNkxpQkjQZOyfwGLuBC0uO58fX/WT5wiRHGf0vgNe+9rV/dMstt0zgy0tSH08++eRPq2pqLfedRPCzwnUrfl5DVR0HjgNMT0/X7OzsBL68JPWR5L/Xet9J/JbOPLB3yfEe4OIEHleSNEGTCP4M8N7xb+vcAbxYVZedzpEkba1VT+kk+TJwJ7AryTzwUeDVAFX1GeAEcDcwB7wEvG+jhpUkrd2qwa+qI6vcXsBfTWwiSdKG8J22ktSEwZekJgy+JDVh8CWpCYMvSU0YfElqwuBLUhMGX5KaMPiS1ITBl6QmDL4kNWHwJakJgy9JTRh8SWrC4EtSEwZfkpow+JLUhMGXpCYMviQ1YfAlqQmDL0lNGHxJasLgS1ITBl+SmjD4ktSEwZekJgy+JDVh8CWpCYMvSU0YfElqwuBLUhMGX5KaMPiS1ITBl6QmDL4kNTEo+EkOJDmXZC7Jwyvc/uYkjyd5KsnTSe6e/KiSpPVYNfhJdgDHgLuA/cCRJPuXLfs74LGqug04DPzjpAeVJK3PkGf4twNzVXW+ql4GHgUOLVtTwOvHl28ALk5uREnSJAwJ/m7gwpLj+fF1S30MuDfJPHAC+MBKD5TkaJLZJLMLCwtrGFeStFZDgp8Vrqtlx0eAz1fVHuBu4ItJLnvsqjpeVdNVNT01NfXKp5UkrdmQ4M8De5cc7+HyUzb3A48BVNX3gNcAuyYxoCRpMoYE/zSwL8lNSa5j9KLszLI1PwbeBZDkrYyC7zkbSbqGrBr8qroEPAicBJ5l9Ns4Z5I8kuTgeNlDwANJfgB8Gbivqpaf9pEkbaGdQxZV1QlGL8Yuve4jSy6fBd4+2dEkSZPkO20lqQmDL0lNGHxJasLgS1ITBl+SmjD4ktSEwZekJgy+JDVh8CWpCYMvSU0YfElqwuBLUhMGX5KaMPiS1ITBl6QmDL4kNWHwJakJgy9JTRh8SWrC4EtSEwZfkpow+JLUhMGXpCYMviQ1YfAlqQmDL0lNGHxJasLgS1ITBl+SmjD4ktSEwZekJgy+JDVh8CWpCYMvSU0MCn6SA0nOJZlL8vAV1rwnydkkZ5J8abJjSpLWa+dqC5LsAI4BfwbMA6eTzFTV2SVr9gF/C7y9ql5I8saNGliStDZDnuHfDsxV1fmqehl4FDi0bM0DwLGqegGgqp6b7JiSpPUaEvzdwIUlx/Pj65a6Gbg5yXeTnEpyYKUHSnI0yWyS2YWFhbVNLElakyHBzwrX1bLjncA+4E7gCPAvSd5w2Z2qjlfVdFVNT01NvdJZJUnrMCT488DeJcd7gIsrrPlGVf2yqn4InGP0D4Ak6RoxJPingX1JbkpyHXAYmFm25uvAOwGS7GJ0iuf8JAeVJK3PqsGvqkvAg8BJ4Fngsao6k+SRJAfHy04Czyc5CzwOfKiqnt+ooSVJr1yqlp+O3xzT09M1Ozu7JV9bkn5TJXmyqqbXcl/faStJTRh8SWrC4EtSEwZfkpow+JLUhMGXpCYMviQ1YfAlqQmDL0lNGHxJasLgS1ITBl+SmjD4ktSEwZekJgy+JDVh8CWpCYMvSU0YfElqwuBLUhMGX5KaMPiS1ITBl6QmDL4kNWHwJakJgy9JTRh8SWrC4EtSEwZfkpow+JLUhMGXpCYMviQ1YfAlqQmDL0lNGHxJasLgS1ITg4Kf5ECSc0nmkjx8lXX3JKkk05MbUZI0CasGP8kO4BhwF7AfOJJk/wrrrgf+Gvj+pIeUJK3fkGf4twNzVXW+ql4GHgUOrbDu48AngJ9PcD5J0oQMCf5u4MKS4/nxdb+W5DZgb1V982oPlORoktkkswsLC694WEnS2g0Jfla4rn59Y/Iq4FPAQ6s9UFUdr6rpqpqempoaPqUkad2GBH8e2LvkeA9wccnx9cCtwHeS/Ai4A5jxhVtJurYMCf5pYF+Sm5JcBxwGZn51Y1W9WFW7qurGqroROAUcrKrZDZlYkrQmqwa/qi4BDwIngWeBx6rqTJJHkhzc6AElSZOxc8iiqjoBnFh23UeusPbO9Y8lSZo032krSU0YfElqwuBLUhMGX5KaMPiS1ITBl6QmDL4kNWHwJakJgy9JTRh8SWrC4EtSEwZfkpow+JLUhMGXpCYMviQ1YfAlqQmDL0lNGHxJasLgS1ITBl+SmjD4ktSEwZekJgy+JDVh8CWpCYMvSU0YfElqwuBLUhMGX5KaMPiS1ITBl6QmDL4kNWHwJakJgy9JTRh8SWpiUPCTHEhyLslckodXuP2DSc4meTrJt5O8ZfKjSpLWY9XgJ9kBHAPuAvYDR5LsX7bsKWC6qv4Q+BrwiUkPKklanyHP8G8H5qrqfFW9DDwKHFq6oKoer6qXxoengD2THVOStF5Dgr8buLDkeH583ZXcD3xrpRuSHE0ym2R2YWFh+JSSpHUbEvyscF2tuDC5F5gGPrnS7VV1vKqmq2p6ampq+JSSpHXbOWDNPLB3yfEe4OLyRUneDXwYeEdV/WIy40mSJmXIM/zTwL4kNyW5DjgMzCxdkOQ24LPAwap6bvJjSpLWa9XgV9Ul4EHgJPAs8FhVnUnySJKD42WfBF4HfDXJfyaZucLDSZK2yJBTOlTVCeDEsus+suTyuyc8lyRpwnynrSQ1YfAlqQmDL0lNGHxJasLgS1ITBl+SmjD4ktSEwZekJgy+JDVh8CWpCYMvSU0YfElqwuBLUhMGX5KaMPiS1ITBl6QmDL4kNWHwJakJgy9JTRh8SWrC4EtSEwZfkpow+JLUhMGXpCYMviQ1YfAlqQmDL0lNGHxJasLgS1ITBl+SmjD4ktSEwZekJgy+JDVh8CWpCYMvSU0MCn6SA0nOJZlL8vAKt/9Wkq+Mb/9+khsnPagkaX1WDX6SHcAx4C5gP3Akyf5ly+4HXqiq3wc+Bfz9pAeVJK3PkGf4twNzVXW+ql4GHgUOLVtzCPi38eWvAe9KksmNKUlar50D1uwGLiw5ngf++EprqupSkheB3wV+unRRkqPA0fHhL5I8s5aht6FdLNurxtyLRe7FIvdi0R+s9Y5Dgr/SM/Vawxqq6jhwHCDJbFVND/j62557sci9WOReLHIvFiWZXet9h5zSmQf2LjneA1y80pokO4EbgJ+tdShJ0uQNCf5pYF+Sm5JcBxwGZpatmQH+Ynz5HuDfq+qyZ/iSpK2z6imd8Tn5B4GTwA7gc1V1JskjwGxVzQD/CnwxyRyjZ/aHB3zt4+uYe7txLxa5F4vci0XuxaI170V8Ii5JPfhOW0lqwuBLUhMbHnw/lmHRgL34YJKzSZ5O8u0kb9mKOTfDanuxZN09SSrJtv2VvCF7keQ94++NM0m+tNkzbpYBPyNvTvJ4kqfGPyd3b8WcGy3J55I8d6X3KmXk0+N9ejrJ2wY9cFVt2B9GL/L+F/B7wHXAD4D9y9b8JfCZ8eXDwFc2cqat+jNwL94J/Pb48vs778V43fXAE8ApYHqr597C74t9wFPA74yP37jVc2/hXhwH3j++vB/40VbPvUF78afA24BnrnD73cC3GL0H6g7g+0Med6Of4fuxDItW3YuqeryqXhofnmL0noftaMj3BcDHgU8AP9/M4TbZkL14ADhWVS8AVNVzmzzjZhmyFwW8fnz5Bi5/T9C2UFVPcPX3Mh0CvlAjp4A3JHnTao+70cFf6WMZdl9pTVVdAn71sQzbzZC9WOp+Rv+Cb0er7kWS24C9VfXNzRxsCwz5vrgZuDnJd5OcSnJg06bbXEP24mPAvUnmgRPABzZntGvOK+0JMOyjFdZjYh/LsA0M/nsmuReYBt6xoRNtnavuRZJXMfrU1fs2a6AtNOT7Yiej0zp3Mvpf338kubWq/meDZ9tsQ/biCPD5qvqHJH/C6P0/t1bV/238eNeUNXVzo5/h+7EMi4bsBUneDXwYOFhVv9ik2TbbantxPXAr8J0kP2J0jnJmm75wO/Rn5BtV9cuq+iFwjtE/ANvNkL24H3gMoKq+B7yG0QerdTOoJ8ttdPD9WIZFq+7F+DTGZxnFfruep4VV9qKqXqyqXVV1Y1XdyOj1jINVteYPjbqGDfkZ+TqjF/RJsovRKZ7zmzrl5hiyFz8G3gWQ5K2Mgr+wqVNeG2aA945/W+cO4MWq+slqd9rQUzq1cR/L8Btn4F58Engd8NXx69Y/rqqDWzb0Bhm4Fy0M3IuTwJ8nOQv8L/Chqnp+66beGAP34iHgn5P8DaNTGPdtxyeISb7M6BTervHrFR8FXg1QVZ9h9PrF3cAc8BLwvkGPuw33SpK0At9pK0lNGHxJasLgS1ITBl+SmjD4ktSEwZekJgy+JDXx/4aZaro1YsjCAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "fig = plt.figure()\n",
    "ax = fig.add_subplot(111)\n",
    "\n",
    "# Adapted from https://stackoverflow.com/questions/14270391/python-matplotlib-multiple-bars\n",
    "N = 4\n",
    "ind = np.arange(N)  # the x locations for the groups\n",
    "width = 0.27       # the width of the bars\n",
    "\n",
    "ed_imm_sim = graph_dist[\"Edit-Distance Immediate Similarity\"]\n",
    "ed_f_sim = graph_dist[\"Edit-Distance Full Similarity\"]\n",
    "ji_sim = graph_dist[\"Jaccard Index Similarity (Method 1)\"]\n",
    "\n",
    "ed_imm_sim_std = graph_dist[\"Edit-Distance Immediate Similarity STD\"]\n",
    "ed_f_sim_std = graph_dist[\"Edit-Distance Full Similarity STD\"]\n",
    "ji_sim_std = graph_dist[\"Jaccard Index Similarity (Method 1) STD\"]\n",
    "\n",
    "rects1 = ax.bar(ind, 1 - ed_imm_sim, width, color='r', yerr=ed_imm_sim_std)\n",
    "rects2 = ax.bar(ind + width, 1 - ed_f_sim, width, color='g', yerr=ed_f_sim_std)\n",
    "rects3 = ax.bar(ind + width * 2, ji_sim, width, color='b', yerr=ji_sim_std)\n",
    "\n",
    "ax.set_ylabel('Similarity')\n",
    "ax.set_xlabel(\"Graph Size (Number of Nodes)\")\n",
    "ax.set_xticks(ind + width)\n",
    "ax.set_xticklabels(graph_dist[\"Nodes\"])\n",
    "ax.legend((rects1[0], rects2[0], rects3[0]), ('Edit-Distance Immediate Similarity', 'Edit-Distance Full Similarity', 'Jaccard Index Similarity (Method 1)'))\n",
    "ax.set_ylim(0, 1)\n",
    "ax.set_title(\"Similarity vs. Graph Size\")\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Other Work"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph_size_dist = pd.read_csv(\"Data/graph-size-distrubtion-5-10-41-10.csv\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph_size_dist.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.scatter(graph_size_dist[\"Nodes\"], 1 - graph_size_dist[\"Edit-Distance Immediate Similarity\"], label = \"Edit-Distance Immediate Similarity\")\n",
    "plt.scatter(graph_size_dist[\"Nodes\"], 1 - graph_size_dist[\"Edit-Distance Full Similarity\"], label = \"Edit-Distance Full Similarity\")\n",
    "plt.scatter(graph_size_dist[\"Nodes\"], graph_size_dist[\"Jaccard Index Similarity (Method 1)\"], label = \"Jaccard Index Similarity (Method 1)\")\n",
    "\n",
    "plt.xlabel('Size of Graph (Number of Nodes)')\n",
    "plt.ylabel('Similarity')\n",
    "plt.title('Similarity vs. Size of Graph')\n",
    "plt.legend()\n",
    "plt.rcParams[\"figure.figsize\"] = (10,7)\n",
    "plt.ylim(0, 1)\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.plot(graph_size_dist[\"Nodes\"], graph_size_dist[\"Longest Maximum Independent Set\"], label = \"Longest Maximum Independent Set\")\n",
    "\n",
    "plt.xlabel('Size of Graph (Number of Nodes)')\n",
    "plt.ylabel('Longest Maximum Independent Set')\n",
    "plt.title('Longest Maximum Independent Set vs. Size of Graph')\n",
    "plt.legend()\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.plot(graph_size_dist[\"Nodes\"], graph_size_dist[\"Number of Maximum Cliques\"], label = \"Number of Maximum Cliques\")\n",
    "\n",
    "plt.xlabel('Size of Graph (Number of Nodes)')\n",
    "plt.ylabel('Number of Maximum Cliques')\n",
    "plt.title('Number of Maximum Cliques vs. Size of Graph')\n",
    "plt.legend()\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.plot(graph_size_dist[\"Nodes\"], graph_size_dist[\"Longest Maximum Clique\"], label = \"Longest Maximum Clique\")\n",
    "\n",
    "plt.xlabel('Size of Graph (Number of Nodes)')\n",
    "plt.ylabel('Longest Maximum Clique')\n",
    "plt.title('Longest Maximum Clique vs. Size of Graph')\n",
    "plt.legend()\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.plot(graph_size_dist[\"Longest Maximum Independent Set\"], graph_size_dist[\"Edit-Distance Full Similarity\"], label = \"Edit-Distance Full Similarity\")\n",
    "\n",
    "plt.xlabel('Longest Maximum Independent Set')\n",
    "plt.ylabel('Edit-Distance Full Similarity')\n",
    "plt.title('Edit-Distance Full Similarity vs. Longest Maximum Independent Set')\n",
    "plt.legend()\n",
    "plt.ylim(0, 1)\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.plot(graph_size_dist[\"Longest Maximum Independent Set\"], graph_size_dist[\"Jaccard Index Similarity (Method 1)\"], label = \"Jaccard Index Similarity (Method 1)\")\n",
    "\n",
    "plt.xlabel('Longest Maximum Independent Set')\n",
    "plt.ylabel('Jaccard Index Similarity (Method 1)')\n",
    "plt.title('Jaccard Index Similarity (Method 1) vs. Longest Maximum Independent Set')\n",
    "plt.legend()\n",
    "plt.ylim(0, 1)\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Distribution of Similarity Over Random Graphs of Constant Size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sim_dist = pd.read_csv(\"Data/sim-dist-10-30-45.csv\")\n",
    "sim_dist = sim_dist.rename(columns={\"Edit-Distance Immediate Similarity Averages\": \"Edit-Distance Immediate Similarity\", \n",
    "                 \"Edit-Distance Full Similarity Averages\": \"Edit-Distance Full Similarity\",\n",
    "                \"Jaccard Index Similarity (Method 1) Averages\": \"Jaccard Index Similarity (Method 1)\"})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sim_dist.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sim_dist[\"Edit-Distance Immediate Similarity\"] = 1 - sim_dist[\"Edit-Distance Immediate Similarity\"]\n",
    "sim_dist[\"Edit-Distance Full Similarity\"] = 1 - sim_dist[\"Edit-Distance Full Similarity\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sim_dist.boxplot(column=[\"Edit-Distance Immediate Similarity\", \"Edit-Distance Full Similarity\", 'Jaccard Index Similarity (Method 1)'], figsize = (15,6), return_type = \"axes\")\n",
    "\n",
    "plt.ylabel(\"Similarity\")\n",
    "plt.xlabel(\"(Using Randomly Generated Directed Graphical Models with 30 nodes and 45 edges)\")\n",
    "plt.title(\"Similarity of Randomly Generated Directed Graphical Models\")\n",
    "plt.ylim(0, 1)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}