topic3 exercise.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Networks and their Structure Assignment\n",
    "\n",
    "## Network Science Topic 3\n",
    "\n",
    "Note that the networks in this exercise are all undirected.\n",
    "\n",
    "Here is a definition of a further kind of centrality known as *assignment centrality*.  It is similar to closeness centrality in that it depends on distances, but the definition is slightly different.  Again, let $d_{ij}$ be the distance from $i$ to $j$.  Then the assignment centrality of $j$ is\n",
    "\n",
    "$$ \\sum_{i \\neq j} \\frac{1}{d_{ij}} $$\n",
    "\n",
    "where $1/d_{ij}$ is 0 if there is no path from $i$ to $j$.\n",
    "\n",
    "1. [3 marks] Describe one advantage of using assignment centrality in preference to closeness centrality."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**The advantage is that assignment centrality produces numbers that are easier to work with, especially with larger networks, than closeness centrality. This is because of their respective definitions. Closeness centrality adds distances in the denominator with a constant numerator of 1, so the resulting numbers are small and close to zero, which is hard to interpret. In contrast, assignment centrality adds the fractions together so that the result is larger and corresponds to a node with a higher value having a greater effect on centrality - this is more meaningful.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "The Medici family were, through success in commerce and banking, wealthy and politically powerful in Florence beginning in the 13th century.  It has been suggested that their prominence can be explained by considering the network, displayed below, of Florentine families and their links by marriage.\n",
    "\n",
    "<img src=\"medici.jpg\" width=\"400\">\n",
    "\n",
    "2. [5 marks] Calculate the assignment centrality of each node in the network and comment on whether the results support the theory that the Medici's power was a result of their position in this network.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "from itertools import combinations\n",
    "from queue import PriorityQueue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def assignment_centrality(a, b, c, d, e):\n",
    "\n",
    "\treturn (1 * a) + (1/2 * b) + (1/3 * c) + (1/4 * d) + (1/5 * e)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Peruzzi: $(\\frac{1}{1} * 3) + (\\frac{1}{2} * 3) + (\\frac{1}{3} * 4) + (\\frac{1}{4} * 3) + (\\frac{1}{5} * 1) + 0 = 6.783$  \n",
    "Bischeri: $(\\frac{1}{1} * 3) + (\\frac{1}{2} * 5) + (\\frac{1}{3} * 3) + (\\frac{1}{4} * 2) + (\\frac{1}{5} * 1) + 0 = 7.200$  \n",
    "Castellani: $(\\frac{1}{1} * 3) + (\\frac{1}{2} * 3) + (\\frac{1}{3} * 5) + (\\frac{1}{4} * 3) + 0 = 6.916$  \n",
    "Lamberteschi: $(\\frac{1}{1} * 1) + (\\frac{1}{2} * 3) + (\\frac{1}{3} * 5) + (\\frac{1}{4} * 4) + (\\frac{1}{5} * 1) + 0 = 5.366$  \n",
    "Strozzi: $(\\frac{1}{1} * 4) + (\\frac{1}{2} * 4) + (\\frac{1}{3} * 4) + (\\frac{1}{4} * 2) + 0 = 7.833$  \n",
    "Guadagni: $(\\frac{1}{1} * 4) + (\\frac{1}{2} * 5) + (\\frac{1}{3} * 4) + (\\frac{1}{4} * 1) + 0 = 8.083$  \n",
    "Ridolfi: $(\\frac{1}{1} * 3) + (\\frac{1}{2} * 8) + (\\frac{1}{3} * 3) + 0 = 8.000$  \n",
    "Tornabuoni: $(\\frac{1}{1} * 3) + (\\frac{1}{2} * 7) + (\\frac{1}{3} * 4) + 0 = 7.833$  \n",
    "Barbadori: $(\\frac{1}{1} * 2) + (\\frac{1}{2} * 7) + (\\frac{1}{3} * 4) + (\\frac{1}{4} * 1) + 0 = 7.083$  \n",
    "Medici: $(\\frac{1}{1} * 6) + (\\frac{1}{2} * 5) + (\\frac{1}{3} * 3) + 0 = 9.500$  \n",
    "Albizzi: $(\\frac{1}{1} * 3) + (\\frac{1}{2} * 7) + (\\frac{1}{3} * 4) + 0 = 7.833$  \n",
    "Acciaiuoli: $(\\frac{1}{1} * 1) + (\\frac{1}{2} * 5) + (\\frac{1}{3} * 5) + (\\frac{1}{4} * 3) + 0 = 5.916$  \n",
    "Salviati: $(\\frac{1}{1} * 2) + (\\frac{1}{2} * 5) + (\\frac{1}{3} * 4) + (\\frac{1}{4} * 3) + (\\frac{1}{5} * 1) + 0 = 6.583$  \n",
    "Ginori: $(\\frac{1}{1} * 1) + (\\frac{1}{2} * 2) + (\\frac{1}{3} * 7) + (\\frac{1}{4} * 3) + (\\frac{1}{5} * 1) + 0 = 5.283$  \n",
    "Pazzi: $(\\frac{1}{1} * 1) + (\\frac{1}{2} * 1) + (\\frac{1}{3} * 5) + (\\frac{1}{4} * 4) + (\\frac{1}{5} * 3) + 0 = 4.766$  \n",
    "Pucci: 0\n",
    "\n",
    "**From the calculations it is clear that the Medici family had the highest assignment centrality of 9.5, whereas the other families ranged from around 6 to 8 on average, one even being zero (an outlier). The results therefore support the theory that the Medici family's power was due to their position in this network.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The next two questions require an implementation of Newman's agglomerative algorithm for community detection (see the hints at the end of these questions).  We met it in `topic3b.pdf`: it is described on Slide 4.  Recall that the algorithm finds many community decompositions.  It starts with the decomposition in which every node alone is a community, and then merges communities until the decomposition in which every node is in the same community is reached.  Thus the output to the algorithm contains a list of many decompositions. Also the algorithm calculates the change in the modularity $Q$ at each step so the relative value of $Q$ for each decomposition is part of the output.  For example, here is the output for the example on Slide 7.\n",
    "\n",
    "$$ \\begin{array}{ll}\n",
    "\\{1\\}, \\{2\\}, \\{3\\}, \\{4\\}, \\{5\\}, \\{6\\}, \\{7\\} & Q=0\\\\\n",
    "\\{1, 2\\}, \\{3\\}, \\{4\\}, \\{5\\}, \\{6\\}, \\{7\\} & Q=0.086 \\\\\n",
    "\\{1, 2, 3\\}, \\{4\\}, \\{5\\}, \\{6\\}, \\{7\\} & Q=0.210 \\\\\n",
    "\\{1, 2, 3\\}, \\{4\\}, \\{5\\}, \\{6, 7\\} & Q=0.296 \\\\\n",
    "\\{1, 2, 3\\}, \\{4\\}, \\{5, 6, 7\\} & Q=0.420 \\\\\n",
    "\\{1, 2, 3, 4\\}, \\{5, 6, 7\\} & Q=0.432\\\\\n",
    "\\{1, 2, 3, 4, 5, 6, 7\\} & Q=0.160\n",
    "\\end{array}\n",
    "$$\n",
    "\n",
    "(Note that this implies that $\\{1, 2, 3, 4\\}, \\{5, 6, 7\\}$ is the best community decomposition as it has the greatest modularity.  Note also that these are relative values as the modularity of the initial decomposition is not zero, but this is enough information for us to determine which decomposition is best.)\n",
    "\n",
    "3. [8 marks] Construct the network defined in `zachary.txt` ignoring edge weights.  Run Newman's agglomerative algorithm on this network and write down the output in the same format used in the example above.  The file relates to the example mentioned in the lecture of a karate club that split in two (see the description in the file).  How do your results compare with what actually happened?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Loaded graph with 34 nodes\n"
     ]
    }
   ],
   "source": [
    "# load the zachary graph ignoring edge weights\n",
    "graph = open(\"zachary.txt\")\n",
    "\n",
    "karate_graph = {}\n",
    "nodes = 0\n",
    "\n",
    "for line in graph:\n",
    "    \n",
    "    data = line.split(' ')\n",
    "    \n",
    "    # skip the text at the beginning\n",
    "    if len(data) == 3:\n",
    "    \n",
    "        node = int(data[0])\n",
    "        neighbour = int(data[1])\n",
    "\n",
    "        if node in karate_graph:\n",
    "            karate_graph[node].add(neighbour)\n",
    "        else:\n",
    "            karate_graph[node] = set([neighbour])\n",
    "            nodes += 1\n",
    "        \n",
    "        if neighbour in karate_graph:\n",
    "            karate_graph[neighbour].add(node)\n",
    "        else:\n",
    "            karate_graph[neighbour] = set([node])\n",
    "            nodes += 1\n",
    "        \n",
    "print(\"Loaded graph with\", nodes, \"nodes\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_graph = {1: [2,3],\n",
    " 2: [1,3],\n",
    " 3: [1,2,4,5],\n",
    " 4: [3,5],\n",
    " 5: [3,4,6,7],\n",
    " 6: [5,7],\n",
    " 7: [5,6]}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# calculates change in modularity if this pair of communities is merged\n",
    "def deltaQ(graph, communities, pair, edges, total_edges, total_endpoints):\n",
    "    \n",
    "    a1 = communities[pair[0]][1]\n",
    "    a2 = communities[pair[1]][1]\n",
    "        \n",
    "    modularity_change = (edges / total_edges) - (2 * (a1 / total_endpoints) * (a2 / total_endpoints))\n",
    "    return modularity_change"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# gets the number of nodes in a pair of communities\n",
    "def get_nodes(community1, community2, communities, num_nodes):\n",
    "        \n",
    "    nodes = communities[community1][0] + communities[community2][0]\n",
    "    return nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# gets the number of edges between two communities\n",
    "def get_num_edges(graph, community1, community2, nodes2, communities):\n",
    "    \n",
    "    edges = 0\n",
    "    nodes1 = communities[community1][0]\n",
    "    \n",
    "    for i in nodes1:\n",
    "        for j in nodes2:\n",
    "            if i in graph[j]:\n",
    "                edges += 1\n",
    "    \n",
    "    return edges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# runs Newman's agglomerative algorithm on a given graph\n",
    "def Newman_algorithm(graph, graph_name):\n",
    "    \n",
    "    # keys are current communities, values are nodes and number of endpoints\n",
    "    communities = {key:([key], len(graph[key])) for key in graph}\n",
    "    num_nodes = len(graph)\n",
    "    \n",
    "    # key for the next merged community\n",
    "    if graph_name == 'karate' or graph_name == 'test':\n",
    "        new_key = num_nodes + 1  \n",
    "    else:\n",
    "        new_key = 'A'\n",
    "    \n",
    "    # get total numbers of edges and endpoints for calculating modularity change\n",
    "    total_endpoints = sum([len(graph[key]) for key in graph])\n",
    "    total_edges = total_endpoints // 2\n",
    "    \n",
    "    # keys are pairs of current communities, values are number of edges between the pair\n",
    "    pairs = {}\n",
    "    nodes = [node for node in graph]\n",
    "    queue = PriorityQueue()  # initialise priority queue\n",
    "    \n",
    "    # initialise pairs dictionary\n",
    "    for combination in list(combinations(nodes, 2)):\n",
    "        \n",
    "        if combination[1] in graph[combination[0]]:\n",
    "            pairs[combination] = 1\n",
    "        else:\n",
    "            pairs[combination] = 0\n",
    "    \n",
    "    # initialise values\n",
    "    prev_Q = 0\n",
    "    total_Q = 0\n",
    "    written = False\n",
    "    new_pairs = pairs\n",
    "    \n",
    "    if graph_name == 'karate' or graph_name == 'test':\n",
    "        print([set(i[0]) for i in list(communities.values())], 'Q = ' + str(total_Q))\n",
    "\n",
    "    while len(communities) > 1:\n",
    "        \n",
    "        # add all community pairs to priority queue\n",
    "        for pair, edges in new_pairs.items():\n",
    "\n",
    "            Q = deltaQ(graph, communities, pair, edges, total_edges, total_endpoints)\n",
    "            queue.put((Q * -1, pair))\n",
    "\n",
    "        # get community pair with greatest increase in modularity and the nodes in the merged community\n",
    "        while True:\n",
    "            Q, pair = queue.get()\n",
    "            if pair in pairs:\n",
    "                break\n",
    "        \n",
    "        # update total Q and get list of nodes in these communities\n",
    "        total_Q += Q * -1\n",
    "        \n",
    "        # write the best community decomposition to file\n",
    "        if graph_name == 'yeast' and total_Q < prev_Q and not written:\n",
    "            \n",
    "            best_communities = [set(i[0]) for i in list(communities.values())]\n",
    "            file = open(\"yeast_communities.txt\", \"w\")\n",
    "\n",
    "            # write nodes of each community on separate lines\n",
    "            for community in best_communities:\n",
    "                \n",
    "                file.write(' '.join(node for node in community))\n",
    "                file.write('\\n')\n",
    "\n",
    "            written = True\n",
    "        \n",
    "        # get nodes in these communities and the number of endpoints\n",
    "        nodes = get_nodes(pair[0], pair[1], communities, num_nodes)\n",
    "        endpoints = 0\n",
    "        for node in nodes:\n",
    "            endpoints += len(graph[node])\n",
    "\n",
    "        # update communities\n",
    "        del communities[pair[0]]\n",
    "        del communities[pair[1]]\n",
    "        \n",
    "        # update pairs by removing entries containing nodes that have been merged \n",
    "        pairs_copy = pairs.copy()\n",
    "        for p in pairs_copy:\n",
    "            if pair[0] in p or pair[1] in p:\n",
    "                del pairs[p]\n",
    "        \n",
    "        new_pairs = {}\n",
    "        \n",
    "        # add new pairs of the merged community with all other communities\n",
    "        for i in communities.keys():\n",
    "            \n",
    "            edges = get_num_edges(graph, i, new_key, nodes, communities)\n",
    "            pairs[i, new_key] = edges\n",
    "            new_pairs[i, new_key] = edges\n",
    "\n",
    "        communities[new_key] = (nodes, endpoints)\n",
    "        \n",
    "        if graph_name == 'karate' or graph_name == 'test':\n",
    "            new_key += 1\n",
    "            print([set(i[0]) for i in list(communities.values())], 'Q = {:.3f} '.format(round(total_Q, 3)))\n",
    "        else:\n",
    "            new_key += 'A'\n",
    "            print('Q = ' + str(total_Q))\n",
    "        \n",
    "        prev_Q = total_Q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[{1}, {2}, {3}, {4}, {5}, {6}, {7}] Q = 0\n",
      "[{3}, {4}, {5}, {6}, {7}, {1, 2}] Q = 0.086 \n",
      "[{4}, {5}, {6}, {7}, {1, 2, 3}] Q = 0.210 \n",
      "[{4}, {5}, {1, 2, 3}, {6, 7}] Q = 0.296 \n",
      "[{4}, {1, 2, 3}, {5, 6, 7}] Q = 0.420 \n",
      "[{5, 6, 7}, {1, 2, 3, 4}] Q = 0.432 \n",
      "[{1, 2, 3, 4, 5, 6, 7}] Q = 0.160 \n"
     ]
    }
   ],
   "source": [
    "Newman_algorithm(test_graph, 'test')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[{1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}, {11}, {12}, {13}, {14}, {18}, {20}, {22}, {32}, {31}, {10}, {28}, {29}, {33}, {17}, {34}, {15}, {16}, {19}, {21}, {23}, {24}, {26}, {30}, {25}, {27}] Q = 0\n",
      "[{1}, {2}, {3}, {4}, {5}, {7}, {8}, {9}, {11}, {12}, {13}, {14}, {18}, {20}, {22}, {32}, {31}, {10}, {28}, {29}, {33}, {34}, {15}, {16}, {19}, {21}, {23}, {24}, {26}, {30}, {25}, {27}, {17, 6}] Q = 0.012 \n",
      "[{1}, {2}, {3}, {4}, {5}, {8}, {9}, {11}, {12}, {13}, {14}, {18}, {20}, {22}, {32}, {31}, {10}, {28}, {29}, {33}, {34}, {15}, {16}, {19}, {21}, {23}, {24}, {26}, {30}, {25}, {27}, {17, 6, 7}] Q = 0.036 \n",
      "[{2}, {3}, {4}, {5}, {8}, {9}, {11}, {12}, {13}, {14}, {18}, {20}, {22}, {32}, {31}, {10}, {28}, {29}, {33}, {34}, {15}, {16}, {19}, {21}, {23}, {24}, {26}, {30}, {25}, {27}, {1, 17, 6, 7}] Q = 0.048 \n",
      "[{2}, {3}, {4}, {8}, {9}, {11}, {12}, {13}, {14}, {18}, {20}, {22}, {32}, {31}, {10}, {28}, {29}, {33}, {34}, {15}, {16}, {19}, {21}, {23}, {24}, {26}, {30}, {25}, {27}, {1, 5, 6, 7, 17}] Q = 0.068 \n",
      "[{2}, {3}, {4}, {8}, {9}, {12}, {13}, {14}, {18}, {20}, {22}, {32}, {31}, {10}, {28}, {29}, {33}, {34}, {15}, {16}, {19}, {21}, {23}, {24}, {26}, {30}, {25}, {27}, {1, 5, 6, 7, 11, 17}] Q = 0.099 \n",
      "[{2}, {3}, {4}, {8}, {9}, {12}, {13}, {14}, {18}, {20}, {22}, {32}, {31}, {10}, {28}, {29}, {33}, {34}, {15}, {16}, {19}, {21}, {23}, {24}, {26}, {25}, {1, 5, 6, 7, 11, 17}, {27, 30}] Q = 0.111 \n",
      "[{2}, {3}, {4}, {8}, {9}, {12}, {13}, {14}, {18}, {20}, {22}, {32}, {31}, {10}, {28}, {29}, {33}, {15}, {16}, {19}, {21}, {23}, {24}, {26}, {25}, {1, 5, 6, 7, 11, 17}, {34, 27, 30}] Q = 0.128 \n",
      "[{2}, {3}, {4}, {8}, {9}, {12}, {13}, {14}, {18}, {20}, {22}, {32}, {31}, {10}, {28}, {29}, {33}, {15}, {16}, {19}, {21}, {23}, {26}, {25}, {1, 5, 6, 7, 11, 17}, {24, 34, 27, 30}] Q = 0.144 \n",
      "[{2}, {3}, {4}, {8}, {9}, {12}, {13}, {14}, {18}, {20}, {22}, {32}, {31}, {10}, {29}, {33}, {15}, {16}, {19}, {21}, {23}, {26}, {25}, {1, 5, 6, 7, 11, 17}, {34, 24, 27, 28, 30}] Q = 0.161 \n",
      "[{2}, {3}, {4}, {8}, {9}, {12}, {13}, {14}, {18}, {20}, {22}, {32}, {31}, {10}, {29}, {33}, {15}, {16}, {19}, {21}, {23}, {1, 5, 6, 7, 11, 17}, {34, 24, 27, 28, 30}, {25, 26}] Q = 0.173 \n",
      "[{2}, {3}, {4}, {8}, {9}, {12}, {13}, {14}, {18}, {20}, {22}, {31}, {10}, {29}, {33}, {15}, {16}, {19}, {21}, {23}, {1, 5, 6, 7, 11, 17}, {34, 24, 27, 28, 30}, {32, 25, 26}] Q = 0.196 \n",
      "[{2}, {3}, {8}, {9}, {12}, {14}, {18}, {20}, {22}, {31}, {10}, {29}, {33}, {15}, {16}, {19}, {21}, {23}, {1, 5, 6, 7, 11, 17}, {34, 24, 27, 28, 30}, {32, 25, 26}, {4, 13}] Q = 0.208 \n",
      "[{3}, {8}, {9}, {12}, {14}, {20}, {22}, {31}, {10}, {29}, {33}, {15}, {16}, {19}, {21}, {23}, {1, 5, 6, 7, 11, 17}, {34, 24, 27, 28, 30}, {32, 25, 26}, {4, 13}, {2, 18}] Q = 0.219 \n",
      "[{8}, {9}, {12}, {14}, {20}, {22}, {31}, {29}, {33}, {15}, {16}, {19}, {21}, {23}, {1, 5, 6, 7, 11, 17}, {34, 24, 27, 28, 30}, {32, 25, 26}, {4, 13}, {2, 18}, {10, 3}] Q = 0.230 \n",
      "[{8}, {12}, {14}, {20}, {22}, {29}, {33}, {15}, {16}, {19}, {21}, {23}, {1, 5, 6, 7, 11, 17}, {34, 24, 27, 28, 30}, {32, 25, 26}, {4, 13}, {2, 18}, {10, 3}, {9, 31}] Q = 0.241 \n",
      "[{8}, {12}, {14}, {20}, {22}, {29}, {15}, {16}, {19}, {21}, {23}, {1, 5, 6, 7, 11, 17}, {34, 24, 27, 28, 30}, {32, 25, 26}, {4, 13}, {2, 18}, {10, 3}, {33, 9, 31}] Q = 0.258 \n",
      "[{8}, {12}, {14}, {20}, {29}, {15}, {16}, {19}, {21}, {23}, {1, 5, 6, 7, 11, 17}, {34, 24, 27, 28, 30}, {32, 25, 26}, {4, 13}, {10, 3}, {33, 9, 31}, {2, 18, 22}] Q = 0.269 \n",
      "[{12}, {14}, {20}, {29}, {15}, {16}, {19}, {21}, {23}, {1, 5, 6, 7, 11, 17}, {34, 24, 27, 28, 30}, {32, 25, 26}, {10, 3}, {33, 9, 31}, {2, 18, 22}, {8, 4, 13}] Q = 0.279 \n",
      "[{12}, {14}, {20}, {29}, {15}, {16}, {19}, {21}, {23}, {1, 5, 6, 7, 11, 17}, {34, 24, 27, 28, 30}, {32, 25, 26}, {33, 9, 31}, {2, 18, 22}, {3, 4, 8, 10, 13}] Q = 0.293 \n",
      "[{12}, {20}, {29}, {15}, {16}, {19}, {21}, {23}, {1, 5, 6, 7, 11, 17}, {34, 24, 27, 28, 30}, {32, 25, 26}, {33, 9, 31}, {2, 18, 22}, {3, 4, 8, 10, 13, 14}] Q = 0.309 \n",
      "[{12}, {20}, {29}, {15}, {16}, {19}, {21}, {23}, {1, 5, 6, 7, 11, 17}, {34, 24, 27, 28, 30}, {32, 25, 26}, {33, 9, 31}, {2, 3, 4, 8, 10, 13, 14, 18, 22}] Q = 0.329 \n",
      "[{20}, {29}, {15}, {16}, {19}, {21}, {23}, {34, 24, 27, 28, 30}, {32, 25, 26}, {33, 9, 31}, {2, 3, 4, 8, 10, 13, 14, 18, 22}, {1, 5, 6, 7, 11, 12, 17}] Q = 0.339 \n",
      "[{20}, {15}, {16}, {19}, {21}, {23}, {34, 24, 27, 28, 30}, {33, 9, 31}, {2, 3, 4, 8, 10, 13, 14, 18, 22}, {1, 5, 6, 7, 11, 12, 17}, {32, 25, 26, 29}] Q = 0.349 \n",
      "[{20}, {15}, {16}, {19}, {21}, {23}, {33, 9, 31}, {2, 3, 4, 8, 10, 13, 14, 18, 22}, {1, 5, 6, 7, 11, 12, 17}, {32, 34, 24, 25, 26, 27, 28, 29, 30}] Q = 0.361 \n",
      "[{20}, {16}, {19}, {21}, {23}, {2, 3, 4, 8, 10, 13, 14, 18, 22}, {1, 5, 6, 7, 11, 12, 17}, {32, 34, 24, 25, 26, 27, 28, 29, 30}, {33, 31, 9, 15}] Q = 0.370 \n",
      "[{20}, {19}, {21}, {23}, {2, 3, 4, 8, 10, 13, 14, 18, 22}, {1, 5, 6, 7, 11, 12, 17}, {32, 34, 24, 25, 26, 27, 28, 29, 30}, {33, 9, 15, 16, 31}] Q = 0.379 \n",
      "[{20}, {21}, {23}, {2, 3, 4, 8, 10, 13, 14, 18, 22}, {1, 5, 6, 7, 11, 12, 17}, {32, 34, 24, 25, 26, 27, 28, 29, 30}, {33, 9, 15, 16, 19, 31}] Q = 0.388 \n",
      "[{20}, {21}, {23}, {2, 3, 4, 8, 10, 13, 14, 18, 22}, {1, 5, 6, 7, 11, 12, 17}, {32, 33, 34, 9, 15, 16, 19, 24, 25, 26, 27, 28, 29, 30, 31}] Q = 0.399 \n",
      "[{20}, {23}, {2, 3, 4, 8, 10, 13, 14, 18, 22}, {1, 5, 6, 7, 11, 12, 17}, {32, 33, 34, 9, 15, 16, 19, 21, 24, 25, 26, 27, 28, 29, 30, 31}] Q = 0.413 \n",
      "[{20}, {2, 3, 4, 8, 10, 13, 14, 18, 22}, {1, 5, 6, 7, 11, 12, 17}, {32, 33, 34, 9, 15, 16, 19, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31}] Q = 0.426 \n",
      "[{2, 3, 4, 8, 10, 13, 14, 18, 22}, {32, 33, 34, 9, 15, 16, 19, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31}, {1, 5, 6, 7, 11, 12, 17, 20}] Q = 0.430 \n",
      "[{32, 33, 34, 9, 15, 16, 19, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31}, {1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 17, 18, 20, 22}] Q = 0.422 \n",
      "[{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34}] Q = 0.050 \n"
     ]
    }
   ],
   "source": [
    "Newman_algorithm(karate_graph, 'karate')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**The results show that with more communities merging, the modularity increases up to the third last step in the algorithm. The modularity is 0.430 at this stage, which is its maximum, and there are 3 communities. If the algorithm goes further than this and merges 2 of the 3 communities together, the modularity decreases for the first time slightly to 0.422. In the final step when the remaining two communities are merged, the modularity decreases significantly to 0.050. This shows that these two communities are very distinct from each other, with very few edges between them to create such a drastic drop in the modularity. The results therefore clearly show two different groups, which is what happened as the karate club split into two separate clubs.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Living cells can be considered as complex webs of macromolecular interactions known as *interactome networks*.  Finding communities in these networks can aid understanding of how the cells function.\n",
    "\n",
    "4. [9 marks] Construct the network defined in `CCSB-Y2H.txt`.  The first two items on each line are a pair of nodes joined by an edge (the rest of the line can be ignored).  The network is of interactions amongst proteins in yeast. Run Newman's agglomerative algorithm on this network.  The best community decomposition found should be written to a text file with the nodes of each community on a separate line.  Are there many other decompositions of a similar quality?  (See the link in the text file for further information on this dataset.)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Loaded graph with 1233 nodes\n"
     ]
    }
   ],
   "source": [
    "# load the yeast graph ignoring edge weights\n",
    "graph = open(\"CCSB-Y2H.txt\")\n",
    "\n",
    "yeast_graph = {}\n",
    "nodes = 0\n",
    "\n",
    "for line in graph:\n",
    "    \n",
    "    data = line.split('\\t')\n",
    "    \n",
    "    # skip the text at the beginning\n",
    "    if len(data) == 3:\n",
    "    \n",
    "        node = data[0]\n",
    "        neighbour = data[1]\n",
    "        \n",
    "        if node != neighbour:  # remove self loops\n",
    "\n",
    "            if node in yeast_graph:\n",
    "                yeast_graph[node].add(neighbour)\n",
    "            else:\n",
    "                yeast_graph[node] = set([neighbour])\n",
    "                nodes += 1\n",
    "\n",
    "            if neighbour in yeast_graph:\n",
    "                yeast_graph[neighbour].add(node)\n",
    "            else:\n",
    "                yeast_graph[neighbour] = set([node])\n",
    "                nodes += 1\n",
    "        \n",
    "print(\"Loaded graph with\", nodes, \"nodes\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Q = 0.0006091988468855475\n",
      "Q = 0.001218397693771095\n",
      "Q = 0.0018275965406566426\n",
      "Q = 0.00243679538754219\n",
      "Q = 0.0030459942344277374\n",
      "Q = 0.003655193081313285\n",
      "Q = 0.004264391928198832\n",
      "Q = 0.00487359077508438\n",
      "Q = 0.005482789621969928\n",
      "Q = 0.006091988468855476\n",
      "Q = 0.0067011873157410235\n",
      "Q = 0.007310386162626571\n",
      "Q = 0.007919585009512118\n",
      "Q = 0.008528783856397666\n",
      "Q = 0.009137982703283214\n",
      "Q = 0.009747181550168762\n",
      "Q = 0.01035638039705431\n",
      "Q = 0.010965579243939858\n",
      "Q = 0.011574778090825405\n",
      "Q = 0.012183976937710953\n",
      "Q = 0.012793175784596501\n",
      "Q = 0.013402374631482049\n",
      "Q = 0.014011573478367597\n",
      "Q = 0.014620772325253144\n",
      "Q = 0.015229971172138692\n",
      "Q = 0.01583917001902424\n",
      "Q = 0.016448368865909786\n",
      "Q = 0.017057567712795332\n",
      "Q = 0.01766676655968088\n",
      "Q = 0.018275965406566425\n",
      "Q = 0.01888516425345197\n",
      "Q = 0.019494363100337517\n",
      "Q = 0.020103561947223063\n",
      "Q = 0.02071276079410861\n",
      "Q = 0.021321959640994155\n",
      "Q = 0.0219311584878797\n",
      "Q = 0.022540357334765247\n",
      "Q = 0.023149556181650793\n",
      "Q = 0.02375875502853634\n",
      "Q = 0.024367953875421886\n",
      "Q = 0.02497715272230743\n",
      "Q = 0.025586351569192978\n",
      "Q = 0.026195550416078524\n",
      "Q = 0.02680474926296407\n",
      "Q = 0.027413948109849616\n",
      "Q = 0.028023146956735162\n",
      "Q = 0.028632345803620708\n",
      "Q = 0.029241544650506254\n",
      "Q = 0.0298507434973918\n",
      "Q = 0.030459942344277346\n",
      "Q = 0.031069141191162893\n",
      "Q = 0.03167834003804844\n",
      "Q = 0.032287538884933985\n",
      "Q = 0.03289673773181953\n",
      "Q = 0.03350593657870508\n",
      "Q = 0.03411513542559062\n",
      "Q = 0.03472433427247617\n",
      "Q = 0.035333533119361715\n",
      "Q = 0.03594273196624726\n",
      "Q = 0.03655193081313281\n",
      "Q = 0.037161129660018354\n",
      "Q = 0.0377703285069039\n",
      "Q = 0.038379527353789446\n",
      "Q = 0.03898872620067499\n",
      "Q = 0.03959792504756054\n",
      "Q = 0.040207123894446084\n",
      "Q = 0.04081632274133163\n",
      "Q = 0.041425521588217176\n",
      "Q = 0.04203472043510272\n",
      "Q = 0.04264391928198827\n",
      "Q = 0.043253118128873815\n",
      "Q = 0.04386231697575936\n",
      "Q = 0.04447151582264491\n",
      "Q = 0.04508071466953045\n",
      "Q = 0.045689913516416\n",
      "Q = 0.046299112363301545\n",
      "Q = 0.04690831121018709\n",
      "Q = 0.04751751005707264\n",
      "Q = 0.04812670890395818\n",
      "Q = 0.04873590775084373\n",
      "Q = 0.049345106597729275\n",
      "Q = 0.04995430544461482\n",
      "Q = 0.05056350429150037\n",
      "Q = 0.051172703138385914\n",
      "Q = 0.05178190198527146\n",
      "Q = 0.052391100832157006\n",
      "Q = 0.05300029967904255\n",
      "Q = 0.05360931285118049\n",
      "Q = 0.054218326023318435\n",
      "Q = 0.054827339195456376\n",
      "Q = 0.05543635236759432\n",
      "Q = 0.05604536553973226\n",
      "Q = 0.0566543787118702\n",
      "Q = 0.05726339188400814\n",
      "Q = 0.05787240505614608\n",
      "Q = 0.058481418228284024\n",
      "Q = 0.059090431400421965\n",
      "Q = 0.05969944457255991\n",
      "Q = 0.06030845774469785\n",
      "Q = 0.06091747091683579\n",
      "Q = 0.06152648408897373\n",
      "Q = 0.06213549726111167\n",
      "Q = 0.06274451043324962\n",
      "Q = 0.06335352360538757\n",
      "Q = 0.06396253677752552\n",
      "Q = 0.06457154994966346\n",
      "Q = 0.06518056312180141\n",
      "Q = 0.06578957629393936\n",
      "Q = 0.06639858946607731\n",
      "Q = 0.06700760263821526\n",
      "Q = 0.0676166158103532\n",
      "Q = 0.06822562898249115\n",
      "Q = 0.0688346421546291\n",
      "Q = 0.06944365532676705\n",
      "Q = 0.070052668498905\n",
      "Q = 0.07066168167104295\n",
      "Q = 0.0712706948431809\n",
      "Q = 0.07187970801531884\n",
      "Q = 0.07248872118745679\n",
      "Q = 0.07309773435959474\n",
      "Q = 0.07370674753173269\n",
      "Q = 0.07431576070387064\n",
      "Q = 0.07492477387600859\n",
      "Q = 0.07553378704814653\n",
      "Q = 0.07614280022028448\n",
      "Q = 0.07675181339242243\n",
      "Q = 0.07736082656456038\n",
      "Q = 0.07796983973669833\n",
      "Q = 0.07857885290883627\n",
      "Q = 0.07918786608097422\n",
      "Q = 0.07979687925311217\n",
      "Q = 0.08040589242525012\n",
      "Q = 0.08101490559738807\n",
      "Q = 0.08162391876952602\n",
      "Q = 0.08223293194166396\n",
      "Q = 0.08284194511380191\n",
      "Q = 0.08345095828593986\n",
      "Q = 0.08405997145807781\n",
      "Q = 0.08466898463021576\n",
      "Q = 0.0852779978023537\n",
      "Q = 0.08588701097449165\n",
      "Q = 0.0864960241466296\n",
      "Q = 0.08710503731876755\n",
      "Q = 0.0877140504909055\n",
      "Q = 0.08832306366304345\n",
      "Q = 0.0889320768351814\n",
      "Q = 0.08954109000731934\n",
      "Q = 0.09015010317945729\n",
      "Q = 0.09075911635159524\n",
      "Q = 0.09136812952373319\n",
      "Q = 0.09197714269587114\n",
      "Q = 0.09258615586800908\n",
      "Q = 0.09319516904014703\n",
      "Q = 0.09380418221228498\n",
      "Q = 0.09441319538442293\n",
      "Q = 0.09502220855656088\n",
      "Q = 0.09563122172869883\n",
      "Q = 0.09624023490083677\n",
      "Q = 0.09684924807297472\n",
      "Q = 0.09745826124511267\n",
      "Q = 0.09806727441725062\n",
      "Q = 0.09867628758938857\n",
      "Q = 0.09928530076152652\n",
      "Q = 0.09989431393366446\n",
      "Q = 0.10050332710580241\n",
      "Q = 0.10111215460319276\n",
      "Q = 0.1017209821005831\n",
      "Q = 0.10232980959797344\n",
      "Q = 0.10293863709536379\n",
      "Q = 0.10354746459275413\n",
      "Q = 0.10415629209014447\n",
      "Q = 0.10476511958753482\n",
      "Q = 0.10537394708492516\n",
      "Q = 0.1059827745823155\n",
      "Q = 0.10659160207970585\n",
      "Q = 0.10720042957709619\n",
      "Q = 0.10780925707448653\n",
      "Q = 0.10841808457187688\n",
      "Q = 0.10902691206926722\n",
      "Q = 0.10963573956665756\n",
      "Q = 0.11024456706404791\n",
      "Q = 0.11085339456143825\n",
      "Q = 0.1114622220588286\n",
      "Q = 0.11207104955621894\n",
      "Q = 0.11267987705360928\n",
      "Q = 0.11328870455099962\n",
      "Q = 0.11389753204838997\n",
      "Q = 0.11450635954578031\n",
      "Q = 0.11511518704317066\n",
      "Q = 0.115724014540561\n",
      "Q = 0.11633284203795134\n",
      "Q = 0.11694166953534169\n",
      "Q = 0.11755049703273203\n",
      "Q = 0.11815932453012237\n",
      "Q = 0.11876815202751272\n",
      "Q = 0.11937697952490306\n",
      "Q = 0.1199858070222934\n",
      "Q = 0.12059463451968375\n",
      "Q = 0.12120346201707409\n",
      "Q = 0.12181228951446443\n",
      "Q = 0.12242111701185478\n",
      "Q = 0.12302994450924512\n",
      "Q = 0.12363877200663546\n",
      "Q = 0.12424759950402581\n",
      "Q = 0.12485642700141615\n",
      "Q = 0.1254652544988065\n",
      "Q = 0.12607408199619682\n",
      "Q = 0.12668290949358715\n",
      "Q = 0.12729173699097748\n",
      "Q = 0.1279005644883678\n",
      "Q = 0.12850939198575814\n",
      "Q = 0.12911821948314847\n",
      "Q = 0.1297270469805388\n",
      "Q = 0.13033587447792913\n",
      "Q = 0.13094470197531946\n",
      "Q = 0.1315535294727098\n",
      "Q = 0.13216235697010012\n",
      "Q = 0.13277118446749045\n",
      "Q = 0.13338001196488078\n",
      "Q = 0.1339888394622711\n",
      "Q = 0.13459766695966144\n",
      "Q = 0.13520649445705177\n",
      "Q = 0.1358153219544421\n",
      "Q = 0.13642414945183243\n",
      "Q = 0.13703297694922276\n",
      "Q = 0.1376418044466131\n",
      "Q = 0.13825063194400342\n",
      "Q = 0.13885945944139375\n",
      "Q = 0.13946828693878408\n",
      "Q = 0.1400771144361744\n",
      "Q = 0.14068575625881713\n",
      "Q = 0.14129439808145985\n",
      "Q = 0.14190303990410258\n",
      "Q = 0.1425116817267453\n",
      "Q = 0.14312032354938803\n",
      "Q = 0.14372896537203075\n",
      "Q = 0.14433760719467348\n",
      "Q = 0.1449462490173162\n",
      "Q = 0.14555489083995893\n",
      "Q = 0.14616353266260165\n",
      "Q = 0.14677217448524438\n",
      "Q = 0.1473808163078871\n",
      "Q = 0.14798945813052983\n",
      "Q = 0.14859809995317255\n",
      "Q = 0.14920674177581528\n",
      "Q = 0.149815383598458\n",
      "Q = 0.15042402542110073\n",
      "Q = 0.15103266724374345\n",
      "Q = 0.15164130906638618\n",
      "Q = 0.1522499508890289\n",
      "Q = 0.15285859271167163\n",
      "Q = 0.15346723453431435\n",
      "Q = 0.15407587635695708\n",
      "Q = 0.15528944650729049\n",
      "Q = 0.1558980883299332\n",
      "Q = 0.15650673015257593\n",
      "Q = 0.15711537197521866\n",
      "Q = 0.15772401379786138\n",
      "Q = 0.1583326556205041\n",
      "Q = 0.15894129744314683\n",
      "Q = 0.16015486759348024\n",
      "Q = 0.16076350941612297\n",
      "Q = 0.1613721512387657\n",
      "Q = 0.16198079306140842\n",
      "Q = 0.16258943488405114\n",
      "Q = 0.16319807670669387\n",
      "Q = 0.1638067185293366\n",
      "Q = 0.16441536035197932\n",
      "Q = 0.16502400217462204\n",
      "Q = 0.16563264399726477\n",
      "Q = 0.1662412858199075\n",
      "Q = 0.16684992764255022\n",
      "Q = 0.16745856946519294\n",
      "Q = 0.16806721128783567\n",
      "Q = 0.1686758531104784\n",
      "Q = 0.16928449493312112\n",
      "Q = 0.16989313675576384\n",
      "Q = 0.17050177857840657\n",
      "Q = 0.1711104204010493\n",
      "Q = 0.17171906222369202\n",
      "Q = 0.17232770404633474\n",
      "Q = 0.17354350229363938\n",
      "Q = 0.1741521441162821\n",
      "Q = 0.17536942776156758\n",
      "Q = 0.1759780695842103\n",
      "Q = 0.17658671140685303\n",
      "Q = 0.17719535322949576\n",
      "Q = 0.17780399505213848\n",
      "Q = 0.1784126368747812\n",
      "Q = 0.17902127869742393\n",
      "Q = 0.17962992052006665\n",
      "Q = 0.18023856234270938\n",
      "Q = 0.1814395066102058\n",
      "Q = 0.18204814843284853\n",
      "Q = 0.18265679025549125\n",
      "Q = 0.18326543207813398\n",
      "Q = 0.1838740739007767\n",
      "Q = 0.18508838675010053\n",
      "Q = 0.18569702857274326\n",
      "Q = 0.18630567039538598\n",
      "Q = 0.1869143122180287\n",
      "Q = 0.18752276836592385\n",
      "Q = 0.188131224513819\n",
      "Q = 0.18873968066171415\n",
      "Q = 0.1893481368096093\n",
      "Q = 0.18995659295750444\n",
      "Q = 0.1905650491053996\n",
      "Q = 0.19117350525329474\n",
      "Q = 0.1917819614011899\n",
      "Q = 0.19239041754908504\n",
      "Q = 0.19299887369698018\n",
      "Q = 0.19360732984487533\n",
      "Q = 0.19421578599277048\n",
      "Q = 0.19482424214066563\n",
      "Q = 0.19543269828856077\n",
      "Q = 0.19604115443645592\n",
      "Q = 0.19664961058435107\n",
      "Q = 0.19725806673224622\n",
      "Q = 0.19786652288014137\n",
      "Q = 0.1984749790280365\n",
      "Q = 0.19908343517593166\n",
      "Q = 0.1996918913238268\n",
      "Q = 0.20030034747172196\n",
      "Q = 0.2009088036196171\n",
      "Q = 0.20151725976751225\n",
      "Q = 0.2021257159154074\n",
      "Q = 0.20273417206330255\n",
      "Q = 0.2033426282111977\n",
      "Q = 0.20395108435909284\n",
      "Q = 0.2045593548322404\n",
      "Q = 0.20516762530538793\n",
      "Q = 0.20577589577853547\n",
      "Q = 0.20638416625168302\n",
      "Q = 0.20759086643635513\n",
      "Q = 0.20819913690950267\n",
      "Q = 0.20880740738265022\n",
      "Q = 0.20941567785579776\n",
      "Q = 0.2100239483289453\n",
      "Q = 0.21063221880209285\n",
      "Q = 0.2112404892752404\n",
      "Q = 0.21184875974838793\n",
      "Q = 0.21245703022153548\n",
      "Q = 0.21306530069468302\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Q = 0.21367357116783056\n",
      "Q = 0.2142818416409781\n",
      "Q = 0.21489011211412565\n",
      "Q = 0.2154983825872732\n",
      "Q = 0.21610665306042073\n",
      "Q = 0.21671492353356828\n",
      "Q = 0.21732319400671582\n",
      "Q = 0.21793146447986336\n",
      "Q = 0.2185397349530109\n",
      "Q = 0.21914800542615845\n",
      "Q = 0.219756275899306\n",
      "Q = 0.22036454637245353\n",
      "Q = 0.22097281684560108\n",
      "Q = 0.22158108731874862\n",
      "Q = 0.22218935779189616\n",
      "Q = 0.2227976282650437\n",
      "Q = 0.22340589873819125\n",
      "Q = 0.2240141692113388\n",
      "Q = 0.22462243968448634\n",
      "Q = 0.22523071015763388\n",
      "Q = 0.22583898063078142\n",
      "Q = 0.22644725110392896\n",
      "Q = 0.2270555215770765\n",
      "Q = 0.22766379205022405\n",
      "Q = 0.2282720625233716\n",
      "Q = 0.22888033299651914\n",
      "Q = 0.22948860346966668\n",
      "Q = 0.23009687394281422\n",
      "Q = 0.23131007274365242\n",
      "Q = 0.23241242372017162\n",
      "Q = 0.23302069419331917\n",
      "Q = 0.2336289646664667\n",
      "Q = 0.23423723513961425\n",
      "Q = 0.2348455056127618\n",
      "Q = 0.23545359041116173\n",
      "Q = 0.23606167520956167\n",
      "Q = 0.2366697600079616\n",
      "Q = 0.23727784480636155\n",
      "Q = 0.2378859296047615\n",
      "Q = 0.23849401440316143\n",
      "Q = 0.23910209920156136\n",
      "Q = 0.2397101839999613\n",
      "Q = 0.24031826879836124\n",
      "Q = 0.24092635359676118\n",
      "Q = 0.24153443839516112\n",
      "Q = 0.24214252319356105\n",
      "Q = 0.242750607991961\n",
      "Q = 0.24335869279036093\n",
      "Q = 0.24396677758876087\n",
      "Q = 0.2445748623871608\n",
      "Q = 0.24518294718556075\n",
      "Q = 0.24579103198396068\n",
      "Q = 0.24639911678236062\n",
      "Q = 0.24700701590601296\n",
      "Q = 0.2476149150296653\n",
      "Q = 0.24822281415331762\n",
      "Q = 0.24883071327696996\n",
      "Q = 0.2494386124006223\n",
      "Q = 0.2506518112014605\n",
      "Q = 0.25125971032511285\n",
      "Q = 0.2518676094487652\n",
      "Q = 0.2524755085724175\n",
      "Q = 0.25308340769606985\n",
      "Q = 0.2536913068197222\n",
      "Q = 0.254905619669046\n",
      "Q = 0.25551351879269835\n",
      "Q = 0.25672114735110846\n",
      "Q = 0.25793397480245145\n",
      "Q = 0.259146059554804\n",
      "Q = 0.25975395867845635\n",
      "Q = 0.2603618578021087\n",
      "Q = 0.260969756925761\n",
      "Q = 0.2621740433387143\n",
      "Q = 0.2633610620001405\n",
      "Q = 0.2639689611237928\n",
      "Q = 0.26457686024744514\n",
      "Q = 0.2651847593710975\n",
      "Q = 0.2657926584947498\n",
      "Q = 0.26640055761840215\n",
      "Q = 0.2670084567420545\n",
      "Q = 0.2676163558657068\n",
      "Q = 0.26822425498935915\n",
      "Q = 0.2688321541130115\n",
      "Q = 0.2700464669623353\n",
      "Q = 0.2712596657631735\n",
      "Q = 0.27186756488682584\n",
      "Q = 0.2724754640104782\n",
      "Q = 0.2736886628113164\n",
      "Q = 0.2749033470101354\n",
      "Q = 0.27611728850996403\n",
      "Q = 0.27672518763361637\n",
      "Q = 0.2773330867572687\n",
      "Q = 0.27794098588092103\n",
      "Q = 0.27854888500457337\n",
      "Q = 0.2791567841282257\n",
      "Q = 0.2803699829290639\n",
      "Q = 0.28097788205271623\n",
      "Q = 0.28158578117636857\n",
      "Q = 0.2821936803000209\n",
      "Q = 0.28280157942367323\n",
      "Q = 0.28340929287257793\n",
      "Q = 0.28401700632148263\n",
      "Q = 0.2852290910738352\n",
      "Q = 0.2858368045227399\n",
      "Q = 0.2864445179716446\n",
      "Q = 0.2870522314205493\n",
      "Q = 0.287659944869454\n",
      "Q = 0.2882676583183587\n",
      "Q = 0.2888753717672634\n",
      "Q = 0.2894830852161681\n",
      "Q = 0.2900907986650728\n",
      "Q = 0.2906985121139775\n",
      "Q = 0.2913062255628822\n",
      "Q = 0.2919139390117869\n",
      "Q = 0.2925216524606916\n",
      "Q = 0.2931293659095963\n",
      "Q = 0.293737079358501\n",
      "Q = 0.29434460713265814\n",
      "Q = 0.29495213490681527\n",
      "Q = 0.2955596626809724\n",
      "Q = 0.2961671904551295\n",
      "Q = 0.29677471822928664\n",
      "Q = 0.29738224600344376\n",
      "Q = 0.2985503258406144\n",
      "Q = 0.29968368449998334\n",
      "Q = 0.30029121227414046\n",
      "Q = 0.3008987400482976\n",
      "Q = 0.3015062678224547\n",
      "Q = 0.30211379559661183\n",
      "Q = 0.30272132337076896\n",
      "Q = 0.3033288511449261\n",
      "Q = 0.3039363789190832\n",
      "Q = 0.30454390669324033\n",
      "Q = 0.30515143446739745\n",
      "Q = 0.3057589622415546\n",
      "Q = 0.3063664900157117\n",
      "Q = 0.3069740177898688\n",
      "Q = 0.30815769430583817\n",
      "Q = 0.30932595981775646\n",
      "Q = 0.3099334875919136\n",
      "Q = 0.3105410153660707\n",
      "Q = 0.31114854314022783\n",
      "Q = 0.31175607091438495\n",
      "Q = 0.3123635986885421\n",
      "Q = 0.3135745693924091\n",
      "Q = 0.3141820971665662\n",
      "Q = 0.3153774711916345\n",
      "Q = 0.31598499896579163\n",
      "Q = 0.3165923410652011\n",
      "Q = 0.3171996831646106\n",
      "Q = 0.3178070252640201\n",
      "Q = 0.3184143673634296\n",
      "Q = 0.3190217094628391\n",
      "Q = 0.3196290515622486\n",
      "Q = 0.32023639366165807\n",
      "Q = 0.32084373576106756\n",
      "Q = 0.32145107786047705\n",
      "Q = 0.32205841995988654\n",
      "Q = 0.32266576205929604\n",
      "Q = 0.32327291848395795\n",
      "Q = 0.32388007490861986\n",
      "Q = 0.3244872313332818\n",
      "Q = 0.3250943877579437\n",
      "Q = 0.3257015441826056\n",
      "Q = 0.3263087006072675\n",
      "Q = 0.3275131726949684\n",
      "Q = 0.32925443047798963\n",
      "Q = 0.3310580749762055\n",
      "Q = 0.33225066388005975\n",
      "Q = 0.3334230142364253\n",
      "Q = 0.3345805106129826\n",
      "Q = 0.3356384853248247\n",
      "Q = 0.3365937819012423\n",
      "Q = 0.33752661183319993\n",
      "Q = 0.3390183227554427\n",
      "Q = 0.3401462968471311\n",
      "Q = 0.3412725998660911\n",
      "Q = 0.3423344737476328\n",
      "Q = 0.3432947835422357\n",
      "Q = 0.34441328822179634\n",
      "Q = 0.34590221402282506\n",
      "Q = 0.3470422569731077\n",
      "Q = 0.34806235403643876\n",
      "Q = 0.3490371464613547\n",
      "Q = 0.3500052545953569\n",
      "Q = 0.3510095693051417\n",
      "Q = 0.3519216036653678\n",
      "Q = 0.3530050158176315\n",
      "Q = 0.35390405294552535\n",
      "Q = 0.3547000405884995\n",
      "Q = 0.3556755757124059\n",
      "Q = 0.35664646896762214\n",
      "Q = 0.3574107062287562\n",
      "Q = 0.3587692883569676\n",
      "Q = 0.3601128308306231\n",
      "Q = 0.3613303001506562\n",
      "Q = 0.3624677436544724\n",
      "Q = 0.36356693816028235\n",
      "Q = 0.3646052313488785\n",
      "Q = 0.3653989908948815\n",
      "Q = 0.3661836523782519\n",
      "Q = 0.3668959007100571\n",
      "Q = 0.36755764551051434\n",
      "Q = 0.36856808748697006\n",
      "Q = 0.36950537361287017\n",
      "Q = 0.37097796003610983\n",
      "Q = 0.37183652006902623\n",
      "Q = 0.37278903152422976\n",
      "Q = 0.37363180920359995\n",
      "Q = 0.37446994501428005\n",
      "Q = 0.37530343895627005\n",
      "Q = 0.3760398250052637\n",
      "Q = 0.37709742836761057\n",
      "Q = 0.3777045847922725\n",
      "Q = 0.3783117412169344\n",
      "Q = 0.3789188976415963\n",
      "Q = 0.3795260540662582\n",
      "Q = 0.38067983694786345\n",
      "Q = 0.3814541006453681\n",
      "Q = 0.382636106088609\n",
      "Q = 0.3838173688328595\n",
      "Q = 0.3849978888781196\n",
      "Q = 0.38615817037589095\n",
      "Q = 0.38729672792819275\n",
      "Q = 0.3889856254323899\n",
      "Q = 0.3907038595467084\n",
      "Q = 0.3924191228650652\n",
      "Q = 0.39410245012683426\n",
      "Q = 0.3957811355199133\n",
      "Q = 0.3974551790443022\n",
      "Q = 0.39906107993632084\n",
      "Q = 0.4005732150807999\n",
      "Q = 0.40228662165168066\n",
      "Q = 0.40395955112758397\n",
      "Q = 0.405724760953046\n",
      "Q = 0.4079487730798351\n",
      "Q = 0.41016814333793417\n",
      "Q = 0.4123828717273431\n",
      "Q = 0.414410996995411\n",
      "Q = 0.41609766640263696\n",
      "Q = 0.4177349463270005\n",
      "Q = 0.41941771656452675\n",
      "Q = 0.4209027431958558\n",
      "Q = 0.42227803605135145\n",
      "Q = 0.4238837512686225\n",
      "Q = 0.42554702565765046\n",
      "Q = 0.42698656197581675\n",
      "Q = 0.4281329178675179\n",
      "Q = 0.42923359777130865\n",
      "Q = 0.430333534976109\n",
      "Q = 0.43143272948191896\n",
      "Q = 0.4325311812887385\n",
      "Q = 0.43362889039656766\n",
      "Q = 0.4347258568054064\n",
      "Q = 0.4358220805152547\n",
      "Q = 0.43691756152611255\n",
      "Q = 0.43801229983798\n",
      "Q = 0.43910629545085705\n",
      "Q = 0.44019954836474373\n",
      "Q = 0.44129205857964\n",
      "Q = 0.4421933238045051\n",
      "Q = 0.4430899471606801\n",
      "Q = 0.44385121362585256\n",
      "Q = 0.4451461093156361\n",
      "Q = 0.446429121821573\n",
      "Q = 0.44806621607118896\n",
      "Q = 0.44944429404789865\n",
      "Q = 0.4511966923157761\n",
      "Q = 0.4531674440868347\n",
      "Q = 0.45467995058080896\n",
      "Q = 0.4558708684119348\n",
      "Q = 0.45692735772579607\n",
      "Q = 0.45790159312646916\n",
      "Q = 0.4590732007838443\n",
      "Q = 0.4605671398030583\n",
      "Q = 0.4620774182000614\n",
      "Q = 0.4631235097280569\n",
      "Q = 0.46408214844993134\n",
      "Q = 0.4649518489677039\n",
      "Q = 0.4658185786895149\n",
      "Q = 0.46668233761536415\n",
      "Q = 0.46728949404002607\n",
      "Q = 0.467896650464688\n",
      "Q = 0.4685038068893499\n",
      "Q = 0.4691109633140118\n",
      "Q = 0.4697181197386737\n",
      "Q = 0.47032527616333564\n",
      "Q = 0.47153754659043584\n",
      "Q = 0.47214470301509776\n",
      "Q = 0.47275185943975967\n",
      "Q = 0.4733590158644216\n",
      "Q = 0.4739661722890835\n",
      "Q = 0.4745733287137454\n",
      "Q = 0.47518029946365975\n",
      "Q = 0.4757872702135741\n",
      "Q = 0.4763942409634884\n",
      "Q = 0.47700102603865513\n",
      "Q = 0.47760781111382183\n",
      "Q = 0.47821459618898854\n",
      "Q = 0.47882138126415524\n",
      "Q = 0.47942816633932195\n",
      "Q = 0.48003495141448865\n",
      "Q = 0.48064173648965536\n",
      "Q = 0.48124852156482206\n",
      "Q = 0.48185530663998877\n",
      "Q = 0.4824619060404079\n",
      "Q = 0.483068505440827\n",
      "Q = 0.48367510484124615\n",
      "Q = 0.4842817042416653\n",
      "Q = 0.4848883036420844\n",
      "Q = 0.48549490304250353\n",
      "Q = 0.48610150244292266\n",
      "Q = 0.48731135909830403\n",
      "Q = 0.48791795849872316\n",
      "Q = 0.4885245578991423\n",
      "Q = 0.4891309716248138\n",
      "Q = 0.4897373853504853\n",
      "Q = 0.49034379907615677\n",
      "Q = 0.49095021280182827\n",
      "Q = 0.49155662652749976\n",
      "Q = 0.49216304025317126\n",
      "Q = 0.49276945397884275\n",
      "Q = 0.49393994758773224\n",
      "Q = 0.49499160935815584\n",
      "Q = 0.4961084429649881\n",
      "Q = 0.4972362313819289\n",
      "Q = 0.4987498519243888\n",
      "Q = 0.499913475567617\n",
      "Q = 0.5015555830354183\n",
      "Q = 0.5032500507820435\n",
      "Q = 0.5049122111225859\n",
      "Q = 0.5064813484145791\n",
      "Q = 0.5081587340844249\n",
      "Q = 0.5101801750615791\n",
      "Q = 0.5117688082020706\n",
      "Q = 0.5133039670152525\n",
      "Q = 0.5148324415375206\n",
      "Q = 0.5163031712132842\n",
      "Q = 0.5177648028264152\n",
      "Q = 0.5193246563810283\n",
      "Q = 0.5207161029395654\n",
      "Q = 0.5222564606456801\n",
      "Q = 0.5236713022224152\n",
      "Q = 0.5251977343224598\n",
      "Q = 0.5264744338869782\n",
      "Q = 0.527610206318066\n",
      "Q = 0.5286990030380102\n",
      "Q = 0.529787057058964\n",
      "Q = 0.5308743683809274\n",
      "Q = 0.5319609370039003\n",
      "Q = 0.5330467629278829\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Q = 0.5340728015831372\n",
      "Q = 0.5350843576080785\n",
      "Q = 0.5360942425602914\n",
      "Q = 0.5371024564397758\n",
      "Q = 0.5380382571676952\n",
      "Q = 0.5389371086208414\n",
      "Q = 0.5397124863668317\n",
      "Q = 0.5404811798219082\n",
      "Q = 0.541243188986071\n",
      "Q = 0.5419985138593202\n",
      "Q = 0.5433565389632887\n",
      "Q = 0.5448668173602917\n",
      "Q = 0.5469032979920018\n",
      "Q = 0.5490162766197243\n",
      "Q = 0.54966186771714\n",
      "Q = 0.5502682814428115\n",
      "Q = 0.550874695168483\n",
      "Q = 0.5520696978440561\n",
      "Q = 0.5526761115697276\n",
      "Q = 0.5532823396206515\n",
      "Q = 0.5538883819968279\n",
      "Q = 0.5544944243730042\n",
      "Q = 0.5551004667491806\n",
      "Q = 0.5557065091253569\n",
      "Q = 0.5569135806595242\n",
      "Q = 0.5587209386526921\n",
      "Q = 0.5593269810288685\n",
      "Q = 0.5599330234050448\n",
      "Q = 0.5605390657812211\n",
      "Q = 0.5617394530244747\n",
      "Q = 0.562345495400651\n",
      "Q = 0.5629515377768274\n",
      "Q = 0.563557394478256\n",
      "Q = 0.5641630655049371\n",
      "Q = 0.5647687365316182\n",
      "Q = 0.5653744075582993\n",
      "Q = 0.5659800785849803\n",
      "Q = 0.5665857496116614\n",
      "Q = 0.5671914206383425\n",
      "Q = 0.5677970916650236\n",
      "Q = 0.5684027626917046\n",
      "Q = 0.5690082480436381\n",
      "Q = 0.5696137333955716\n",
      "Q = 0.5702192187475051\n",
      "Q = 0.5708247040994386\n",
      "Q = 0.5720174786780405\n",
      "Q = 0.5732228791394794\n",
      "Q = 0.5744266085281899\n",
      "Q = 0.5756175263593157\n",
      "Q = 0.5762230117112492\n",
      "Q = 0.5774287835221833\n",
      "Q = 0.5780342688741168\n",
      "Q = 0.5786397542260503\n",
      "Q = 0.5792450539032362\n",
      "Q = 0.5798503535804221\n",
      "Q = 0.5804554675828604\n",
      "Q = 0.5810605815852986\n",
      "Q = 0.5816655099129893\n",
      "Q = 0.5822704382406799\n",
      "Q = 0.5828753665683706\n",
      "Q = 0.5834802948960612\n",
      "Q = 0.5840852232237519\n",
      "Q = 0.5846901515514425\n",
      "Q = 0.5852950798791332\n",
      "Q = 0.5859000082068239\n",
      "Q = 0.5865047508597669\n",
      "Q = 0.587710522670701\n",
      "Q = 0.5883152653236441\n",
      "Q = 0.5889200079765872\n",
      "Q = 0.5895245649547827\n",
      "Q = 0.5901291219329782\n",
      "Q = 0.5907336789111737\n",
      "Q = 0.5913475196267493\n",
      "Q = 0.5920638528030018\n",
      "Q = 0.5927735016883405\n",
      "Q = 0.5934764662827656\n",
      "Q = 0.5942598280429028\n",
      "Q = 0.5948641993463506\n",
      "Q = 0.5954685706497984\n",
      "Q = 0.5960727562784986\n",
      "Q = 0.5966769419071989\n",
      "Q = 0.5972811275358991\n",
      "Q = 0.5978853131645994\n",
      "Q = 0.5984894987932996\n",
      "Q = 0.5990934987472523\n",
      "Q = 0.5996974987012049\n",
      "Q = 0.6003014986551576\n",
      "Q = 0.6009054986091102\n",
      "Q = 0.6015093128883153\n",
      "Q = 0.6021131271675204\n",
      "Q = 0.6027169414467255\n",
      "Q = 0.6033207557259306\n",
      "Q = 0.6039245700051357\n",
      "Q = 0.6045283842843407\n",
      "Q = 0.6051321985635458\n",
      "Q = 0.6057358271680033\n",
      "Q = 0.6063394557724608\n",
      "Q = 0.6069430843769184\n",
      "Q = 0.6075467129813759\n",
      "Q = 0.6081501559110857\n",
      "Q = 0.6087535988407955\n",
      "Q = 0.6093570417705053\n",
      "Q = 0.6099604847002151\n",
      "Q = 0.610563927629925\n",
      "Q = 0.6117604157034789\n",
      "Q = 0.6123638586331888\n",
      "Q = 0.6129673015628986\n",
      "Q = 0.6135707444926084\n",
      "Q = 0.6141741874223182\n",
      "Q = 0.6147774446772805\n",
      "Q = 0.6153807019322427\n",
      "Q = 0.6159839591872049\n",
      "Q = 0.6166475607351382\n",
      "Q = 0.6174374211114415\n",
      "Q = 0.6180406783664038\n",
      "Q = 0.618643935621366\n",
      "Q = 0.6192470072015807\n",
      "Q = 0.6198500787817953\n",
      "Q = 0.62045315036201\n",
      "Q = 0.6210562219422247\n",
      "Q = 0.6216591078476917\n",
      "Q = 0.6222619937531588\n",
      "Q = 0.6228648796586259\n",
      "Q = 0.623467765564093\n",
      "Q = 0.6240706514695601\n",
      "Q = 0.6246733517002795\n",
      "Q = 0.6253573774704491\n",
      "Q = 0.626124028503302\n",
      "Q = 0.6268860376674648\n",
      "Q = 0.6274887378981842\n",
      "Q = 0.6280914381289036\n",
      "Q = 0.628694138359623\n",
      "Q = 0.6292968385903424\n",
      "Q = 0.6298995388210618\n",
      "Q = 0.6305022390517812\n",
      "Q = 0.631104753607753\n",
      "Q = 0.6317072681637248\n",
      "Q = 0.632309597044949\n",
      "Q = 0.6329119259261733\n",
      "Q = 0.63351406913265\n",
      "Q = 0.6341162123391266\n",
      "Q = 0.6347183555456033\n",
      "Q = 0.6353203130773323\n",
      "Q = 0.6359222706090613\n",
      "Q = 0.6365242281407902\n",
      "Q = 0.6371261856725192\n",
      "Q = 0.6377281432042482\n",
      "Q = 0.6383299150612296\n",
      "Q = 0.6389315012434634\n",
      "Q = 0.6395330874256973\n",
      "Q = 0.6401346736079311\n",
      "Q = 0.6407360741154173\n",
      "Q = 0.641337288948156\n",
      "Q = 0.6419385037808947\n",
      "Q = 0.6425397186136333\n",
      "Q = 0.6431407477716243\n",
      "Q = 0.6437417769296153\n",
      "Q = 0.6443422490633636\n",
      "Q = 0.6455134853712435\n",
      "Q = 0.6461135861554965\n",
      "Q = 0.6467136869397495\n",
      "Q = 0.6473130450250121\n",
      "Q = 0.6479122174355271\n",
      "Q = 0.6485113898460421\n",
      "Q = 0.6491103765818095\n",
      "Q = 0.6497093633175769\n",
      "Q = 0.6503083500533443\n",
      "Q = 0.6509073367891117\n",
      "Q = 0.6515061378501315\n",
      "Q = 0.6521047532364036\n",
      "Q = 0.6527031829479282\n",
      "Q = 0.6533014269847052\n",
      "Q = 0.6538996710214822\n",
      "Q = 0.6544979150582592\n",
      "Q = 0.6550959734202886\n",
      "Q = 0.6556938461075703\n",
      "Q = 0.6562915331201045\n",
      "Q = 0.656889034457891\n",
      "Q = 0.65748635012093\n",
      "Q = 0.658083665783969\n",
      "Q = 0.658680981447008\n",
      "Q = 0.6592781114352994\n",
      "Q = 0.6598752414235907\n",
      "Q = 0.6604721857371344\n",
      "Q = 0.6610689443759306\n",
      "Q = 0.6616655173399791\n",
      "Q = 0.6622620903040277\n",
      "Q = 0.6628584775933286\n",
      "Q = 0.6634548648826295\n",
      "Q = 0.6640510664971828\n",
      "Q = 0.6646470824369886\n",
      "Q = 0.6652430983767943\n",
      "Q = 0.6663924250644571\n",
      "Q = 0.6669884410042628\n",
      "Q = 0.6675835285703305\n",
      "Q = 0.6681784304616507\n",
      "Q = 0.668772775328728\n",
      "Q = 0.6698378056809791\n",
      "Q = 0.6707476119442339\n",
      "Q = 0.6713413997870684\n",
      "Q = 0.6719337022319221\n",
      "Q = 0.6725252619777853\n",
      "Q = 0.6731162646994058\n",
      "Q = 0.6737055963482979\n",
      "Q = 0.6742949279971899\n",
      "Q = 0.6748837026218392\n",
      "Q = 0.6754722915717408\n",
      "Q = 0.6760608805216425\n",
      "Q = 0.676648541097806\n",
      "Q = 0.6772358303244744\n",
      "Q = 0.6780535419129182\n",
      "Q = 0.678640645464839\n",
      "Q = 0.6792277490167599\n",
      "Q = 0.6798120674474666\n",
      "Q = 0.6803963858781733\n",
      "Q = 0.6809786618866565\n",
      "Q = 0.6815601951961492\n",
      "Q = 0.6821417285056419\n",
      "Q = 0.6827227047908918\n",
      "Q = 0.6833034954013941\n",
      "Q = 0.6838839146624012\n",
      "Q = 0.6844634055496702\n",
      "Q = 0.6850414110389584\n",
      "Q = 0.6856194165282467\n",
      "Q = 0.686194079872078\n",
      "Q = 0.6867667007936857\n",
      "Q = 0.6873359795698366\n",
      "Q = 0.6879035872732591\n",
      "Q = 0.6884706379524387\n",
      "Q = 0.6890365745831327\n",
      "Q = 0.6896019541895839\n",
      "Q = 0.6901671481212875\n",
      "Q = 0.6907306709802628\n",
      "Q = 0.6917949586335234\n",
      "Q = 0.6923575531187606\n",
      "Q = 0.6929090071191416\n",
      "Q = 0.6934580473478038\n",
      "Q = 0.6940982538775391\n",
      "Q = 0.6946430235870064\n",
      "Q = 0.6951861222237452\n",
      "Q = 0.6957286638362412\n",
      "Q = 0.6962678633032804\n",
      "Q = 0.6968003784794059\n",
      "Q = 0.6973317796070457\n",
      "Q = 0.6978544540215482\n",
      "Q = 0.6983769427613031\n",
      "Q = 0.6988992458263105\n",
      "Q = 0.6994213632165702\n",
      "Q = 0.6999432949320823\n",
      "Q = 0.7004650409728468\n",
      "Q = 0.7009866013388637\n",
      "Q = 0.701507976030133\n",
      "Q = 0.7020291650466548\n",
      "Q = 0.7025501683884289\n",
      "Q = 0.7030709860554554\n",
      "Q = 0.7035916180477343\n",
      "Q = 0.7041120643652656\n",
      "Q = 0.7046323250080493\n",
      "Q = 0.7051525856508329\n",
      "Q = 0.7059524724635068\n",
      "Q = 0.7064727331062904\n",
      "Q = 0.7069928080743265\n",
      "Q = 0.707512697367615\n",
      "Q = 0.7080324009861559\n",
      "Q = 0.7085519189299492\n",
      "Q = 0.7090712511989948\n",
      "Q = 0.7095903977932929\n",
      "Q = 0.7101093587128434\n",
      "Q = 0.7106281339576462\n",
      "Q = 0.711146909202449\n",
      "Q = 0.7116654987725043\n",
      "Q = 0.7121840883425595\n",
      "Q = 0.7127024922378672\n",
      "Q = 0.7132208961331749\n",
      "Q = 0.7137391143537349\n",
      "Q = 0.714257332574295\n",
      "Q = 0.7147753651201075\n",
      "Q = 0.71529339766592\n",
      "Q = 0.7158112445369849\n",
      "Q = 0.7163290914080497\n",
      "Q = 0.7168467526043669\n",
      "Q = 0.7173642281259366\n",
      "Q = 0.7178815179727587\n",
      "Q = 0.7183986221448331\n",
      "Q = 0.7189157263169075\n",
      "Q = 0.7194326448142343\n",
      "Q = 0.7199495633115611\n",
      "Q = 0.7204662961341404\n",
      "Q = 0.7209830289567196\n",
      "Q = 0.7214995761045513\n",
      "Q = 0.722016123252383\n",
      "Q = 0.7225324847254669\n",
      "Q = 0.7230488461985509\n",
      "Q = 0.7235650219968873\n",
      "Q = 0.7240811977952237\n",
      "Q = 0.7245971879188126\n",
      "Q = 0.7251131780424014\n",
      "Q = 0.7256289824912426\n",
      "Q = 0.7261447869400839\n",
      "Q = 0.7266604057141776\n",
      "Q = 0.7271760244882712\n",
      "Q = 0.7276914575876172\n",
      "Q = 0.7282068906869632\n",
      "Q = 0.7287221381115616\n",
      "Q = 0.72923738553616\n",
      "Q = 0.7297524472860109\n",
      "Q = 0.7302675090358617\n",
      "Q = 0.7307823851109649\n",
      "Q = 0.7312972611860682\n",
      "Q = 0.7318119515864238\n",
      "Q = 0.7323266419867793\n",
      "Q = 0.7328411467123873\n",
      "Q = 0.7333556514379953\n",
      "Q = 0.7338699704888557\n",
      "Q = 0.7343842895397161\n",
      "Q = 0.734898422915829\n",
      "Q = 0.7354125562919418\n",
      "Q = 0.735926503993307\n",
      "Q = 0.7364404516946721\n",
      "Q = 0.7369542137212897\n",
      "Q = 0.7374679757479072\n",
      "Q = 0.7379815520997772\n",
      "Q = 0.7384951284516472\n",
      "Q = 0.7390087048035172\n",
      "Q = 0.7395220954806396\n",
      "Q = 0.740035486157762\n",
      "Q = 0.7405486911601368\n",
      "Q = 0.7410618961625115\n",
      "Q = 0.7415749154901387\n",
      "Q = 0.7420879348177658\n",
      "Q = 0.7426007684706454\n",
      "Q = 0.743113602123525\n",
      "Q = 0.743626250101657\n",
      "Q = 0.744138898079789\n",
      "Q = 0.7446513603831734\n",
      "Q = 0.7451638226865578\n",
      "Q = 0.7456760993151945\n",
      "Q = 0.7461883759438313\n",
      "Q = 0.7467004668977204\n",
      "Q = 0.7472125578516096\n",
      "Q = 0.7477244631307511\n",
      "Q = 0.7482361827351451\n",
      "Q = 0.7487477166647915\n",
      "Q = 0.7492590649196902\n",
      "Q = 0.7497704131745889\n",
      "Q = 0.7502815757547401\n",
      "Q = 0.7507925526601437\n",
      "Q = 0.7513033438907996\n",
      "Q = 0.7518139494467079\n",
      "Q = 0.7523243693278686\n",
      "Q = 0.7528346035342818\n",
      "Q = 0.7533446520659473\n",
      "Q = 0.7538545149228651\n",
      "Q = 0.7543641921050355\n",
      "Q = 0.7548736836124582\n",
      "Q = 0.7553794616249289\n",
      "Q = 0.7558737278030482\n",
      "Q = 0.7563661372336914\n",
      "Q = 0.7568557615431206\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Q = 0.7573407439838598\n",
      "Q = 0.7578253550751036\n",
      "Q = 0.758667575730231\n",
      "Q = 0.7594470383206685\n",
      "Q = 0.7601238227756816\n",
      "Q = 0.7605783545578138\n",
      "Q = 0.7610046637783103\n",
      "Q = 0.7614309729988069\n",
      "Q = 0.7618565395203131\n",
      "Q = 0.7622774641731291\n",
      "Q = 0.7626584687552106\n",
      "Q = 0.7630246193574838\n",
      "Q = 0.7633571628304409\n",
      "Q = 0.7636880352306694\n",
      "Q = 0.764018907630898\n",
      "Q = 0.7643358544250564\n",
      "Q = 0.7646511301464863\n",
      "Q = 0.7649647347951879\n",
      "Q = 0.765276668371161\n",
      "Q = 0.7655858168259201\n",
      "Q = 0.7658932942079507\n",
      "Q = 0.7661991005172529\n",
      "Q = 0.7665032357538267\n",
      "Q = 0.7667897318893782\n",
      "Q = 0.7670114275380162\n",
      "Q = 0.767232751837159\n",
      "Q = 0.7674466491463977\n",
      "Q = 0.767632695243496\n",
      "Q = 0.7677751077749075\n",
      "Q = 0.767912878437629\n",
      "Q = 0.7680460072316604\n",
      "Q = 0.7681744941570017\n",
      "Q = 0.7682760582439405\n",
      "Q = 0.7683739088359273\n",
      "Q = 0.768470831054176\n",
      "Q = 0.7685640397774728\n",
      "Q = 0.7686086017168975\n",
      "Q = 0.7686078590179071\n",
      "Q = 0.7686071163189166\n",
      "Q = 0.7686063736199262\n",
      "Q = 0.7686056309209358\n",
      "Q = 0.7686048882219454\n",
      "Q = 0.768604145522955\n",
      "Q = 0.7686034028239646\n",
      "Q = 0.7686026601249741\n",
      "Q = 0.7686019174259837\n",
      "Q = 0.7686011747269933\n",
      "Q = 0.7686004320280029\n",
      "Q = 0.7685996893290125\n",
      "Q = 0.768598946630022\n",
      "Q = 0.7685982039310316\n",
      "Q = 0.7685974612320412\n",
      "Q = 0.7685967185330508\n",
      "Q = 0.7685959758340604\n",
      "Q = 0.7685952331350699\n",
      "Q = 0.7685944904360795\n",
      "Q = 0.7685937477370891\n",
      "Q = 0.7685930050380987\n",
      "Q = 0.7685922623391083\n",
      "Q = 0.7685915196401178\n",
      "Q = 0.7685907769411274\n",
      "Q = 0.768590034242137\n",
      "Q = 0.7685892915431466\n",
      "Q = 0.7685885488441562\n",
      "Q = 0.7685878061451658\n",
      "Q = 0.7685870634461753\n",
      "Q = 0.7685863207471849\n",
      "Q = 0.7685855780481945\n",
      "Q = 0.7685848353492041\n",
      "Q = 0.7685840926502137\n",
      "Q = 0.7685833499512232\n",
      "Q = 0.7685826072522328\n",
      "Q = 0.7685818645532424\n",
      "Q = 0.768581121854252\n",
      "Q = 0.7685803791552616\n",
      "Q = 0.7685796364562711\n",
      "Q = 0.7685788937572807\n",
      "Q = 0.7685781510582903\n",
      "Q = 0.7685774083592999\n",
      "Q = 0.7685766656603095\n",
      "Q = 0.7685751802623286\n",
      "Q = 0.768572209466367\n",
      "Q = 0.7685692386704053\n",
      "Q = 0.7685662678744436\n",
      "Q = 0.7685632970784819\n",
      "Q = 0.7685603262825202\n",
      "Q = 0.7685573554865586\n",
      "Q = 0.7685543846905969\n",
      "Q = 0.7685514138946352\n",
      "Q = 0.7685484430986735\n",
      "Q = 0.7685454723027119\n",
      "Q = 0.7685425015067502\n",
      "Q = 0.7685395307107885\n",
      "Q = 0.7685365599148268\n",
      "Q = 0.7685335891188652\n",
      "Q = 0.7685306183229035\n",
      "Q = 0.7685276475269418\n",
      "Q = 0.7685246767309801\n",
      "Q = 0.7685217059350185\n",
      "Q = 0.7685187351390568\n",
      "Q = 0.7685157643430951\n",
      "Q = 0.7685127935471334\n",
      "Q = 0.7685098227511717\n",
      "Q = 0.7685068519552101\n",
      "Q = 0.7685038811592484\n",
      "Q = 0.7685009103632867\n",
      "Q = 0.768497939567325\n",
      "Q = 0.7684949687713634\n",
      "Q = 0.7684919979754017\n",
      "Q = 0.76848902717944\n",
      "Q = 0.7684860563834783\n",
      "Q = 0.7684830855875167\n",
      "Q = 0.768480114791555\n",
      "Q = 0.7684734305006413\n",
      "Q = 0.7684667462097277\n",
      "Q = 0.768460061918814\n",
      "Q = 0.7684522635794147\n",
      "Q = 0.7684418657935489\n",
      "Q = 0.7684299826097023\n",
      "Q = 0.7684180994258557\n",
      "Q = 0.7684062162420091\n",
      "Q = 0.7683943330581625\n",
      "Q = 0.7683824498743159\n",
      "Q = 0.7683705666904693\n",
      "Q = 0.7683586835066227\n",
      "Q = 0.7683468003227761\n",
      "Q = 0.7683349171389295\n",
      "Q = 0.768323033955083\n",
      "Q = 0.7683111507712364\n",
      "Q = 0.7682992675873898\n",
      "Q = 0.7682873844035432\n",
      "Q = 0.7682755012196966\n",
      "Q = 0.76826361803585\n",
      "Q = 0.7682517348520034\n",
      "Q = 0.7682368808721951\n",
      "Q = 0.7682101437085402\n",
      "Q = 0.7681811784479141\n",
      "Q = 0.7681510991388024\n",
      "Q = 0.7681147068882722\n",
      "Q = 0.7680729300700615\n",
      "Q = 0.7680253973346751\n",
      "Q = 0.7679778645992887\n",
      "Q = 0.7679303318639024\n",
      "Q = 0.767882799128516\n",
      "Q = 0.7678352663931296\n",
      "Q = 0.7677877336577432\n",
      "Q = 0.7677402009223568\n",
      "Q = 0.7676926681869705\n",
      "Q = 0.7676358517142039\n",
      "Q = 0.7675511840292969\n",
      "Q = 0.767435137312045\n",
      "Q = 0.7672791705240585\n",
      "Q = 0.7671064930087876\n",
      "Q = 0.7669163620672421\n",
      "Q = 0.7667262311256966\n",
      "Q = 0.7665361001841511\n",
      "Q = 0.7663459692426056\n",
      "Q = 0.7661439551172134\n",
      "Q = 0.7658645146220708\n",
      "Q = 0.7654460037409736\n",
      "Q = 0.7649353981850653\n",
      "Q = 0.7642784809280457\n",
      "Q = 0.7635179571618638\n",
      "Q = 0.7627574333956818\n",
      "Q = 0.7613815835159433\n",
      "Q = 0.759918652179579\n",
      "Q = 0.7578708453882651\n",
      "Q = 0.7555508394169652\n",
      "Q = 0.7525087443522371\n",
      "Q = 0.7494267292167744\n",
      "Q = 0.7445754194114025\n",
      "Q = 0.7344271804064112\n",
      "Q = 0.7210229490274531\n",
      "Q = 0.7036452780497902\n",
      "Q = 0.6735258631926168\n",
      "Q = 0.6298132000634253\n",
      "Q = 0.5654975099159587\n",
      "Q = 0.41049418819472405\n",
      "Q = 0.0033258060790642974\n"
     ]
    }
   ],
   "source": [
    "Newman_algorithm(yeast_graph, 'yeast') # max = 0.7686086017168975"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**The modularity of the best community decomposition found for this network is 0.7686086017168975. There are a large number of other decompositions of the same quality of around ~0.768, as shown in the results above.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us describe an algorithm called *community finder*.  Rather than find a community decomposition, it just finds the community that a particular vertex $v$ belongs to.   The input to community finder is a network $N$, one of its nodes $v$ and a threshold value $a$ (a positive real number).  Let $d_i$ be the number of edges between nodes at distance $i$ from $v$ to nodes at distance $i+1$ from $v$.  So $d_0$ is just the degree of $v$.  Let $\\Delta_i=d_i/d_{i-1}$.   Community finder calculates $\\Delta_1, \\Delta_2, \\ldots$ and stops when it finds a value $\\ell$ such that $\\Delta_\\ell < a$.  Then the community of $v$ is simply all nodes at distance at most $\\ell$ from $v$.\n",
    "\n",
    "5. [3 marks] Does the definition of community suggest that the community finder algorithm is likely to succeed in finding communities?  In what circumstances might it perform well or badly?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**The definition of community suggests that the community finder algorithm is unlikely to succeed at finding communities. It would perform well in graphs with a large diameter, as these graphs have greater distances between nodes and so it is more likely to run for a longer period of time and thus find better communities. However, in smaller graphs with a smaller diameter, the algorithm would perform worse as there are smaller distances between nodes and so it is more difficult to prudently find communities.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "6. [6 marks] Implement community finder and apply to the network of `zachary.txt` and comment on the results compared to your findings of Question 3.  You will need to run it for various choices of $v$ and $a$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# returns dictionary of distances from v as keys and nodes at those distance from v as values\n",
    "def breadth_first_search(graph, v):\n",
    "        \n",
    "    # create queue containing source vertex\n",
    "    queue = [v]\n",
    "    distance_nodes_dict = {\n",
    "        0: set([v])\n",
    "    }\n",
    "    nodes_distances_dict = {\n",
    "        v: 0\n",
    "    }\n",
    "    \n",
    "    while queue:\n",
    "        \n",
    "        u = queue.pop(0)\n",
    "        u_distance = nodes_distances_dict[u]\n",
    "        \n",
    "        neighbours = graph[u]\n",
    "        new_distance = u_distance + 1\n",
    "        \n",
    "        \n",
    "        for neighbour in neighbours:\n",
    "            \n",
    "            if neighbour not in nodes_distances_dict:\n",
    "                \n",
    "                queue.append(neighbour)\n",
    "                \n",
    "                if new_distance not in distance_nodes_dict:\n",
    "                    distance_nodes_dict[new_distance] = set()\n",
    "            \n",
    "                distance_nodes_dict[new_distance].add(neighbour)\n",
    "                nodes_distances_dict[neighbour] = new_distance\n",
    "    \n",
    "    return distance_nodes_dict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "# calculates delta di / delta di - 1\n",
    "def delta_calculator(graph, distance_nodes_dict, i):\n",
    "    \n",
    "    if i + 1 not in distance_nodes_dict:\n",
    "        return 0\n",
    "    \n",
    "    edges_i = edges_i_minus_1 = 0\n",
    "    \n",
    "    # calculate the number of edges from nodes at distance i from v to nodes at distance i + 1 from v\n",
    "    # and from nodes at distance i - 1 to nodes at distance i for di-1\n",
    "    nodes_distance_i_minus_1 = distance_nodes_dict[i - 1]\n",
    "    nodes_distance_i = distance_nodes_dict[i]\n",
    "    nodes_distance_i_plus_1 = distance_nodes_dict[i + 1]\n",
    "    \n",
    "    for i in nodes_distance_i:\n",
    "        \n",
    "        for j in nodes_distance_i_plus_1:\n",
    "            if i in graph[j]:\n",
    "                edges_i += 1\n",
    "        \n",
    "        for k in nodes_distance_i_minus_1:\n",
    "            if i in graph[k]:\n",
    "                edges_i_minus_1 += 1\n",
    "    \n",
    "    delta_i = edges_i / edges_i_minus_1\n",
    "    return delta_i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "# finds and returns the community that v belongs to\n",
    "def community_finder(graph, v, a):\n",
    "    \n",
    "    l = 0\n",
    "    delta_l = float('inf')\n",
    "    distance_nodes_dict = breadth_first_search(graph, v)\n",
    "    \n",
    "    # calculate delta l starting at l = 1 and stop if delta l found smaller than a\n",
    "    while delta_l >= a:\n",
    "        \n",
    "        l += 1\n",
    "        delta_l = delta_calculator(graph, distance_nodes_dict, l)\n",
    "\n",
    "    # add all nodes at distance <= l from v to community\n",
    "    community = []\n",
    "    for distance in distance_nodes_dict:\n",
    "        if distance <= l:\n",
    "            community += (list(distance_nodes_dict[distance]))\n",
    "        \n",
    "    return set(sorted(community))\n",
    "\n",
    "# Newman's algorithm results\n",
    "#[{2, 3, 4, 8, 10, 13, 14, 18, 22}, {32, 33, 34, 9, 15, 16, 19, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31}, \n",
    "#  {1, 5, 6, 7, 11, 12, 17, 20}] Q = 0.430\n",
    "#[{32, 33, 34, 9, 15, 16, 19, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31}, \n",
    "#  {1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 17, 18, 20, 22}] Q = 0.422"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 18, 20, 22, 28, 29, 31, 32, 33, 34} size = 23\n"
     ]
    }
   ],
   "source": [
    "community = community_finder(karate_graph, 2, 1.5)\n",
    "print(community, 'size =', len(community))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1, 2, 3, 4, 8, 14, 18, 20, 22, 31} size = 10\n"
     ]
    }
   ],
   "source": [
    "community = community_finder(karate_graph, 2, 5)\n",
    "print(community, 'size =', len(community))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 23, 24, 25, 28, 29, 30, 31, 32, 33, 34} size = 31\n"
     ]
    }
   ],
   "source": [
    "community = community_finder(karate_graph, 3, 2)\n",
    "print(community, 'size =', len(community))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1, 2, 3, 4, 33, 8, 9, 10, 14, 28, 29} size = 11\n"
     ]
    }
   ],
   "source": [
    "community = community_finder(karate_graph, 3, 4)\n",
    "print(community, 'size =', len(community))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 17, 18, 20, 22, 25, 26, 28, 29, 31, 32, 33, 34} size = 26\n"
     ]
    }
   ],
   "source": [
    "community = community_finder(karate_graph, 12, 1.1)\n",
    "print(community, 'size =', len(community))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{32, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 18, 20, 22} size = 17\n"
     ]
    }
   ],
   "source": [
    "community = community_finder(karate_graph, 12, 1.5)\n",
    "print(community, 'size =', len(community))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 23, 24, 27, 28, 29, 30, 31, 32, 33, 34} size = 31\n"
     ]
    }
   ],
   "source": [
    "community = community_finder(karate_graph, 20, 6)\n",
    "print(community, 'size =', len(community))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1, 2, 20, 34} size = 4\n"
     ]
    }
   ],
   "source": [
    "community = community_finder(karate_graph, 20, 14)\n",
    "print(community, 'size =', len(community))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 17, 18, 20, 22, 25, 26, 28, 29, 31, 32, 33, 34} size = 26\n"
     ]
    }
   ],
   "source": [
    "community = community_finder(karate_graph, 17, 1.2)\n",
    "print(community, 'size =', len(community))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{32, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 17, 18, 20, 22} size = 18\n"
     ]
    }
   ],
   "source": [
    "community = community_finder(karate_graph, 17, 1.5)\n",
    "print(community, 'size =', len(community))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[{32, 33, 34, 9, 15, 16, 19, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31}, {1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 17, 18, 20, 22}] Q = 0.422\n",
    "\n",
    "**The results of community finder run on the karate club graph compared to Newman's algorithm are quite interesting. With larger values of a, the community found is smaller than the both the communities in the two-community found by Newman's algorithm, shown above, which is the case for most test nodes. With smaller values of a, the community found is larger than both communities in the two-community found by Newman's algorithm. Whether they are smaller or larger, the nodes within the communities when compared are almost identical for all nodes tested.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "7. [6 marks] You could run community finder for every node in a network, but then you would have as many communities as there are nodes and they would overlap.  Suggest how community finder could be used as the basis of a community decomposition algorithm (that, as usual, partitions the nodes into disjoint sets) and test your idea on the network of `zachary.txt`.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Start by selecting a random node from a list of nodes in the graph to run community finder on. Once this community has been obtained, check if any of its nodes exist in previously discovered communities and remove these nodes from the current community if so. Append the current community to a list of communities and remove the nodes found in this community from the initial list of nodes. Repeat this process by selecting another node at random from the new list and continue until there are no nodes left in the list of nodes. All nodes are then part of disjoint sets, or communities.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [],
   "source": [
    "# uses community finder as a basis for a community decomposition algorithm\n",
    "def community_finder_decomposition(graph, a):\n",
    "    \n",
    "    # initalise communities and nodes\n",
    "    communities = []\n",
    "    nodes = list(graph)\n",
    "    \n",
    "    # carry on until all nodes are in a community\n",
    "    while nodes:\n",
    "        \n",
    "        # pick random node to run community finder on\n",
    "        v = random.choice(nodes)\n",
    "        community = community_finder(graph, v, a)\n",
    "        test_community = community.copy()\n",
    "        \n",
    "        # remove nodes that are in other discovered communities\n",
    "        for check_community in communities:\n",
    "            for node in test_community:\n",
    "                if node in check_community:\n",
    "                    community.remove(node)\n",
    "        \n",
    "        # add community to communities list and update nodes\n",
    "        communities.append(community)\n",
    "        nodes = [node for node in nodes if node not in community]\n",
    "\n",
    "    return communities"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{32, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 17, 18, 20, 22}\n",
      "{33, 34, 10, 15, 16, 19, 21, 23, 24, 27, 28, 29, 30, 31}\n",
      "{25, 26}\n"
     ]
    }
   ],
   "source": [
    "communities = community_finder_decomposition(karate_graph.copy(), 2.5)\n",
    "for community in communities:\n",
    "    print(community)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "#### Newman's agglomerative algorithm for community detection\n",
    " \n",
    "If you can find a library to provide the algorithm, you can use that although it might require you to define networks in a different way.  Here is an outline approach to the implementation.  You should first reread the description of the algorithm.\n",
    "\n",
    "Define a dictionary called, say, `communities` that throughout the run of the algorithm will contains as keys the current communities (so the keys will keep changing as communities are merged).  The values in the dictionary will record the nodes in the community and the number of endpoints incident with those nodes.\n",
    "\n",
    "Define a dictionary called, say, `pairs` that throughout the run of the algorithm will contains as keys each pair of current communities.  The values in the dictionary will record the number of edges between the pair.\n",
    "\n",
    "Define a function called, say, `deltaQ` whose input is a pair of communities and whose output is the change in modularity if that pair of communities is merged. \n",
    "\n",
    "Create a priority queue that contains each pair of communities keyed by the change in modularity if that pair were merged.\n",
    "\n",
    "Then the algorithm repeatedly picks the pair of communities from the priority queue whose merger will give the maximum change in modularity and merges that pair (and updates `communities` and `pairs` and pushes new pairs onto the priority queue).\n",
    "\n",
    "For the priority queue you could use\n",
    "\n",
    "```python\n",
    "from queue import PriorityQueue\n",
    "```\n",
    "\n",
    "but note that this only allows queues from which you can pick the entry with the minimum value.  You can make such a queue perform as a *maximum* priority queue by multiplying all the keys by -1.\n",
    "\n",
    "Below is the network from the lecture that you can use to test your implementation.\n",
    "\n",
    "Note that, with a reasonable implementation, no computation required by this exercise should take more than a couple of minutes."
   ]
  }
 ],
 "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}