tutorials/Billion-scale 2-approximated vertex cover with GRAPE.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "0df9a85c",
   "metadata": {},
   "source": [
    "# Billion-scale 2-approximated vertex cover with 🍇 GRAPE 🍇\n",
    "In this tutorial, I will show you how to use the [GRAPE library](https://github.com/AnacletoLAB/grape) to compute an approximate vertex cover of a graph. A vertex cover is a set of vertices that includes at least one endpoint of every edge in the graph, and the goal in finding a vertex cover is to minimize the number of vertices in the cover. We will use GRAPE to compute a 2-approximate vertex cover, which is a cover that is guaranteed to be at most twice as large as the smallest possible vertex cover for the given graph.\n",
    "\n",
    "I will then briefly explain what the [NP](https://en.wikipedia.org/wiki/NP_(complexity)) and [APX](https://en.wikipedia.org/wiki/APX) complexity classes are, and the 2-approximated algorithm for vertex cover and the relative heuristics available in [GRAPE!](https://github.com/AnacletoLAB/grape).\n",
    "\n",
    "By the end of the tutorial, you will have a good understanding of how to use [GRAPE!](https://github.com/AnacletoLAB/grape) to compute a 2-approximated vertex cover of a graph and apply this knowledge to your projects.\n",
    "\n",
    "[Remember to ⭐ GRAPE!](https://github.com/AnacletoLAB/grape)\n",
    "\n",
    "### What is GRAPE?\n",
    "[🍇🍇 GRAPE 🍇🍇](https://github.com/AnacletoLAB/grape) is a graph processing and embedding library that enables users to easily manipulate and analyze graphs. With [GRAPE](https://github.com/AnacletoLAB/grape), users can efficiently load and preprocess graphs, generate random walks, and apply various node and edge embedding models. Additionally, [GRAPE](https://github.com/AnacletoLAB/grape) provides a fair and reproducible evaluation pipeline for comparing different graph embedding and graph-based prediction methods.\n",
    "\n",
    "![features in GRAPE](https://github.com/AnacletoLAB/grape/raw/main/images/sequence_diagram.png?raw=true)\n",
    "\n",
    "*The methods shown in the tutorial are available from the nightly version of 🍇 on GitHub, which we'll release on PyPI next week. (Today is 28/12/2022)*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1e666f1e",
   "metadata": {},
   "source": [
    "## What is a vertex cover?\n",
    "In a graph, a [vertex cover](https://en.wikipedia.org/wiki/Vertex_cover) is a set of vertices that includes at least one endpoint of every edge in the graph. The concept of a vertex cover is useful in graph theory because it can be used to find a small set of vertices that \"covers\" all the edges of the graph, meaning that every edge in the graph is incident to at least one vertex in the cover.\n",
    "\n",
    "In the following illustration we show an an example of a graph with a vertex cover, where the red nodes containing an eye represent the nodes in the cover.\n",
    "\n",
    "<img src=\"https://github.com/AnacletoLAB/grape/blob/main/images/approximated_vertex_cover.jpg?raw=true\" width=500 />\n",
    "\n",
    "### NP\n",
    "In computer science, the class [NP](https://en.wikipedia.org/wiki/NP_(complexity)) (short for \"nondeterministic polynomial time\") is a set of problems for which it is possible to verify the correctness of a proposed solution in polynomial time, it is not known whether it's possible to find a solution in polynomial time.\n",
    "\n",
    "The class NP includes many fundamental problems in computer science and mathematics, like deciding if a logic formula can be satisfied ([SAT](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem)), factoring a number into its prime factors ([Factorization](https://en.wikipedia.org/wiki/Factorization)), and finding a cycle that visits every node in a graph ([Hamiltonian cycle](https://en.wikipedia.org/wiki/Hamiltonian_path)).\n",
    "\n",
    "NP problems are the foundation of most modern cryptography, so that system can quickly check that you know the answer, but finding it would require thousands of years.\n",
    "\n",
    "\n",
    "#### NP = P?\n",
    "The `NP = P` problem is a problem in computer science that asks whether every problem in the class NP (nondeterministic polynomial time) can be solved in polynomial time.\n",
    "\n",
    "The `NP = P` problem is one of the most important open problems in computer science, and it has attracted a great deal of attention from researchers over the years. If it were shown that `NP = P`, it would mean that many important problems that are currently believed to be computationally hard could be solved efficiently, which would have significant implications for a wide range of fields, including mathematics, computer science, and engineering.\n",
    "\n",
    "However, despite much effort, the `NP = P` problem remains unsolved, and it is not known whether `NP = P` or whether there are problems in NP that cannot be solved in polynomial time. This has led to the development of other complexity classes, such as `NP-hard` and `NP-complete`, which capture the complexity of certain types of problems.\n",
    "\n",
    "[The impact of proving `P=NP` is big enough that they made a movie about it.](https://en.wikipedia.org/wiki/Travelling_Salesman_(2012_film))\n",
    "\n",
    "### NPC\n",
    "\n",
    "The [NP-Complete](https://en.wikipedia.org/wiki/NP-completeness) problems are a set which are both hard to solve and to verify. Most commonly, the only way to verify that the solution is optimal is to solve the problem again.\n",
    "\n",
    "The class NPC includes many problems related to optimization and decision-making. Some examples of problems known to be in NPC are the [traveling salesman problem](https://en.wikipedia.org/wiki/Travelling_salesman_problem), the [knapsack problem](https://en.wikipedia.org/wiki/Knapsack_problem), and the [vertex cover](https://en.wikipedia.org/wiki/Vertex_cover) problem.\n",
    "\n",
    "The [vertex cover](https://en.wikipedia.org/wiki/Vertex_cover) problem is known to be in NPC, meaning that solving it would require exponential time, and the only way to verify that our solution is the **minimal** vertex cover is to recompute it.\n",
    "\n",
    "It's not possible to solve these problems on anything but toy data, so we try to find a close enough approximation.\n",
    "\n",
    "### APX\n",
    "In computer science, the class [APX](https://en.wikipedia.org/wiki/APX) (short for \"approximation\") is a set of problems for which it is possible to find approximate solutions that are guaranteed to be within a certain factor of the optimal solution. In other words, for any problem in APX, there exists an algorithm that can find a solution that is at most a certain multiple of the optimal solution, where the multiple is known as the \"approximation factor.\"\n",
    "\n",
    "The class [APX](https://en.wikipedia.org/wiki/APX) is important because it includes many problems that are believed to be computationally hard and for which it is not known whether efficient exact solutions exist. By finding approximate solutions to these problems, it is possible to get some of the benefits of an exact solution without the computational cost of finding one.\n",
    "\n",
    "One example of a problem in [APX](https://en.wikipedia.org/wiki/APX) is the vertex cover problem. There are several different algorithms that can be used to find approximate solutions to the vertex cover problem, with approximation factors ranging from 2 to 4. This means that these algorithms can find a vertex cover that is at most twice (or four times, depending on the algorithm) as large as the smallest possible vertex cover for a given graph.\n",
    "\n",
    "### 2-approximated vertex cover\n",
    "[The 2-approximated vertex cover algorithm](https://d1wqtxts1xzle7.cloudfront.net/27074702/gavril-1980-edgedomset-libre.pdf?1390871693=&response-content-disposition=inline%3B+filename%3DEdge_dominating_sets_in_graphs.pdf&Expires=1672255140&Signature=g~-Mr3WPULKivgM4M8I5ONXekgtWHknBuKtZXzvfUmIedjyjVL4kFtAy6wvi9sOyCIw6gXrGe1SrXihn9Jq3N15PiX7HVZxHuOh8e-tMg5~7UM~RUw1aZJJcW6Zr~Wc0RSwhmGdjQkpEAD6S4MaBbVbR6KtfkwkLZkVGhmTMR1QnNAAdFWQEM60l0eNNgdAu9l3ki02EQeq-ohAkJjkQW3LZo5WLe1fvLUelU6aDjkqGpzhILPkPQzoxFIlDGcWMbdVu1V9sYhP3zFmYS2SN-afUQsn~mmMQU1yxDEMeuJmV-5V-dUQH~VLxk5e0Y3F5LyawvBGU0gQR13zBIvRelA__&Key-Pair-Id=APKAJLOHF5GGSLRBV4ZA) can be described as follows:\n",
    "\n",
    "1. Initialize an empty set, which we call here `cover`. This will be used to store the vertices that are included in the vertex cover.\n",
    "2. Iterate over all the edges in the graph. For each edge `(src, dst)`, do the following:\n",
    "\n",
    "    a. If either `src` or `dst` is already in the cover set, skip this edge and move on to the next one.\n",
    "    \n",
    "    b. If neither `src` nor `dst` is in the cover set, add both `src` and `dst` to the cover set.\n",
    "    \n",
    "    c. Repeat this process until all edges have been processed. At this point, the cover set will contain a 2-approximate solution to the vertex cover problem.\n",
    "    \n",
    "6. The idea behind this algorithm is to greedily add vertices to the cover set as long as they are needed to cover an uncovered edge. This results in a vertex cover that is as small as possible, but it is only guaranteed to be at most twice as large as the smallest possible vertex cover for the given graph.\n",
    "\n",
    "```python\n",
    "cover = set()\n",
    "for src, dst im graph.edges():\n",
    "    if src in cover or dst in cover:\n",
    "        continue\n",
    "    cover.add(src)\n",
    "    cover.add(dst)\n",
    "```\n",
    "\n",
    "Also the following approach that only inserts the source node and not the destination will lead to an approximated vertex cover. Which on the two approaches is better? **It heavily depends on the order of the edges!**\n",
    "\n",
    "The following approach seems to be better when the source nodes are sorted by decreasing node degrees.\n",
    "\n",
    "Note that **for the following algorithm there is no guarantee for it to be a 2-approximation!**\n",
    "\n",
    "```python\n",
    "cover = set()\n",
    "for src, dst im graph.edges():\n",
    "    if src in cover or dst in cover:\n",
    "        continue\n",
    "    cover.add(src)\n",
    "```\n",
    "\n",
    "#### On the order of the edges\n",
    "Yes, the order in which the edges are processed can have a significant impact on the performance of the 2-approximate greedy algorithm for the vertex cover problem. Depending on the topology of the graph, different edge orders may result in different sizes of the vertex cover.\n",
    "\n",
    "For example, if the graph has a lot of high-degree vertices, then processing these high-degree nodes first may result in a smaller vertex cover.\n",
    "\n",
    "The implementation available in GRAPE includes several different approaches for ordering the edges:\n",
    "\n",
    "* `arbitrary`: This approach uses the order of the edges as they are loaded into the graph. This may not be the most effective approach, because the order in which the edges are loaded into the graph is often arbitrary and may not reflect the structure of the graph.\n",
    "\n",
    "* `decreasing_node_degree`: This approach sorts the edges by decreasing node degree, which means that edges incident to high-degree vertices are processed first. This may result in a smaller vertex cover, because high-degree vertices are more likely to be included in the cover set.\n",
    "\n",
    "* `increasing_node_degree`: This approach sorts the edges by increasing node degree, which means that edges incident to low-degree vertices are processed first. This may result in a larger vertex cover, because more vertices will need to be included in the cover set in order to cover all the edges.\n",
    "\n",
    "* `random`: This approach shuffles the edges using a random seed. This may result in a more diverse set of vertex covers, depending on the random seed used.\n",
    "\n",
    "Overall, the choice of edge order will depend on the specific characteristics of the graph and the desired properties of the vertex cover. Different edge orders may be more or less effective for different types of graphs, and it may be worth experimenting with different orders to find the one that works best for a given application.\n",
    "\n",
    "### What are approximated vertex covers for?\n",
    "\n",
    "Approximate solutions to the vertex cover problem can be useful in situations where finding an exact solution is either computationally infeasible or not necessary. For example, approximate solutions can be used to get a good sense of the structure of a graph without having to spend a lot of time computing an exact solution.\n",
    "\n",
    "Approximate solutions to the vertex cover problem can also be useful as a starting point for other algorithms or as a subroutine in more complex algorithms. For example, an approximate vertex cover can be used as an initial solution for a local search or metaheuristic algorithm, which can then be improved upon by making small changes to the cover.\n",
    "\n",
    "We will use in a future tutorial how we can use this [to compute efficiently the number of triangles and clustering coefficient of large graphs](https://davidbader.net/publication/2013-g-ba/2013-g-ba.pdf)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2de848e2",
   "metadata": {},
   "source": [
    "## Installing GRAPE\n",
    "First, we install the GRAPE library from PyPI:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "8e5462cc",
   "metadata": {},
   "outputs": [],
   "source": [
    "!pip install grape -qU"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2c4c963f",
   "metadata": {},
   "source": [
    "## Experiments\n",
    "Welcome to the experiments section of this tutorial! In this section, we will put our knowledge into practice by applying the 2-approximated vertex cover algorithm on four different graphs: the [KGCOVID19 knowledge graph](https://www.cell.com/patterns/fulltext/S2666-3899(20)30203-8?_returnURL=https%3A%2F%2Flinkinghub.elsevier.com%2Fretrieve%2Fpii%2FS2666389920302038%3Fshowall%3Dtrue), the [Friendster graph](https://networkrepository.com/friendster.php), the [ClueWeb09 web graph](https://networkrepository.com/web-ClueWeb09.php), and [the WikiData graph](https://www.wikidata.org/wiki/Wikidata:Main_Page).\n",
    "\n",
    "We run these experiments on a machine with 24 threads and 12 cores.\n",
    "\n",
    "**Do note that, for the limits of memory of my desktop, I will restart the jupyter after running the experiment on each of the large graphs.**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "31fb6fdc",
   "metadata": {},
   "source": [
    "In my machine I only have 24 threads. You can estimate the expected computation time by interpolating the time estimates on 24 threads and the amount you have:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "00549fe2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "24"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import os\n",
    "\n",
    "os.cpu_count()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c2253bbb",
   "metadata": {},
   "source": [
    "Also, this machine has about `128GB` of RAM:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "7cc9ed99",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "125.7713851928711"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import psutil\n",
    "    \n",
    "psutil.virtual_memory().total / 1024**3 # total physical memory in Bytes"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "15280e49",
   "metadata": {},
   "source": [
    "### KGCOVID19\n",
    "We kick off our experiments with a relatively small graph, considering the sizes of the networks we will tackle by the end of it: KGCOVID19, with `574K` nodes and `18M` edges.\n",
    "\n",
    "#### What is KGCOVID19?\n",
    "[KGCOVID19](https://doi.org/10.1016%2Fj.patter.2020.100155) is a framework for producing knowledge graphs (KGs) that integrate and integrate biomedical data related to the COVID-19 pandemic. The framework is designed to be flexible and customizable, allowing researchers to create KGs for different downstream applications, including machine learning tasks, hypothesis-based querying, and browsable user interfaces for exploring and discovering relationships in COVID-19 data. The goal of KGCOVID19 is to provide an up-to-date, integrated source of data on SARS-CoV-2 and related viruses, including SARS-CoV and MERS-CoV, to support the biomedical research community in its efforts to respond to the COVID-19 pandemic. The framework can also be applied to other situations where siloed biomedical data must be quickly integrated for various research purposes, including future pandemics."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "2c0b685e",
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 33.8 s, sys: 3.56 s, total: 37.4 s\n",
      "Wall time: 10.7 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "from grape.datasets.kghub import KGCOVID19\n",
    "\n",
    "kgcovid19 = KGCOVID19()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5901df14",
   "metadata": {},
   "source": [
    "We display the number of nodes, `574K` and of undirected edges `18M`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "878ffc06",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(574232, 18251238)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kgcovid19.get_number_of_nodes(), kgcovid19.get_number_of_edges()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "55921909",
   "metadata": {},
   "source": [
    "And now we compute a 2-approximated vertex cover of KGCOVID19. We start by using the arbitrary approach:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "9c35198a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 20.6 ms, sys: 0 ns, total: 20.6 ms\n",
      "Wall time: 13.2 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "217552"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "cover = kgcovid19.get_approximated_vertex_cover(\n",
    "    approach=\"arbitrary\",\n",
    "    sequential=True,\n",
    "    insert_only_source=False\n",
    ")\n",
    "\n",
    "cover.sum()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7afc2543",
   "metadata": {},
   "source": [
    "This vertex cover required `37%` of the nodes in the graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "7264c5af",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.3788573259588459"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "217552 / 574232"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bee04f01",
   "metadata": {},
   "source": [
    "We can now try the approach sorting by decreasing node degree:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "5fc845f5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 79.7 ms, sys: 0 ns, total: 79.7 ms\n",
      "Wall time: 47 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "180150"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "cover = kgcovid19.get_approximated_vertex_cover(\n",
    "    approach=\"decreasing_node_degree\",\n",
    "    sequential=True,\n",
    "    insert_only_source=True\n",
    ")\n",
    "\n",
    "cover.sum()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6b6ea0e2",
   "metadata": {},
   "source": [
    "Here the result was a bit better! We are down to `31%` of the nodes!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "542c46da",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.3137233731314173"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "180150 / 574232"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3270c2a9",
   "metadata": {},
   "source": [
    "### Friendster\n",
    "[Friendster](https://en.wikipedia.org/wiki/Friendster) was a social networking service launched in 2002. It was one of the first social networking sites and was popular in the early 2000s. The site allowed users to connect with friends and meet new people through the use of personal profiles and networks of friends. Friendster was initially successful but eventually faced competition from more recent social networking sites such as MySpace and Facebook. In 2011, the company announced that it was transitioning from a social networking site to a social gaming site, and in 2015 it was acquired by a Malaysian company.\n",
    "\n",
    "#### What is the network repository?\n",
    "[Network Repository](https://networkrepository.com/index.php) is a scientific network data repository that provides interactive visualization and mining tools for analyzing and exploring network data. It is the first interactive repository of its kind. Network Repository is intended to facilitate scientific research on networks by making it easier for researchers to access and analyze an extensive network data collection. It is a valuable resource for researchers in various fields, including network science, bioinformatics, machine learning, data mining, physics, and social science."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9f30b201",
   "metadata": {},
   "source": [
    "#### ⚠️⚠️⚠️ WARNING: Make sure you have enough disk space! ⚠️⚠️⚠️\n",
    "*Please be aware that this graph is not small and requires a significant amount of disk space to store and work with. Before proceeding with the tutorial, ensure you have enough free space on your hard drive or other storage devices to accommodate the size of the graph. If you do not have sufficient space, you may encounter errors or other issues when downloading or working with the graph. It is important to ensure that you have enough space available before proceeding. If necessary, consider freeing up additional space on your device to make room for the graph.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "afafaae2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "97G\t/bfd/graphs/networkrepository/SocFriendster\r\n"
     ]
    }
   ],
   "source": [
    "!du -sh /bfd/graphs/networkrepository/SocFriendster"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8f15366b",
   "metadata": {},
   "source": [
    "In the next cell we retrieve and load the Friendster dataset from GRAPE, dataset from the [network repository](https://networkrepository.com/index.php).. Do note that we are configuring it to not load the node names and edge types in order to conserve memory. The cell also includes a directive to measure and display the execution time of the code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "bb5927ad",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 40min 10s, sys: 1min 11s, total: 41min 21s\n",
      "Wall time: 4min 57s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "from grape.datasets.networkrepository import SocFriendster\n",
    "\n",
    "friendster = SocFriendster(\n",
    "    # We cannot load the node names, as the would require too much memory\n",
    "    # for my poor old desktop.\n",
    "    load_nodes=False,\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b30f59e5",
   "metadata": {},
   "source": [
    "We display the number of nodes, `65.6M`, and of undirected edges, `1.8G`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "fdbee4bf",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(65608366, 1806067135)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "friendster.get_number_of_nodes(), friendster.get_number_of_edges()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "220ae65d",
   "metadata": {},
   "source": [
    "We start by computing a 2-approximated vertex cover using the arbitrary approach:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "9246eb75",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 7.73 s, sys: 729 ms, total: 8.46 s\n",
      "Wall time: 7.9 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "37992302"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "cover = friendster.get_approximated_vertex_cover(\n",
    "    approach=\"arbitrary\",\n",
    "    sequential=True,\n",
    "    insert_only_source=False,\n",
    ")\n",
    "\n",
    "cover.sum()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "82147e79",
   "metadata": {},
   "source": [
    "This vertex cover requires about `57%` of the nodes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "7112ee1b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.5790770951375317"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "37992302 / 65608366"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4a4dff48",
   "metadata": {},
   "source": [
    "Then we move to the decreasing node degrees approach:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "d4abc378",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 27.1 s, sys: 482 ms, total: 27.6 s\n",
      "Wall time: 14.1 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "31641804"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "cover = friendster.get_approximated_vertex_cover(\n",
    "    approach=\"decreasing_node_degree\",\n",
    "    sequential=True,\n",
    "    insert_only_source=True,\n",
    ")\n",
    "\n",
    "cover.sum()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "04add47c",
   "metadata": {},
   "source": [
    "This vertex cover is better, as it requires about `48%` of the nodes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "90883ad8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.4822830673758892"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "31641804 / 65608366"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5074f7bb",
   "metadata": {},
   "source": [
    "### ClueWeb\n",
    "[The ClueWeb09 dataset](http://lemurproject.org/clueweb09/) was created to support research on information retrieval and related human language technologies; it consists of about `1.7` billion web pages that were collected in January and February 2009 and the roughly `8` billion undirected links.\n",
    "\n",
    "It is used for research on information retrieval and related human language technologies and is used by several tracks of the TREC conference. The dataset includes web pages in various languages and a web graph that includes unique URLs and total outlinks for the entire dataset and for a subset called TREC Category B (the first 50 million English pages). The ClueWeb09 dataset and subsets are distributed in different formats, including as tarred/gzipped files on hard disk drives and as a subset that is downloaded from the web. The Lemur Project provides online services for searching and interacting with the ClueWeb09 dataset, including an Indri search engine for searching the English and Japanese subsets and Wikipedia, as well as a batch query service and an attribute lookup service. The Lemur Project also offers hosted copies of the ClueWeb09 dataset for organizations that have licenses to use it.\n",
    "\n",
    "*We also retrieve this graph from [Network Repository](https://networkrepository.com/index.php)*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "be4ca962",
   "metadata": {},
   "source": [
    "#### ⚠️⚠️⚠️ This is a big graph! Make sure you have the disk space! ⚠️⚠️⚠️\n",
    "*This is a warning to ensure that users have sufficient disk space before downloading and using a large graph. It is important to ensure that you have enough space on your hard drive or another storage device to accommodate the graph size, as attempting to download or work with a graph that is too large for your available space can lead to errors and other issues. It is advisable to check your available disk space before downloading or working with a large graph and free up additional space if necessary.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "8a437d6f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "631G\t/bfd/graphs/networkrepository/WebClueweb09/\r\n"
     ]
    }
   ],
   "source": [
    "!du -sh /bfd/graphs/networkrepository/WebClueweb09/"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5c9525bb",
   "metadata": {},
   "source": [
    "In the following cell we retrieve and load the `Clueweb09` dataset from the [network repository](https://networkrepository.com/index.php). We configure it to not load the node names in order to conserve memory. The cell also includes a directive to measure and display the execution time of the code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "5e6a8aba",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 2h 55min 34s, sys: 8min 16s, total: 3h 3min 51s\n",
      "Wall time: 37min 58s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "from grape.datasets.networkrepository import WebClueweb09\n",
    "\n",
    "clueweb = WebClueweb09(\n",
    "    # We cannot load the node names, as the would require too much memory\n",
    "    # for my poor old desktop.\n",
    "    load_nodes=False,\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0743a6c8",
   "metadata": {},
   "source": [
    "We display the number of nodes, `1.68G`, and of undirected edges, `7.8G`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "3ea0be87",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1684868322, 7811385827)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clueweb.get_number_of_nodes(), clueweb.get_number_of_edges()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1198087a",
   "metadata": {},
   "source": [
    "We compute the vertex cover of ClueWeb using the decreasing node degrees approach:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "45575c12",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 4min 24s, sys: 23.7 s, total: 4min 47s\n",
      "Wall time: 2min 40s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "cover = clueweb.get_approximated_vertex_cover(\n",
    "    approach=\"decreasing_node_degree\",\n",
    "    sequential=True,\n",
    "    insert_only_source=True,\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "0a9eef3f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "277934787"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cover.sum()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a194ca53",
   "metadata": {},
   "source": [
    "This vertex cover uses only `16%` of the nodes!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "bb81e781",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.16495935223595473"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "277934787 / 1684868322"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2c84125c",
   "metadata": {},
   "source": [
    "## WikiData\n",
    "[WikiData](https://www.wikidata.org/wiki/Wikidata:Main_Page) is a collaborative, multilingual, free knowledge base that can be read and edited by humans and machines. It provides structured data representing the relationships between concepts and entities, including real-world objects, events, ideas and abstract concepts. The data in WikiData is organized into a graph structure, with nodes representing concepts or entities and edges representing relationships between them. For example, a node for the idea \"dog\" might be connected to other nodes representing specific dog breeds, such as \"Labrador Retriever\" or \"Poodle,\" through edges that define the relationship \"breed of.\"\n",
    "\n",
    "The WikiData graph is constantly growing and changing as users contribute new data and edit existing data. It is based on a flexible data model that allows for creation of new properties and classes to represent the relationships between concepts and entities. The WikiData graph is used in various applications, including data integration, natural language processing, and machine learning. It also provides structured data for Wikipedia and other Wikimedia projects."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3f3f7fe8",
   "metadata": {},
   "source": [
    "#### ⚠️⚠️⚠️ This is a big graph! Make sure you have the disk space! ⚠️⚠️⚠️\n",
    "*This is a warning to ensure that users have sufficient disk space before downloading and using a large graph. It is important to ensure that you have enough space on your hard drive or another storage device to accommodate the graph size, as attempting to download or work with a graph that is too large for your available space can lead to errors and other issues. It is advisable to check your available disk space before downloading or working with a large graph and free up additional space if necessary.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "8010181d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1,7T\t/bfd/graphs/wikidata/WikiData\r\n"
     ]
    }
   ],
   "source": [
    "!du -sh /bfd/graphs/wikidata/WikiData"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ab979081",
   "metadata": {},
   "source": [
    "In the next cell we retrieve and load the WikiData dataset from GRAPE, directly from [WikiData's website](https://www.wikidata.org/wiki/Wikidata:Main_Page). Do note that we are configuring it to not load the node names and edge types in order to conserve memory. The cell also includes a directive to measure and display the execution time of the code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "d1b8b27e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1h 54min 27s, sys: 5min 4s, total: 1h 59min 31s\n",
      "Wall time: 20min 22s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "from grape.datasets.wikidata import WikiData\n",
    "\n",
    "wikidata = WikiData(\n",
    "    # We cannot load the node names, as the would require too much memory\n",
    "    # for my poor old desktop.\n",
    "    load_nodes=False,\n",
    "    # Same thing for the edge types.\n",
    "    load_edge_types=False\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "033dc051",
   "metadata": {},
   "source": [
    "We display the number of nodes, `1.29G` and of undirected edges `5G`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "9ee9bc66",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1294126247, 5040170396)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "wikidata.get_number_of_nodes(), wikidata.get_number_of_edges()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "714b43a1",
   "metadata": {},
   "source": [
    "We proceed to compute the 2-approximated vertex cover of WikiData."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "692c5296",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 19 s, sys: 7.99 s, total: 27 s\n",
      "Wall time: 20.3 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "290732842"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "cover = wikidata.get_approximated_vertex_cover(\n",
    "    approach=\"arbitrary\",\n",
    "    sequential=True,\n",
    "    insert_only_source=False,\n",
    ")\n",
    "\n",
    "cover.sum()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "511ec38b",
   "metadata": {},
   "source": [
    "We see that by using the second algorithm, which sorts the source nodes by decrease node degree, we achieve a smaller approximated vertex cover. This requires a bit more time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "725abe03",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1min 38s, sys: 7.99 s, total: 1min 46s\n",
      "Wall time: 1min 1s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "202196618"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "cover = wikidata.get_approximated_vertex_cover(\n",
    "    approach=\"decreasing_node_degree\",\n",
    "    sequential=True,\n",
    "    insert_only_source=True,\n",
    ")\n",
    "\n",
    "cover.sum()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "829e24aa",
   "metadata": {},
   "source": [
    "This vertex cover uses only the 15% of the nodes!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "f1602b3c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.15624180289112086"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "202196618 / 1294126247"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3a33eee6",
   "metadata": {},
   "source": [
    "Now we use the increasing node degree, which as could be expected, leads to a larger vertex cover. Since this is also a 2-approximation, the fact that this one is almost double of the previous one means that the previous one **is quite close to the optimal vertex cover**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "092855cc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1min 7s, sys: 7.7 s, total: 1min 14s\n",
      "Wall time: 40.1 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "386277067"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "cover = wikidata.get_approximated_vertex_cover(\n",
    "    approach=\"increasing_node_degree\",\n",
    "    sequential=True,\n",
    "    insert_only_source=False,\n",
    ")\n",
    "\n",
    "cover.sum()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "34bbe454",
   "metadata": {},
   "source": [
    "As a baseline, here is a 2-approximated vertex cover using a random order of the node degrees."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "cf52349a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 3min 36s, sys: 7.83 s, total: 3min 44s\n",
      "Wall time: 3min 36s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "359142190"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "cover = wikidata.get_approximated_vertex_cover(\n",
    "    approach=\"random\",\n",
    "    sequential=True,\n",
    "    insert_only_source=False,\n",
    "    random_seed=5425635\n",
    ")\n",
    "\n",
    "cover.sum()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a94c3cab",
   "metadata": {},
   "source": [
    "## Conclusions\n",
    "\n",
    "In this tutorial, we learned how to use the [GRAPE](https://github.com/AnacletoLAB/grape) library to compute approximate vertex covers of large graphs. We discussed the NP and APX complecity classes, and the concept of a vertex cover. We also learned about the 2-approximate greedy algorithm for the vertex cover problem and how it can be used to find a set of vertices that covers all the edges in a graph.\n",
    "\n",
    "I hope you now have a better grasp on vertex covers and how to use GRAPE to compute them for your projects. Do feel free to reach out with any questions or feedback, as I always look for ways to improve this tutorial.\n",
    "\n",
    "[And remember to ⭐ GRAPE!](https://github.com/AnacletoLAB/grape)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}