tutorials/Exact billion-scale graph diameter with GRAPE.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "0df9a85c",
   "metadata": {},
   "source": [
    "# Exact billion-scale graph diameter with 🍇🍇 GRAPE 🍇🍇\n",
    "In this tutorial, I will show you how to use the [GRAPE library](https://github.com/AnacletoLAB/grape) to compute the exact diameter of a graph, which is the longest shortest path between any two nodes in the graph. This is a challenging problem, especially for large graphs with millions or billions of nodes and edges.\n",
    "\n",
    "We will discuss some of the basics of graph analysis and introduce key concepts such as quality control, computational complexity, and breadth-first search. We will also briefly touch the concept of graph neural networks.\n",
    "\n",
    "We will discuss how many graphs have short average distances between nodes, and IFUB, a great algorithm to efficiently compute the diameter of large graphs. We will execute that algorithm on a the KGCOVID19 knowledge graph, and then move to two graphs with over one billion nodes: ClueWeb09 and WikiData. We will see how IFUB performs impeccably in the first one, and struggles more in the latter.\n",
    "\n",
    "By the end of the tutorial, you will have a good understanding of how to use GRAPE to compute the exact diameter of a graph and apply this knowledge to your own projects.\n",
    "\n",
    "[Remember to ⭐ GRAPE!](https://github.com/AnacletoLAB/grape)\n",
    "\n",
    "## Some basics\n",
    "In this section, we will provide a brief overview of some key concepts that will be discussed throughout the tutorial. These include quality control of datasets, computational complexity, graphs and their various applications, breadth-first search, and graph neural networks. Understanding these basic concepts is essential for understanding the more advanced topics that will be covered in the tutorial. We will also introduce the concept of graph convolutional networks, which are a specialized type of neural network used for processing graph-structured data. **It is likely you are familiar with all of these concepts, and you may just skip this section**, but I made it available so that more readers can be on the same page when the tutorial starts.\n",
    "\n",
    "### Quality control\n",
    "Quality control of datasets is the process of ensuring that the data used for various purposes is accurate, reliable, and relevant. It involves checking the data for completeness, accuracy, and consistency, and correcting or removing any errors or inconsistencies that may be present. Quality control of datasets is important because the quality of the data has a direct impact on the accuracy and reliability of the results obtained from the data. Poor quality data can lead to incorrect conclusions, which can have serious consequences in fields such as healthcare, finance, and scientific research. Ensuring the quality of datasets is therefore essential for ensuring the integrity and reliability of the results obtained from the data. [We have already learned how to create an extensive quality control report for graphs in this other GRAPE tutorial](https://github.com/AnacletoLAB/grape/blob/main/tutorials/Create%20extensive%20knowledge%20graph%20reports%20using%20GRAPE.ipynb)\n",
    "\n",
    "### Computational complexity\n",
    "[Computational complexity](https://en.wikipedia.org/wiki/Computational_complexity) refers to the amount of resources (e.g., time, space) required by an algorithm to solve a problem. It is typically measured in terms of the size of the input data. Worst-case complexity refers to the maximum amount of resources required by the algorithm over all possible inputs of a given size. This measure is useful because it provides a guarantee on the performance of the algorithm, regardless of the specific input data. However, it may not accurately reflect the average performance of the algorithm on typical input data.\n",
    "\n",
    "### What is a graph\n",
    "[A graph](https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)) is a data structure that consists of a set of vertices, or nodes, and a set of edges connecting these vertices. Graphs are used to represent relationships between different entities in a wide range of applications, such as social networks, transportation systems, and biological networks.\n",
    "\n",
    "Some graphs can be very large, with millions or even billions of vertices and edges. The size of a graph can significantly impact the performance of algorithms used to analyze or process it. Therefore, it is important to develop efficient algorithms for analyzing large graphs.\n",
    "\n",
    "### Breadth-first search\n",
    "[Breadth-first search (BFS)](https://en.wikipedia.org/wiki/Breadth-first_search) is an algorithm for traversing or searching a graph, tree, or other data structure. It starts at some arbitrary root node and explores the neighbor nodes first, before moving to the next level neighbors.\n",
    "\n",
    "The algorithm works by using a queue to store nodes that are waiting to be processed, with the first node in the queue being the one that was most recently discovered. The algorithm continues to process nodes in the queue, adding any neighbors that have not yet been discovered to the queue, until the queue is empty.\n",
    "\n",
    "BFS has a number of applications, including finding the shortest path between two nodes in a graph and checking if a graph is connected. It is also used as a building block for other algorithms, such as topological sorting and network connectivity analysis.\n",
    "\n",
    "### Graph neural networks\n",
    "[Graph neural networks (GNNs)](https://www.cs.mcgill.ca/~wlh/grl_book/) are a class of neural networks that are specifically designed to process graph-structured data. They have been applied to a variety of tasks including node classification, link prediction, and graph classification. GNNs are particularly useful for tasks that involve the analysis of relationships between entities in a graph, as they are able to incorporate the graph structure in their learning process.\n",
    "\n",
    "#### Graph convolutional networks\n",
    "[Graph convolutional networks (GCNs)](https://arxiv.org/pdf/1609.02907.pdf) are a type of neural network designed specifically to operate on graph-structured data. Like traditional convolutional neural networks, GCNs use convolutional layers to process and analyze data. However, rather than operating on grid-structured data such as images, GCNs perform convolutions on the graph structure itself, using the relationships between nodes in the graph as the basis for their analysis. GCNs have been successfully applied to a wide range of tasks in domains such as computer vision, natural language processing, and drug discovery, and have been shown to outperform traditional methods on many graph-based problems.\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",
    "![GRAPE](https://github.com/AnacletoLAB/grape/raw/main/images/sequence_diagram.png?raw=true)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1e666f1e",
   "metadata": {},
   "source": [
    "## What is the diameter?\n",
    "The diameter of a graph is a measure of the size of the graph, defined as the maximum distance between any pair of nodes in the graph. It is an important metric for characterizing the structure of a graph. Computing the diameter of a graph can be a challenging task, particularly for large graphs with many nodes and edges. Exact algorithms for computing the diameter typically have a high time complexity, scaling poorly with the size of the graph. As a result, it can be difficult to compute the diameter of very large graphs in a reasonable amount of time. Despite this, the diameter is an important metric for various applications, including graph neural networks and graph convolutional networks. These types of networks are used to process and analyze graphs, and the diameter can impact the performance and accuracy of these networks. For example, the diameter of a graph may determine the maximum depth of a graph neural network required to accurately process the graph, and manage expectations of the performance of those models.\n",
    "\n",
    "<img src=\"https://github.com/AnacletoLAB/grape/blob/main/images/diameter.jpg?raw=true\" width=300 />\n",
    "\n",
    "## Four degrees of separation\n",
    "[The Four Degrees of Separation paper](https://arxiv.org/pdf/1111.4570.pdf) presents the results of a study on the distance distribution of the Facebook social network, which at the time of the study contained approximately 721 million active users and approximately 69 billion friendship links. The goal of the study was to identify statistical parameters that can distinguish proper social networks from other complex networks, such as web graphs. The study found that the average distance, or number of degrees of separation, between two users on Facebook is 4.74, corresponding to 3.74 intermediaries or \"degrees of separation.\" This is significantly lower than the average number of intermediaries found in previous studies, such as the ones conducted by Stanley Milgram, which ranged between 4.4 and 5.7. The study also analyzed the distance distribution of geographic subgraphs of Facebook and observed their evolution over time.\n",
    "\n",
    "## On computing the diameter of real-world undirected graphs\n",
    "The algorithm we are going to use in this tutorial is a highly parallelized version of the algorithm described in Crescenzi et al. fantastic paper [On computing the diameter of real-world undirected graphs](https://who.rocq.inria.fr/Laurent.Viennot/road/papers/ifub.pdf), which I cannot suggest enough to read.\n",
    "\n",
    "This paper presents the IFUB algorithm, an exact method for computing the diameter of large graphs. It works by starting a breadth-first search from a randomly chosen node or a node with the highest degree, and refining both a lower bound and an upper bound on the diameter until the two bounds meet. This is done through an iterative process that terminates when the upper and lower bounds meet.\n",
    "\n",
    "The IFUB algorithm has a worst-case complexity of `O(|V||E|)`, where `|V|` is the number of nodes and `|E|` is the number of edges in the graph, but it has been shown to work in `O(|E|)` time in practice on almost `200` real-world graphs.\n",
    "\n",
    "It is a significant improvement over other methods, such as those based on random sampling, which do not provide a useful bound on the error and may not be precise in practice. The IFUB algorithm has been shown to be particularly useful for computing the diameter of large graphs, where other methods may be too time-consuming.\n",
    "\n",
    "**The performance of the IFUB algorithm can vary greatly depending on the topology of the input graph. Some graphs may be more suited to IFUB and result in faster execution times, while others may be more challenging for IFUB and result in slower execution times.**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2de848e2",
   "metadata": {},
   "source": [
    "## Installing GRAPE\n",
    "First, we install the GRAPE library from PyPI:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "8e5462cc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\r\n",
      "\u001b[1m[\u001b[0m\u001b[34;49mnotice\u001b[0m\u001b[1;39;49m]\u001b[0m\u001b[39;49m A new release of pip available: \u001b[0m\u001b[31;49m22.2.2\u001b[0m\u001b[39;49m -> \u001b[0m\u001b[32;49m22.3.1\u001b[0m\r\n",
      "\u001b[1m[\u001b[0m\u001b[34;49mnotice\u001b[0m\u001b[1;39;49m]\u001b[0m\u001b[39;49m To update, run: \u001b[0m\u001b[32;49mpip install --upgrade pip\u001b[0m\r\n"
     ]
    }
   ],
   "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 IFUB algorithm to compute the diameter of four different graphs: the KGCOVID19 knowledge graph, the Friendter graph, the ClueWeb09 web graph, and the WikiData graph.\n",
    "\n",
    "We will observe the performance of IFUB on each of these graphs and discuss the results. By the end of this section, you will have a better understanding of how IFUB performs on different types of graphs and how to use GRAPE to compute the exact diameter of a graph.\n",
    "\n",
    "**Do note that, for 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": "15280e49",
   "metadata": {},
   "source": [
    "### KGCOVID19\n",
    "We kick off our experiments with a rather small graph, considering the sizes of the networks we are going to 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 in which siloed biomedical data must be quickly integrated for various research purposes, including future pandemics."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "2c0b685e",
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 23 s, sys: 279 ms, total: 23.3 s\n",
      "Wall time: 1.87 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": 6,
   "id": "878ffc06",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(574232, 18251238)"
      ]
     },
     "execution_count": 6,
     "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 the diameter. It should be pretty much instantenous."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "9c35198a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1.35 s, sys: 10.4 ms, total: 1.36 s\n",
      "Wall time: 64.7 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "38.0"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "kgcovid19.get_diameter()"
   ]
  },
  {
   "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 it eventually faced competition from newer 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 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 and is also the largest network repository, containing thousands of network data sets in over 30 domains, including biological, social, and machine learning data. The repository allows users to visualize and explore network data sets, view interactive statistics and plots, and download massive network data sets with billions of edges. It also includes a visual analytics platform called GraphVis, which allows users to interactively analyze and explore network data in real-time over the web and use it for educational purposes. Network Repository is intended to facilitate scientific research on networks by making it easier for researchers to access and analyze a large collection of network data. It is a valuable resource for researchers in a variety of 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, make sure that you have enough free space on your hard drive or other storage device to accommodate the size of the graph. If you do not have sufficient space, you may encounter errors or other issues when attempting to download or work 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": 8,
   "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": 9,
   "id": "bb5927ad",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 33min 11s, sys: 23.3 s, total: 33min 34s\n",
      "Wall time: 2min 20s\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": 10,
   "id": "fdbee4bf",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(65608366, 1806067135)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "friendster.get_number_of_nodes(), friendster.get_number_of_edges()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a7d0a392",
   "metadata": {},
   "source": [
    "And now we compute the diameter. In this particular graph, even though it is large, we see that the IFUB heuristic works great and it completes in a very short time.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "b4000078",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 30min 4s, sys: 7.72 s, total: 30min 12s\n",
      "Wall time: 1min 17s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "37.0"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "friendster.get_diameter()"
   ]
  },
  {
   "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 available before attempting to download and use a large graph. It is important to ensure that you have enough space on your hard drive or other storage device to accommodate the size of the graph, 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 attempting to download or work with a large graph, and to free up additional space if necessary.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "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": 9,
   "id": "5e6a8aba",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 2h 59min 41s, sys: 6min 31s, total: 3h 6min 12s\n",
      "Wall time: 37min 52s\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": 10,
   "id": "3ea0be87",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1684868322, 7811385827)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clueweb.get_number_of_nodes(), clueweb.get_number_of_edges()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1198087a",
   "metadata": {},
   "source": [
    "And now we compute the diameter. In this particular graph, even though it is colossal, we see that the IFUB heuristic works great and it completes in a very short time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "45575c12",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 40min 39s, sys: 34.3 s, total: 41min 13s\n",
      "Wall time: 1min 53s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "124.0"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "clueweb.get_diameter()"
   ]
  },
  {
   "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 that represents the relationships between concepts and entities, including real-world objects, events, and ideas, as well as 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 concept \"dog\" might be connected to other nodes representing specific dog breeds, such as \"Labrador Retriever\" or \"Poodle,\" through edges that represent 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 the creation of new properties and classes to represent the relationships between concepts and entities. The data in the WikiData graph is available for free and can be accessed through a variety of methods, including the WikiData API, SPARQL queries, and third-party tools and services. The WikiData graph is used in a variety of applications, including data integration, natural language processing, and machine learning. It is also used to provide 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 available before attempting to download and use a large graph. It is important to ensure that you have enough space on your hard drive or other storage device to accommodate the size of the graph, 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 attempting to download or work with a large graph, and to free up additional space if necessary.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "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": 1,
   "id": "d1b8b27e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1h 56min 23s, sys: 4min 52s, total: 2h 1min 15s\n",
      "Wall time: 20min 23s\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": [
    "And now we compute the diameter. In this particular graph, quite differently from the previous one, we encounter a case where IFUB is having a very hard time, and takes very long to compute the diameter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "692c5296",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "wikidata.get_diameter()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d19ffc5a",
   "metadata": {},
   "source": [
    "This last one, after 12 hours of executions on my 24 threads desktop, has not seen the end of it yet. **But why is that? Why is IFUB failing here?** IFUB tests all nodes at a given distance `k` to check whether any of of them may be the diameter, and gradually closes in the bound. If a large amount of nodes are all at a distance equal to or very close to the diameter, IFUB needs to test all of them, leading to an explosion of computing time."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a94c3cab",
   "metadata": {},
   "source": [
    "## Conclusions\n",
    "\n",
    "In this tutorial, we learned how to use the GRAPE library to compute the exact diameter of large graphs. We started by discussing some basic concepts of graph analysis, including quality control, computational complexity, and breadth-first search. We briefly touched upon the concept of graph neural networks and discussed the IFUB algorithm, which is an efficient way to compute the diameter of large graphs. We applied IFUB to four different graphs: the KGCOVID19 knowledge graph, Friendster, ClueWeb09, and WikiData. We saw that IFUB performed well on the KGCOVID19, Friendster and ClueWeb09 graphs, but struggled more on the WikiData graph.\n",
    "\n",
    "You should now have a good understanding of how scalable IFUB is, how to use it with GRAPE and where it may fail.\n",
    "\n",
    "Do feel free to reach out with questions, so we may 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.7.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}