kmedoids/clarans.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "ac6b410c-5754-47e6-bcb3-8b4fc6163ccf",
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "from graphdatascience import GraphDataScience\n",
    "from getpass import getpass\n",
    "from time import perf_counter\n",
    "import kmedoids\n",
    "import urllib.request\n",
    "import zipfile"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5aec0aa1-4520-462d-9777-868c579ba5fc",
   "metadata": {},
   "source": [
    "# Connect to Neo4j"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "762d9d31-c7c5-47e9-800b-38e7d2b9d931",
   "metadata": {},
   "source": [
    "The connection URI for your Neo4j instance is available in the AuraDS console or by copying the Bolt port from the details panel for for your DBMS in Neo4j Desktop. If you are using Neo4j Desktop, make sure you have GDS installed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "8f372fcf-efbe-42bb-b8fb-cff1758085d7",
   "metadata": {},
   "outputs": [],
   "source": [
    "connection_uri = \"neo4j+s://80102ec4.databases.neo4j.io\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "82a8144d-b4f0-4e02-8b2f-7dbb0126f4b4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "Neo4j password ········\n"
     ]
    }
   ],
   "source": [
    "neo4j_pwd = getpass(\"Neo4j password\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "90261f4d-174c-4050-af15-cca934eeb5bf",
   "metadata": {},
   "outputs": [],
   "source": [
    "gds = GraphDataScience(connection_uri, auth=(\"neo4j\", neo4j_pwd))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "96cb2d3f-28e6-431b-a3ca-d73a08a9a6b6",
   "metadata": {},
   "outputs": [],
   "source": [
    "gds.set_database(\"neo4j\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "abe471f4-72e8-4ea0-95d9-d43a4cb5d0ad",
   "metadata": {},
   "source": [
    "# Download datasets\n",
    "## Smaller genetic dataset\n",
    "Data from Cho, Ara and Shin, Junha and Hwang, Sohyun and Kim, Chanyoung and Shim, Hongseok and Kim, Hyojin and Kim, Hanhae and Lee, Insuk (2014). \"WormNet v3: a network-assisted hypothesis-generating server for Caenorhabditis elegans.\" Nucleic acids research, 42(W1), W76-W82.\n",
    "\n",
    "Hosted by [The Network Data Repository with Interactive Graph Analytics and Visualization](https://networkrepository.com)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "905544d7-789c-4c5b-8430-6969e5cb715a",
   "metadata": {},
   "outputs": [],
   "source": [
    "file_name, headers = urllib.request.urlretrieve(\"https://nrvis.com/download/data/bio/bio-CE-LC.zip\", \"bio-CE-LC.zip\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "748d6809-45b4-4c7d-9b84-44a04be01798",
   "metadata": {},
   "outputs": [],
   "source": [
    "with zipfile.ZipFile(file_name, 'r') as zip_ref:\n",
    "    zip_ref.extractall('.')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99e0106c-d2e1-4ce2-9b87-1bbb13762daa",
   "metadata": {},
   "source": [
    "## Larger collaboration dataset\n",
    "Data from Gehrke, Johannes and Ginsparg, Paul and Kleinberg Jon (2003). \"Overview of the 2003 KDD Cup.\" ACM SIGKDD Explorations Newsletter, 5(2), 149-151.\n",
    "\n",
    "Hosted by [The Network Data Repository with Interactive Graph Analytics and Visualization](https://networkrepository.com)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "169e82a6-350a-49dd-989d-cab96be396be",
   "metadata": {},
   "outputs": [],
   "source": [
    "file_name, headers = urllib.request.urlretrieve(\"https://nrvis.com/download/data/soc/ca-HepPh.zip\", \"ca-HepPh.zip\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "82824ce7-56b2-458d-a641-cc14847964ff",
   "metadata": {},
   "outputs": [],
   "source": [
    "with zipfile.ZipFile(file_name, 'r') as zip_ref:\n",
    "    zip_ref.extractall('.')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b3451ef-c281-436e-ac69-abef954e7f4f",
   "metadata": {},
   "source": [
    "# CLARANS functions"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "61b7c4a6-78b8-4b4d-b1c0-f73c05fe8bc3",
   "metadata": {},
   "source": [
    "The k-medoid algorithm assumes that we can calculate a distance from each node in the base graph to each medoid. This means that there must be a path from each node in the graph to each other node in the graph. If you have a disconnected graph, running weakly connected components (WCC) is a good first step towards clustering. Depending on the results of WCC, you can use other clustering algorithms like CLARANS to further analyze the structure of the largest WCC components.\n",
    "\n",
    "This function creates a subgraph based on the largest connected component in the provided graph projection. It also applies a new label to the nodes in the largest component so that we can efficiently query these nodes with Cypher."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "da37f080-9a72-4cd0-be8c-d490cd373657",
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_giant_component(projection, wccProperty, subgraph_name, subgraph_node_label):\n",
    "    # Mutate the graph with wcc id so we can use it for filtering\n",
    "    gds.wcc.mutate(projection, mutateProperty=wccProperty)\n",
    "    # Write the wcc id to the graph so we can use it for filtering in Bloom\n",
    "    gds.graph.nodeProperties.write(projection, wccProperty)\n",
    "    # Get the id of the giant component\n",
    "    wcc_df = gds.graph.nodeProperties.stream(projection, wccProperty)\n",
    "    biggest_component_id = wcc_df['propertyValue'].value_counts().idxmax()\n",
    "    # Filter the projection to the giant component\n",
    "    subgraph, result = gds.graph.filter(subgraph_name,\n",
    "                                projection,\n",
    "                                f\"n.{wccProperty} = {biggest_component_id}\",\n",
    "                                \"*\")\n",
    "    gds.run_cypher(f\"\"\"MATCH (n) WHERE n.wccId = $biggestComponentId\n",
    "                       CALL apoc.create.addLabels(n, [$subgraphNodeLabel])\n",
    "                       YIELD node\n",
    "                       RETURN count(*) AS nodesUpdated\"\"\",\n",
    "                  {\"biggestComponentId\": biggest_component_id,\n",
    "                  \"subgraphNodeLabel\": subgraph_node_label})\n",
    "    return subgraph, result, biggest_component_id"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7699e38b-3fa8-4f73-beea-337336484c07",
   "metadata": {},
   "source": [
    "This function selects a random group of k nodes as medoids to begin an iteration of the CLARANS search."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "42a2d768-8ca0-4905-8bba-2f756b049836",
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_new_candidate(k, label):\n",
    "    candidate_df = gds.run_cypher(f\"\"\"MATCH (g:{label})\n",
    "                                     WITH g ORDER BY rand()\n",
    "                                     LIMIT $k\n",
    "                                     WITH collect(g) AS medoids\n",
    "                                     CREATE (c:Candidate)\n",
    "                                     WITH c, medoids\n",
    "                                     UNWIND medoids as m\n",
    "                                     MERGE (c)-[:HAS_MEDOID]->(m)\n",
    "                                     RETURN id(c) AS candidate_id\n",
    "                                     LIMIT 1\"\"\",\n",
    "                                  {\"k\":k, \"label\": label})\n",
    "    return candidate_df.iloc[0,0]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0dd02b0e-26a2-49ae-a890-0359c1cc1d6d",
   "metadata": {},
   "source": [
    "This function uses the [Delta-Stepping Single-Source Shortest Path](https://neo4j.com/docs/graph-data-science/current/algorithms/delta-single-source/) algorithm to calculate the distance from each medoid to all the other nodes in the graph. We store the calculated distances as properties on `HAS_DISTANCE` relationships in the graph.\n",
    "\n",
    "Once the distances are known, we can calculate the sum of the distances from each node in the base graph to its closest medoid."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "ab1a046e-7532-477e-afe9-23ef524141f1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_candidate_cost(projection, candidate_id):\n",
    "    #If distances to all other nodes are not already present for each medoid, calculate the missing distances\n",
    "    gds.run_cypher(\"\"\"\n",
    "                      MATCH (c)-[:HAS_MEDOID]->(m)\n",
    "                      WHERE id(c) = $candidateId\n",
    "                      AND NOT EXISTS {(m)-[:HAS_DISTANCE]->()}\n",
    "                      WITH m\n",
    "                      CALL gds.allShortestPaths.delta.write(\n",
    "                          $graphName,\n",
    "                          {writeRelationshipType: \"HAS_DISTANCE\",\n",
    "                          sourceNode: id(m)})\n",
    "                      YIELD relationshipsWritten\n",
    "                      RETURN relationshipsWritten\n",
    "                          \"\"\",\n",
    "                   {\"candidateId\": candidate_id,\n",
    "                    \"graphName\": projection.name()})\n",
    "    #Calculate the cost for this group of candidate medoids\n",
    "    cost_df = gds.run_cypher(\"\"\"\n",
    "                      MATCH (c)-[:HAS_MEDOID]->(m)\n",
    "                      WHERE id(c) = $candidateId\n",
    "                      MATCH (m)-[d:HAS_DISTANCE]->(n)\n",
    "                      WITH c, m, n, d \n",
    "                      ORDER BY d.totalCost ASC\n",
    "                      WITH c, n, collect(d.totalCost) AS costList\n",
    "                      WITH c, n, costList[0] AS closestMedoidCost\n",
    "                      WITH c, sum(closestMedoidCost) AS totalCost\n",
    "                      SET c.totalCost = totalCost\n",
    "                      RETURN totalCost\"\"\",\n",
    "                  {\"candidateId\": candidate_id})\n",
    "    return cost_df.iloc[0,0]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e8588338-46c6-4178-836d-8bea6bcf53a0",
   "metadata": {},
   "source": [
    "Given an existing node in the candidate graph, this function creates a neighboring candidate node by swapping out one of the medoids associated with the original candidate with a randomly selected node in the base graph. We create a `HAS_NEIGHBOR` relationship from the original candidate to the new candidate so that we have an audit trail of the candidates that were searched."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "42774031-3dc7-410d-adf0-3bc634ea0450",
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_neighboring_candidate(candidate_id, k, label):\n",
    "    new_candidate_df = gds.run_cypher(f\"\"\"\n",
    "                                       MATCH (c:Candidate)\n",
    "                                       WHERE id(c) = $candidateId\n",
    "                                       MATCH (g:{label}) \n",
    "                                       WHERE NOT EXISTS {{(c)-[:HAS_MEDOID]->(g)}}\n",
    "                                       WITH c, g \n",
    "                                       ORDER BY rand()\n",
    "                                       LIMIT 1\n",
    "                                       MATCH (c)-[:HAS_MEDOID]->(m)\n",
    "                                       WITH c, g, m \n",
    "                                       ORDER BY rand()\n",
    "                                       LIMIT $k -1\n",
    "                                       WITH c, g, collect(m) AS medoids\n",
    "                                       WITH c, medoids + g AS newMedoids\n",
    "                                       CREATE (newCandidate:Candidate)\n",
    "                                       WITH c, newCandidate, newMedoids\n",
    "                                       MERGE (c)-[:HAS_NEIGHBOR]->(newCandidate)\n",
    "                                       WITH newMedoids, newCandidate\n",
    "                                       UNWIND newMedoids as newMedoid\n",
    "                                       MERGE (newCandidate)-[:HAS_MEDOID]->(newMedoid)\n",
    "                                       RETURN id(newCandidate) AS newCandidateId\n",
    "                                       LIMIT 1\"\"\",\n",
    "                                     {\"candidateId\": candidate_id,\n",
    "                                      \"k\": k,\n",
    "                                      \"label\": label})\n",
    "    return new_candidate_df.iloc[0, 0]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4f3b6521-a41b-4479-a156-71fc3ca22625",
   "metadata": {},
   "source": [
    "This function runs the full CLARANS algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "5e5d326e-f082-4963-b075-6080863cd8ef",
   "metadata": {},
   "outputs": [],
   "source": [
    "def run_clarans(projection, k, label, num_local=2, max_neighbor=None, verbose=False):\n",
    "    #If max_neighbor was not provided, calculate 1.25% times k(n-k)\n",
    "    if max_neighbor == None:\n",
    "        node_count_df = gds.run_cypher(f\"\"\"MATCH (n:{label}) RETURN count(*) as nodeCount\"\"\")\n",
    "        node_count = node_count_df.iloc[0,0]\n",
    "        max_neighbor = round(k*(node_count-k)*0.0125)\n",
    "        if verbose:\n",
    "            print(f\"max_neighbor: {max_neighbor}\")\n",
    "    min_cost = 999999999\n",
    "    # The i counter keeps track of the number of times we begin the search at a new randomly selected candidate node\n",
    "    i = 1\n",
    "    while i <= num_local:\n",
    "        current_candidate_id = create_new_candidate(k, label)\n",
    "        current_cost = calculate_candidate_cost(projection, current_candidate_id)\n",
    "        if verbose:\n",
    "            print(f\"Starting search from candidate {current_candidate_id} with cost {current_cost}\")\n",
    "        # The j counter keeps track of the number of times we have checked a neighbor of the currently selected node\n",
    "        j = 1\n",
    "        while j <= max_neighbor:\n",
    "            neighbor_candidate_id = create_neighboring_candidate(current_candidate_id, k, label)\n",
    "            neighbor_cost = calculate_candidate_cost(projection, neighbor_candidate_id)\n",
    "            if verbose:\n",
    "                print(f\"Neighbor cost: {neighbor_cost}\")\n",
    "            if neighbor_cost < current_cost:\n",
    "                j = 1\n",
    "                current_candidate_id = neighbor_candidate_id\n",
    "                current_cost = neighbor_cost\n",
    "                if verbose:\n",
    "                    print(f\"Current cost: {current_cost}\")\n",
    "            else:\n",
    "                j = j + 1\n",
    "        if current_cost < min_cost:\n",
    "            min_cost = current_cost\n",
    "            best_candidate_id = current_candidate_id\n",
    "            if verbose:\n",
    "                print(f\"Min cost: {min_cost}\")\n",
    "        i = i + 1\n",
    "    return best_candidate_id, min_cost"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0905457d-c5d0-4b8f-886f-5a768b6beed9",
   "metadata": {},
   "source": [
    "# PAM Functions\n",
    "To compare perfromance of CLARANS and PAM, we need a function to provide the input distance array for the PAM algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b2f408d0-604b-4586-8158-5ccaecde7e87",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_distance_array(projection, \n",
    "                       relationshipWeightProperty=None, \n",
    "                       concurrency=4):\n",
    "    all_pairs = gds.allShortestPaths.stream(projection, \n",
    "                                            relationshipWeightProperty = relationshipWeightProperty, \n",
    "                                            concurrency=concurrency)\n",
    "    distance_df = all_pairs.pivot(index='sourceNodeId', columns='targetNodeId', values='distance')\n",
    "    distance_array = distance_df.fillna(0).values\n",
    "    return distance_array, distance_df.columns"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "afe9ca5b-4d8b-44ca-a1ea-21886e8617e5",
   "metadata": {},
   "source": [
    "# Try on small genetic network\n",
    "## Load data to Neo4j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "615a05ae-3743-4468-bb28-d11225c0ae01",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "Empty DataFrame\n",
       "Columns: []\n",
       "Index: []"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gds.run_cypher(\"\"\"CREATE CONSTRAINT geneId FOR (p:Gene) REQUIRE p.id IS NODE KEY\"\"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "c2f1f266-5e86-4bf2-aebd-fdb2a778aea0",
   "metadata": {},
   "outputs": [],
   "source": [
    "edge_df = pd.read_csv('bio-CE-LC.edges', sep=' ', header=None)\n",
    "edge_list = edge_df.values.tolist()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "01b05ab2-c670-4070-9543-c974d4e5a2dc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "Empty DataFrame\n",
       "Columns: []\n",
       "Index: []"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gds.run_cypher(\"\"\"\n",
    "UNWIND $edgeList AS rel\n",
    "WITH rel[0] AS id1, rel[1] AS id2 \n",
    "MERGE (m1:Gene {id:id1})\n",
    "MERGE (m2:Gene {id:id2})\n",
    "MERGE (m1)-[:RELATES_TO]->(m2)\"\"\",\n",
    "               {\"edgeList\": edge_list})"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5c6fa94f-575c-42ef-9a96-cdd06e9adcce",
   "metadata": {},
   "source": [
    "## Create GDS projection"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "ddb3f2f8-67fe-431f-b9c7-30f472bf407b",
   "metadata": {},
   "outputs": [],
   "source": [
    "g_gene, result = gds.graph.project(\"genes\", \"Gene\", {\"RELATES_TO\": {\"orientation\": \"UNDIRECTED\"}})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "b99e7aca-8c99-4cd1-8989-23a4884628a2",
   "metadata": {},
   "outputs": [],
   "source": [
    "g_gene_connected, result, biggest_component_id = find_giant_component(g_gene, \"wccId\", \"gene_connected\", \"ConnectedGene\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "a180035f-f63f-471e-9175-19ae457b4524",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "fromGraphName                  genes\n",
       "nodeFilter               n.wccId = 0\n",
       "relationshipFilter                 *\n",
       "graphName             gene_connected\n",
       "nodeCount                        993\n",
       "relationshipCount               2600\n",
       "projectMillis                     62\n",
       "Name: 0, dtype: object"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "70c815d5-5d54-45a2-ade7-0f8d51f6ce9a",
   "metadata": {},
   "source": [
    "## Find medoids with CLARANS "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "26b36c43-e2e1-407a-bada-1628c6c9b83e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Elapsed seconds: 248.6279336229927\n"
     ]
    }
   ],
   "source": [
    "start_time = perf_counter()\n",
    "best_candidate_id, min_cost = run_clarans(g_gene_connected, 5, \"ConnectedGene\")\n",
    "end_time = perf_counter()\n",
    "print(f\"Elapsed seconds: {end_time - start_time}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "ca1d5d3a-8500-4ef9-bf48-5acb0227b2f9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1970 3837.0\n"
     ]
    }
   ],
   "source": [
    "print(best_candidate_id, min_cost)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8a268578-c554-4a9d-8a77-8cbfea42317f",
   "metadata": {},
   "source": [
    "## Find medoids with PAM"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "d94868c2-9b96-4dc1-9844-f2beda5d4000",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Elapsed seconds: 67.33841312400182\n"
     ]
    }
   ],
   "source": [
    "start_time = perf_counter()\n",
    "dist_array, array_index = get_distance_array(g_gene_connected)\n",
    "km = kmedoids.KMedoids(5, method=\"fasterpam\")\n",
    "c = km.fit(dist_array)\n",
    "end_time = perf_counter()\n",
    "print(f\"Elapsed seconds: {end_time - start_time}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "5cf455c8-d489-4761-843c-837e0d84db91",
   "metadata": {},
   "outputs": [],
   "source": [
    "medoid_ids = [array_index[i] for i in c.medoid_indices_]\n",
    "pam_candidate_df = gds.run_cypher(\"\"\"UNWIND $medoidIds as medoidId\n",
    "                                     MATCH (n) WHERE id(n) = medoidId\n",
    "                                     WITH collect(n) AS medoids\n",
    "                                     CREATE (c:Candidate)\n",
    "                                     WITH c, medoids\n",
    "                                     UNWIND medoids as m\n",
    "                                     MERGE (c)-[:HAS_MEDOID]->(m)\n",
    "                                     RETURN id(c) AS candidate_id\n",
    "                                     LIMIT 1\"\"\",\n",
    "                                  {\"medoidIds\": medoid_ids})\n",
    "pam_candidate_id = pam_candidate_df.iloc[0,0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "35d5825e-a1fc-47de-a852-b212f7a6ca5b",
   "metadata": {},
   "outputs": [],
   "source": [
    "pam_cost = calculate_candidate_cost(g_gene_connected, pam_candidate_id)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "8bd812cc-f89c-4803-a4fa-f144256c4695",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2033 3525.0\n"
     ]
    }
   ],
   "source": [
    "print(pam_candidate_id, pam_cost)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a9f79031-83de-4005-aeab-fd3395c8c705",
   "metadata": {},
   "source": [
    "What is the percentage improvement in the total distance with PAM vs. CLARANS?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "66338546-e293-4796-8092-390b0eb504e6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.08131352619233777"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(3837 - 3525)/3837"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d398336f-6778-4b8e-8246-d3165f55a53f",
   "metadata": {},
   "source": [
    "## Clean up"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "ac6ca38a-66d8-4162-938f-ab250baa6e5e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "graphName                                                   gene_connected\n",
       "database                                                             neo4j\n",
       "memoryUsage                                                               \n",
       "sizeInBytes                                                             -1\n",
       "nodeCount                                                              993\n",
       "relationshipCount                                                     2600\n",
       "configuration            {'relationshipProperties': {}, 'jobId': '72bf5...\n",
       "density                                                           0.002639\n",
       "creationTime                           2024-01-09T22:46:26.813185992+00:00\n",
       "modificationTime                       2024-01-09T22:46:26.876123796+00:00\n",
       "schema                   {'graphProperties': {}, 'nodes': {'Gene': {'wc...\n",
       "schemaWithOrientation    {'graphProperties': {}, 'nodes': {'Gene': {'wc...\n",
       "Name: 0, dtype: object"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gds.graph.drop(g_gene)\n",
    "gds.graph.drop(g_gene_connected)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "fc76af2f-5639-493e-9804-18f81febcd20",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "Empty DataFrame\n",
       "Columns: []\n",
       "Index: []"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gds.run_cypher(\"\"\"MATCH (n) CALL {WITH n DETACH DELETE n} IN TRANSACTIONS OF 1000 ROWS\"\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aa01fd40-b8d9-46ba-a14a-44f1041f88c1",
   "metadata": {},
   "source": [
    "# Try on larger collaboration network\n",
    "## Load data to Neo4j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "c9c8a267-8f88-4d4a-86aa-c97f39ea792d",
   "metadata": {},
   "outputs": [],
   "source": [
    "edge_df = pd.read_csv('ca-HepPh.mtx', sep=' ', skiprows=2, header=None)\n",
    "edge_list = edge_df.values.tolist()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "7913f42d-8654-451e-b9c6-1d9d8613ed08",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "Empty DataFrame\n",
       "Columns: []\n",
       "Index: []"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gds.run_cypher(\"\"\"CREATE CONSTRAINT authorId FOR (p:Author) REQUIRE p.id IS NODE KEY\"\"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "ac0e6437-6a0c-4970-a846-6d9bfb6b41d8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "Empty DataFrame\n",
       "Columns: []\n",
       "Index: []"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gds.run_cypher(\"\"\"\n",
    "UNWIND $edgeList AS rel\n",
    "WITH rel[0] AS id1, rel[1] AS id2 \n",
    "MERGE (m1:Author {id:id1})\n",
    "MERGE (m2:Author {id:id2})\n",
    "MERGE (m1)-[:WORKED_WITH]->(m2)\"\"\",\n",
    "               {\"edgeList\": edge_list})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "0b390c04-9cd1-4fc0-a8cf-b709864c4035",
   "metadata": {},
   "outputs": [],
   "source": [
    "g_authors, result = gds.graph.project(\"authors\", \"Author\", {\"WORKED_WITH\": {\"orientation\": \"UNDIRECTED\"}})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "188fa32a-f046-4447-a3e8-5d63e020e448",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "nodeProjection            {'Author': {'label': 'Author', 'properties': {}}}\n",
       "relationshipProjection    {'WORKED_WITH': {'aggregation': 'DEFAULT', 'or...\n",
       "graphName                                                           authors\n",
       "nodeCount                                                             11204\n",
       "relationshipCount                                                    235238\n",
       "projectMillis                                                           138\n",
       "Name: 0, dtype: object"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "1b3df6ad-26ea-4a58-beb6-186243974742",
   "metadata": {},
   "outputs": [],
   "source": [
    "g_authors_connected, result, biggest_component_id = find_giant_component(g_authors, \"wccId\", \"authors_connected\", \"ConnectedAuthor\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "df4d82f1-ca60-4a3c-a9e6-bae8f4e8a5bc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "fromGraphName                   authors\n",
       "nodeFilter                  n.wccId = 0\n",
       "relationshipFilter                    *\n",
       "graphName             authors_connected\n",
       "nodeCount                         11204\n",
       "relationshipCount                235238\n",
       "projectMillis                       156\n",
       "Name: 0, dtype: object"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b90ad27d-a88d-4589-89eb-3428a4eaa142",
   "metadata": {},
   "source": [
    "The full graph is the same as the subgraph, because the full graph is a connected graph. We'll use the full graph for our testing, and drop the subgraph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "id": "e7e7e984-d1fa-4d92-afa3-64dca8efd3c0",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Failed to write data to connection ResolvedIPv4Address(('34.28.32.244', 7687)) (ResolvedIPv4Address(('34.28.32.244', 7687)))\n",
      "Failed to write data to connection IPv4Address(('80102ec4.databases.neo4j.io', 7687)) (ResolvedIPv4Address(('34.28.32.244', 7687)))\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "graphName                                                authors_connected\n",
       "database                                                             neo4j\n",
       "memoryUsage                                                               \n",
       "sizeInBytes                                                             -1\n",
       "nodeCount                                                            11204\n",
       "relationshipCount                                                   231960\n",
       "configuration                                                           {}\n",
       "density                                                           0.001848\n",
       "creationTime                           2024-01-10T16:14:54.145022085+00:00\n",
       "modificationTime                       2024-01-10T16:14:54.144915127+00:00\n",
       "schema                   {'graphProperties': {}, 'nodes': {'Author': {'...\n",
       "schemaWithOrientation    {'graphProperties': {}, 'nodes': {'Author': {'...\n",
       "Name: 0, dtype: object"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gds.graph.drop(g_authors_connected)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f5b5ca2c-733b-4418-a128-4077090744ba",
   "metadata": {},
   "source": [
    "## Find medoids with CLARANS "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "a909bc14-6838-47dd-ad85-deb927d30593",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Elapsed seconds: 1380.257974052991\n"
     ]
    }
   ],
   "source": [
    "start_time = perf_counter()\n",
    "best_candidate_id, min_cost = run_clarans(g_authors, 5, \"Author\")\n",
    "end_time = perf_counter()\n",
    "print(f\"Elapsed seconds: {end_time - start_time}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "335a00c9-8e6d-41ed-9ba1-a4f8b35efda3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12690 31164.0\n"
     ]
    }
   ],
   "source": [
    "print(best_candidate_id, min_cost)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "27384261-1fcb-4574-af19-d8f06184a298",
   "metadata": {},
   "source": [
    "What percetage of nodes were considered as medoid candidates?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "a6772e2e-327f-46a8-b9a8-2b4c0428a73b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>totalNodeCount</th>\n",
       "      <th>candidateCount</th>\n",
       "      <th>candidatePercent</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>11204</td>\n",
       "      <td>1997</td>\n",
       "      <td>17.823991</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   totalNodeCount  candidateCount  candidatePercent\n",
       "0           11204            1997         17.823991"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gds.run_cypher(\"\"\"MATCH (a:Author)\n",
    "                  WITH count(*) AS totalNodeCount,\n",
    "                  SUM(CASE WHEN EXISTS {(a)<-[:HAS_MEDOID]-(:Candidate)} THEN 1 else 0 END) \n",
    "                      AS candidateCount\n",
    "                  RETURN totalNodeCount, candidateCount, \n",
    "                  candidateCount * 100.0 / totalNodeCount AS candidatePercent\"\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8e58e6bd-b71a-4637-98c9-31137f4f5f0f",
   "metadata": {},
   "source": [
    "How many unique author pairs had the shortest path calculated?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "cc9de496-54f0-4df5-a016-7895bd4d1c32",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>authorPairCount</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>20379385</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   authorPairCount\n",
       "0         20379385"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gds.run_cypher(\"\"\"MATCH (a1:Author)-[:HAS_DISTANCE]-(a2:Author)\n",
    "                  WHERE id(a1) < id(a2)\n",
    "                  WITH DISTINCT a1, a2\n",
    "                  RETURN COUNT(*) AS authorPairCount\"\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "92dbe75a-77dc-45bb-bba2-2927325169c2",
   "metadata": {},
   "source": [
    "How many total author pair shortest paths could have been calculated?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "911591ef-b956-4ec1-a1ab-e6977738c792",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "62759206.0"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "11204*(11204-1)/2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e366dfe7-a6d3-42b0-b24d-7c561221969b",
   "metadata": {},
   "source": [
    "What percent of possible shortest paths were calculated?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "86473159-1abd-4006-96e9-62c586080e9c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "32.472343579362686"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "20379385/62759206*100.0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c8f92c3b-d1fd-476a-9547-40f801ce4795",
   "metadata": {},
   "source": [
    "What percent of shortest paths that were calculated were redundant because the relationships are undirected?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "adb00ccc-89d3-4f5e-be88-c4c267087e88",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>distanceCount</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>22374388</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   distanceCount\n",
       "0       22374388"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gds.run_cypher(\"\"\"MATCH ()-[:HAS_DISTANCE]->() RETURN count(*) as distanceCount\"\"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "2b8394cb-ecb9-4693-a7a6-4f3ad104037b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9.789318961293484"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(22374388-20379385)/20379385*100.0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f41c068e-deda-49c2-aa27-2cdfd2b2f0a0",
   "metadata": {},
   "source": [
    "## Find medoids with PAM"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "74fffdae-cf2e-4c2f-98f2-964d47e44f42",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Elapsed seconds: 8890.122705282003\n"
     ]
    }
   ],
   "source": [
    "start_time = perf_counter()\n",
    "dist_array, array_index = get_distance_array(g_authors)\n",
    "km = kmedoids.KMedoids(5, method=\"fasterpam\")\n",
    "c = km.fit(dist_array)\n",
    "end_time = perf_counter()\n",
    "print(f\"Elapsed seconds: {end_time - start_time}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "176c310d-1e4c-4127-bbc2-f18c477dc763",
   "metadata": {},
   "source": [
    "Create a candidate node based on the PAM medoids."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "5de8f05f-aa77-4f10-911d-6712fd1f5b4e",
   "metadata": {},
   "outputs": [],
   "source": [
    "medoid_ids = [array_index[i] for i in c.medoid_indices_]\n",
    "pam_candidate_df = gds.run_cypher(\"\"\"UNWIND $medoidIds as medoidId\n",
    "                                     MATCH (n) WHERE id(n) = medoidId\n",
    "                                     WITH collect(n) AS medoids\n",
    "                                     CREATE (c:Candidate)\n",
    "                                     WITH c, medoids\n",
    "                                     UNWIND medoids as m\n",
    "                                     MERGE (c)-[:HAS_MEDOID]->(m)\n",
    "                                     RETURN id(c) AS candidate_id\n",
    "                                     LIMIT 1\"\"\",\n",
    "                                  {\"medoidIds\": medoid_ids})\n",
    "pam_candidate_id = pam_candidate_df.iloc[0,0]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "831eb1ef-e388-4ee6-8a88-d3ae0d2d8160",
   "metadata": {},
   "source": [
    "Calculate the cost for the PAM candidate."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "ae4e558b-7204-4671-9e2b-72bb51369699",
   "metadata": {},
   "outputs": [],
   "source": [
    "pam_cost = calculate_candidate_cost(g_authors, pam_candidate_id)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "55c29d1a-d6e9-45fd-b065-170ab0be2133",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "13391 29333.0\n"
     ]
    }
   ],
   "source": [
    "print(pam_candidate_id, pam_cost)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c67671f4-eccb-4b98-976a-a3d537f2161a",
   "metadata": {},
   "source": [
    "What is the percentage improvement in the total distance with PAM vs. CLARANS?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "332f3b9c-a3ab-44de-8d28-8198090ad406",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0587536901553074"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(31164 - 29333)/31164"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "392447d6-272a-444f-9431-bcccbca021f0",
   "metadata": {},
   "source": [
    "What was the percentage decrease in run time for CLARANS vs. PAM?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "211ce8b3-3938-48f3-9cbf-582757090220",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "84.4769403824522"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(8890-1380)/8890*100.0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7ce7f4ad-59ff-4739-b18b-c68206af08b4",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "clarans",
   "language": "python",
   "name": "clarans"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}