examples/notebooks/NASA keywords (PGFrames + Neo4j analytics tutorial).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Prerequisites and installation instructions\n",
    "\n",
    "\n",
    "In order to run this notebook Neo4j database must be installed and started (please, see [Neo4j installation instructions](https://neo4j.com/docs/operations-manual/current/installation/)). Typically, the Neo4j-based interfaces provided by BlueGraph require the database uri (the bolt port), username and password to be provided. In addition, BlueGraph uses the Neo4j Graph Data Science (GDS) library, which should be installed separately for the database on which you would like to run the analytics (see [installation instructions](https://neo4j.com/docs/graph-data-science/current/installation/)). Current supported Neo4j GDS version is `>=1.6.1`.\n",
    "\n",
    "BlueGraph and the set of dependecies supporting `neo4j` can be installed using:\n",
    "\n",
    " ```\n",
    " pip install bluegraph[neo4j]\n",
    " ```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# NASA dataset keywords analysis\n",
    "\n",
    "In this notebook we use graph-based co-occurrence analysis on the publicly available Data catalog of NASA (https://data.nasa.gov/browse, and the API endpoint https://data.nasa.gov/data.json). This dataset consists of the meta-data for different NASA datasets. \n",
    "\n",
    "We will work on the sets of keywords attached to each dataset and build a keyword co-occurrence graph describing relations between different dataset keywords. The keyword relations in the above-mentioned graph are quantified using mutual-information-based scores (normalized pointwise mutual information).\n",
    "\n",
    "See the related tutorial here: https://www.tidytextmining.com/nasa.html\n",
    "\n",
    "In this tutorial we will use the Neo4j-based implementation of different analytics interfaces provided by BlueGraph. Therefore, in order to use it, you need a running instance of the Neo4j database (see installation [instructions](https://neo4j.com/docs/operations-manual/current/installation/))."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "import json\n",
    "import pandas as pd\n",
    "import requests\n",
    "import getpass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from bluegraph.core import (PandasPGFrame,\n",
    "                            pretty_print_paths,\n",
    "                            pretty_print_tripaths)\n",
    "from bluegraph.preprocess.generators import CooccurrenceGenerator\n",
    "from bluegraph.backends.neo4j import (pgframe_to_neo4j,\n",
    "                                      Neo4jMetricProcessor,\n",
    "                                      Neo4jPathFinder,\n",
    "                                      Neo4jCommunityDetector,\n",
    "                                      Neo4jGraphProcessor)\n",
    "from bluegraph.backends.networkx import NXPathFinder, networkx_to_pgframe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## I. Data preparation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Download and read the NASA dataset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "NASA_META_DATA_URL = \"https://data.nasa.gov/data.json\"\n",
    "if not os.path.isfile(\"../data/nasa.json\"):\n",
    "    r = requests.get(NASA_META_DATA_URL)\n",
    "    open(\"../data/nasa.json\", \"wb\").write(r.content)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(\"../data/nasa.json\", \"r\") as f:\n",
    "    data = json.load(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Example dataset: \")\n",
    "print(\"----------------\")\n",
    "print(json.dumps(data[\"dataset\"][0], indent=\"   \"))\n",
    "\n",
    "print()\n",
    "print(\"Keywords: \", data[\"dataset\"][0][\"keyword\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Create a dataframe with keyword occurrence in different datasets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rows = []\n",
    "for el in data['dataset']:\n",
    "    row = [el[\"identifier\"]]\n",
    "    if \"keyword\" in el:\n",
    "        for k in el[\"keyword\"]:\n",
    "            rows.append(row + [k])\n",
    "keyword_data = pd.DataFrame(rows, columns=[\"dataset\", \"keyword\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "keyword_data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Aggregate dataset ids for each keyword and select the 500 most frequently used keywords."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 500"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "aggregated_datasets = keyword_data.groupby(\"keyword\").aggregate(set)[\"dataset\"]\n",
    "most_frequent_keywords = list(aggregated_datasets.apply(len).nlargest(n).index)\n",
    "most_frequent_keywords[:5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Create a property graph object whose nodes are unique keywords."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph = PandasPGFrame()\n",
    "graph.add_nodes(most_frequent_keywords)\n",
    "graph.add_node_types({n: \"Keyword\" for n in most_frequent_keywords})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Add sets of dataset ids as properties of our keyword nodes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "aggregated_datasets.index.name = \"@id\"\n",
    "graph.add_node_properties(aggregated_datasets, prop_type=\"category\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph._nodes.sample(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n_datasets = len(keyword_data[\"dataset\"].unique())\n",
    "print(\"Total number of dataset: \", n_datasets)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## II. Co-occurrence graph generation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We create a co-occurrence graph using the 500 most frequent keywords: nodes are keywords and a pair of nodes is connected with an undirected edge if two corresponding keywords co-occur in at lease one dataset. Moreover, the edges are equipped with weights corresponding to:\n",
    "\n",
    "- raw co-occurrence frequency\n",
    "- normalized pointwise mutual information (NPMI)\n",
    "- frequency- and mutual-information-based distances (1 / frequency, 1 / NPMI)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "generator = CooccurrenceGenerator(graph)\n",
    "comention_edges = generator.generate_from_nodes(\n",
    "    \"dataset\", total_factor_instances=n_datasets,\n",
    "    compute_statistics=[\"frequency\", \"npmi\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Remove edges with zero NPMI"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "comention_edges = comention_edges[comention_edges[\"npmi\"] > 0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compute the NPMI-based distance score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "comention_edges.loc[:, \"distance_npmi\"] = comention_edges.loc[:, \"npmi\"].apply(lambda x: 1 / x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Add generated edges to the property graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph.remove_node_properties(\"dataset\") # Remove datasets from node properties\n",
    "graph._edges = comention_edges.drop(columns=[\"common_factors\"])\n",
    "graph._edge_prop_types = {\n",
    "    \"frequency\": \"numeric\",\n",
    "    \"npmi\": \"numeric\",\n",
    "    \"distance_npmi\": \"numeric\"\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph.edges(raw_frame=True).sample(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## III. Initializing Neo4j graph from a PGFrame\n",
    "\n",
    "In this section we will populate a Neo4j database with the generated keyword co-occurrence property graph."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the cells below provide the credentials for connecting to your instance of the Neo4j database."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "NEO4J_URI = \"bolt://localhost:7687\"\n",
    "NEO4J_USER = \"neo4j\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "NEO4J_PASSWORD = getpass.getpass()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Populate the Neo4j database with the nodes and edges of the generated property graph using `pgframe_to_neo4j`. We specify labels of nodes (`Keyword`) and edges (`CoOccurs`) to use for the new elements."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "NODE_LABEL = \"Keyword\"\n",
    "EDGE_LABEL = \"CoOccurs\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# (!) If you run this cell multiple times, you may create nodes and edges of the graph\n",
    "# multiple times, if you have already run the notebook, set the parameter `pgframe` to None\n",
    "# this will prevent population of the Neo4j database with the generated graph, but will create\n",
    "# the necessary `Neo4jGraphView` object.\n",
    "graph_view = pgframe_to_neo4j(\n",
    "    pgframe=graph,  # None, if no population is required\n",
    "    uri=NEO4J_URI, username=NEO4J_USER, password=NEO4J_PASSWORD, \n",
    "    node_label=NODE_LABEL, edge_label=EDGE_LABEL,\n",
    "    directed=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# # If you want to clear the database from created elements, run\n",
    "# graph_view._clear()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## IV. Nearest neighours by NPMI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this section we will compute top 10 neighbors of the keywords 'mars' and 'saturn' by the highest NPMI.\n",
    "\n",
    "To do so, we will use the `top_neighbors` method of the `PathFinder` interface provided by the BlueGraph. This interface allows us to search for top neighbors with the highest edge weight. In this example, we use Neo4j-based `Neo4jPathFinder` interface."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "path_finder = Neo4jPathFinder.from_graph_object(graph_view)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "path_finder.top_neighbors(\"mars\", 10, weight=\"npmi\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "path_finder.top_neighbors(\"saturn\", 10, weight=\"npmi\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## V. Graph metrics and node centrality measures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "BlueGraph provides the `MetricProcessor` interface for computing various graph statistics. We will use Neo4j-based `Neo4jMetricProcessor` interface."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "metrics = Neo4jMetricProcessor.from_graph_object(graph_view)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Density of the constructed network: \", metrics.density())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Node centralities"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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": [
    "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": [
    "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": [
    "metrics.betweenness_centrality(\"distance_npmi\", write=True, write_property=\"betweenness\")"
   ]
  },
  {
   "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_graph = metrics.get_pgframe(node_prop_types=graph._node_prop_types, edge_prop_types=graph._edge_prop_types)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "new_graph.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_graph.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_graph.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_graph.nodes(raw_frame=True).nlargest(10, columns=[\"betweenness\"]).index:\n",
    "    print(\"\\t\", n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## VI. Community detection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Community detection_ methods partition the graph 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. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, we create a `Neo4j`-based instance and use several different community detection strategies provided by Neo4j."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "com_detector = Neo4jCommunityDetector.from_graph_object(graph_view)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Louvain algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "partition = com_detector.detect_communities(\n",
    "    strategy=\"louvain\", weight=\"npmi\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Modularity: \", com_detector.evaluate_parition(partition, metric=\"modularity\", weight=\"npmi\"))\n",
    "print(\"Performance: \", com_detector.evaluate_parition(partition, metric=\"performance\", weight=\"npmi\"))\n",
    "print(\"Coverage: \", com_detector.evaluate_parition(partition, metric=\"coverage\", weight=\"npmi\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Label propagation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "partition = com_detector.detect_communities(\n",
    "    strategy=\"lpa\", weight=\"npmi\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Modularity: \", com_detector.evaluate_parition(partition, metric=\"modularity\", weight=\"npmi\"))\n",
    "print(\"Performance: \", com_detector.evaluate_parition(partition, metric=\"performance\", weight=\"npmi\"))\n",
    "print(\"Coverage: \", com_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": [
    "com_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_graph = com_detector.get_pgframe(\n",
    "    node_prop_types=new_graph._node_prop_types,\n",
    "    edge_prop_types=new_graph._edge_prop_types)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "new_graph.nodes(raw_frame=True).sample(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## VII. Export network and the computed metrics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Save graph as JSON"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "new_graph.export_json(\"../data/nasa_comention.json\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Save the graph for Gephi import."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "new_graph.export_to_gephi(\n",
    "    \"../data/gephi_nasa_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 raw frequency of the co-occurrence edges, node sizes are proportional to the PageRank of nodes and edge thickness to the NPMI values.\n",
    "\n",
    "![alt text](./figures/nasa/full_network.png \"NASA dataset keywords co-occurrence network\")\n",
    "\n",
    "We can zoom into some of the communities of keywords identified using the community detection method above\n",
    "\n",
    "Community | Zoom\n",
    "- | - \n",
    "Celestial bodies <img src=\"./figures/nasa/celestial_body_cluster.png\" alt=\"Drawing\" style=\"width: 400px;\"/>|<img src=\"./figures/nasa/celestial_body_cluster_zoom.png\" alt=\"Drawing\" style=\"width: 400px;\"/>\n",
    "Earth science <img src=\"./figures/nasa/earth_science.png\" alt=\"Drawing\" style=\"width: 400px;\"/>|<img src=\"./figures/nasa/earch_science_zoom.png\" alt=\"Drawing\" style=\"width: 400px;\"/>\n",
    "Space programs and missions <img src=\"./figures/nasa/programs_missions.png\" alt=\"Drawing\" style=\"width: 400px;\"/>|<img src=\"./figures/nasa/programs_missions_zoom.png\" alt=\"Drawing\" style=\"width: 400px;\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## VIII. Minimum spanning tree"
   ]
  },
  {
   "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 Neo4j-based implementation of the `PathFinder` interface."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "path_finder.minimum_spanning_tree(distance=\"distance_npmi\", write=True, write_edge_label=\"MSTEdge\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "new_graph._nodes.index.unique()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "nx_path_finder = NXPathFinder(new_graph, directed=False)\n",
    "tree = nx_path_finder.minimum_spanning_tree(distance=\"distance_npmi\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_pgframe = networkx_to_pgframe(\n",
    "    tree,\n",
    "    node_prop_types=new_graph._node_prop_types,\n",
    "    edge_prop_types=new_graph._edge_prop_types)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_pgframe._nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_pgframe.export_to_gephi(\n",
    "    \"../data/gephi_nasa_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": [
    "![alt text](./figures/nasa/tree.png \"Minimum spanning tree\")\n",
    "\n",
    "Zoom Earth Science | Zoom Asteroids\n",
    "-|-\n",
    "![alt text](./figures/nasa/tree_zoom_1.png \"Minimum spanning tree\")|![alt text](./figures/nasa/tree_zoom_2.png \"Minimum spanning tree\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## IX. 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": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "path = path_finder.shortest_path(\"ecosystems\", \"oceans\")\n",
    "pretty_print_paths([path])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The cell above illustrates that the single shortest path form 'ecosystems' and 'oceans' consists of the direct edge between them.\n",
    "\n",
    "Now to explore related keywords 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",
    "In the following examples we use Yen's algorithm for finding $n$ loopless shortest paths from the source to the target (https://en.wikipedia.org/wiki/Yen%27s_algorithm)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paths = path_finder.n_shortest_paths(\n",
    "    \"ecosystems\", \"oceans\", n=10,\n",
    "    distance=\"distance_npmi\",\n",
    "    strategy=\"yen\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pretty_print_paths(paths)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paths = path_finder.n_shortest_paths(\n",
    "    \"mission\", \"mars\", n=10,\n",
    "    distance=\"distance_npmi\",\n",
    "    strategy=\"yen\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pretty_print_paths(paths)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## X. 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": [
    "paths1 = path_finder.n_nested_shortest_paths(\n",
    "    \"ecosystems\", \"oceans\",\n",
    "    top_level_n=10, nested_n=3, depth=2, distance=\"distance_npmi\",\n",
    "    strategy=\"yen\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paths2 = path_finder.n_nested_shortest_paths(\n",
    "    \"mission\", \"mars\",\n",
    "    top_level_n=10, nested_n=3, depth=2, distance=\"distance_npmi\",\n",
    "    strategy=\"yen\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now build and 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_oceans = networkx_to_pgframe(nx_path_finder.get_subgraph_from_paths(paths1))\n",
    "summary_graph_mars = networkx_to_pgframe(nx_path_finder.get_subgraph_from_paths(paths2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Save the graph for Gephi import.\n",
    "summary_graph_oceans.export_to_gephi(\n",
    "    \"../data/gephi_nasa_path_graph_oceans\", \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",
    "    })\n",
    "# Save the graph for Gephi import.\n",
    "summary_graph_mars.export_to_gephi(\n",
    "    \"../data/gephi_nasa_path_graph_mars\", \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 graphs visualized with Gephi\n",
    "\n",
    "Ecosystems <-> Oceans\n",
    "<img src=\"./figures/nasa/path_graph_ocean.png\" alt=\"NASA path graph\" style=\"width: 800px;\"/>\n",
    "\n",
    " Mission <-> Mars\n",
    "<img src=\"./figures/nasa/path_graph_mars.png\" alt=\"NASA path graph\" 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
}