Communities_in_edge_labeled_graphs.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "id": "fPS7WlgtOEvZ"
   },
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "import copy\n",
    "from edgelabelgraph import EdgeLabelGraph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "from bintrees import RBTree\n",
    "\n",
    "def greedy_find_dense_label_induced_subgraph(graph, conjunction=True, return_graph=False):\n",
    "    G = graph.create_copy()\n",
    "    \n",
    "    r_v_k = dict()\n",
    "    m_k = Counter()\n",
    "    n_k = Counter()\n",
    "\n",
    "    for edge in G.edges:\n",
    "        for label in G.edge_labels[edge]:\n",
    "            m_k[label] += 1\n",
    "            for vertex in edge:\n",
    "                if not vertex in r_v_k:\n",
    "                    r_v_k[vertex] = Counter()\n",
    "                r_v_k[vertex][label] += 1\n",
    "\n",
    "    for vertex in r_v_k:\n",
    "        for label in r_v_k[vertex]:\n",
    "            n_k[label] += 1\n",
    "    \n",
    "    \n",
    "    L = []\n",
    "    L_set = set()\n",
    "    best_L = []\n",
    "    best_density = -1\n",
    "    best_G = None\n",
    "    if not conjunction and return_graph:\n",
    "        G2 = EdgeLabelGraph()\n",
    "    \n",
    "    if conjunction:\n",
    "        T = RBTree()\n",
    "        label_densities = dict()\n",
    "        for label in G.all_labels:\n",
    "            if n_k[label] == 0:\n",
    "                density = 0\n",
    "            else:\n",
    "                density = m_k[label] / n_k[label]\n",
    "            label_densities[label] = density\n",
    "            T.insert((density, label), None)\n",
    "    else:\n",
    "        n = 0\n",
    "        m = 0\n",
    "        r_v = dict()\n",
    "        for edge in G.edges:\n",
    "            for v in edge:\n",
    "                r_v[v] = 0\n",
    "\n",
    "    while len(G.all_labels) > len(L) and (not conjunction or len(T) > 0):\n",
    "        if conjunction:\n",
    "            density, k = T.pop_max()[0]\n",
    "        else:\n",
    "            best_k_density = -1\n",
    "            best_k = None\n",
    "            for k in G.all_labels:\n",
    "                if k in L_set:\n",
    "                    continue\n",
    "                if n == 0 and n_k[k] == 0:\n",
    "                    density = 0\n",
    "                else:\n",
    "                    density = (m + m_k[k])/(n + n_k[k])\n",
    "                if density > best_k_density:\n",
    "                    best_k_density = density\n",
    "                    best_k = k\n",
    "            density, k = best_k_density, best_k\n",
    "        L.append(k)\n",
    "        L_set.add(k)\n",
    "        updated_labels = []\n",
    "        for edge in tuple(G.edges):\n",
    "            u, v = edge\n",
    "            if conjunction:\n",
    "                if k in G.edge_labels[edge]:\n",
    "                    continue\n",
    "                for l in tuple(G.edge_labels[edge]):\n",
    "                    if l in L_set:\n",
    "                        continue\n",
    "                    m_k[l] -= 1\n",
    "                    r_v_k[v][l] -= 1\n",
    "                    r_v_k[u][l] -= 1\n",
    "                    if r_v_k[v][l] == 0:\n",
    "                        n_k[l] -= 1\n",
    "                    if r_v_k[u][l] == 0:\n",
    "                        n_k[l] -= 1\n",
    "                    updated_labels.append(l)\n",
    "            else:\n",
    "                if k not in G.edge_labels[edge]:\n",
    "                    continue\n",
    "                for l in tuple(G.edge_labels[edge]):\n",
    "                    if l in L_set:\n",
    "                        continue\n",
    "                    m_k[l] -= 1\n",
    "                m += 1\n",
    "                if r_v[v] == 0:\n",
    "                    for l in r_v_k[v]:\n",
    "                        n_k[l] -= 1\n",
    "                    n += 1\n",
    "                if r_v[u] == 0:\n",
    "                    for l in r_v_k[u]:\n",
    "                        n_k[l] -= 1\n",
    "                    n += 1\n",
    "                r_v[v] = 1\n",
    "                r_v[u] = 1\n",
    "            if not conjunction and return_graph:\n",
    "                G2.add_edge_with_labels(edge, G.edge_labels[edge])\n",
    "            G.delete_edge(edge)\n",
    "\n",
    "        for l in updated_labels:\n",
    "            T.pop((label_densities[l], l))\n",
    "            if n_k[l] == 0:\n",
    "                new_density = 0\n",
    "            else:\n",
    "                new_density = m_k[l] / n_k[l]\n",
    "            T.insert((new_density, l), None)\n",
    "            label_densities[l] = new_density\n",
    "\n",
    "        if density > best_density:\n",
    "            best_L = L.copy()\n",
    "            best_density = density\n",
    "            if return_graph:\n",
    "                if conjunction:\n",
    "                    best_G = G.create_copy()\n",
    "                else:\n",
    "                    best_G = G2.create_copy()\n",
    "        \n",
    "    if return_graph:\n",
    "        return (best_density, best_L, best_G)\n",
    "    return (best_density, best_L)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from datetime import datetime\n",
    "\n",
    "def repeated_find_label_subgraph(graph, conjunction=True, max_iterations=5, track_time=False):\n",
    "    results = []\n",
    "    current_graph = graph.create_copy()\n",
    "    i = 1\n",
    "    while (i <= max_iterations or max_iterations <= 0) and current_graph.number_of_edges() > 0:\n",
    "        if track_time:\n",
    "            start_time = datetime.now()\n",
    "        density, labels, return_graph = greedy_find_dense_label_induced_subgraph(\n",
    "            current_graph, conjunction=conjunction, return_graph=True)\n",
    "        print(density, labels, return_graph.number_of_nodes(), return_graph.number_of_edges())\n",
    "        if track_time:\n",
    "            print(datetime.now()-start_time)\n",
    "        results.append((density, labels, return_graph.create_copy()))\n",
    "        for edge in return_graph.edges:\n",
    "            current_graph.delete_edge(edge)\n",
    "        if not conjunction:\n",
    "            current_graph.all_labels -= set(labels)\n",
    "        i += 1\n",
    "    return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "Yzby0NnA2bY-",
    "outputId": "71e1931d-a2b2-4e86-831e-b859653b67c8"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.00 9.50 9.50 [10, 13, 18, 30, 46] [10, 13, 18, 30, 46]\n",
      "0.05 9.05 9.05 [17, 21, 27, 38, 46] [17, 21, 27, 38, 46]\n",
      "0.10 8.55 8.55 [0, 5, 27, 30, 43] [0, 5, 27, 30, 43]\n",
      "0.15 8.20 8.20 [24, 30, 33, 35, 44] [24, 30, 33, 35, 44]\n",
      "0.20 7.05 7.05 [5, 8, 10, 24, 40] [5, 8, 10, 24, 40]\n",
      "0.25 5.68 5.68 [6, 14, 21, 26, 34] [6, 14, 21, 26, 34]\n",
      "0.30 4.75 6.43 [2, 5, 7, 22, 28] [28]\n",
      "0.35 2.86 8.04 [13, 16, 22, 32, 40] [40]\n",
      "0.40 2.01 10.41 [12, 27, 37, 44, 49] [12]\n",
      "0.45 1.72 12.62 [1, 14, 26, 33, 35] [1]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "np.random.seed(123)\n",
    "n_vertices = 200\n",
    "n_labels = 50\n",
    "vertices = np.arange(n_vertices)\n",
    "labels = np.arange(n_labels)\n",
    "\n",
    "n_target_labels = 5\n",
    "n_cliques = n_target_labels+1\n",
    "n_clique_vertices_list = [10]*n_target_labels + [20]\n",
    "\n",
    "epsilons = np.arange(0,0.5,0.05)\n",
    "\n",
    "target_densities = np.array([])\n",
    "greedy_densities = np.array([])\n",
    "\n",
    "for epsilon in epsilons:\n",
    "    p_add_clique_edge = 1.0-epsilon\n",
    "    p_add_other_edge = 0+epsilon\n",
    "    p_add_label = 0+epsilon\n",
    "\n",
    "    G = EdgeLabelGraph()\n",
    "\n",
    "    target_labels = list(sorted(np.random.choice(labels, size=n_target_labels, replace=False)))\n",
    "    target_labels_set = set(target_labels)\n",
    "    other_labels = set(labels)-set(target_labels)\n",
    "    n_target_edges = 0\n",
    "    target_vertices = set()\n",
    "\n",
    "    vertex_indx = 0\n",
    "    for clique_indx in range(n_cliques):\n",
    "        n_clique_vertices = n_clique_vertices_list[clique_indx]\n",
    "        clique_labels = set(target_labels[:clique_indx] + target_labels[clique_indx+1:])\n",
    "\n",
    "        for u in range(vertex_indx, vertex_indx + n_clique_vertices - 1):\n",
    "            for v in range(u+1, vertex_indx + n_clique_vertices):\n",
    "                if np.random.random() <= p_add_clique_edge: \n",
    "                    edge_labels = clique_labels.copy()\n",
    "                    for label in other_labels:\n",
    "                        if np.random.random() <= p_add_label: \n",
    "                            edge_labels.add(label)\n",
    "                    G.add_edge_with_labels((u,v), edge_labels)\n",
    "                    if target_labels_set.issubset(edge_labels):\n",
    "                        n_target_edges += 1\n",
    "                        target_vertices.add(u)\n",
    "                        target_vertices.add(v)\n",
    "\n",
    "\n",
    "                \n",
    "        for u in range(vertex_indx, vertex_indx + n_clique_vertices):\n",
    "            for v in range(vertex_indx + n_clique_vertices, n_vertices):\n",
    "                if np.random.random() <= p_add_other_edge: \n",
    "                    edge_labels = set()\n",
    "                    for label in labels:\n",
    "                        if np.random.random() <= p_add_label: \n",
    "                            edge_labels.add(label)\n",
    "                    G.add_edge_with_labels((u,v), edge_labels)\n",
    "                    if target_labels_set.issubset(edge_labels):\n",
    "                        n_target_edges += 1\n",
    "                        target_vertices.add(u)\n",
    "                        target_vertices.add(v)\n",
    "\n",
    "        vertex_indx += n_clique_vertices\n",
    "\n",
    "    n_target_clique_vertices = n_clique_vertices_list[-1]\n",
    "\n",
    "    target_density = n_target_edges/len(target_vertices)\n",
    "    greedy_density, greedy_labels = greedy_find_dense_label_induced_subgraph(G, conjunction=True)\n",
    "    target_densities = np.append(target_densities, target_density)\n",
    "    greedy_densities = np.append(greedy_densities, greedy_density)\n",
    "    print(\"{:.2f}\".format(epsilon), \"{:.2f}\".format(target_density), \"{:.2f}\".format(greedy_density), target_labels, sorted(greedy_labels))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "from matplotlib import pyplot as plt\n",
    "import matplotlib.ticker as ticker\n",
    "import matplotlib\n",
    "\n",
    "def plot_synthetic_density(epsilons, target_densities, greedy_densities, figname):\n",
    "    fig, ax = plt.subplots(1,1)\n",
    "    fig.set_size_inches(4, 3)\n",
    "    plt.plot(epsilons, target_densities, label=\"Target density\", linewidth=3)\n",
    "    plt.plot(epsilons, greedy_densities, label=\"Greedy density\", linewidth=3)\n",
    "    plt.legend()\n",
    "    plt.xlabel(\"Random noise ε\")\n",
    "    plt.ylabel(\"Density\")\n",
    "    ax.xaxis.set_major_locator(ticker.MultipleLocator(0.05))\n",
    "    ax.xaxis.set_major_formatter(ticker.FormatStrFormatter('%g'))\n",
    "    plt.tight_layout()\n",
    "    plt.savefig(figname, dpi=100, pad_inches=0)\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAARgAAADQCAYAAADcQn7hAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8li6FKAAAgAElEQVR4nO2dd3hVRfrHP296QgIBQg8QQm8hCQkQmoC0RaUsKiqIICIq8EN3bcvqwqLuorgWkNVFFBBQsCIWBEEFpRN6CxAIEDoBQkJ6Mr8/zk2DJKTcm5N7M5/nuU/OzJkz883Nvd/MmTPzjiil0Gg0GlvgZLYAjUbjuGiD0Wg0NkMbjEajsRnaYDQajc3QBqPRaGyGi9kCioOfn58KCAgwW4ZGoymAyMjIy0qpWgWdswuDCQgIYMeOHWbL0Gg0BSAiJws7p2+RNBqNzdAGo9FobIY2GI1GYzPsYgymINLT04mNjSUlJcVsKZoS4uHhgb+/P66urmZL0RTEjTjwrA5OZe9/2K3BxMbG4uPjQ0BAACJithxNMVFKERcXR2xsLE2aNDFbjuZm0pNh8RDwqQ9//p9hNGXAbm+RUlJSqFmzpjYXO0NEqFmzpu55VkSUgh+ehfP74Ohq+Kg/ZKaXqUq7NRhAm4udov9uFZSdn8DuJbnpzhPAuWy3sXZtMBqNxkqc3QU/PpebDnoAwsaVuVptMKUkLi6O4OBggoODqVu3Lg0aNMhJp6Wl2aTNnTt38tNPPxWrbPfu3dm9e7fV2j59+jQjRowosQ6NHZB0BZaPhsxUI127Ldz9Nlihp2m3g7xmU7NmzZwv8PTp0/H29ubZZ58t9vWZmZk4OzuXqM2dO3eyf/9+Bg4cWKLrrEHDhg1Zvny56To0ViYrC74eD/GnjLR7VRixGNy8rFK97sHYgHvuuYeOHTvStm1b5s+fD0BGRga+vr689NJLdOrUiW3btrFy5UpatmxJjx49mDx5MkOHDgUgMTGRMWPG0KlTJ0JCQvjuu+9ITk5mxowZLF26lODgYL788st8bSYlJXHfffcRFBTEAw88kG8QddWqVURERBAaGsqIESO4ceMGAP7+/kyfPp2QkBCCgoI4cuQIAL/88gsdOnQgODiY0NBQbty4wbFjxwgODr5Fx/Lly2nWrBlXrlwBDOMMDAzMSWsqOBvegGNrc9PDPoCaTa1Wvc16MCLyMXA3cFEp1c6SNwu4B0gDooGxSqlrZW0r4MUfylpFocTMvKvE1yxatIgaNWqQlJREWFgYw4cPx8fHh/j4eEJDQ3n11VdJSkqiRYsWbNy4kUaNGnH//ffnXD9jxgwGDhzIwoULuXr1Kp07d2bv3r384x//YP/+/bzzzju3tPnee+9RvXp19u7dy65duwgLCwPg4sWLzJw5k3Xr1uHl5cVrr73Gu+++y9SpUwGoU6cOu3btYvbs2bz11lt88MEHzJo1i3nz5tG5c2cSExPx8PDIacfT0/MWHfv37+fTTz9l0qRJrF69mvDwcGrUqFHi901TzhxdC7/NzE13expalfzzXhS27MEsBG7uQ/8MtFNKBQFHgL/ZsH3TePvtt+nQoQMRERHExsYSHR0NgJubG8OGDQPg4MGDtGzZksaNGyMiPPjggznXr1mzhtdee43g4GB69+5NSkoKp06dKrLNDRs2MGrUKABCQkJo27YtAJs2beLgwYN07dqV4OBgli5dSkxMTM51f/7znwHo2LFjTn63bt14+umnmTNnDtevX7/trdy4ceNYtGgRAB9//DFjx44t5julMY2rJ+HrxwBLTO6AHtDnZas3Y7MejFJqg4gE3JS3Jk9yC3Cvrdo3i7Vr17Jhwwa2bNmCp6cn3bt3z7ld8fT0zHlEW1SwdaUUK1asoGnT/F3VDRs2FNl2QY9/lVIMHDiQxYsXF3iNu7s7AM7OzmRkZADw0ksvMXjwYH744QfCw8P57bffiny0HBAQQPXq1fn111/ZtWsX/fv3L1KnxmTSU+Dz0ZB81Uj71IN7F4Cz9e3AzEHeR4HlhZ0UkceBxwEaNWpUZEWluY2xFfHx8dSoUQNPT08OHDjA9u3bCyzXtm1boqKiOH36NP7+/jkDqAADBgxg9uzZvPvuuwDs2rWLkJAQfHx8SEhIKLC+nj17snTpUnr06MGePXs4cOAAAF27dmXKlCkcP36cwMBAbty4wdmzZ2nevHmhv0N0dDRBQUEEBQWxceNGoqKiaNWqVc75gnSMGzeOkSNHMnbsWJysMMVcY0N+egHOWZ4wOrnAfYvAu8BwLmXGlE+CiPwdyACWFlZGKTVPKRWmlAqrVcs2v7wtuOuuu0hKSqJDhw7MmDGDzp07F1jOy8uL9957j759+9KjRw/q169PtWrVAJg2bRpJSUm0b9+etm3bMn36dAD69OnDnj17CAkJuWWQd9KkScTFxREUFMTbb7+dMwZTp04dPvroI0aMGEGHDh3o2rVrzmBuYbz55pu0a9eOoKAgfH19b+mRFKRj2LBhxMfHM2bMmJK+ZZryZNdSiFyYmx7wL2hU8GfUKiilbPYCAoD9N+U9AmwGvIpbT8eOHdXNHDx48JY8eyMhIUEppVRWVpYaP368mj17tsmKSs/mzZtVr169il3eEf5+dsfZPUq9UlupaVWN1xePKpWVVeZqgR2qkO9uufZgRGQg8AIwWCmVVJ5tV0Tef/99goODadOmDcnJyYwfP95sSaXitddeY8SIEfzrX/8yW4qmMJKvwucPQ4Zl+kKtVnDPu1aZTFcUomy0s6OIfAb0AvyAC8A0jKdG7kCcpdgWpdQTt6srLCxM3Rwy89ChQ7Ru3dqakjXliP77lSNZWbDsQThimX3t5g2P/wZ+hY/DlQQRiVRKhRV0zpZPkR4sIPsjW7Wn0WgK4Y+3cs0FYMhcq5nL7dDD/RqNIxP9K/z6Wm46YhK0HVpuzWuD0WgclfhY+GocqCwj3agr9J1erhK0wWg0jkhGqjGZLsky3OldB+5bUOb4LiVFG0wZuHDhAg899BCBgYF07NiRiIgIvvnmG5u0tXDhQiZNmlTq6729va2oBlauXMnMmcY6lhUrVnDw4EGr1q8pI6unwplI41ic4b6F4FO33GVogyklSimGDh1Kz549OX78OJGRkSxbtozY2NhbymZPwXckBg8ezIsvvghog6lw7FkO2+fnpvvNgMZdTZGiDaaU/PLLL7i5ufHEE7lP2Rs3bszkyZMBo8dx3333cc899+TMhJ01axbh4eEEBQUxbdq0nOuWLFlCp06dCA4OZsKECWRmZgKwYMECWrRowR133MHGjRsBSEhIoEmTJqSnG7FSr1+/TkBAQE46mxMnThAREUF4eDgvv5x/EVtBOmJiYmjdujXjx4+nbdu29O/fn+TkZABmz55NmzZtckJBZP9+kyZNYtOmTaxcuZLnnnuO4OBgoqOjCQ0NzWnr6NGjdOzYsYzvtqbYXDgA303JTbcZAhETTZPjGAGnplezYd3xBWYfOHAg3xepIDZv3szevXupUaMGa9as4ejRo2zbtg2lFIMHD2bDhg3UqlWL5cuXs3HjRlxdXXnqqadYunQp/fr1Y9q0aURGRlKtWjV69+6dsx6pV69e/PDDDwwdOpRly5YxfPjwW7YAmTJlCk8++SSjR49m7ty5OfmF6WjUqBFHjx7ls88+48MPP+T+++/nq6++YtSoUcycOZMTJ07g7u7OtWv5o2t07dqVwYMHc/fdd3Pvvcba1WrVqrF7926Cg4NZsGCBXj5QXqTEw/JRkGH8Y6Bmc+ORtIkxkHUPxkpMnDiRDh06EB4enpPXr1+/nLgoa9asYc2aNYSEhBAaGsrhw4c5evQo69atIzIykvDwcIKDg1m3bh3Hjx9n69at9OrVi1q1auHm5pYTrhLgscceY8GCBYDRyykoPMLGjRtzQkA8/PDDOfmF6QBo0qQJwcHBQP7wDUFBQYwcOZIlS5bg4nL7/0nZ+jIzM1m+fDkPPfRQSd5KTWlQClY8BVeOG2nXKjBiCbj7mCrLMXowJtC2bVu++uqrnPTcuXO5fPlyziJDgCpVquQcK6X429/+xoQJE/LVM2fOHB555BH+/e9/58tfsWJFoSESunXrRkxMDOvXryczM5N27doVWK6w8A0F6YiJickJ3QBG+IbsW6QffviBDRs2sHLlSl555ZWcldqFMXz4cP75z3/Sp08fOnbsSM2aNYssr7ECG9+Fw9/npgfPhtqtCi9fTjiGwRRyG2NL+vTpw9SpU3n//fd58sknASNsZWEMGDCAl19+mZEjR+Lt7c2ZM2dwdXXlzjvvZMiQITzzzDPUrl2bK1eukJCQQOfOnZkyZQpxcXFUrVqVL774gg4dOuTUN3r0aB588MFbxley6datG8uWLWPUqFEsXZq7aL0wHYWRlZXF6dOn6d27N927d+fTTz8lMTExX5mbwzd4eHgwYMAAnnzyST76SE/etjknfod1/8xNd34C2leMUEv6FqmUiAgrVqxg/fr1NGnShE6dOvHII4/w+uuvF1i+f//+PPTQQ0RERNC+fXvuvfdeEhISaNOmDa+++ir9+/cnKCiIfv36ce7cOerVq8f06dOJiIigb9++t4z3jBw5kqtXr+aLhJeXd999l7lz5xIeHk58fK4BF6ajMDIzMxk1ahTt27cnJCSEZ555Bl9f33xlHnjgAWbNmkVISEhO9L6RI0ciIjr4lK25fha+HJs7ma5hZ+j3irma8mCzxY7WRC92vJUvv/ySb7/9ttBIdWbz5ptvEh8fzyuvFPxhr+x/P6uQkQaL7obTW410lVowYQNUrV+uMkxZ7KixHZMnT2bVqlX8+OOPZkspkGHDhhEdHc0vv/xithTH5ud/5JqLOMG9H5e7udwObTB2yJw5c8yWUCS2ms2sycO+L2Hr+7npO6dBk57m6SkEux6DsYfbO82t6L9bGbl4GFb+X2661d3QbUrh5U3Ebg3Gw8ODuLg4/WG1M5RSxMXF5dtrSVMC0pLgi0cg3dg8jxqBMPS/pk6mKwq7vUXy9/cnNjaWS5cumS1FU0I8PDzw9/c3W4Z9snoqXDpsHLt4wv2LwcOGM9nLiN0ajKurK02aNDFbhkZTfhxcCZELctN/eh3qFjzJsqJgs1skEflYRC6KyP48eTVE5GcROWr5Wd1W7Ws0DkV8LKycnJtuMwRCR5unp5iU99axLwLrlFLNgXWWtEajKYqsTPh6AqRYFppWa1guOwJYA5sZjFJqA3DlpuwhwCLL8SKg/IKDajT2yu9vwck/jGNxgj9/CJ720fkv76dIdZRS5wAsP2uXc/sajX1xaiv8lmchbM/noXGEeXpKSIV9TC0ij4vIDhHZoZ8UaSolydfgq8dAGQHIaBQBPZ8zV1MJKW+DuSAi9QAsPy8WVlDZ6d7UGo1VUAq+fwbiTxlpj2rGrZGzfT34LW+DWYmxNzWWn9+Wc/sajX2weykc+Do3fc9s8G1onp5SYsvH1J9hbHLfUkRiRWQcMBPoJyJHgX6WtEajycvlY/Dj87np0NHlulmaNSnvrWMB7rRFe/s3fod3jXo0bhmKOFXYoSWNpmgyUo34LtlLAfxawED7/T9sXzd0RVBt7fM0VGe5jC8xVcNQAT3x7ziQeo1bmi1Noyk+62bA+b3GsbMbDP8I3KoUfU0FxiEM5kJsNA3VWQD8uIbf9bWwdy3s/QexUpcz1Tvh0qwXTcIGUqN2A5PVajSFcHQtbH4vN91vBtQLMk+PFXAIg0lLTmRnlZ4E3tiJL/njxfqr8/hfWQnbVsK2vxDt3IRLfl3wbNmHZuH9qeLjW0itGk05kngRVuTusUXz/kZsXTvHbkNmFkRWZibH92/m8t41eJ3ZSLPkfXhJaqHl05Uzx9xacq1uV6q16Uuz0N64ueswAppyJisLPr0Pjq010lVqw5ObwNs+pmcUFTLToQzmZlJTkojetZ74g2vxPb+JZmlRuEpmoeWTlDvHPNuT1KAbfkH9CWwXgZOzc1mkazS3Z/NcIwxDNqO+hmY2eRZiEyqtwdxM4vWrRO9YTXLUr9S+tIXArJgiy1/Dm+NVQklv3IP6IQPwb9peP6HSWJdze+DDOyHLsvVv1/+D/hVnV4DioA2mEOIuxBKz4ycyo3+jwdVtNFAXiix/jlqcqtkN9zZ/omWXu/CsYu6ueRo7JzUR5t0BcceMdP0QeHQNuLiZq6uEaIMpJmdjooiNXIVTzAYCEiLx41qhZVOVK1GewSQH3Il/p6E0CNRbcGhKyLcTYdcS49i1CjzxO9Rsaq6mUqANphSorCxiDkdyYfdqPGL/oNmN3XhLcqHlTzr5c65WD7zbD6JFeH89WKwpmv1fGxPqshn6PgTb5x7e2mCsQHpaKkd2rCNh7/fUvfg7AVmnCi2bqDw54h1GRmBfAiOG4Ve/cTkq1VR4rp6ED3pAqmXHzXb3wvD5dhFAqiC0wdiAszFRnN72LR4n1tIiaReeklZo2WPOTblU7w6qd7iL5iG9cHZxiOlHmtKQmQELB+VumObb2Lg1qsCBu2+HNhgbk5KUSNTWVaQc+JGGcX9QXxUahYKr+BBdtTO0GEDziCFUq1mnHJVqTOfXf8F6y/7l4gyProaG4eZqKiPaYMoRlZXFqSO7ObdjJT6nfqFF6v5C595kKuGIW2viG/TGL+QuAtqE4+JqX08QNCUgZqOxl3T2RvV9Xoaez5qryQpogzGRhPgrHN28kozDqwm8tqnIJ1NJyp2Tbk2Jr94OF/9QareKwL9pez3ZzxFIugIfdIfrZ4x0QA8Y/S042f/fVhtMBSF7KcOlnd9R48xvNE+PwkmKfv8TlScn3ZuTUKM9rg1Dqds6gvoBrfWEP3tCKfj8YTj0nZH2rG4sBahgG9WXFm0wFZSrl84RvXkFcnQNDRN2U/uWTRgKJp4qnHJvSWLN9ng07ki91l2p499Um05FZccC+P7p3PQDn0Kru8zTY2W0wdgJl8+eJPbQZpJjduB1eS/+yYepSXyxro2jGrGeLUnyC8KzcRj+bbrqx+MVgYuHYV4vyLDMoQp/DO76j6mSrE2ZDUZEvgI+BlYplT1CVX5UFoO5GZWVxcWzJzhzYBOpp3ZQJW4fjVKibglJURgXqcEZr1ak1AqiftcHadwy2MaKNflIT4H5d8IFy+amtdvA+F/A1dNcXVbGGgbTFxgLdAG+ABYqpQ5bVWURVFaDKQiVlcW5k0c4d2gzaad3UDVuH41Sj+BTxCxjMEJT7Gg8jrBRr+Lq5l5Oais5q16ArR8Yxy4eMP5XqNPGXE02wGq3SCJSDXgQ+DtwGvgQWKKUSi+hoGeAxwAF7APGKqVSCiuvDaZosjIzOXN8PxcObyEjdidVr+wnIO1ogbFwjjk3xWnY+wS262yC0kpE1E/w2Yjc9KA3odN48/TYEKsYjIjUBEYBDwNngaVAd6C9UqpXCcQ0AP4A2iilkkXkc+BHpdTCwq7RBlNyMjMyOH10N5eituBzYCmt0g/mnEtTzkQGjCds5Azdm7EFFw7Awrsh2TJo3/IueGCp3S4FuB1FGUyxHjuIyNfA74AXcI9SarBSarlSajLgXQpNLoCniLhY6jxbijo0ReDs4kJA6zDCh06i+Qu/s6X5X0hRrgC4SSYRJz8g5vWunDi43WSlDsbp7bBgUK65+NSHIe85rLncjuI+15yvlGqjlPp39t7SIuIOUJhzFYZS6gzwJnAKOAfEK6XW3FxObx1rPZxdXOgychoXR64lyqVVTn7zzGM0WD6QzYumkpFe+FoqTTGJ/gU+GQwplsmU7lXh/k/Aq4a5ukykuAbzagF5m0vToIhUB4YATYD6QBURGXVzOb11rPVp1CKYZi9uZEvTKaTm9GYyiDgxl+Ovd+Pk4Z0mK7RjDn4LS++H9CQj7eUHY763+3VGZaVIgxGRuiLSEeN2JkREQi2vXhi3NqWhL3BCKXXJMjj8NdC1lHVpSoiziwtdHp7B+QfXcMSlRU5+i4wj1P2sP1sW/4PMjAwTFdohOxfDF2Nyw15W9TcWMdbrYKqsisDtejADMG5n/IG3gP9YXn8BphZxXVGcArqIiJeICMZOj4dKWZemlDRuFUrgCxvZ3GQSacoIH+Eu6XSJfpdjM7tx6shukxXaCZvmwMpJuQsYazaHcavBr5m5uioIxZ0HM1wp9ZXVGhX5JzACyAB2AY8ppQrdX0Q/RbItJw5uJ+OrJ2ieeSwnL0W5srvFZMJH/F3HrykIpeCXV+D3PLNy63UwdgSo4meeLhMo9WNqERmllFoiIn/FmLOSD6XUW9aTWTjaYGxPeloqOz6dRscT83DLE17ikGsbvEfMo2Gz9iaqq2BkZcGPz8KOj3LzGneDB5eBR1XzdJlEWR5TZ2+K6w34FPDSOAiubu5EjJlJ7H2rOOacG3i6dfpB/Bb3Ycunr5KVWfieUpWGzHT4enx+c2kxEEZ9VSnN5XboxY6aW0hPS2XHkpcJOzk/X7Csg67tqPbgPBoEtjVRnYmkJcEXj8DRPLMq2t8PQ/8Lzq7m6TIZa0y0e0NEqoqIq4isE5HLBT1a1jgGrm7uRDz6BqeGf89xp4Cc/Dbp+6m+qDdbl/278vVmUuJhyfD85hI+Hob9r1Kby+0o7jyY/kqp68DdQCzQAnjOZqo0FYKmQV3xf2Ermxs+RoYyPipekkrnwzM59Hovzp4ot/Wu5pJ4CRbeBac25eb1fB4GzQIdg6dIivvuZFv0IOAzpVTxIiNp7B43dw8ixv2HE8NWcsIpN75M27S9+C7sydbP33Ds3sy107BgIJzfl5s34F/Q5++Vdvp/SSiuwXwnIoeBMGCdiNQCCl39rHE8mgf3oP7zW9jcYGz+3szB1zj4Rh8unz1pskIbcOkIfDwgd2tXcYIhcyFiorm67IiSrKauDlxXSmWKiBdQVSl13qbqLOhB3orFkZ3rcft+IgFZp3PyLlGduEEf0qpTPxOVWZGzu4wxl6Q4I+3sBsM/gjaDzdVVASnzIK+F1sAIERkN3Av0t4Y4jf3RIvQO6j63lc31RpOpjNuEWlwl8IcRbP3iTVRWuQc9tC4xf8DCe3LNxbUKPPS5NpdSUNynSIsxlgx0B8ItrxKtotY4Fh6eVYiYMIdD/T7hqmVKlJtk0vnAK2yf8zCpKUkmKywlUT8ZPZe0BCPt4QuPrISmvc3VZacUd6nAIYwAUaZMmtG3SBWbcyejuPHJgzTLjM7Ji3Jpie+Yz6jj37SIKysYez+Hb54AZRm09q4LD3/jkGEurYk1bpH2A3WtJ0njSNRr3BL/v25ge7Xcu+aWGVG4zO/NwS0/maisBGz70Jihm20u1QPg0Z+0uZSR4hqMH3BQRFaLyMrsly2FaewLDy9vwqYsZ0vL53OeMtUknuarHmLr8pkVd1xGKVg/y1hblE3tNka4hRpNzNPlIBT3FumOgvKVUuutrqgA9C2SfXFg04/UWzOBGlzPydtebSDtJ3yEh1dpIqzaiKwsWPMSbJmbm+cfbgzoVuIodCWlzLdIFiOJAVwtx9sBHf5MUyBtuw4ibdyvHHVpnpMXHv8Tp/9zB+dPHTVRWR7SU2Dl5PzmEtgbHl6hzcWKFPcp0njgS+B/lqwGwApbidLYP3UbNqPhX9ezzXdQTl7zzGO4f9yHAxt/ME9Y4kX49d/wTjvYvSQ3v/VgeGg5uFegHpYDUNwxmIlANzD6vEqpo0BtW4nSOAYenlUI/7+lbG09lXTlDEB1rtNyzSi2fPpq+Y7LnN8HK56Ct9vC+plwI08g+ZBRcO8CcNFbuFib4hpMqlIqJ+y8ZbuRih/nQWM64uRE5xEvcGzQZ1zGFwAXyaLLkVlEvnMfyTcSbNd4VhZErYJF98AH3WH3UsjMs3tC1Qbwpzdg8HvgrKP22YLivqvrRWQqRvDvfsBTwHe2k6VxNFp3HsBF/9+IWjCClhlRAIRdX0v0Wz3xfHgZ9QNaWq+x1ETY8xlseR+uRN96vkEYRDxl3BbpUAs2pbhPkZyAcRjLAwRYjbFXUql6MSLiC8wH2mH0hB5VShW6DYp+iuQ4pKYksWfe43S6kvv/6So+xPaZS/ueQ8pWeXwsbP0f7FxkxG/JizgZhhIxERp2Kls7mnxYa+vYWgBKqTLvgiYii4DflVLzRcQN8FJKXSusvDYYx2PrF/8hZP9rOfF/M5WwvfkUOj80DSlpjJXT22HLf429idRNoSPcq0HH0dDpcfBtZCX1mryUJei3ANOASRg9FwEygTlKqRmlFFMV2AMEFrcHpA3GMTm8fS01f3iMWlzNyYv06U3rCYvw8q5W9MWZGXBopWEssQVsf1sjEDo/CcEP6SdDNqYsBvMMRpCpx5VSJyx5gcD7wE9KqbdLISYYmAccBDoAkcAUpdSNm8o9DjwO0KhRo44nTzpgvBENl8+e5PKCB2iVfjAn74RTAG6jPqNBYAHT9JOvGbdAW+fB9dhbzwf0gC5PQYsB4ORsQ+WabMpiMLuAfkqpyzfl1wLWKKVCSiEmDNgCdFNKbRWRdzHizLxc2DW6B+PYpKWmsGveBDrH5U6tiqcKJ3vNIajXcCMjLhq2fgC7lkL6jfwVOLtBu3uhy5NQL6gclWugaIO53VMk15vNBYxxGBEp7fB7LBCrlNpqSX8JvFjKujQOgJu7B50nL2LbV+8QvPcV3CSDatyg3a/j2Bm9nhDPC8iR1dwyM8LLD8LHQdg48KljinZN0dzOYNJKea5QlFLnReS0iLRUSkVhbB178HbXaRyfTsOf5kiTYHxXjqU2V3ASRejpRbcWrN3G6K20vx9cPcpfqKbY3M5gOojI9QLyBSjLX3YysNTyBOk4MLYMdWkciBahvbhcfwMHP3qANun78507UKULfn2foU7wAB1w207QG69pKiTpaals+/iv1D27ls1ZbViQOZBo1QBXZ2Fk58ZM7tOMmt56an9FwCrzYMxEG0zl5djFBN74KYo1By/ky/d2d+HxnoGM696EKu56mr+ZaIPR2D2RJ6/w7x8Ps+Pk1Xz5ft7uPN23OSPCG+LqrDdBMwNtMBqHQCnF2kMXef2nwxy7mJjvXKBfFZ4b0JKB7eoienymXNEGo3EoMjKz+HrnGd76+Qjnr+ff/69DQ1/+9qdWdAmsaZK6yoc2GI1DkuQNNBYAAA6tSURBVJyWycJNMfz3t2MkpGTkO9enVW2eH9iSVnWrmqSu8qANRuPQXEtKY+6vx1i06SRpmblBrERgeKg/z/RrQQNfTxMVOjbaYDSVgtirSbz18xG+2XWGvB9rNxcnxnQN4KleTfH1cjNPoIOiDUZTqTh07jpv/HSYX6PyRxap6uHCU72bMaZrAB6ueiGktdAGo6mUbI6OY+aqQ+yJzR98ql41D57p14Lhof44O+knTmVFG4ym0qKUYtX+88xaHcWJy/lXYbeo483UQa3p1VLHry8L1tg6VqOxS0SEQe3rseaZnrwytB1+eZYXHLmQyJgF2/l8x2kTFTo22mA0lQJXZyce7tKY9c/14pm+LajiljsG87ev97H2pqUIGuugDUZTqaji7sKUvs357bnetK5nzJHJzFJM/HQn22OumKzO8dAGo6mU1PJxZ9HYcBrWMObHpGZkMW7hdg6fLyg6iaa0aIPRVFpqV/Vg8aOd8fM25sZcT8ngkY+3EXs1yWRljoM2GE2lJsCvCgvHdsLbEvLhwvVURn+0jbjEVJOVOQbaYDSVnnYNqjFvdEfcLOEejl++waMLt3MjNeM2V2puhzYYjQbo2tSPdx4IzonEuSc2nieWRJKWkVX0hZoiMc1gRMRZRHaJyPdmadBo8jKofT1eGdIuJ/370cs8+8UesrIq/mTUioqZPZgpwCET29dobmFUl8Y83bd5TnrlnrPM+P4g9jDjvSJiisGIiD9wFzDfjPY1mqKYcmdzHu7SOCdtxJyJNlGR/WJWD+Yd4Hmg0BtcEXlcRHaIyI5Lly4VVkyjsToiwvTBbRnUvm5O3qzVUSzbdspEVfZJuRuMiNwNXFRKRRZVTik1TykVppQKq1WrVjmp02gMnJ2Et0cE07VpbujNqd/sY/WB8yaqsj/M6MF0AwaLSAywDOgjIktM0KHRFIm7izP/e7gj7RoYSwqyFEz+bBdbj8eZrMx+KHeDUUr9TSnlr5QKAB4AflFKjSpvHRpNcfDxcGXBmE40rukFQFpGFo99soND5/SSguKg58FoNLehlo87ix/tTC0fI9RDQkoGoz/exukreknB7TDVYJRSvyml7jZTg0ZTHBrV9GLR2E74WJYUXEpI5eGPtnJZLykoEt2D0WiKSZv6VfnwkTDcXIyvTUxcEmMXbCdRLykoFG0wGk0J6BJYk9kPhJAdynffmXgmLN5BakamucIqKNpgNJoSMrBdXV4b1j4nvfFYHH/5fA+ZeknBLWiD0WhKwYOdGvFs/xY56R/2nuOf3x3QSwpuQhuMRlNKJlr2WMrmk80nmb3umHmCKiDaYDSaUiIi/OPuNtzToX5O3ttrj7Bky0kTVVUstMFoNGXAyUn4z30d6NHcLyfv5W/3s2rfORNVVRy0wWg0ZcTNxYn3R3UkyL8aAErBlGW72RR92WRl5qMNRqOxAt7uLiwYE06gXxUA0jKzePyTSFYfOF+pB361wWg0VqKmtzuLHu1EnarGkoLE1AwmLI7k7jl/VFqj0Qaj0ViRhjW8WPRoJ6p7uebkHTh7nQmLIxk0+w9+2n+uUoXg1Aaj0ViZVnWrsvqZnjzWvQkerrlfsUPnrvPEkp0Mmv07P+6rHEYj9tBtCwsLUzt27DBbhkZTYi4lpPLh78dZvPkkyen5lxO0qOPN5D7NGdS+Hs7Zaw/sEBGJVEqFFXhOG4xGY3suJ+YaTVJafqNpVtubyX2acXdQfbs0Gm0wGk0F4cqNND78/TifbIrhxk1G07RWFSb3ac49HezLaLTBaDQVjKs30pj/x3EWbTp5S7iHQL8qTOrTjMEd6uPiXPGHSbXBaDQVlGtJaXz8xwkWbIwh4SajCajpxcTezRgW0qBCG402GI2mghOflM7HG0/w8cYTJKTkN5pGNbyY1LsZw0Ib4FoBjaZCGYyINAQ+Aepi7Is0Tyn1blHXaIPRVBbik9NZuDGGj/44zvWbjKZhDU8m9mrGn0P9c6LqVQQqmsHUA+oppXaKiA8QCQxVSh0s7BptMJrKxvWUdBZtjGH+HyeIT07Pd66BrycTezdjaEh9vNxcTFKYS4UymFsEiHwLvKeU+rmwMtpgNJWVhJR0Ptl8kvm/H+dqUn6jETFun1rU8aFlHR9a1DV+NvGrUq49nAprMCISAGwA2imlrt907nHgcYBGjRp1PHlSx9jQVF4SUzNYvPkkH/5+nCs30oos6+osBPp5WwzH2zCguj40rO6Fkw0ef1dIgxERb2A98JpS6uuiyuoejEZjcCM1gyVbTvJlZCzHL98oURxgT1dnmmcbTp4eT52q7oiU3ngqnMGIiCvwPbBaKfXW7cprg9FobiUlPZPjl25w5EICURcSOHI+gcPnEzhzLblE9VTzdLUYjrfx09Lj8fVyK9b1FcpgxLDKRcAVpdTTxblGG4xGU3wSUtI5ejGRI+ctxnMhgajziSXeJG5YSAPeHhF823JFGYwZQ9DdgIeBfSKy25I3VSn1owlaNBqHw8fDldBG1QltVD1fflxiKkcuJHLkgtHTOWLp9dw8wS+butU8yqyl3A1GKfUHYD8LLTQaB6GmtzsR3u5ENK2Zk6eU4lx8Ss4tVnaP5+iFRFrW8Slzm+Y/RNdoNKYhItT39aS+rye9W9bOyc/MUlbZSE4bjEajuQVnJ7HKiu6KM99Yo9E4HNpgNBqNzdAGo9FobIY2GI1GYzNMX+xYHETkElCcxUh+gC2307Nl/Vp7+ddt6/ori/bGSqlaBZ2wC4MpLiKyo7AZhRW9fq29/Ou2df1au75F0mg0NkQbjEajsRmOZjDz7Lh+rb3867Z1/ZVeu0ONwWg0moqFo/VgNBpNBUIbjEajsRkOYzAiMlBEokTkmIi8aM1rxWC25fxeEQnNcy5GRPaJyG4RuW1UrGK01UpENotIqog8a8v6bKB9pOX92Ssim0Skg63qK4n2YrQzxNLGbhHZISLdi34nylanNbXnKRcuIpkicq+t6ivp5wUw4kHY+wtwBqKBQMAN2AO0sda1wCBgFUYcmy7A1jznYgA/K7ZVGwgHXgOetWV9NtDeFahuOf5T3vfJ2vUVV3sx2/EmdzwyCDhsyzqtqT1PuV+AH4F7bVVfST4v2S9H6cF0Ao4ppY4rpdKAZcAQK147BPhEGWwBfMXY38nqOpVSF5VS24H0giqwcX1lbWuTUuqqJbkF8C/H+srSTqKyfIOAKsDtnnzYos5StWNhMvAVcLGc67stjmIwDYDTedKxljxrXVtUGQWsEZFIy1YrttJpi/psqX0cRq/PVvUVV3ux2hGRYSJyGPgBeLSI+qxRp9W0i0gDYBjwwW00W6O+knxeAMcJOFVQZJzi/scozrVFlemmlDorIrWBn0XksFJqgw102qI+m2gXkd4YhlDUWEZZ6yuu9mK1o5T6BvhGRHoCrwB9y6q9iDqtqf0d4AWlVKbcfuuRstZXks8L4Dg9mFigYZ60P3DWitcWWkYplf3zIvANRjfUFjqtXp8ttItIEDAfGKKUirNVfSXQXqL3yPKFaSoifmXVXlidVtYeBiwTkRjgXuC/IjLUFvWV8PNiUJIBm4r6wuiJHQeakDt41dZa1wJ3kX+Qd5slvwrgk+d4EzDQGjqB6dx+kLfU9dlCO9AIOAZ0tdL7XmB9JdFezHaakTsgGwqcyU5bu05ra7+p/EKKHuQtdX0l/bzk1FGSL3JFfmE86TmCMUr+97JeCzwBPGE5FmCu5fw+IMySH2j5I+0BDhSn3WK0VRfjP8114JrluKq167OR9vnAVWC35bXDFvWVVHsx2nnBUs9uYDPQ3QrvRYF1Wlv7TWUXUoTBlKW+0nxelFJ6qYBGo7EdjjIGo9FoKiDaYDQajc3QBqPRaGyGNhiNRmMztMFoNBqboQ3GQbGshN0tIvtF5DsR8bVSvQEist8adZVRR30R+dJsHZqi0QbjuCQrpYKVUu2AK8BEswVZE6XUWaVUkaEJNOajDaZysBnLojYR8RaRdSKy0xLbY4glP0BEDonIhyJyQETWiIin5VxHEdkjIpvJY1Qi4iEiCyz17LKsGUJExojICkvP6YSITBKRv1jKbBGRGjcLFJGFYsTc2SQix7PjkIjBLEtPbJ+IjMijd7/luK2IbLP02PaKSHNL/qg8+f8TEecC2n3a0t5OEVlq3bddY/oMXP2yzQtItPx0Br7AMq0bY7p4VcuxH8ZUfAECgAwg2HLuc2CU5XgvcIfleBaw33L8V2CB5bgVcArwAMZY6vUBagHx5M5wfRt4ugC9Cy06nYA2GGEFAIYDP1t+jzqWNupZ9GbrmAOMtBy7AZ5Aa+A7wNWS/19gdAHtXsTYOMz0v5kjvnQPxnHxFJHdQBxQA+NLCoaZ/EtE9gJrMXo2dSznTiildluOI4EAEakG+Cql1lvyF+dpo3t2Wil1GGP3zRaWc78qpRKUUpcwDOY7S/4+DHMoiBVKqSyl1ME8mroDnymlMpVSF4D1GAG08rIZmCoiL2CYRTJwJ9AR2G55H+7EmO5+M/8ADll6Zxorow3GcUlWSgUDjTH+q2ff2ozE6FV0tJy/gNHrAEjNc30mRm9HKDwERFHxAfLWlZUnnUXhYULyXiM3/SwUpdSnwGAgGVgtIn0s1y1SxjhUsFKqpVJqej7xIq4YcVqaK6UibteOpuRog3FwlFLxwP8Bz1q+UNWAi0qpdMuYSePbXH8NiJfcmLIj85zekJ0WkRYYq5+jrPwrbABGiIiziNQCegLb8hYQkUDguFJqNrASI0TlOuBeS+wSRKSGiNz8u3phrHpOtZSxypM2TS6OEnBKUwRKqV0isgd4AFgKfGcJ2rwbOFyMKsYCH4tIErA6T/5/gQ9EZB/G+M0YpVRqMQIflYRvgAiMVbwKeF4pdV5EAvKUGQGMEpF04DwwQyl1RURewojA5oQRMnQixm0cYJiviEwH/hCRVCBDRMKVUlnW/AUqM3o1tUajsRn6Fkmj0dgMbTAajcZmaIPRaDQ2QxuMRqOxGdpgNBqNzdAGo9FobIY2GI1GYzP+H9+vcoFm2DpMAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 288x216 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plot_synthetic_density(epsilons, target_densities, greedy_densities, \"synthetic_density_conjunction.pdf\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.00 19.50 19.50 [10, 13, 18, 30, 46] [10, 13, 18, 30, 46]\n",
      "0.05 18.48 18.48 [15, 24, 31, 37, 43] [15, 24, 31, 37, 43]\n",
      "0.10 17.60 17.60 [2, 9, 10, 30, 44] [2, 9, 10, 30, 44]\n",
      "0.15 16.12 16.12 [6, 13, 25, 29, 44] [6, 13, 25, 29, 44]\n",
      "0.20 15.10 15.10 [8, 19, 36, 40, 43] [8, 19, 36, 40, 43]\n",
      "0.25 14.72 14.72 [2, 25, 31, 39, 43] [2, 25, 31, 39, 43]\n",
      "0.30 13.22 12.20 [10, 18, 43, 45, 47] [1, 2, 3, 6, 8, 13, 16, 17, 20, 24, 26, 30, 31, 41, 46]\n",
      "0.35 13.22 13.28 [10, 13, 17, 33, 41] [1, 4, 6, 8, 12, 18, 21, 34, 36, 39, 42, 45, 48, 49]\n",
      "0.40 11.22 14.95 [8, 20, 26, 41, 49] [2, 5, 18, 19, 21, 24, 35, 40, 47, 48]\n",
      "0.45 10.62 16.07 [2, 12, 21, 40, 47] [0, 1, 3, 8, 9, 10, 16, 23, 24, 25]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "np.random.seed(123)\n",
    "n_vertices = 200\n",
    "n_labels = 50\n",
    "vertices = np.arange(n_vertices)\n",
    "labels = np.arange(n_labels)\n",
    "\n",
    "n_target_labels = 5\n",
    "n_clique_vertices = 40\n",
    "n_clique_edges = n_clique_vertices * (n_clique_vertices - 1)/2\n",
    "\n",
    "\n",
    "epsilons = np.arange(0,0.5,0.05)\n",
    "\n",
    "target_densities = np.array([])\n",
    "greedy_densities = np.array([])\n",
    "\n",
    "for epsilon in epsilons:\n",
    "    p_add_clique_edge = 1.0-epsilon\n",
    "    p_add_other_edge = 0+epsilon\n",
    "    p_add_label = 0+epsilon\n",
    "\n",
    "    n_target_label_edges = np.zeros(n_target_labels)\n",
    "\n",
    "    G = EdgeLabelGraph()\n",
    "\n",
    "    target_labels = list(sorted(np.random.choice(labels, size=n_target_labels, replace=False)))\n",
    "    target_labels_set = set(target_labels)\n",
    "    other_labels = set(labels)-set(target_labels)\n",
    "    n_target_edges = 0\n",
    "    target_vertices = set()\n",
    "\n",
    "    for u in range(n_clique_vertices-1):\n",
    "        for v in range(u+1, n_clique_vertices):\n",
    "            target_label_idx = np.random.choice(np.where(n_target_label_edges <= n_clique_edges/n_target_labels)[0])\n",
    "            n_target_label_edges[target_label_idx] += 1\n",
    "            \n",
    "            if np.random.random() <= p_add_clique_edge: \n",
    "                n_target_edges += 1\n",
    "                target_vertices.add(u)\n",
    "                target_vertices.add(v)\n",
    "                edge_labels = set({target_labels[target_label_idx]})\n",
    "\n",
    "                for label in other_labels:\n",
    "                    if np.random.random() <= p_add_label: \n",
    "                        edge_labels.add(label)\n",
    "                G.add_edge_with_labels((u,v), edge_labels)\n",
    "        \n",
    "        for v in range(n_clique_vertices, n_vertices):\n",
    "            if np.random.random() <= p_add_other_edge: \n",
    "                edge_labels = set()\n",
    "                for label in other_labels:\n",
    "                    if np.random.random() <= p_add_label: \n",
    "                        edge_labels.add(label)\n",
    "                G.add_edge_with_labels((u,v), edge_labels)\n",
    "\n",
    "    target_density = n_target_edges/len(target_vertices)\n",
    "    greedy_density, greedy_labels = greedy_find_dense_label_induced_subgraph(G, conjunction=False)\n",
    "    target_densities = np.append(target_densities, target_density)\n",
    "    greedy_densities = np.append(greedy_densities, greedy_density)\n",
    "    print(\"{:.2f}\".format(epsilon), \"{:.2f}\".format(target_density), \"{:.2f}\".format(greedy_density), target_labels, sorted(greedy_labels))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAARgAAADQCAYAAADcQn7hAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8li6FKAAAgAElEQVR4nO2deVyVxf7H318QBBXBBfcFLVcUDru4paa2ut3cUnO5VnZTK7ut91Z6Lbve9FpWtqeUmVpZpqmlqenvqqig4G5uqOROigsi2/z+eA4HUJaDnMOBw7xfr/PimXmemflwOOfDPPPMfEeUUmg0Go09cHG0AI1G47xog9FoNHZDG4xGo7Eb2mA0Go3d0Aaj0WjsRiVHC7CG2rVrKz8/P0fL0Gg0+RAbG3tBKeWb37lyYTB+fn7ExMQ4WoZGo8kHETle0Dl9i6TRaOyGNhiNRmM3tMFoNBq7US7GYKxBZWVxKeksNXzrO1qKpgDS09NJTEwkNTXV0VI0t4GHhweNGjXCzc3N6jJOYzDbvptJy33vEd91BoE9hjpajiYfEhMT8fLyws/PDxFxtBxNMVBKkZSURGJiIs2aNbO6nFPcIh3dsxXT3reowWUCN44j+sMnSLuh/0uWNVJTU6lVq5Y2l3KIiFCrVq1i9z6dwmDSrl8hWbws6Q5nF3L8rU4kHt7jQFWa/NDmUn65nb+dUxhM67CeuI3fTJxnB0tei8zD1Jh/NzHLP3agMo2mYuMUBgNQw7c+gc+vIrrl86QpVwCqSiqhsS+w7Z2HSbma7GCFGkeTlJSEyWTCZDJRr149GjZsaEmnpaXZpc0dO3bw888/W3Vt586diYuLs1nbJ0+eZMiQIcXWYUucxmAAxMWFDsNe4fiAH0mUnKdJ4ZdWcmFWJEd2RztQncbR1KpVi7i4OOLi4njiiSeYNGmSJe3u7l5k+czMzGK36agvNkDjxo1ZvHixQ3U4lcFk08LUBZ9JW4ip3suS1yTrDxp99yBbF09HZWU5UJ2mLNKnTx9CQkLw9/fns88+AyAjIwMfHx9eeeUVwsPD2bZtG8uWLaNVq1Z06dKFiRMn0r9/fwCuXr3K6NGjCQ8PJygoiOXLl3P9+nWmTp3KggULMJlMfPfdd3naTElJYdCgQQQEBDB06NA8A6irVq0iMjKS4OBghgwZwrVr1wBo1KgRU6ZMISgoiICAAH7//XcA1q1bR2BgICaTieDgYK5du8bhw4cxmUy36Fi8eDF33nknf/75J2AYZ/PmzS1pW+I0j6lvplr1GoQ++x3bl87Bf+e/qCI3qCzpROz/NztnbqT52Hl416rraJkVFr+XVtit7oTpDxS7zBdffEHNmjVJSUkhNDSUhx56CC8vL5KTkwkODuaNN94gJSWFli1bsmnTJpo0acLgwYMt5adOncq9995LVFQUFy9eJCIigl27dvHaa6+xZ88e3nnnnVvafP/996lRowa7du1i586dhIaGAnDu3DmmT5/O2rVrqVKlCtOmTWP27Nn84x//AKBu3brs3LmTd999l1mzZvHRRx8xY8YMPvnkEyIiIrh69SoeHh6Wdjw9PW/RsWfPHr7++msmTJjAL7/8QlhYGDVr1iz2+1YUTtmDyU1Y//FcGL6aI67NLXlBKZu4/l5H9m/9xYHKNGWJt99+m8DAQCIjI0lMTOTIkSMAuLu7M2DAAAD27dtHq1ataNq0KSLCww8/bCm/evVqpk2bhslkonv37qSmpnLixIlC29y4cSMjRowAICgoCH9/fwA2b97Mvn376NixIyaTiQULFpCQkGAp95e//AWAkJAQS36nTp145plneO+997h8+TKurq6Ftj127Fi++OILAObOncuYMWOsfKeKh9P2YHLTpKWJ1Of+x9a5TxFx3uim1uMCviuHsGXfOMIfmYZrpQrxVmjy4ddff2Xjxo1ER0fj6elJ586dLbcrnp6elsezhQXIV0qxdOlS7rjjjjz5GzduLLTt/B79KqW49957mT9/fr5lKleuDICrqysZGRkAvPLKK/Tt25cVK1YQFhbGb7/9VuhjZT8/P2rUqMH69evZuXMnvXv3LlTn7VJhvlUenlWJGP85O1d3p9nmF/HhKq6iiDz+EXvf2kKd0V/i28DP0TIrDLdzG2MvkpOTqVmzJp6enuzdu5ft27fne52/vz8HDx7k5MmTNGrUyDKACnDPPffw7rvvMnv2bAB27txJUFAQXl5eXLlyJd/6unbtyoIFC+jSpQvx8fHs3bsXgI4dO/L0009z9OhRmjdvzrVr1zh16hQtWrQo8Hc4cuQIAQEBBAQEsGnTJg4ePEjr1q0t5/PTMXbsWIYPH86YMWNwcbHPzYzT3yLdTFDvEaSO3cA+t3aWPP+0eCp90oX4dd84UJnGUTzwwAOkpKQQGBjI1KlTiYiIyPe6KlWq8P7779OzZ0+6dOlCgwYN8Pb2BmDy5MmkpKTQvn17/P39mTJlCgA9evQgPj6eoKCgWwZ5J0yYQFJSEgEBAbz99tuWMZi6devy+eefM2TIEAIDA+nYsaNlMLcgZs6cSbt27QgICMDHx+eWHkl+OgYMGEBycjKjR48u7ltmNVIe9kUKDQ1Vtg44lZGexvYvXybixOe4SM57EF33YYL/+g7ulT0KKa25Hfbv30+bNm0cLaNEXL16lWrVqqGUYty4cbRv356JEyc6WtZtER0dzcsvv8z69eutLpPf31BEYpVSofldX+F6MNlUcnMncux/2d97AefIGT3vcHYhx2d01ssMNPny4YcfYjKZaNu2LdevX+exxx5ztKTbYtq0aQwZMoQ333zTru1U2B5Mbi6eP82JuaMIvL7VkndVeXIgbCqhDz5ut3YrGs7Qg6no6B7MbVDDtz4Bz/9MdMvnLMsMqsl1QmOe18sMNJoSoA3GjLHM4NV8lxmcn9VRLzPQaG4DbTA3kbPMoKclr2lWorHMYNG/ybqN9SgaTUVFG0w+VKteg5BnvmW7aRopypjUVFnSiTgwnYPTu3B8f6yDFWo05QNtMAUgLi6E9Z9gXmaQEyKwTfpe6i/qxZZPnyE15aoDFWpuh7NnzzJs2DCaN29OSEgIkZGR/PDDD3ZpKyoqigkTJtx2+WrVqtlQDSxbtozp06cDsHTpUvbt22fT+vNDG0wRNGlpouFzm9jScDTp5gFgd8kk8o95XJgRwu6NPzpYocZalFL079+frl27cvToUWJjY1m0aBGJiYm3XJs9Bd+Z6Nu3Ly+99BKgDaZM4eFZlcjHZvPH0NUccGtryW+kztB+3UhiZg0k6eytH1JN2WLdunW4u7vzxBNPWPKaNm1qmSgXFRXFoEGD6NOnj2Um7IwZMwgLCyMgIIDJkydbyn311VeEh4djMpkYN26cJVbMvHnzaNmyJXfddRebNm0C4MqVKzRr1oz09HQALl++jJ+fnyWdzbFjx4iMjCQsLIxXX301z7n8dCQkJNCmTRsee+wx/P396d27N9evXwfg3XffpW3btpZQENm/34QJE9i8eTPLli3j+eefx2QyceTIEYKDgy1tHTp0iJCQkBK+2wYVZi2SLfBrE0rWS/9j6/fv0Gbvf6mOEaMj9PIakj8MZ1v7FwjtPxGXIlayaoAp3nasO/9pBXv37s3zRcqPLVu2sGvXLmrWrMnq1as5dOgQ27ZtQylF37592bhxI76+vixevJhNmzbh5ubGk08+yYIFC+jVqxeTJ08mNjYWb29vunfvblmP1K1bN1asWEH//v1ZtGgRDz300C3bfzz99NP87W9/Y+TIkcyZM8eSX5COJk2acOjQIRYuXMinn37K4MGDWbJkCSNGjGD69OkcO3aMypUrc+nSpTztdOzYkb59+/Lggw8ycOBAALy9vYmLi8NkMjFv3jybLR/QPZhi4uLqSsSgv5P2RDQxXndb8r25RvjuyRyY3pXjB3Y4UKHGWsaPH09gYCBhYWGWvF69elnioqxevZrVq1cTFBREcHAwBw4c4NChQ6xdu5bY2FjCwsIwmUysXbuWo0ePsnXrVrp164avry/u7u6WcJUAjz76KPPmzQOMXk5+4RE2bdpkCQHxyCOPWPIL0gHQrFkzTCYTkDd8Q0BAAMOHD+err76ikhWRArL1ZWZmsnjxYoYNG1act7JA7GYwIjJXRM6JyJ5ceSYRiRaROBGJEZFwe7Vvb2rXa0Lo379nV7e5nJKcwFVt0/dQf2FPoj97ltTr1xyoUHMz/v7+7NiRY/5z5sxh7dq1nD9/3pJXtWpVy7FSipdfftkSVvPw4cOMHTsWpRSjRo2y5B88eNCyuLGgEAmdOnUiISGBDRs2kJmZSbt27fK9rqDwDfnpgJzQDZA3fMOKFSsYP348sbGxhISEFDmm9NBDD7Fq1Sp++uknQkJCqFWrVqHXW41Syi4voCsQDOzJlbcauM98fD/wmzV1hYSEqLJMytXLavPHE1TaazWUmlzd8joxpbXavXGpo+WVGfbt2+fQ9rOyslR4eLj64IMPLHnHjx9XTZs2VUopNW/ePDV+/HjLuV9++UWFh4erK1euKKWUSkxMVGfPnlV79+5Vd955pzp79qxSSqmkpCSVkJCgTp06pZo0aaIuXLig0tLSVOfOnfPUN3PmTFW/fv087eemT58+av78+UoppT744ANVtWrVQnUcO3ZM+fv7W8rPmDFDTZ48WWVmZqpjx44ppZRKS0tTderUURcvXszz+02YMEHNnTs3T/sTJkxQ9evXVytXrizwPczvbwjEqAK+u3brwSilNgI3B/lUQHXzsTdwyl7tlyaeVb2IfPw9Egev4kClnHUajdUp2q0dyfa3B/PnuT8cqFADRu9g6dKlbNiwgWbNmhEeHs6oUaP4z3/+k+/1vXv3ZtiwYURGRtK+fXsGDhzIlStXaNu2LW+88Qa9e/cmICCAXr16cfr0aerXr8+UKVOIjIykZ8+et4z3DB8+nIsXL+aJhJeb2bNnM2fOHMLCwkhOzhlHKkhHQWRmZjJixAjat29PUFAQkyZNwsfHJ881Q4cOZcaMGQQFBVmi9w0fPhwRsWnwKbsudhQRP+AnpVQ7c7oN8AsgGLdnHZVSxwso+zjwOECTJk1Cjh/P97IyR1ZmJtuXzKLNvllUJ8WSf4lq/B74ImH9JiB2Cu5T1qnoix2/++47fvzxxwIj1TmamTNnkpyczOuvv17gNcVd7FjaT5H+BkxSSi0RkcHA50DP/C5USn0CfALGaurSk1gyXFxdiRj8PBdODSZ24dOEXDFibfhwlfD4V9m7/xuqPfQ+TVuZHKxUU5pMnDiRVatWsXLlSkdLyZcBAwZw5MgR1q1bZ9N6S7sHkwz4KKWUGKNZyUqp6oVUAdg/XIM9iV//Lb4b/0EDdc6Sl6YqEdtkDEHD/oWHZ9VCSjsXFb0H4wyU9XANp4C7zMc9gEOl3H6pE9h9EDWe28GW+iPIUMbb7S4ZRJ78lPNvhbJn03IHKyxd7PkPTWNfbudvZ8/H1AuBLUArEUkUkbHAY8B/RSQeeBPzGIuz41nVi8hxczgx6GcOVmplyW+sTtFuzQi2vz2Ei+dPO1Bh6eDh4UFSUpI2mXKIUoqkpKQ8+y1Zg45oV8pkZmQQ8/0s2u6dhZdct+RfxIvE7u/S/q6/OFCdfUlPTycxMTHPDoaa8oOHhweNGjW6ZQZyYbdI2mAcxPlTCZz8+imCr26w5KUqN470/gL/TmVnSw+NpijK0hiMxoxvAz+Cn1tGfNePLUHHPSQdv9V/5fcdvzlWnEZjI7TBOJjAHkNJH7mS89QAoKqkUnfZMI7u2VpESY2m7KMNpgzQsHkbUoYs4aJ5krM316j+3WBOHop3sDKNpmRogykjNG0TQtKAhVxRngDU5hJuC/7C6eMHHaxMo7l9tMGUIe4M7Mwf939piQNcjwtkRvXjwqnysUxCo7kZbTBljNYRvTly96ekKWMVRyN1miuf9eHShTMOVqbRFB9tMGWQ9l37sbfTbMvM32ZZxzn/0YNcSb55cbpGU7bRBlNGCeo9grjQ6WQpIwBRi4xDnJzTl+vXCl6mr9GUNbTBlGFC+4xje7uc4M9t03Zz6L0B3EhNKaSURlN20AZTxokY9HeiWzxrSQekbmfve0PISE9zoCqNxjq0wZQDOgyfzJbGj1nSwdc2svP9EXobW02ZRxtMOaHDmLeIrpsTajEs+Re2f/goKivLgao0msLRBlNOEBcXIsZ9wLaafSx5ERe+J/qzpx2oSqMpHG0w5QhxcSHkyShiqudEGY089SXRUf9woCqNpmC0wZQzXCtVInDC1+ys0tGS1yFhDtEL33SgKo0mf7TBlEPc3CvTZuJ37KmcEzi8w8H/sO2Hdx2oSqO5FW0w5RQPz6o0n7iMA25tLXkhca8Ru3KeA1VpNHnRBlOOqVLNm/pPLuew6x0AuIoiYOvfiV/3jYOVaTQG2mDKOd41alNz3HKOuzQGwE0yabXhSfZuWuFgZRqNNhinoGadhniOXc4pqQvkhN48GGPbTbQ0muKiDcZJqNOwGYxcZonvW1VSqffTCB16U+NQtME4EQ2ateb60LyhN72/G6RDb2ochjYYJ6Np62CSBiziMlUAqEWyDr2pcRj23NlxroicE5E9N+VPFJGDIrJXRN6yV/sVmTsDO3HqptCbMu8BPSajsY7EWIj+yCZV2bMHEwXcmztDRLoD/YAApZQ/MNOO7VdoWof34mjPnNCb9ThP8+UDif7yVb0KW1MwO76EeffCzy/CwVUlrs5uBqOU2gjcHOPxb8B0pdQN8zXn7NW+Btp16cf+bh9ZbpfcJJMOR99lz4xeXDhz0sHqNGWKjDT4aRIsmwiZ5lhDq16AzPQSVWuVwYjIEhF5QERKakgtgS4islVENohIWCFtPi4iMSISc/78+RI2W3EJ7D6Iq6N/42Cl1pa8gNRY+Kgzuzf+4EBlmjLDlTPwxYMQMzcnr44/jPwRXN0KLmcF1hrGh8Aw4JCITBeR1kUVKIBKQA2gA/A88I2ISH4XKqU+UUqFKqVCfX19b7M5DUADv1Y0f2EjWxqMtMT4rc0l2q8bzZaPJ5KedsPBCjUO4+R2+KQbnMw1ncF/ADy6Bmo2L3H1VhmMUupXpdRwIBhIANaIyGYRGSMixbG4ROB7ZbANyAJqF1e0pvi4uVcm8vH32Hv3PC7gY8mPPP0lR9/qyqljBxyoTuMQYqNg3n1w5bSRFhfoNRUGzgP3qjZpwupbHhGpBYwGHgV2ArMxDGdNMdpbCvQw19cScAcuFKO8poS07zoAnvgfuzxCLHmtMg5Q7YvueqFkRSHjBix/2nhlmcdYPGvAiCXQ6WnI/6bitrB2DOZ74P+AKkAfpVRfpdRipdREoFoBZRYCW4BWIpIoImOBuUBz86PrRcAopZSyxS+isZ7a9RrT7vk1RDd/inTlCkB1UgjZ9gxb3xtJaspVByvU2I3LpyHqAaP3kk3d9vD4b3BHD5s3J9Z8v0XkfqXUypvyKmc/DbI3oaGhKiYmpjSaqnAcjFmH14pxNMj1QC/BpQkMmodfm1AHKtPYnBPR8M1IuHo2J6/dQOj7HrhXue1qRSRWKZXvh8XaW6Q38snbctuKNGWGVqE9qPrUFnZUu8uS55d1grqL7mPbd7N0UHFnQCnY/jlEPZhjLuICvafBQ5+VyFyKolCDEZF6IhICeIpIkIgEm1/dAPup0pQq3jVqE/TsUra1m0yqMsbsPSWN8D3/Yues/iRf1MNk5Zb0VGNuy4pnc4231IRHlkLHCTYdb8mPQm+RRGQUxsBuKJD7HuUKEKWU+t6u6szoW6TSI2F/DHw7Br+sE5a8U1KHyw98ROvQux2oTFNskv+Abx6BP2Jz8uq1hyELoEZTmzVT2C2StWMwDymllthMUTHRBlO6XL92hV1zxxOR9KMlL125EnPHeCKGT8HF1dWB6jRWcXyzMd5yLdck1faDoc9sm98S3bbBiMgIpdRXIvJ34JYLlVKzbCezYLTBOIbYlfNose0fVCdnL+zdlYOpP+ZLatdr7EBlmgJRCrZ/Bj+/BFkZRp64wj3TIOIJu9wSlWSQN3u2TTXAK5+XxokJuX/MLcsM2t/YoZcZlFXSU+HHCbDyuRxzqVLLmPLf4W92H2/JD6tukRyN7sE4lvS0G8REPUfEH/NxkZzPy5b6IwkdMxM398oOVKcBIDkRFo+AUztz8uqbYMhX4GPf3maJH1OLyFsiUl1E3ERkrYhcEJERtpWpKavoZQZlnIT/wcd35TWXwIfhrz/b3VyKwtp5ML2VUpeBBzHWE7XEWKyoqUAUtMzAJ6orcW/dS/TCNzl+YIeeO1NaKGUEhvqiL6SYpxK4VIL7ZkD/D8HN07H6MFY3W0P2gsb7gYVKqT8LWAStcXJq12tMzefXEL1gCiFH5uAmmVSRG5hStsDBLXDwP5yjJsd9IpDm3fALf0APCNuD9Ouw/BnYtSgnr6ovDPoC/Do5TtdNWPuYejrQH7gOhAM+wE9KqQj7yjPQYzBlk4Mx66i88uk8c2by46iLH+d8I6nSuictwu/Bs6p+PlAikhNh0TA4nSuYe4NgY7zFu2GpyynxPBhzJTWAy0qpTBGpAlRXSp2xoc4C0QZTdlFZWSQe3cup2JW4Hd/InSk78jzWvpk0VYlDldtypUEXagbcwx0BnXCtZG1HWkPKn/BZT/jzSE6eaQQ88F9w83CIJFsZTEfAj1y3VUqpL20hsCi0wZQfMtLTOBz/f1zcvRrv05u488Y+3KXgGMDJVOVI1RDS/e6iUcgDNGzephTVljMy02H+AEj4PyPtUgnunQ5hjzrkEXQ2tpjJOx+4A4gDsj8tSin1lM1UFoI2mPLLtSuXOLx9NdcP/Eq9C1uKvJ06JXU5WSMCtxY9uCP8frxr1S0lpWUcpeCnZ/KGWRj0Bfj3d5ikbGxhMPuBto6K3aINxnm4cOo4x7avgKPr8Uveji8XC7w2SwmH3VqQ2vlFAroNLEWVZZDoj4xI/9l0fwXuKhsPcm1hMN8CTymlTttanDVog3FOVFYWxw/u4MzOVXie/D9apMRRRW4NMXRVeRI3YD2dTRX09unQGvh6MCjz4//2g+Avnzr0tig3hRmMtaNrtYF9IrINsHwClFJ9baBPU0ERFxf82oRaAlul3Uhl3471JO9dQ80zm7gz/SCuoqgm1zn+/Wu4e39MeLOaDlZdypzbD9+OyTGXhqHQ9/0yYy5FYW0P5q788pVSG2yuKB90D6ZikrTjR2otGwlAhnJhALP49+N/oV1DbwcrKyWuJcGn3eHScSNdvRE8tg68yta4VImXCpiNJAFwMx9vB3bYTKFGkw+1gvqS2rAjAJUkiwlZXzFq7jaOnK8AMYMz0oy1Rdnm4lYVhi0qc+ZSFNauRXoM+A742JzVEGOHAI3Gfojg8cCbluQ9rjE0T9nFI59t5Y9L1x0ozM4oZeyyeGKzOUOM0Jb12jtU1u1g7Vqk8UAn4DKAUuoQUMdeojQaCw2CjEBJZv7p9hWnk1N45LOtXLjqpBvGbX4P4r7KSfecAq3vd5SaEmGtwdxQSqVlJ0SkEvkEoNJo7MLdr4KrERLC5HKUB12iOXrhGqPmbuNyasn2Ti5zHFwFa17LSQcOM/YqKqdYazAbROQfGMG/ewHfAsvtJ0ujyYVPE+jwhCX5gtti3Eln76nLPBoVQ2p6wTOFyxVn9sCSR7H8724SCX3eKTdPjPLDWoN5CTgP7AbGASuBV+wlSqO5hc7PGtHwgcZynpGuqwHYlvAnTy7YQXpmOQ8RcfUcLBwKaeYBbJ8mxuLFSuU7mJe1T5GyMAZ1n1RKDVRKfap3ZNSUKp4+cNcLluTznsvwxvgyrjtwjr9/E09mVjn9SKanwqLhkHzSSLt7wcOLoWr537a9qH2RRESmiMgF4ABwUETOi8hrhZUzl50rIufM28TefO45EVEiUv7fQU3pEToWajQDoHLGFT5v9pvl1LL4U0xetody939PKVj+FCRuM9LiAgPnQt22jtVlI4rqwTyD8fQoTClVSylVE4gAOonIpCLKRgH33pwpIo2BXkDhq940mpup5G48UTETcvZbngrKmYz+VfQJZq4+WPq6SsL/ZsGuxTnp3m9Ay96O02NjijKYkcDDSqlj2RlKqaPACPO5AlFKbQT+zOfU28AL6KdQmtuhbT9oFA6AZKUzyWUR/UwNLKfnrD/CJxuPFFS6bLFvGaydmpMOHgUdnnScHjtQlMG4KaVu2TdUKXWenDCaViMifYE/lFLxVlz7uIjEiEjM+fPni7pcU1EQMf7LZyf3fs9/O6bTo3XOtKw3Vx5g8fYy3kE+HQ8/jMtJ+3WB+2eW6ydG+VGUwaTd5rlbMEfB+ydQ5PgNgFLqE6VUqFIq1NfXtzhNaZydJhFGT8ZMpV9f44NhQXkWQr78/W5W7nbI4v+iuXIGvh4K6ebIfzWaweAvjVtAJ6MogwkUkcv5vK4AxZ23fAfQDIgXkQSgEbBDROoVX7amwnP3ZHAxd6JPbMHjyCo+GxVKu4bVAchS8PSinWz8vYz1ftOvw8KH4copI13ZG4Z9A1Wcc5V4oQajlHJVSlXP5+WllCrWLZJSardSqo5Syk8p5Yex/UlwacX11TgZte6AsLE56TWTqe4GX4wJp7mvsSFpeqZi3PxYYo/nNxToAJSCpU/CKfM6YXGFwVHg29KhsuyJtRPtio2ILAS2AK1EJFFExhZVRqMpFl1fMHoAYATBjo2iVrXKfDU2goY+xp5A19MzGTNvO/tPX3agUDMb/gN7v89J3/cfuKOH4/SUAnYzGKXUw0qp+kopN6VUI6XU5zed98tvAFmjsZqqtaDLsznp3/4Nqck08PFk/thwalU1xjQup2bwyOfbSLhwzUFCgT1LDH3ZhD0K4Y85Tk8pYTeD0WhKhYgnwNu8sVtKEvzvHQCa+1bji7+G41XZmCdz4eoNRny+lTPJqaWv8Y9Y49Yom+bdjN0AKgDaYDTlGzcPuDvXg8noD4yNyYB2Db2ZOyYMDzfjY5548TqPfL6Vi9eK9QC0ZCT/AQuHQYbZ2Gq1gEFR4FrsWR7lEm0wmvJPu4FQ32QcZ6TCupx5MmF+NflweAiVXIz5JYfOXWX0vG1cvZFhf11p14wFjFfNzzE8fGDYYvCsYSJlJDIAABAYSURBVP+2ywjaYDTlHxeXPJPviF+UZ1vV7q3rMGuIyTKHLT4xmce+sHOYh6wsYyLdmV1mjZVgyHzj6VcFQhuMxjlo1gVaZi99U7D6VeOxsJm+gQ14o387S3rL0SQmLtxJhj3CPCgF616H/blCJt0/E5p1tX1bZRy9KbDGeeg11dhDSGXCsQ1w+Fdo0ctyenhEU5Kvp/PWz8aCyDX7zjL0k2ga1vC0mQS3rBsMPPsOHZJX5WR2eBJCx9isjfKENhiN8+DbCoJHQuw8I736VWjeHVxzPuZ/u+sOklPS+XjjUQBijl8k5njBu0sWh8Zylg/dZtPOJcGSF+MWQkCPf+F8iwCsQ98iaZyLbi+DezXj+Px+iFuQ57SI8NJ9rXk4vIlNm+3hsoOf3P+Zx1yWZHZmxJUJzF5/1KZtlSes2njN0eiN1zTFYsNbsH6acVytLkzcAZWr5blEKcWmw0kl35lAZdLmwBxa/f6RJStLKrGq8STG/24CBBeBb8ZFEurnnOuNSrw3taPRBqMpFmnX4L0QuGJeTd3tZej2ku3buZYES8bC0fU5edUbweAvyWoQzCNzt7LpcBIAjWt6svKpLnh5ON/8lxLv7KjRlCvcq0L3f+akN802QiTYksRY+LhrXnNp3h3GbYRGIbi4CDMHBVLdwxj/OfnndaYu32dbDeUAbTAa58Q0DOr4G8fpKbD+zcKvtxalYPvnMO9euJyYk9/1eRixxFgfZaa+tydvDMiJavJtbCI/7ymjMWrshDYYjXPi4gq9c4Wj3Dkfzu0vWZ1pKbD0b7DiWcg0Lzfw8DZ2AOjxitHmTfQNbEDfwJyQni9/v5tzlx2wHspBaIPROC939jRuWwBUVt4dE4tL0hH4vBfEL8zJq9ceHt8ArW6JbZ+H1/u1o763BwAXU9J5Ycmu8rf7wW2iDUbj3PR+HTCvETi0Go7+Vvw6DqyET7rD2Vw78JhGwNg1ULNZkcW9q7jx30GBlvRvB8/zVfTx4usoh2iD0Tg39dob4zHZrH7VWCdkDZkZ8Ou/YNHDcCPZyHN1hz6zod/74Gb9DOCOd9bm0c45ZjRt5X6OnL9qdfnyijYYjfPT/Z9QyWwGZ3bB7m+KLnP1PHw1wNi3KBvvJvDXXyBk9G1F/3/unla0rucFQGp6FpMWx5X/LW+LQBuMxvnxbgiR43PSa183gm8XxMntxiPoYxtz8u64G8ZtgIbBty3Dw82Vt4eYcHc1vna7EpN5b+2h266vPKANRlMx6PQ0VDHvVHw5EaI/vPUapWDrJzDvvpyo/wjc9RIM/9Ymkf/b1K/Oc/fkBPl+f/1hYm20Fqosog1GUzHwqA7dX85J/+9tuJYrJHTaNfj+cVj1PGSlm8v4GMbS/eV8H0HfLo92bk6H5oZZZSl49ps4rpVGACwHoA1GU3EIHmWErAS4cdmI8g9w4TB81jPv2Ex9kzErN1e4B1vh4iL8d7DJEi/4eFIKr//knLN8tcFoKg6ubkbMmGxi5sKWD+CTbnAu1xc8eKQxmFujqd2kNPTxZGp/f0t60faTrNl31m7tOQptMJqKRav7oGkn4zgrA355GdKuGGnXytD3fej7nhFM3M70NzXkgYD6lvRLS3Zx/koJV3eXMbTBaCoWIubJdzfh0xQeXQPBj5SiFGFa/3bUq26YWdK1NF50slm+9tzZca6InBORPbnyZojIARHZJSI/iIiPvdrXaAqkYQi0H5yTbnGP8Qi6fmDBZeyETxV3Zuaa5bvuwDm+3nai1HXYC3v2YKKAmxdprAHaKaUCgN+Bl28upNGUCn3ege6vQL8P4OFFDt1KpHOL2ozp5GdJv/HTfo46ySxfe24duxH486a81Uqp7Odx0UAje7Wv0RSKe1W463kIGm5se+JgXry3NS3qGFH3rqdnMumbeKeY5evId/avwKqCTorI4yISIyIx58+fL0VZGk3p4+HmyjtDTbi5GksQ4k9e4v11hx2squQ4xGBE5J9ABrCgoGuUUp8opUKVUqG+vr6lJ06jcRD+Dbx5tlcrS/r99YfZeaJ8z/ItdYMRkVHAg8Bw5UzD5RqNDXi8a3PCzcHBM7MUkxbHkZJWfmf5lqrBiMi9wItAX6VUSmm2rdGUB1xdhP8ODqSaeZZvQlIKb6woYSQ+B2LPx9QLgS1AKxFJFJGxwPuAF7BGROJE5KNCK9FoKiCNa1ZhSt+cWb5fbz3B2v3lc5avPZ8iPayUqq+UclNKNVJKfa6UulMp1VgpZTK/nrBX+xpNeeah4Ibc166eJf3ikl0l38PJATj++ZxGo7kFEeHNAe2p41UZgAtX03hpye5yN8tXG4xGU0apUdWdGblm+f66/yyLt590oKLiow1GoynD3NXSl1GROau6p/60j4QL1xyoqHhog9Foyjgv3deGO3yrApCSlsmkb+LIKCezfLXBaDRlHE93V2YPDaKSizHLd+eJS3zw2xEHq7IObTAaTTmgXUNvJvXKieU7e+0h4k9ecqAi69AGo9GUE8Z1bU5IU2PVd2aWYvS8bcxa83uZ3opWG4xGU06o5OrC24NNVHU3ApBfTEnn3bWH6Dh9HU8v2lkm1y1pg9FoyhFNalXho0dCLFHwADKyFD/GnWLAB5vpN2cTS3f+QVpG2RgElvIwcSc0NFTFxMQ4WoZGU2ZIz8xi9d6zRG0+xvaEW3suvl6VGRbehOEdmlDHy77xhUUkVikVmu85bTAaTflmzx/JRG1OYFn8qVt6Lm6uwgPt6zO6UzNMje0ToVYbjEZTAUi6eoNF208yf8txzuQz8Gtq7MOYTn7c164+7pVsNzqiDUajqUCkZ2bxy94zRG1KICafbWl9vSozIqIpwyKa4Gte61QStMFoNBWU3YnG7dPy+FOkZd56+9QnoAGjOvoRWILbJ20wGk0F58LVGyzceoL50cc5l8/mbkFNfBjd8fZun7TBaDQawLh9WrXnDFGbjrHjxK0zget4VWZEh6Y8HG797ZM2GI1Gcwu7Ei8RtTmBn+JP33L75O7qwsDQRrw5oH2R9RRmMHqinUZTQQlo5MOswSY2vdSDZ3u1zNNjScvMIiur5J0PbTAaTQXH16syT93dgk0v9mD2UBNBTYwB31Ed/Upcd6US16DRaJwC90ou9DM1pJ+pIYfOXqFFXa8S16l7MBqN5hZsYS6gDUaj0dgRbTAajcZuaIPRaDR2QxuMRqOxG+Viop2InAeOW3FpbeCCHaXYs36tvfTrtnf9FUV7U6WUb34nyoXBWIuIxBQ0o7Cs16+1l37d9q5fa9e3SBqNxo5og9FoNHbD2Qzmk3Jcv9Ze+nXbu/4Kr92pxmA0Gk3Zwtl6MBqNpgyhDUaj0dgNpzEYEblXRA6KyGERecmWZcXgXfP5XSISnOtcgojsFpE4ESkyKpYVbbUWkS0ickNEnrNnfXbQPtz8/uwSkc0iEmiv+oqj3Yp2+pnbiBORGBHpXPg7UbI6bak913VhIpIpIgPtVV9xPy8AKKXK/QtwBY4AzQF3IB5oa6uywP3AKkCADsDWXOcSgNo2bKsOEAZMA56zZ3120N4RqGE+vi/3+2Tr+qzVbmU71cgZjwwADtizTltqz3XdOmAlMNBe9RXn85L9cpYeTDhwWCl1VCmVBiwC+tmwbD/gS2UQDfiISH176FRKnVNKbQfSHVBfSdvarJTK3icjGmhUivWVpJ2ryvwNAqoCRT35sEedt9WOmYnAEuBcKddXJM5iMA2Bk7nSieY8W5Ut7BoFrBaRWBF53I467VGfPbWPxej12as+a7Vb1Y6IDBCRA8AK4K+F1GeLOm2mXUQaAgOAj4rQbIv6ivN5AZwnop3kk2ftfwxryhZ2TSel1CkRqQOsEZEDSqmNdtBpj/rsol1EumMYQmFjGSWtz1rtVrWjlPoB+EFEugKvAz1Lqr2QOm2p/R3gRaVUpkh+l9u0vuJ8XgDn6cEkAo1zpRsBp2xYtsBrlFLZP88BP2B0Q+2h0+b12UO7iAQAnwH9lFJJ9qqvGNqL9R6ZvzB3iEjtkmovqE4baw8FFolIAjAQ+EBE+tujvmJ+XgyKM2BTVl8YPbGjQDNyBq/8bVUWeIC8g7zbzPlVAa9cx5uBe22hE5hC0YO8t12fPbQDTYDDQEcbve/51lcc7Va2cyc5A7LBwB/ZaVvXaWvtN10fReGDvLddX3E/L5Y6ivNFLssvjCc9v2OMkv+zpGWBJ4AnzMcCzDGf3w2EmvObm/9I8cBea9q1oq16GP9pLgOXzMfVbV2fnbR/BlwE4syvGHvUV1ztVrTzormeOGAL0NkG70W+ddpa+03XRlGIwZSkvtv5vCil9FIBjUZjP5xlDEaj0ZRBtMFoNBq7oQ1Go9HYDW0wGo3GbmiD0Wg0dkMbjJNiXgkbJyJ7RGS5iPjYqF4/Edlji7pKqKOBiHznaB2awtEG47xcV0qZlFLtgD+B8Y4WZEuUUqeUUoWGJtA4Hm0wFYMtmBe1iUg1EVkrIjvMsT36mfP9RGS/iHwqIntFZLWIeJrPhYhIvIhsIZdRiYiHiMwz17PTvGYIERktIkvNPadjIjJBRJ41XxMtIjVvFigiUWLE3NksIkez45CIwQxzT2y3iAzJpXeP+dhfRLaZe2y7RKSFOX9ErvyPRcQ1n3afMbe3Q0QW2PZt1zh8Bq5+2ecFXDX/dAW+xTytG2O6eHXzcW2MqfgC+AEZgMl87htghPl4F3CX+XgGsMd8/Hdgnvm4NXAC8ABGm+v1AnyBZHJmuL4NPJOP3iizThegLUZYAYCHgDXm36OuuY36Zr3ZOt4DhpuP3QFPoA2wHHAz538AjMyn3XMYG4c5/G/mjC/dg3FePEUkDkgCamJ8ScEwkzdFZBfwK0bPpq753DGlVJz5OBbwExFvwEcptcGcPz9XG52z00qpAxi7b7Y0n1uvlLqilDqPYTDLzfm7McwhP5YqpbKUUvtyaeoMLFRKZSqlzgIbMAJo5WYL8A8ReRHDLK4DdwMhwHbz+3A3xnT3m3kN2G/unWlsjDYY5+W6UsoENMX4r559azMco1cRYj5/FqPXAXAjV/lMjN6OUHAIiMLiA+SuKytXOouCw4TkLiM3/SwQpdTXQF/gOvCLiPQwl/tCGeNQJqVUK6XUlDziRdww4rS0UEpFFtWOpvhog3FylFLJwFPAc+YvlDdwTimVbh4zaVpE+UtAsuTElB2e6/TG7LSItMRY/XzQxr/CRmCIiLiKiC/QFdiW+wIRaQ4cVUq9CyzDCFG5Fhhojl2CiNQUkZt/1yoYq55vmK+xyZM2TQ7OEnBKUwhKqZ0iEg8MBRYAy81Bm+OAA1ZUMQaYKyIpwC+58j8APhKR3RjjN6OVUjesCHxUHH4AIjFW8SrgBaXUGRHxy3XNEGCEiKQDZ4CpSqk/ReQVjAhsLhghQ8dj3MYBhvmKyBTgfyJyA8gQkTClVJYtf4GKjF5NrdFo7Ia+RdJoNHZDG4xGo7Eb2mA0Go3d0Aaj0WjshjYYjUZjN7TBaDQau6ENRqPR2I3/B0HeozsSa1R+AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 288x216 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plot_synthetic_density(epsilons, target_densities, greedy_densities, \"synthetic_density_disjunction.pdf\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def remove_sparse_labels(graph, min_edges_proportion = 0.005):\n",
    "    label_edge_counts = dict()\n",
    "    for edge in graph.edges:\n",
    "        for label in graph.edge_labels[edge]:\n",
    "            if not label in label_edge_counts:\n",
    "                label_edge_counts[label] = 0\n",
    "            label_edge_counts[label] += 1\n",
    "    removed_labels = set()\n",
    "    for label in label_edge_counts:\n",
    "        if label_edge_counts[label] < min_edges_proportion*graph.number_of_edges():\n",
    "            removed_labels.add(label)\n",
    "    for edge in tuple(graph.edges):\n",
    "        graph.edge_labels[edge] -= removed_labels\n",
    "        if len(graph.edge_labels[edge]) == 0:\n",
    "            graph.delete_edge(edge)\n",
    "    graph.all_labels -= removed_labels\n",
    "    return label_edge_counts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def run_decompostion(test_graph):\n",
    "    vertex_to_index = dict([(v, i) for i, v in enumerate(test_graph.nodes)])\n",
    "    with open(\"test_graph.txt\", \"w+\") as f:\n",
    "        for edge in test_graph.edges:\n",
    "            f.write(f\"{vertex_to_index[edge[0]]} {vertex_to_index[edge[1]]}\\n\")\n",
    "\n",
    "    decomposition_path=\"../density-friendly-decomposition-master/decomposition/core\"\n",
    "    input_file=\"test_graph.txt\"\n",
    "    decomposition = !$decomposition_path -i $input_file -m e | head -n 1\n",
    "    density, n_nodes = decomposition[0].split(\" \")[:2]\n",
    "    return density, n_nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pickle\n",
    "datasets = [\n",
    "    (\"Enron\", \"enron_graph_subject_only.pkl\", True),\n",
    "    (\"HEP-TH\", \"phys_graph_title_min_91_shared_2.pkl\", False),\n",
    "    (\"DBLP\", \"dblp_graph_title_min_140_shared_2.pkl\", False),\n",
    "    (\"Twitter\", \"tweets_graph.pkl\", True),\n",
    "]\n",
    "\n",
    "with open(\"graph_results.csv\", \"w+\") as results_file:\n",
    "    results_file.write(\"dataset,n,m,L,p,density,t-con,n-con,m-con,density-con,L-con,\"+\\\n",
    "                       \"t-dis,n-dis,m-dis,density-dis,L-dis,\"+\\\n",
    "                       \"density-decomp,n-decomp\\n\")\n",
    "    for title, graph_file, sparse_labels_removal in datasets:\n",
    "        print(title)\n",
    "        with open(graph_file, \"rb\") as file:\n",
    "            test_graph = pickle.load(file)\n",
    "        if sparse_labels_removal:\n",
    "            min_edges_proportion = 0.001\n",
    "            label_edge_counts = remove_sparse_labels(test_graph, min_edges_proportion=min_edges_proportion)\n",
    "        else:\n",
    "            test_graph.update_label_set()\n",
    "        results = []\n",
    "        for conjunction in [True, False]:\n",
    "            t = datetime.now()\n",
    "            density, labels, return_graph = greedy_find_dense_label_induced_subgraph(\n",
    "                test_graph, conjunction=conjunction, return_graph=True)\n",
    "            results.append(datetime.now()-t)\n",
    "            results.append(return_graph.number_of_nodes())\n",
    "            results.append(return_graph.number_of_edges())\n",
    "            results.append(density)\n",
    "            results.append(len(labels))\n",
    "        results = [str(r) for r in results]\n",
    "        decomp_density, decomp_nodes = run_decompostion(test_graph)\n",
    "        n = test_graph.number_of_nodes()\n",
    "        m = test_graph.number_of_edges()\n",
    "        L = len(test_graph.all_labels)\n",
    "        p = 0\n",
    "        for edge in test_graph.edges:\n",
    "            p += len(test_graph.edge_labels[edge])\n",
    "        density = test_graph.density()\n",
    "        results_file.write(f\"\\\\dtname{{{title}}},{n},{m},{L},{p},{density},\"+\\\n",
    "                            f\"{','.join(results)},{decomp_density},{decomp_nodes}\\n\")\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pickle\n",
    "\n",
    "#with open(\"enron_graph_subject_only.pkl\", \"rb\") as file:\n",
    "#with open(\"phys_graph_title_min_91_shared_2.pkl\", \"rb\") as file:\n",
    "with open(\"tweets_graph.pkl\", \"rb\") as file:\n",
    "#with open(\"dblp_graph_title_min_140_shared_2.pkl\", \"rb\") as file:\n",
    "    test_graph = pickle.load(file)\n",
    "    \n",
    "sparse_labels_removal = True\n",
    "if sparse_labels_removal:\n",
    "    print(f\"Labels before removal: {len(test_graph.all_labels)}\")\n",
    "    min_edges_proportion = 0.001\n",
    "    print(f\"Remove labels that occur in less than {int(min_edges_proportion*test_graph.number_of_edges())} edges\")\n",
    "    label_edge_counts = remove_sparse_labels(test_graph, min_edges_proportion=min_edges_proportion)\n",
    "    \n",
    "print(f\"Nodes: {test_graph.number_of_nodes()}\")\n",
    "print(f\"Edges: {test_graph.number_of_edges()}\")\n",
    "print(f\"Labels: {len(test_graph.all_labels)}\")\n",
    "print(f\"Density: {test_graph.density()}\")\n",
    "if not sparse_labels_removal:\n",
    "    test_graph.update_label_set()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "density, n_nodes = run_decompostion(test_graph)\n",
    "print(density, n_nodes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.7222222222222223 ['mopa', 'action'] 18 31\n",
      "1.5887265135699373 ['legal'] 479 761\n",
      "1.7714285714285714 ['ecommerc', 'origin'] 35 62\n",
      "1.5480769230769231 ['gi', 'updat'] 208 322\n",
      "1.8333333333333333 ['meet', 'instruct', 'ga'] 12 22\n",
      "------\n",
      "2.1987023519870235 ['mopa', 'legal', 'gi', 'stanley', 'paraleg', 'raptor', 'pope', 'collater', 'ucc', 'scientist', 'org', 'ecommerc', 'bruce', 'emmis', 'alberta', 'plastic', 'pastoria', 'puls', 'japan', 'seat', 'gastech', 'block', 'setoff', 'england', 'wharton', 'bermuda', 'toll', 'entergi', 'usec', 'transammonia', 'tarantula', 'morton', 'rbc', 'singapor', 'demonstr', 'securit', 'ongo', 'cmua', 'currenc', 'staf', 'clerk', 'monterrey', 'clarksdal', 'ormet', 'distil', 'gambl', 'powel', 'westlaw', 'tibco', 'banqu', 'lover', 'japanes', 'mahonia', 'ibj', 'movement', 'mitsubishi', 'transmitt', 'dte', 'calm', 'metroga', 'offlin', 'imperi', 'asian', 'carol', 'ecp', 'omnibu', 'carr', 'balhorn', 'diamond', 'spinnak', 'plc', 'samuel', 'lunchabl', 'mne', 'amount', 'damiri', 'indusrial', 'diaz', 'talon', 'avici', 'schott', 'multicurr', 'sissi', 'servicio', 'vidriera', 'sladoj', 'outlet', 'waterhous', 'floo', 'fka', 'comercializadora', 'belvieu', 'ripon', 'trantula', 'egrm', 'jermain', 'grupo', 'nationsbank', 'lambert', 'bermudean', 'calidra', 'hensley', 'anexb', 'utilti', 'llp', 'pricewaterhousecoop', 'cpi', 'spanish', 'abil', 'reinsur', 'teesid', 'drift', 'elit', 'manhattan', 'tradespark', 'declin', 'andi', 'interim', 'self', 'ctc', 'massey', 'bryson', 'cftc', 'larg', 'hoecker', 'suspens', 'dig', 'freight', 'rick', 'gtc', 'clark', 'solvenc', 'mission', 'alto', 'asst', 'pira', 'small', 'connect', 'cmt', 'outcom', 'staffer', 'ridgewood', 'spokesman', 'sender', 'braintre', 'eager', 'capitol', 'illustr', 'bosk', 'swipe', 'courag', 'spin', 'cling', 'committte', 'knew', 'ize', 'joskow', 'own', 'admit', 'urg', 'cmta', 'brownbag', 'flood', 'huski', 'belco', 'falcon', 'elliott', 'pariba', 'iii', 'instruct', 'restrict', 'argentin', 'dabhol', 'prospect', 'loui', 'reg', 'northeast', 'kim', 'mention', 'randi', 'escap', 'treasuri', 'exec', 'ye', 'tape', 'enroncredit', 'rang', 'scope', 'trend', 'blake', 'dpl', 'riverval', 'equit'] 1233 2711\n",
      "1.7173789173789173 ['fantasi', 'superstici', 'shreveport', 'midstream', 'redraw', 'tubervil', 'erni', 'chic', 'dti', 'geaux', 'hd', 'algo', 'fil', 'roanok', 'formula', 'mdq', 'breath', '_aug', 'clgf', 'percentag', 'proprietari', 'cope', 'bridgeback', 'niagara', 'marketlink', 'caneast', 'larosa', 'oracl', 'flip', 'outdat', 'strg', 'bucket', 'leagu', 'demograph', 'sixteen', 'judi', 'rebook', 'paintbal', 'cct', 'score', 'unbeliev', 'hunter', 'strand', 'chandley', 'greenash', 'panelist', 'eye', 'tgt', 'avoid', 'sonoco', 'del', 'uccsu', 'borenstein', 'prevail', 'interli', 'paperexchang', 'paperloop', 'unanim', 'feintsein', 'uipdat', 'testifi', 'palmdal', 'pact', 'bois', 'ratepay', 'idaho', 'manufatur', 'silicon', 'regenc', 'taken', 'cma', 'pdt', 'neast', 'gain', 'bailey', 'teja', 'cgv', 'bounc', 'agav', 'sonat', 'forfeit', 'rocker', 'rudi', 'coke', 'zealand', 'advert', 'gore', 'keneal', 'militari', 'marcher', 'mpeg', 'teasingcat', 'mpg', 'goron', 'ultim', 'chili', 'secon', 'chamber', 'sql', 'tie', 'inject', 'orwel', 'luv', 'poam', 'suburban', 'bookout', 'lakesid', 'cglf', 'brainstorm', 'kristin', 'doorstep', 'entex', 'anticip', 'conferen', 'promptli', 'calp', 'nful', 'todd', 'dayton', 'juri', 'rehear', 'shorten', 'rout', 'half', 'devil', 'usag', 'gallup', 'nbp', 'ipp', 'courtesi', 'cedar', 'coronado', 'loos', 'requri', 'resutl', 'allenergi', 'nors', 'larenc', 'demarco', 'mrkt', 'ofo', 'optim', 'merlin', 'cousino', 'wgl', 'miscellan', 'aghh', 'teamleadership', 'nath', 'cmr', 'snowden', 'kaufman', 'tani', 'authorizarion', 'sim', 'commonwealth', 'alaska', 'cub', 'oglethorp', 'midcoast', 'enough', 'petroleum', 'carter', 'done', 'sea', 'expenditur', 'overview', 'bowen', 'voter', 'exit', 'six', 'chicken', 'salari', 'hedstrom', 'mass', 'aegi', 'lambertvil', 'leidi', 'oprisk', 'unifi', 'sitara', 'hess', 'port', 'meter', 'rose', 'varianc', 'sith', 'dpr', 'pretti', 'transport', 'desk', 'track', 'trader', 'reliant', 'ce', 'basi', 'tenaska', 'columbia', 'commod', 'broker', 'id', 'tagg', 'oneok', 'crestar', 'nicor', 'assist', 'old', 'survey', 'phi', 'devon', 'republ', 'cove', 'td', 'wisconsin', 'orig', 'lone', 'chemic', 'migrat', 'turn', 'coenergi', 'keep', 'fin', 'ugi', 'accomplish', 'insid', 'cargil', 'admin', 'interact', 'map', 'entellig', 'banker', 'merchant', 'agent', 'also', 'pilot', 'enov', 'bennett', 'anp', 'exp', 'formerli', 'logic', 'iroq', 'stingray', 'synthet', 'mpr', 'cnr', 'replac', 'nng', 'egan', 'divis', 'setup', 'learn', 'preced', 'denver', 'gate', 'engag', 'flash', 'overdu', 'margin', 'phillip', 'adjust', 'reloc', 'altrad', 'reorgan', 'commoditylog', 'aurora', 'five', 'intra', 'cfo', 'cast', 'conoco', 'script', 'usa', 'claus', 'improv', 'bag', 'marin', 'citibank', 'perri', 'forest', 'ngpl', 'psnc', 'mart', 'gomez', 'alliant', 'interdesk', 'firstenergi', 'pure', 'outercurv', 'puerco', 'walton', 'lite', 'owe', 'sapient', 'vpn', 'thompson', 'parodi', 'prior', 'devonian', 'tmg', 'leed', 'kirkendal', 'agl', 'salomon', 'braodcast', 'concess', 'shade', 'singer', 'nabisco', 'chilean', 'proxicom', 'retract', 'cand', 'aristech', 'maintenac', 'viant', 'unlead', 'alreadi', 'replic', 'rpt', 'hopewel', 'resumpt', 'analytica', 'ttt', 'serious', 'grey', 'spear', 'intercompani', 'massachusett', 'nova', 'bytz', 'greg', 'cm', 'consid', 'joy', 'pipe', 'vng', 'roll', 'natsourc', 'timothi', 'ppt', 'neg', 'social', 'torch', 'imc', 'kellogg', 'basketbal', 'assess', 'fom', 'tetco', 'formosa', 'gcp', 'click', 'lobbi', 'skill', 'exposur', 'hub', 'wti', 'coverag', 'central', 'chees', 'tiger', 'window', 'verif', 'txu', 'island', 'eastern', 'recap', 'logist', 'statoil', 'consolid', 'nimo', 'cone', 'susan', 'friendli', 'count', 'path', 'interfac', 'belden', 'theoret', 'coh', 'treati', 'perez', 'eugenio', 'api', 'borrow', 'lectur', 'nipsco', 'nortel', 'vpp', 'phoenix', 'interst', 'brant', 'counterparti', 'shackleton', 'gen', 'cogener', 'monet', 'strong', 'erm', 'opt', 'cannon', 'redmeteor', 'allegro', 'daughter', 'equitran', 'neat', 'influenc', 'ucla', 'hou', 'tembec', 'ontario', 'pvm', 'fletcher', 'aspect', 'cityg', 'hast', 'eob', 'ora', 'incorpor', 'discount', 'gupta', 'anuj', 'tf', 'portland', 'pasadena', 'river', 'float', 'obmc', 'index', 'forcenergi', 'paso', 'la', 'histori', 'disput', 'cogen', 'illinoi', 'erequest', 'place', 'allen', 'joe', 'humor', 'ecc', 'chronic', 'undercollect', 'solv', 'mere', 'lamb', 'asham', 'educ', 'grand', 'hyatt', 'inclus', 'upon', 'cheryl', 'heart', 'attn', 'sleev', 'poin', 'marriag', 'differ', 'promis', 'johnston', 'marq', 'cng', 'cleburn', 'withdraw', 'saga', 'enpow', 'shipper', 'trigger', 'redibook', 'ground', 'deem', 'amoco', 'panther', 'puget', 'sound', 'agt', 'wki', 'tco', 'sep', 'png', 'scotia', 'cao', 'telecom', 'eagl', 'webmethod', 'io', 'kill', 'attack', 'transit', 'pnm', 'rodeo', 'meh', 'unknown', 'kick', 'chicago', 'junior', 'achiev', 'demo', 'tripl', 'employ', 'bonu', 'guidelin', 'bridg', 'trust', 'relationship', 'cibc', 'integr', 'aep', 'nlrb', 'lutz', 'compens', 'prepar', 'macerich', 'bid', 'rush', 'personnel', 'text', 'vision', 'montana', 'liquid', 'limit', 'spill', 'wilson', 'calc', 'louisiana', 'format', 'virginia', 'tennesse', 'east', 'deutsch', 'dickenson', 'delainey', 'duke', 'excit', 'thru', 'jersey', 'flight', 'tim', 'trco', 'resourc', 'david', 'expens', 'archeolog', 'topock', 'outlook', 'farewel', 'understand', 'quiz', 'post', 'act', 'memori', 'watch', 'engin', 'vote', 'progress', 'affair', 'decemb', 'analyst', 'deal', 'center', 'offic', 'daili', 'prc', 'curv', 'congratul', 'mitig', 'asset', 'var', 'ee', 'regulatori', 'nymex', 'cdwr', 'eol', 'xm', 'origin', 'budget', 'upstream', 'associ', 'tva', 'subcommitte', 'wind', 'whalley', 'respond', 'tech', 'submit', 'heat', 'gordon', 'accrual', 'deseret', 'cfa', 'produc', 'web', 'sempra', 'qbr', 'balanc', 'player', 'yesterday', 'court', 'load', 'hit', 'amp', 'benefit', 'gari', 'palo', 'histor', 'focus', 'windfal', 'critic', 'manipul', 'consider', 'fail', 'annuiti', 'near', 'district', 'loss', 'atlant', 'apr', 'feder', 'shortag', 'target', 'cent', 'bod', 'hall', 'expans', 'mainlin', 'intellig', 'ice', 'mari', 'phase', 'ec', 'discoveri', 'robert', 'per', 'dash', 'steel', 'daishowa', 'sierra', 'ashland', 'wheel', 'flag', 'dynegi', 'border', 'candid', 'conting', 'harass', 'administr', 'pulp', 'provid', 'certain', 'exempt', 'key', 'richard', 'deposit', 'csa', 'employe', 'orient', 'mobil', 'exchang', 'like', 'william', 'packet', 'smith', 'structur', 'disregard', 'barclay', 'patti', 'mine', 'carnegi', 'sacramento', 'vicki', 'underwrit', 'period', 'redwood', 'exercis', 'myth', 'revenu', 'organiz', 'output', 'complet', 'nation', 'juvenil', 'expir', 'appeal', 'drill', 'kern', 'mkt', 'bay', 'hard', 'ew', 'congrat', 'discrep', 'segment', 'continent', 'coral', 'chronicl', 'role', 'european', 'nat', 'antonio', 'fundament', 'timber', 'hydrocarbon', 'hpl', 'potenti', 'calpin', 'unit', 'enw', 'govern', 'ship', 'idea', 'claim', 'flow', 'prioriti', 'litig', 'natur', 'regul', 'arbitr', 'procedur', 'metal', 'taylor', 'exampl', 'auto', 'coop', 'wsj', 'pro', 'epc', 'oregon', 'goug', 'redrock', 'manual', 'sce', 'sdg', 'interview', 'albani', 'chafe', 'inga', 'iou', 'tidbit', 'delaney', 'compon', 'expos', 'hint', 'reuter', 'prohibit', 'iep', 'bln', 'armageddon', 'freeman', 'tribun', 'mex', 'recoveri', 'ceo', 'smutni', 'seattl', 'kees', 'insead', 'dohn', 'satellit', 'linger', 'host', 'rooki', 'former', 'lambast', 'esai', 'motiv', 'maul', 'revalu', 'rfb', 'justifi', 'forbear', 'tea', 'alleg', 'extraordinari', 'seller', 'creditdotcom', 'hertzberg', 'conspir', 'sector', 'megawatt', 'fiscal', 'duqu', 'turnonthetruth', 'woe', 'bei', 'peevey', 'effici', 'kari', 'fiddl', 'cinergi', 'penal', 'shiver', 'approach', 'rabi', 'unfair', 'surcharg', 'gao', 'vacanc', 'major', 'diann', 'powerpl', 'rod', 'congression', 'burton', 'everyon', 'mellon', 'poll', 'abus', 'pace', 'lrc', 'wptf', 'pioneer', 'rio', 'reaction', 'infrastructur', 'plummet', 'seismic', 'probe', 'costlier', 'signific', 'faltinsen', 'intrast', 'threat', 'shen', 'gouger', 'feinstein', 'protest', 'cmte', 'denounc', 'easier', 'fyi_____iso', 'conserv', 'rosenfield', 'pinnacl', 'whaley', 'legsil', 'grc', 'suspend', 'loom', 'politician', 'resolv', 'via', 'modesto', 'fed', 'phoni', 'rise', 'pub', 'sheila', 'forese', 'endors', 'inventori', 'unsur', 'baja', 'metcalf', 'freez', 'outrag', 'cohen', 'venu', 'specialist', 'halliburton', 'halt', 'checkout', 'apx', 'fastbal', 'advisor', 'bearish', 'caifornia', 'fiction', 'stakehold', 'senior', 'soar', 'congest', 'orang', 'commentari', 'svmg', 'grid', 'caucu', 'attitud', 'californian', 'barton', 'dire', 'lobbyist', 'statistician', 'averag', 'ogc', 'codgil', 'platt', 'yurkanin', 'seiz', 'karrieremoeglichkeiten', 'defend', 'shelter', 'qf', 'blueprint', 'prudenc', 'applicatio', 'whoop', 'cdwp', 'magic', 'hinder', 'tex', 'ban', 'stig', 'crescendo', 'product', 'sell', 'valid', 'third', 'andersen', 'brown', 'tom'] 3510 6028\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.1791823112223614 ['gir', 'accord', 'eix', 'timet', 'noon', 'sfo', 'blame', 'examin', 'fellow', 'lower', 'misdirect', 'ladwp', 'angelid', 'rais', 'editori', 'sac', 'bee', 'wit', 'elimin', 'coastal', 'pcg', 'voluntari', 'tra', 'figur', 'utilit', 'secretari', 'newsmak', 'montali', 'face', 'challeng', 'brult', 'pst', 'ami', 'refund', 'dereg', 'abx', 'declar', 'northern', 'cesg', 'principl', 'later', 'let', 'lawmak', 'soft', 'consequ', 'calif', 'alpert', 'walter', 'harvey', 'other', 'input', 'exam', 'florio', 'arm', 'sdge', 'hogan', 'deregul', 'expertfind', 'chief', 'gop', 'deliv', 'delay', 'ldc', 'legislatur', 'notebook', 'socalga', 'disclos', 'taster', 'merg', 'inquiri', 'type', 'titan', 'clair', 'purpos', 'acknowledg', 'mount', 'king', 'rebutt', 'specif', 'hunger', 'fountain', 'pegasu', 'peac', 'hace', 'iroquoi', 'psco', 'cut', 'turbopark', 'sec', 'teleconfer', 'mcneali', 'northwestern', 'checklist', 'testimoni', 'delta', 'coalit', 'cheney', 'wagner', 'kinder', 'pwr', 'food', 'sbx', 'doctor', 'advisori', 'overrid', 'electrobolt', 'carla', 'dicastro', 'www', 'http', 'henwood', 'three', 'iri', 'mack', 'yergin', 'reregul', 'kean', 'comprehens', 'sen', 'stay', 'piec', 'creditor', 'simul', 'middl', 'suit', 'posey', 'agre', 'broadband', 'partnership', 'root', 'heard', 'breakout', 'behind', 'aguirr', 'sddp', 'oklahoma', 'grade', 'up', 'compar', 'governor', 'wright', 'csu', 'republican', 'edit', 'delet', 'coffe', 'stage', 'mon', 'summari', 'clarif', 'peggi', 'denni', 'verbag', 'nice', 'promin', 'berkeley', 'barb', 'focu', 'memorandum', 'lacima', 'clewlow', 'shift', 'differenti', 'ohio', 'multipl', 'cera', 'wood', 'highlight', 'srac', 'mayor', 'linda', 'believ', 'kpmg', 'subsidiari', 'dapsa', 'telecon', 'tradewel', 'amerex', 'aether', 'signatori', 'excambria', 'express', 'wow', 'young', 'bellingham', 'tut', 'wnba', 'comet', 'timelin', 'transform', 'followup', 'commiss', 'australian', 'subscript', 'section', 'mann', 'epf', 'gulf', 'rac', 'prebon', 'bandwidth', 'cancel', 'polit', 'bankruptci', 'point', 'committe', 'electron', 'board', 'mba', 'law', 'quot', 'organ', 'goal', 'coal', 'follow', 'award', 'field', 'consult', 'itinerari', 'preliminari', 'entiti', 'hold', 'newslett', 'retent', 'prepay', 'ghost', 'mexico', 'receipt', 'urgent', 'video', 'comment', 'investig', 'statement', 'locat', 'dec', 'georg', 'agmt', 'clickpap', 'temporari', 'continu', 'effort', 'legisl', 'astro', 'hear', 'epmi', 'john', 'harvard', 'steve', 'research', 'quarter', 'audit', 'bloomberg', 'gov', 'valuat', 'senat', 'fcel', 'eecc', 'caiso', 'allianc', 'india', 'blue', 'still', 'charl', 'conflict', 'waiver', 'lynch', 'economist', 'canadian', 'dakota', 'articl', 'misc', 'alumni', 'american', 'privat', 'rule', 'park', 'littl', 'met', 'lesson', 'toronto', 'sign', 'comput', 'futur', 'sampl', 'nanni', 'leadership', 'clear', 'alloc', 'support', 'media', 'page', 'announc', 'stock', 'top', 'base', 'socal', 'lexi', 'descript', 'gleason', 'nois', 'navi', 'peaker', 'privileg', 'pat', 'permit', 'emiss', 'westinghous', 'cover', 'equiti', 'bear', 'remind', 'demand', 'cornhusk', 'septemb', 'jim', 'speaker', 'recruit', 'cst', 'pac', 'protect', 'chairman', 'bob', 'compressor', 'forward', 'phone', 'bush', 'merger', 'chri', 'lost', 'long', 'link', 'confirm', 'guaranti', 'lng', 'brokerag', 'review', 'issu', 'esa', 'around', 'lotu', 'onlin', 'standard', 'access', 'execut', 'hedg', 'southern', 'analysi', 'data', 'spread', 'energi', 'thursday', 'subpoena', 'chart', 'cargo', 'counsel', 'enrononlin', 'crisi', 'need', 'canada', 'agenc', 'detail', 'stuff', 'feedback', 'letter', 'swap', 'compress', 'volum', 'custom', 'approv', 'mike', 'vacat', 'meet', 'offsit', 'houston', 'rsvp', 'doc', 'system', 'night', 'interest', 'seminar', 'news', 'argentina', 'construct', 'use', 'local', 'total', 'celebr', 'split', 'organis', 'mill', 'harri', 'forecast', 'aron', 'graph', 'begin', 'mac', 'print', 'pep', 'renew', 'sunday', 'week', 'level', 'correct', 'dial', 'first', 'exclus', 'washington', 'cash', 'interconnect', 'super', 'austin', 'softwar', 'ken', 'hotel', 'acr', 'fan', 'explor', 'technic', 'run', 'yahoo', 'penn', 'haedick', 'johnson', 'train', 'leav', 'concern', 'goe', 'worth', 'abb', 'month', 'disclosur', 'site', 'calpx', 'york', 'variou', 'pacif', 'creditworthi', 'suppli', 'perform', 'arrang', 'workshop', 'document', 'termsheet', 'seek', 'calendar', 'buy', 'enrol', 'introduct', 'station', 'mid', 'foundat', 'wholesal', 'outag', 'option', 'set', 'client', 'particip', 'clickathom', 'et', 'enterpris', 'problem', 'error', 'sent', 'rfp', 'code', 'april', 'databas', 'spreadsheet', 'earth', 'end', 'activ', 'camp', 'moor', 'priceless', 'send', 'relat', 'chase', 'cob', 'escrow', 'fuel', 'name', 'australia', 'gener', 'paul', 'convent', 'notif', 'brazil', 'extens', 'paper', 'packag', 'propos', 'hour', 'aquila', 'gift', 'max', 'market', 'juli', 'jan', 'footbal', 'season', 'book', 'bench', 'rocket', 'success', 'take', 'greet', 'petro', 'mou', 'capit', 'stan', 'ok', 'tenn', 'recount', 'remedi', 'expect', 'front', 'introduc', 'ten', 'cooper', 'modifi', 'koch', 'tariff', 'dan', 'marathon', 'cpa', 'quarterli', 'union', 'black', 'laptop', 'winner', 'jessi', 'miller', 'impact', 'god', 'land', 'labor', 'bailout', 'trash', 'tourney', 'auction', 'ap', 'noncor', 'supplier', 'share', 'wheatland', 'enhanc', 'nomin', 'lie', 'ltr', 'bail', 'relief', 'committ', 'translat', 'depart', 'outsid', 'underway', 'restructur', 'gonzal', 'factor', 'wisdom', 'implement', 'spike', 'cross', 'mirant', 'disast', 'forc', 'gpg', 'tnrcc', 'municip', 'bakersfield', 'handl', 'desktop', 'midland', 'fix', 'csfb', 'hope', 'aggi', 'council', 'ballet', 'white', 'salmon', 'bash', 'zone', 'tower', 'avista', 'oblig', 'consumpt', 'tue', 'curtail', 'tip', 'involv', 'wire', 'nerc', 'extend', 'anderson', 'transcript', 'retail', 'lincoln', 'dominion', 'friendship', 'profil', 'stearn', 'jackson', 'pressur', 'push', 'catalytica', 'commerci', 'author', 'fpl', 'asap', 'proceed', 'add', 'especailli', 'dunn', 'remaind', 'gun', 'postpon', 'duti', 'card', 'welcom', 'larri', 'cell', 'arizona', 'speech', 'offer', 'citi', 'sheet', 'citizen', 'affili', 'fact', 'awesom', 'matter', 'util', 'nov', 'memo', 'weekli', 'indian', 'teco', 'btu', 'guid', 'studi', 'pcb', 'repli', 'feel', 'turbin', 'oil', 'region', 'monitor', 'eott', 'recordkeep', 'nitrogen', 'sulfur', 'bug', 'topic', 'cge', 'facilit', 'task', 'password', 'standbi', 'shop', 'plug', 'head', 'chapter', 'suess', 'jurisdict', 'upcom', 'experi', 'readi', 'extra', 'econ', 'effect', 'rock', 'core', 'tab', 'internet', 'mexican', 'nelson', 'contractor', 'woman', 'pager', 'crane', 'reschedul', 'tour', 'natrual', 'father', 'past', 'stress', 'put', 'indic', 'due', 'dilig', 'talk', 'bobbi', 'owner', 'better', 'stand', 'california', 'lay', 'puc', 'iso', 'solut', 'nyseg', 'assembl', 'singl', 'real', 'debat', 'ene', 'earlier', 'audio', 'conferenc', 'wrestl', 'fake', 'folk', 'countri', 'fli', 'fa', 'rmt', 'advanc', 'constel', 'ferc', 'eta', 'dwr', 'say', 'incom', 'voicemail', 'westlb', 'gone', 'lisa', 'ventur', 'wait', 'mhi', 'estim', 'peak', 'fyi', 'univers', 'physic', 'phil', 'arkansa', 'creek', 'stabil', 'fire', 'valley', 'tank', 'hendrick', 'wall', 'situat', 'nom', 'paid', 'pre', 'info', 'non', 'solicit', 'current', 'cultur', 'win', 'ask', 'dow', 'jone', 'sita', 'great', 'money', 'requir', 'airlin', 'default', 'high', 'entri', 'plenti', 'blackout', 'gray', 'davi', 'motion', 'ranch', 'tier', 'pain', 'blacklin', 'fri', 'judg', 'cpr', 'altern', 'contribut', 'appoint', 'profit', 'increas', 'printer', 'burn', 'pledg', 'intent', 'diabet', 'bullet', 'choke', 'req', 'leader', 'attorney', 'represent', 'network', 'director', 'opinion', 'server', 'reach', 'resolut', 'consum', 'accept', 'clean', 'side', 'francisco', 'calcul', 'cpuc', 'commerc', 'redraft', 'damag', 'sue', 'war', 'alon', 'deadlin', 'cal', 'supplement', 'pse', 'actual', 'knight', 'sourc', 'clinton', 'applic', 'busi', 'china', 'summit', 'digit', 'econom', 'floor', 'trade', 'manag', 'babi', 'promot', 'februari', 'net', 'sap', 'penney', 'staff', 'tournament', 'montreal', 'cap', 'box', 'holiday', 'game', 'golf', 'rotat', 'san', 'ect', 'annual', 'oper', 'life', 'thought', 'eim', 'earnest', 'earli', 'diego', 'jesu', 'prime', 'shutdown', 'beach', 'pig', 'space', 'platform', 'even', 'mtg', 'beck', 'time', 'apt', 'posit', 'seri', 'alert', 'reserv', 'tana', 'plane'] 4794 5653\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.0 ['mckinsey', 'cuiaba', 'siemen', 'eca', 'miracl', 'globe', 'biggest', 'rubi', 'compet', 'barney', 'websit', 'global', 'sher', 'manifesto', 'assumpt', 'repo', 'kaiser', 'kc', 'eweb', 'annex', 'hawaii', 'arthur', 'utilicorp', 'sara', 'must', 'morgan', 'bond', 'hill', 'transmiss', 'commission', 'bit', 'brief', 'length', 'sooo', 'mdea', 'cec', 'negoti', 'michael', 'respons', 'exhibit', 'consent', 'loi', 'spa', 'vepco', 'pass', 'counti', 'suiza', 'given', 'edgecomb', 'evil', 'lilco', 'advic', 'rev', 'elizabethtown', 'etown', 'ad', 'salsa', 'till', 'britney', 'swing', 'bomb', 'alp', 'develop', 'discuss', 'stanford', 'vinc', 'submitt', 'outlin', 'togeth', 'mgmt', 'recent', 'comparison', 'plant', 'mathemat', 'user', 'speak', 'rice', 'gourmet', 'lehman', 'altra', 'room', 'full', 'jame', 'luck', 'copi', 'brother', 'church', 'distribut', 'protocol', 'journal', 'initi', 'signatur', 'play', 'deer', 'cellular', 'cgey', 'grandma', 'student', 'voic', 'shoe', 'buddi', 'find', 'modif', 'hand', 'mess', 'nike', 'guarante', 'cp', 'pseg', 'math', 'provis', 'florida', 'nrg', 'mother', 'kid', 'bold', 'neumin', 'ppl', 'amend', 'sale', 'america', 'polici', 'lawyer', 'firm', 'eei', 'enfolio', 'facil', 'cga', 'januari', 'joint', 'midwest', 'etc', 'definit', 'evalu', 'paragraph', 'brent', 'con', 'term', 'rep', 'edison', 'member', 'air', 'process', 'eb', 'certif', 'complaint', 'newport', 'august', 'north', 'gisb', 'psa', 'tenni', 'electr', 'latest', 'four', 'allegheni', 'properti', 'master', 'isda', 'llc', 'viru', 'free', 'spring', 'much', 'ncaa', 'team', 'jeff', 'redlin', 'reimburs', 'investor', 'guest', 'pge', 'red', 'commit', 'contest', 'afternoon', 'egm', 'spot', 'practic', 'transfer', 'industri', 'ballot', 'economi', 'nda', 'tokyo', 'visit', 'wed', 'ethic', 'direct', 'sweet', 'way', 'water', 'tuesday', 'short', 'wednesday', 'would', 'perfect', 'revis', 'line', 'slide', 'acquisit', 'trial', 'bath', 'sailor', 'petit', 'ignor', 'tag', 'agreement', 'ecoga', 'languag', 'case', 'background', 'thing', 'possibl', 'risk', 'receiv', 'oct', 'monday', 'draft', 'save', 'scott', 'start', 'ena', 'bridgelin', 'catch', 'wish', 'import', 'hire', 'travel', 'competit', 'million', 'cartoon', 'valu', 'epa', 'winter', 'salli', 'contract', 'project', 'mani', 'contact', 'mark', 'number', 'deriv', 'friday', 'class', 'pleas', 'ticket', 'want', 'rate', 'invoic', 'note', 'job', 'sach', 'dad', 'membership', 'telephon', 'credit', 'file', 'transact', 'go', 'action', 'join', 'thanksgiv', 'alex', 'friend', 'true', 'tree', 'away', 'quick', 'home', 'round', 'special', 'result', 'children', 'corpor', 'beauti', 'see', 'never', 'enjoy', 'africa', 'loan', 'purchas', 'light', 'model', 'emerg', 'boy', 'regist', 'anim', 'bill', 'everyth', 'capac', 'girl', 'termin', 'matrix', 'bad', 'signal', 'profession', 'read', 'gather', 'look', 'partner', 'worksheet', 'return', 'well', 'fee', 'tax', 'fish', 'ppa', 'could', 'pictur', 'tonight', 'texa', 'vega', 'serv', 'xma', 'lsu', 'corrupt', 'best', 'choic', 'cold', 'smile', 'pic', 'calgari', 'loser', 'suggest', 'part', 'matt', 'avg', 'word', 'write', 'late', 'surpris', 'conf', 'storag', 'inform', 'ga', 'resum', 'request', 'chang', 'joke', 'present', 'public', 'subject', 'work', 'today', 'saturday', 'list', 'program', 'messag', 'power', 'year', 'day', 'statu', 'internship', 'order', 'releas', 'roundtabl', 'remov', 'jdf', 'assign', 'form', 'payment', 'enron', 'test', 'new', 'thank', 'call', 'parti', 'question', 'birthday', 'address', 'confer', 'mail', 'trip', 'dinner', 'may', 'hello', 'lunch', 'attach', 'hey', 'fwd', 'summer', 'weekend', 'report', 'march', 'instal'] 3374 3374\n",
      "0.8888888888888888 ['campaign', 'technolog', 'breakfast', 'frank', 'recept'] 9 8\n"
     ]
    }
   ],
   "source": [
    "# enron\n",
    "results = repeated_find_label_subgraph(test_graph, conjunction=True)\n",
    "print(\"------\")\n",
    "results = repeated_find_label_subgraph(test_graph, conjunction=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.0 ['brane', 'theori', 'covari', 'super'] 7 14\n",
      "1.3715083798882681 ['brane'] 1074 1473\n",
      "2.5 ['theori', 'casimir', 'light'] 6 15\n",
      "2.0 ['theori', 'mill', 'condens', 'nonlinear'] 5 10\n",
      "2.0 ['theori', 'super', 'mechan', 'three'] 5 10\n",
      "------\n",
      "1.7015834348355663 ['brane', 'string', 'supergrav', 'super', 'supersymmetri', 'supersymmetr', 'noncommut', 'yau', 'superstr', 'bp', 'self', 'brst', 'instanton', 'superconform', 'orbifold', 'orientifold', 'vacua', 'entropi', 'extrem', 'sitter', 'seiberg', 'superspac', 'chern', 'dualiti', 'toda', 'wall', 'plane', 'curv', 'casimir', 'four', 'dual', 'moduli', 'induc', 'note', 'cohomolog', 'mirror', 'susi', 'monopol', 'singular', 'tachyon'] 3284 5588\n",
      "0.9570011025358324 ['close', 'simon', 'calabi', 'bound', 'flow', 'condens', 'gordon', 'chain', 'exact', 'critic', 'correl', 'multi', 'limit', 'spectrum', 'lattic', 'hierarchi', 'amplitud', 'type', 'sine', 'surfac', 'perturb', 'five', 'class', 'renorm', 'problem', 'classic', 'approach', 'group', 'construct', 'reduct', 'three', 'current', 'descript', 'qcd', 'realiz', 'calogero', 'world', 'intersect', 'vacuum', 'equival', 'depend', 'infeld', 'commut', 'dynam', 'chiral', 'condit', 'constant', 'physic', 'one', 'energi', 'constraint', 'fraction', 'interact', 'new', 'transform', 'soliton', 'thermodynam', 'dirac', 'form', 'mode', 'method', 'open'] 1814 1736\n",
      "0.6666666666666666 ['properti'] 12 8\n",
      "0.6666666666666666 ['correct'] 9 6\n",
      "0.6666666666666666 ['particl', 'charg'] 57 38\n"
     ]
    }
   ],
   "source": [
    "# phys\n",
    "results = repeated_find_label_subgraph(test_graph, conjunction=True)\n",
    "print(\"------\")\n",
    "results = repeated_find_label_subgraph(test_graph, conjunction=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12.0 ['novel', 'rate', 'techniqu'] 25 300\n",
      "10.73913043478261 ['identif', 'combin', 'process'] 23 247\n",
      "6.2 ['forecast', 'experi', 'use'] 15 93\n",
      "6.0 ['heterogen', 'manag', 'stream', 'use'] 13 78\n",
      "2.0 ['heterogen', 'segment'] 5 10\n",
      "3.125 ['heterogen', 'manag', 'use', 'dynam'] 8 25\n",
      "2.5 ['heterogen', 'sourc', 'toward'] 6 15\n",
      "2.5 ['heterogen', 'construct', 'dimension', 'network'] 6 15\n",
      "2.25 ['heterogen', 'mobil', 'regular', 'data'] 8 18\n",
      "2.142857142857143 ['heterogen', 'rule', 'applic'] 7 15\n",
      "------\n",
      "2.213991769547325 ['novel'] 243 538\n",
      "1.9069767441860466 ['identif'] 258 492\n",
      "1.6532663316582914 ['forecast'] 199 329\n",
      "1.5826446280991735 ['heterogen'] 484 766\n",
      "1.496007515265383 ['mine', 'recommend', 'social', 'multi', 'detect', 'via', 'rank', 'text', 'factor', 'onlin', 'identifi', 'graph', 'stream', 'topic', 'studi', 'regular', 'distribut', 'extract', 'preserv', 'advertis', 'task', 'tempor', 'search', 'class', 'link', 'discoveri', 'discov', 'measur', 'awar', 'adversari', 'similar', 'converg', 'tensor', 'view', 'sourc', 'dataset', 'sentiment', 'understand', 'point', 'propag', 'chang', 'automat', 'semi', 'increment', 'word', 'latent', 'event', 'relat', 'attent', 'comparison', 'enhanc', 'exploit', 'match', 'domain', 'tree', 'problem', 'find', 'metric', 'subspac', 'unsupervis', 'risk', 'page', 'spectral', 'correl', 'frequent', 'itemset', 'video', 'outlier', 'decomposit'] 8516 12740\n",
      "1.0 ['manag'] 41 41\n",
      "0.96875 ['low'] 32 31\n",
      "0.9629629629629629 ['document'] 27 26\n",
      "0.8571428571428571 ['design'] 49 42\n",
      "0.8571428571428571 ['integr'] 70 60\n"
     ]
    }
   ],
   "source": [
    "# dblp\n",
    "results = repeated_find_label_subgraph(test_graph, conjunction=True, max_iterations=10)\n",
    "print(\"------\")\n",
    "results = repeated_find_label_subgraph(test_graph, conjunction=False, max_iterations=10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.5833333333333335 ['metooase'] 12 31\n",
      "1.875 ['streamer'] 16 30\n",
      "1.75 ['anubhavmohanty'] 16 28\n",
      "1.7142857142857142 ['victimservices'] 7 12\n",
      "1.8333333333333333 ['causette', 'lfi'] 6 11\n",
      "1.625 ['istandwithjohnny'] 8 13\n",
      "1.4285714285714286 ['rupertmurdock'] 7 10\n",
      "1.25 ['marilynmanson'] 8 10\n",
      "1.2142857142857142 ['balancetonporcfi'] 14 17\n",
      "1.3 ['melenchon'] 10 13\n",
      "------\n",
      "2.5833333333333335 ['metooase'] 12 31\n",
      "1.875 ['streamer'] 16 30\n",
      "1.75 ['anubhavmohanty'] 16 28\n",
      "1.7142857142857142 ['sudbury'] 7 12\n",
      "1.6363636363636365 ['causette'] 11 18\n",
      "1.625 ['istandwithjohnny'] 8 13\n",
      "1.4285714285714286 ['rupertmurdock'] 7 10\n",
      "1.3 ['melenchon'] 10 13\n",
      "1.25 ['marilynmanson'] 8 10\n",
      "1.1764705882352942 ['silenceiscomplicity'] 17 20\n"
     ]
    }
   ],
   "source": [
    "# twitter\n",
    "results = repeated_find_label_subgraph(test_graph, conjunction=True, max_iterations=10)\n",
    "print(\"------\")\n",
    "results = repeated_find_label_subgraph(test_graph, conjunction=False, max_iterations=10)"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "Communities in edge-labeled graphs.ipynb",
   "provenance": []
  },
  "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.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}