examples/notebooks/Literature exploration (PGFrames + in-memory analytics tutorial).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Prerequisites and installation instructions\n",
    "\n",
    "\n",
    "In order to run this notebook `graph-tool` must be installed manually (it cannot be installed as a part of `pip install bluegraph`, as it is not an ordinary Python library, but a wrapper around a C++ library). Please, see [graph-tool installation instructions](https://git.skewed.de/count0/graph-tool/-/wikis/installation-instructions#native-installation) (currently, BlueGraph supports :code:`graph-tool<=2.37`.)\n",
    "\n",
    "We recommend using `conda` for installing `graph-tool`. For example:\n",
    "\n",
    "```\n",
    "conda install -c conda-forge graph-tool==2.37\n",
    "```\n",
    "\n",
    "or as a part of a new `conda` environment:\n",
    "\n",
    "```\n",
    "conda create --name <your_environment> -c conda-forge graph-tool==2.37\n",
    "conda activate <your_environment>\n",
    "```\n",
    "\n",
    "BlueGraph and the set of its dependecies can be installed using:\n",
    "\n",
    " ```\n",
    " pip install bluegraph\n",
    " ```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Literature exploration by term co-occurrance analysis\n",
    "\n",
    "In this example we illustrate how network analytics can be used for literature exploration. \n",
    "\n",
    "The input dataset contains occurrences of different terms in paragraphs of scientific articles previously extracted by means of a Named Entity Recognition (NER) model. This dataset is transformed into three co-occurrence networks: representing paper- and paragraph-level co-occurrence relation between terms. The term relations in the above-mentioned networks are quantified using mutual-information-based scores (pointwise mutual information and its normalized version).\n",
    "\n",
    "The networks are further analysed using classical tools from complex networks: we find various centrality measures characterizing the importance of extracted terms, we detect term communities representing denesely connected clusters of terms and finally we illustrate how the algorithms for finding shortest paths and minimum spanning trees can be used to perform guided search in networks."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "import pandas as pd\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from bluegraph.core import (PandasPGFrame,\n",
    "                            pretty_print_paths,\n",
    "                            pretty_print_tripaths,\n",
    "                            graph_elements_from_paths)\n",
    "from bluegraph.preprocess.generators import CooccurrenceGenerator\n",
    "\n",
    "from bluegraph.backends.graph_tool import (GTMetricProcessor,\n",
    "                                           GTPathFinder,\n",
    "                                           GTGraphProcessor,\n",
    "                                           GTCommunityDetector)\n",
    "from bluegraph.backends.graph_tool import graph_tool_to_pgframe\n",
    "\n",
    "from bluegraph.backends.networkx import NXCommunityDetector, NXPathFinder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## I. Entity-occurrence property graph\n",
    "\n",
    "In this section we will create a property graph whose nodes are papers and extracted named entities, and whose edges connect entities to the papers they occur in."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The input data is given by occurrences of different entities in specific paragraphs of scientific articles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mentions = pd.read_csv(\"../data/literature_NER_example.csv\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mentions.sample(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Every paragraph is identified using the format `<paper_id>:<section_id>:<paragraph_id>`. From this data we will extract occurrences in distinct papers/paragraphs as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Extract unique paper/seciton/paragraph identifiers\n",
    "mentions[\"paper\"] = mentions[\"occurrence\"].apply(\n",
    "    lambda x: x.split(\":\")[0])\n",
    "\n",
    "mentions = mentions.rename(columns={\"occurrence\": \"paragraph\"})\n",
    "mentions.sample(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We, first, create an empty property graph object."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph = PandasPGFrame()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then we add nodes for unique entities and papers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "entity_nodes = mentions[\"entity\"].unique()\n",
    "graph.add_nodes(entity_nodes)\n",
    "graph.add_node_types({n: \"Entity\" for n in entity_nodes})\n",
    "\n",
    "paper_nodes = mentions[\"paper\"].unique()\n",
    "graph.add_nodes(paper_nodes)\n",
    "graph.add_node_types({n: \"Paper\" for n in paper_nodes})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph.nodes(raw_frame=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now add edges from entities to the papers they occur in storing paragraphs as edge properties."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "occurrence_edges = mentions.groupby(by=[\"entity\", \"paper\"]).aggregate(set)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "occurrence_edges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph.add_edges(occurrence_edges.index)\n",
    "graph.add_edge_types({e: \"OccursIn\" for e in occurrence_edges.index})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "occurrence_edges.index = occurrence_edges.index.rename([\"@source_id\", \"@target_id\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph.add_edge_properties(occurrence_edges[\"paragraph\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph.edges(raw_frame=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## II. Entity co-occurrence graphs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will generate co-occurrence graphs for different occurrence factors (paper/paragraph), i.e. an edge between a pair of entities is added if they co-occur in the same paper or paragraph."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**NB: Some statistics computed during the co-occurrence analysis**\n",
    "\n",
    "- `ppmi`: _positive pointwise mutual information (PPMI)_ is defined as $PPMI(x, y) = \\log_2{\\frac{p(x, y)}{p(x)p(y)}} $, if $p(x) \\neq 0$ and $p(y) \\neq 0$, and $PPMI(x, y) = 0$ otherwise.\n",
    "\n",
    "- `npmi`: _normalized pointwise mutual information (NPMI)_ is defined as $NPMI(x, y) = \\frac{PPMI(x, y)}{-\\log_2{p(x, y)}} $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Paper-based co-occurrence\n",
    "\n",
    "We first generate co-occurrence network from edges of type `OccursIn` linking entities and papers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gen = CooccurrenceGenerator(graph)\n",
    "paper_cooccurrence_edges = gen.generate_from_edges(\n",
    "     \"OccursIn\", compute_statistics=[\"frequency\", \"ppmi\", \"npmi\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "paper_cooccurrence_edges[\"@type\"] = \"CoOccursWith\"\n",
    "paper_cooccurrence_edges"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From the generated edges we remove the ones with zero NPMI scores."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paper_cooccurrence_edges = paper_cooccurrence_edges[paper_cooccurrence_edges[\"npmi\"] != 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "entity_nodes = graph.nodes_of_type(\"Entity\").copy()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paper_frequency = mentions.groupby(\"entity\").aggregate(set)[\"paper\"].apply(len)\n",
    "paper_frequency.name = \"paper_frequency\"\n",
    "\n",
    "entity_nodes[\"paper_frequency\"] = paper_frequency"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We create a new property graph object from generated edges and entity nodes as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paper_network = PandasPGFrame.from_frames(\n",
    "    nodes=entity_nodes,\n",
    "    edges=paper_cooccurrence_edges,\n",
    "    node_prop_types={\n",
    "        \"paper_frequency\": \"numeric\",\n",
    "        \"paragraph_frequency\": \"numeric\"\n",
    "    },\n",
    "    edge_prop_types={\n",
    "        \"frequency\": \"numeric\",\n",
    "        \"ppmi\": \"numeric\",\n",
    "        \"npmi\": \"numeric\"\n",
    "    })"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paper_network.edges(raw_frame=True).sample(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paper_network.nodes(raw_frame=True).sample(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Paragraph-based co-occurrence\n",
    "\n",
    "We perform similar operation for paragraph-level co-occurrence. In order to use another co-occurrence factor, we will define the following 'factor_aggregator' function (`aggregate_paragraph`) that takes a collection of sets of paragraphs and merges them into the same set. This aggregator will be used to collect sets of common paragraphs of `OccursIn` edges pointing from a pair of entities to the same paper."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def aggregate_paragraphs(data):\n",
    "    return set(sum(data[\"paragraph\"].apply(list), []))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "paragraph_cooccurrence_edges = gen.generate_from_edges(\n",
    "     \"OccursIn\", \n",
    "    factor_aggregator=aggregate_paragraphs,\n",
    "    compute_statistics=[\"frequency\", \"ppmi\", \"npmi\"],\n",
    "    parallelize=True, cores=8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "paragraph_cooccurrence_edges[\"@type\"] = \"CoOccursWith\"\n",
    "paragraph_cooccurrence_edges.sample(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From the generated edges we remove the ones with zero NPMI scores."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paragraph_cooccurrence_edges = paragraph_cooccurrence_edges[paragraph_cooccurrence_edges[\"npmi\"] != 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paragraph_network = PandasPGFrame.from_frames(\n",
    "    nodes=entity_nodes,\n",
    "    edges=paragraph_cooccurrence_edges,\n",
    "    node_prop_types={\n",
    "        \"paper_frequency\": \"numeric\",\n",
    "    },\n",
    "    edge_prop_types={\n",
    "        \"frequency\": \"numeric\",\n",
    "        \"ppmi\": \"numeric\",\n",
    "        \"npmi\": \"numeric\"\n",
    "    })"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Faster paragraph-based co-occurrence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alternatively, to generate paragraph-level co-occurrence network, we can assign sets of paragraphs where entities occur as properties of their respective nodes (as follows)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paragraph_prop = pd.DataFrame({\"paragraphs\": mentions.groupby(\"entity\").aggregate(set)[\"paragraph\"]})\n",
    "graph.add_node_properties(paragraph_prop, prop_type=\"category\")\n",
    "graph.nodes(raw_frame=True).sample(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And then use the `generate_from_nodes` method of `CooccurrenceGenerator` in order to generate co-occurrence edges for nodes whose `paragraphs` property has a non-empty intersection."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "generator = CooccurrenceGenerator(graph)\n",
    "paragraph_cooccurrence_edges = generator.generate_from_nodes(\n",
    "    \"paragraphs\", total_factor_instances=len(mentions.paragraph.unique()),\n",
    "    compute_statistics=[\"frequency\", \"npmi\"],\n",
    "    parallelize=True, cores=8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Additional co-occurrence measures: NPMI-based distance\n",
    "\n",
    "For both paper- and paragraph-based networks we will compute a mutual-information-based distance as follows:\n",
    "$D = \\frac{1}{NPMI}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "def compute_distance(x):\n",
    "    return 1 / x if x > 0 else math.inf"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "npmi_distance = paper_network.edges(raw_frame=True)[\"npmi\"].apply(compute_distance)\n",
    "npmi_distance.name = \"distance_npmi\"\n",
    "paper_network.add_edge_properties(npmi_distance, \"numeric\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paper_network.edges(raw_frame=True).sample(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "npmi_distance = paragraph_network.edges(raw_frame=True)[\"npmi\"].apply(compute_distance)\n",
    "npmi_distance.name = \"distance_npmi\"\n",
    "paragraph_network.add_edge_properties(npmi_distance, \"numeric\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paper_network.edges(raw_frame=True).sample(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## III. Nearest neighours by co-occurrence scores"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To illustrate the importance of computing mutual-information-based scores over raw frequencies consider the following example, where we would like to estimate top closest (most related) neighbors to a specific term.\n",
    "\n",
    "To do so, we will use the paragraph-based network and the raw co-occurrence frequency as the weight of our co-occurrence relation. The `top_neighbors` method of the `PathFinder` interface provided by the BlueGraph allows us to search for top neighbors with the highest edge weight. In this example, we use `graph_tool`-based `GTPathFinder` interface."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paragraph_path_finder = GTPathFinder(paragraph_network, directed=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Observe in the following cell that the path finder interface generated a backend-specific graph object."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paragraph_path_finder.graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paragraph_path_finder.top_neighbors(\"glucose\", 10, weight=\"frequency\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paragraph_path_finder.top_neighbors(\"lung\", 10, weight=\"frequency\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We observe that 'glucose' and 'lung' share a lot of the closest neighbors by raw frequency. If we look into the list of top 10 entities by paragraph frequency in the entire corpus and we notice that 'glucose' and 'blood' co-occur the most with the terms that are simply the most frequent in our corpus, such as 'covid-19' and 'diabetes mellitus'.\n",
    "\n",
    "(Closest inspection of the distribution of weighted node degrees suggests that the network contains _hubs_, nodes with significantly high-degree connectivity to other nodes.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paragraph_network._nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paragraph_network.nodes(raw_frame=True).nlargest(10, columns=[\"paper_frequency\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To account for the presence of such hubs, we use the mutual-information-based scores presented above. They 'balance' the influence of the highly connected hub nodes such as 'covid-19' and 'diabetes mellitus' in our example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paragraph_path_finder.top_neighbors(\"glucose\", 10, weight=\"npmi\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "paragraph_path_finder.top_neighbors(\"lung\", 10, weight=\"npmi\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## IV. Graph metrics and centrality measures\n",
    "\n",
    "BlueGraph provides the `MetricProcessor` interface for computing various graph statistics. As in the previous example, we will use `graph_tool`-based `GTMetricProcessor` interface."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paper_metrics = GTMetricProcessor(paper_network, directed=False)\n",
    "paragraph_metrics = GTMetricProcessor(paragraph_network, directed=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Graph density"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Density of a graph is quantified by the proportion of all possible edges ($n(n-1) / 2$ for the undirected graph with $n$ nodes) that are realized."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Density of the paper-based network: \", paper_metrics.density())\n",
    "print(\"Density of the paragraph-based network: \", paragraph_metrics.density())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The results above show that in the paper, section and paragraph network repsectively 80%, 42% and 22% of all possible term pairs co-occur at least once."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Node centrality (importance) measures\n",
    "\n",
    "In this example we will compute the Degree and PageRank centralities only for the raw frequency, and the Betweenness centrality for the mutual-information-based scores. We will use methods provided by the `MetricProcessor` interface in the _write_ mode, i.e. computed metrics will be written as node properties of the underlying graph object."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Degree centrality_ is given by the sum of weights of all incident edges of the given node and characterizes the importance of the node in the network in terms of its connectivity to other nodes (high degree = high connectivity)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paragraph_metrics.degree_centrality(\"frequency\", write=True, write_property=\"degree\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_PageRank centrality_ is another measure that estimated the importance of the given node in the network. Roughly speaking it can be interpreted as the probablity that having landed on a random node in the network we will jump to the given node (here the edge weights are taken into account\").\n",
    "\n",
    "https://en.wikipedia.org/wiki/PageRank"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paragraph_metrics.pagerank_centrality(\"frequency\", write=True, write_property=\"pagerank\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We then compute the betweenness centrality based on the NPMI distances.\n",
    "\n",
    "_Betweenness centrality_ is a node importance measure that estimates how often a shortest path between a pair of nodes will pass through the given node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paragraph_metrics.betweenness_centrality(\"distance_npmi\", write=True, write_property=\"betweenness\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can inspect the underlying graph object and observe the newly added properties:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paragraph_metrics.graph.vp.keys()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, we will export this backend-specific graph object into a `PGFrame`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "new_paragraph_network = paragraph_metrics.get_pgframe()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "new_paragraph_network.nodes(raw_frame=True).sample(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Top 10 nodes by degree\")\n",
    "for n in new_paragraph_network.nodes(raw_frame=True).nlargest(10, columns=[\"degree\"]).index:\n",
    "    print(\"\\t\", n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Top 10 nodes by PageRank\")\n",
    "for n in new_paragraph_network.nodes(raw_frame=True).nlargest(10, columns=[\"pagerank\"]).index:\n",
    "    print(\"\\t\", n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Top 10 nodes by betweenness\")\n",
    "for n in new_paragraph_network.nodes(raw_frame=True).nlargest(10, columns=[\"betweenness\"]).index:\n",
    "    print(\"\\t\", n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Compute multiple metrics in one go"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alternatively, we can compute all the metrics in one go. To do so, we need to specify edge attributes used for computing different metrics (if an empty list is specified as a weight list for a metric, computation of this metric is not performed). \n",
    "\n",
    "We select the paragraph-based network and re-compute all some of the previously illustrated metrics as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "result_metrics = paragraph_metrics.compute_all_node_metrics(\n",
    "    degree_weights=[\"frequency\"],\n",
    "    pagerank_weights=[\"frequency\"],\n",
    "    betweenness_weights=[\"distance_npmi\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "result_metrics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## VI. Community detection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Community detection_ methods partition the network into clusters of densely connected nodes in a way that nodes in the same community are more connected between themselves relatively to the nodes in different communities. In this section we will illustrate the use of the `CommunityDetector` interface provided by BlueGraph for community detection and estimation of its quality using modularity, performance and coverange methods. The unified interface allows us to use various community detection methods available in different graph backends."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, we create a `NetworkX`-based instance and use several different community detection strategies provided by this library. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx_detector = NXCommunityDetector(new_paragraph_network, directed=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx_detector.graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Louvain algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "partition = nx_detector.detect_communities(\n",
    "    strategy=\"louvain\", weight=\"npmi\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Modularity: \", nx_detector.evaluate_parition(partition, metric=\"modularity\", weight=\"npmi\"))\n",
    "print(\"Performance: \", nx_detector.evaluate_parition(partition, metric=\"performance\", weight=\"npmi\"))\n",
    "print(\"Coverage: \", nx_detector.evaluate_parition(partition, metric=\"coverage\", weight=\"npmi\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Label propagation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "partition = nx_detector.detect_communities(\n",
    "    strategy=\"lpa\", weight=\"npmi\", intermediate=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Modularity: \", nx_detector.evaluate_parition(partition, metric=\"modularity\", weight=\"npmi\"))\n",
    "print(\"Performance: \", nx_detector.evaluate_parition(partition, metric=\"performance\", weight=\"npmi\"))\n",
    "print(\"Coverage: \", nx_detector.evaluate_parition(partition, metric=\"coverage\", weight=\"npmi\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Stochastic block model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gt_detector = GTCommunityDetector(new_paragraph_network, directed=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "partition = gt_detector.detect_communities(strategy=\"sbm\", weight=\"npmi\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "print(\"Modularity: \", nx_detector.evaluate_parition(partition, metric=\"modularity\", weight=\"npmi\"))\n",
    "print(\"Performance: \", nx_detector.evaluate_parition(partition, metric=\"performance\", weight=\"npmi\"))\n",
    "print(\"Coverage: \", nx_detector.evaluate_parition(partition, metric=\"coverage\", weight=\"npmi\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Writing community partition as node properties"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx_detector.detect_communities(\n",
    "    strategy=\"louvain\", weight=\"npmi\",\n",
    "    write=True, write_property=\"louvain_community\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "new_paragraph_network = nx_detector.get_pgframe(\n",
    "    node_prop_types=new_paragraph_network._node_prop_types,\n",
    "    edge_prop_types=new_paragraph_network._edge_prop_types)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "new_paragraph_network.nodes(raw_frame=True).sample(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## V. Export network and the computed metrics"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Save graph as JSON\n",
    "new_paragraph_network.export_json(\"../data/literature_comention.json\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Save the graph for Gephi import.\n",
    "new_paragraph_network.export_to_gephi(\n",
    "    \"../data/gephi_literature_comention\", \n",
    "    node_attr_mapping = {\n",
    "        \"degree\": \"Degree\",\n",
    "        \"pagerank\": \"PageRank\",\n",
    "        \"betweenness\": \"Betweenness\",\n",
    "        \"louvain_community\": \"Community\"\n",
    "    },\n",
    "    edge_attr_mapping={\n",
    "        \"npmi\": \"Weight\"\n",
    "    })"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The representation of the network saved above can be imported into Gephi for producing graph visualizations, as in the following example:\n",
    "\n",
    "In the figures below colors represent communities detected using the Louvain algorithm (with NPMI edge weights), node sizes are proportional to the PageRank of nodes and edge thickness to the NPMI values.\n",
    "\n",
    "**Full network**\n",
    "<img src=\"./figures/literature/full_network.png\" alt=\"Literature co-occurrence network\" style=\"width: 400px;\"/>\n",
    "\n",
    "**Community \"Symptoms and comorbidities\"**\n",
    "<img src=\"./figures/literature/covid_19_comorbidities.png\" alt=\"Drawing\" style=\"width: 400px;\"/>\n",
    "\n",
    "**Community \"Viral biology\"**\n",
    "<img src=\"./figures/literature/virus.png\" alt=\"Drawing\" style=\"width: 600px;\"/>\n",
    "\n",
    "**Community \"Immunity\"**\n",
    "<img src=\"./figures/literature/immunity.png\" alt=\"Drawing\" style=\"width: 600px;\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## VII. Minimum spanning trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A _minimum spanning tree_ of a network is given by a subset of edges that make the network connected ($n - 1$ edges connecting $n$ nodes). Its weighted version minimizes not only the number of edges included in the tree, but the total edge weight.\n",
    "\n",
    "In the following example we compute a minimum spanning tree minimizing the NPMI-based distance weight of the network edges. We use the `graph_tool`-based implementation of the `PathFinder` interface."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gt_paragraph_path_finder = GTPathFinder(new_paragraph_network, directed=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gt_paragraph_path_finder.graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "tree = graph_tool_to_pgframe(gt_paragraph_path_finder.minimum_spanning_tree(distance=\"distance_npmi\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree.export_to_gephi(\n",
    "    \"../data/gephi_literature_spanning_tree\", \n",
    "    node_attr_mapping = {\n",
    "        \"degree\": \"Degree\",\n",
    "        \"pagerank\": \"PageRank\",\n",
    "        \"betweenness\": \"Betweenness\",\n",
    "        \"louvain_community\": \"Community\"\n",
    "    },\n",
    "    edge_attr_mapping={\n",
    "        \"npmi\": \"Weight\"\n",
    "    })"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The representation of the network saved above can be imported into Gephi for producing graph visualizations, as in the following example:\n",
    "\n",
    "In the figures below colors represent communities detected using the NPMI weight, node sizes are proportional to the PageRank of nodes and edge thickness to the NPMI values.\n",
    "\n",
    "**Full network**\n",
    "<img src=\"./figures/literature/tree.png\" alt=\"Literature co-occurrence MST\" style=\"width: 400px;\"/>\n",
    "\n",
    "**Zoom into \"covid-19\"**\n",
    "<img src=\"./figures/literature/tree_covid-19.png\" alt=\"Drawing\" style=\"width: 700px;\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## VIII. Shortest path search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The _shortest path search problem_ consisits in finding a sequence of edges from the source node to the target node that minimizes the cumulative weight (or distance) associated to the edges. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "path = gt_paragraph_path_finder.shortest_path(\"lung\", \"sars-cov-2\")\n",
    "pretty_print_paths([path])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The cell above illustrates that the single shortest path form 'lung' and 'sars-cov-2' consists of the direct edge between them.\n",
    "\n",
    "We adapt this problem to the literature exploration task, i.e. having fixed the source and the target concepts (the relation here is actually symmetric as the edges of our network are undirected), we would like to find a _set_ of $n$ shortest paths between them. Moreover, we would like these paths to be _indirect_ (not to include the direct edge from the source to the target). In the following examples we use mutual-information-based edge weights to perform our literature exploration. \n",
    "\n",
    "The library includes two strategies for finding such $n$ shortest paths. The first strategy uses Yen's algorithm for finding $n$ loopless shortest paths from the source to the target (https://en.wikipedia.org/wiki/Yen%27s_algorithm).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx_paragraph_path_finder = NXPathFinder(new_paragraph_network, directed=False)\n",
    "paths = nx_paragraph_path_finder.n_shortest_paths(\n",
    "    \"lung\", \"sars-cov-2\", n=10,\n",
    "    distance=\"distance_npmi\", strategy=\"yen\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pretty_print_paths(paths)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The second, _naive_, strategy is suitable in the scenarios when our networks are large and highly dense (then the performance of Yen's algorithm degragates as the number of edges is approaching $O(N^2)$ with $N$ being the number of nodes). \n",
    "\n",
    "This strategy simply finds _all_ the indirect shortest paths from the source to the target (in dense graphs the most common such paths are of length 2, i.e. `source <-> intermediary <-> target`, and therefore, the number of such path is roughly proportional to the number of nodes in the network). Then, the cumulative distance score is computed for every path and the top $n$ paths with the best score are selected."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paths = gt_paragraph_path_finder.n_shortest_paths(\n",
    "    \"lung\", \"sars-cov-2\", n=10,\n",
    "    distance=\"distance_npmi\", strategy=\"naive\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pretty_print_paths(paths)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The library provides an additional utility for finding _tripaths_, paths of the shape `source <-> intermediary <-> target`. Setting the parameter `intersecting` to `False` we can ensure that the entities the sets of entities discovered on the paths `source <-> intermediary` and `intermediary <-> target` do not overlap."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "(\"sars-cov-2\", \"glucose\") in new_paragraph_network.edges()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gt_paragraph_path_finder.n_shortest_paths(\n",
    "    \"glucose\", \"sars-cov-2\", n=10,\n",
    "    distance=\"distance_npmi\", strategy=\"naive\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "path_a_b, path_b_c = gt_paragraph_path_finder.n_shortest_tripaths(\n",
    "    \"lung\", \"glucose\", \"sars-cov-2\", 10,\n",
    "    strategy=\"naive\", distance=\"distance_npmi\", overlap=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pretty_print_tripaths(\"lung\", \"glucose\", \"sars-cov-2\", 10, path_a_b, path_b_c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## IX. Nested path search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To explore the space of co-occurring terms in depth, we can run the path search procedure presented above in a _nested fashion_. For each edge $e_1, e_2, ..., e_n$ encountered on a path from the source to the target  from, we can\n",
    "further expand it into $n$ shortest paths between each pair of successive entities (i.e. paths between $e_1$ and $e_2$, $e_2$ and $e_3$, etc.)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paths = gt_paragraph_path_finder.n_nested_shortest_paths(\n",
    "    \"lung\", \"glucose\", top_level_n=10, nested_n=2, depth=2, distance=\"distance_npmi\",\n",
    "    strategy=\"naive\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "paths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now visualize the subnetwork constructed using the nodes and the edges discovered during our nested path search."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "summary_graph = graph_tool_to_pgframe(\n",
    "    gt_paragraph_path_finder.get_subgraph_from_paths(paths))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "print(\"Number of nodes: \", summary_graph.number_of_nodes())\n",
    "print(\"Number of edges: \", summary_graph.number_of_edges())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Save the graph for Gephi import.\n",
    "summary_graph.export_to_gephi(\n",
    "    \"../data/gephi_literature_path_graph\", \n",
    "    node_attr_mapping = {\n",
    "        \"degree\": \"Degree\",\n",
    "        \"pagerank\": \"PageRank\",\n",
    "        \"betweenness\": \"Betweenness\",\n",
    "        \"louvain_community\": \"Community\"\n",
    "    },\n",
    "    edge_attr_mapping={\n",
    "        \"npmi\": \"Weight\"\n",
    "    })"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The resulting example graph visualized with Gephi\n",
    "<img src=\"./figures/literature/path_graph_example.png\" alt=\"Literature co-occurrence network\" style=\"width: 800px;\"/>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "clean_bg",
   "language": "python",
   "name": "clean_bg"
  },
  "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.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}