Part 2 - Network Science.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b6f26d5a-daad-493d-aeb6-7e312ee2472d",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "import calendar\n",
    "import json\n",
    "import os\n",
    "import pickle\n",
    "import random\n",
    "import re\n",
    "import sys\n",
    "from datetime import date\n",
    "from typing import List\n",
    "\n",
    "import dateutil\n",
    "import graphistry\n",
    "import matplotlib.pyplot as plt\n",
    "import networkx as nx\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import seaborn as sns\n",
    "\n",
    "from graphml_class.clean import clean_graph\n",
    "from graphml_class.palette import CATEGORICAL_PALETTE\n",
    "\n",
    "sns.set(style='white', context='poster')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f9c73178-317f-4bda-953e-74597e4b6f6c",
   "metadata": {},
   "source": [
    "Part 2: Network Science: Quantitative Networks\n",
    "==============================================\n",
    "\n",
    "Having demonstrated _knowledge graph construction_ in Part 1, it is time to survey network science! Please keep in mind that as a vast and multidisciplinary field with papers covering many areas of science, network science is impossible to cover completely. What I will do is paint the broad strokes of tools common to many fields where network science is used to analyze and understand domain-specific networks.\n",
    "\n",
    "_Note: you may notice we don't cover community detection [graph clustering] or role discovery in this section of the course. That's because we do so in Part 4 - Graph Machine Learning :)_\n",
    "\n",
    "## Section Textbook\n",
    "\n",
    "<center><img src=\"images/Network-Science-Book-by-Albert-Laszlo-Barabasi.png\" width=\"800px\"/></center>\n",
    "\n",
    "[Network Science](http://networksciencebook.com) is a book on the web at [http://networksciencebook.com/](http://networksciencebook.com/) by Albert-László Barabási is an excellent resource that contains more information than I can cover in 20 classroom hours. It is a resource where you can look up terms and techniques. [Albert-László Barabási](https://barabasi.com/) [see his [Wikipedia page](https://en.wikipedia.org/wiki/Albert-L%C3%A1szl%C3%B3_Barab%C3%A1si)] is a world-renowned expert who discovered [Scale Free Networks](https://en.wikipedia.org/wiki/Scale-free_network). Network Science provides more in-depth treatment of topics like [graph theory](http://networksciencebook.com/chapter/2), [random networks](http://networksciencebook.com/chapter/3) and [communities](http://networksciencebook.com/chapter/9), as well as many more. I encourage students to take the time to review what we cover in this section of the course in Network Science and to refer to it later as well.\n",
    "\n",
    "## Setting up Graphistry\n",
    "\n",
    "Throughout this part of the course we will be using `pygraphistry` and [Graphistry Hub](https://hub.graphistry.com/) [https://hub.graphistry.com/](https://hub.graphistry.com/) to visualize networks. Both are free for personal use and are powerful for visualizing networks large and small.\n",
    "\n",
    "You can [signup](https://hub.graphistry.com/accounts/signup/) for a Graphistry account at [https://hub.graphistry.com/accounts/signup/](https://hub.graphistry.com/accounts/signup/). <b>You should use a username/password/email to get the required credentials</b>, although after that you can login with your Github or Google account.\n",
    "\n",
    "<center><img src=\"images/graphistry_hub_registration.png\" /></center>\n",
    "\n",
    "Retain and use your credentials in the login form and in the environment variables in the next cell below. You should set the `GRAPHISTRY_USERNAME` and `GRAPHISTRY_PASSWORD` variables in the `env/graphistry.env` file, and then restart this docker container to pickup the new values.\n",
    "\n",
    "<center><img src=\"images/graphistry_hub_homepage.png\" /></center>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "526ec783-7ddf-406c-913e-588c376cde4c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Environment variable setup\n",
    "GRAPHISTRY_USERNAME = os.getenv(\"GRAPHISTRY_USERNAME\")\n",
    "GRAPHISTRY_PASSWORD = os.getenv(\"GRAPHISTRY_PASSWORD\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "96638e3d-bff3-48eb-916a-34b9b042a080",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# May need to re-run if you step away for a while\n",
    "graphistry.register(\n",
    "    api=3,\n",
    "    username=GRAPHISTRY_USERNAME,\n",
    "    password=GRAPHISTRY_PASSWORD,\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "19301619-b0bb-442b-9277-79db0287a5c2",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Configuration for Graphistry\n",
    "GRAPHISTRY_PARAMS = {\n",
    "    \"play\": 500,\n",
    "    \"pointOpacity\": 0.7,\n",
    "    \"edgeOpacity\": 0.3,\n",
    "    \"edgeCurvature\": 0.3,\n",
    "    \"showArrows\": True,\n",
    "    \"gravity\": 0.15,\n",
    "    \"showPointsOfInterestLabel\": False,\n",
    "    \"labels\": {\n",
    "        \"shortenLabels\": False,\n",
    "    },\n",
    "}\n",
    "FAVICON_URL = \"https://graphlet.ai/assets/icons/favicon.ico\"\n",
    "LOGO = {\"url\": \"https://graphlet.ai/assets/Branding/Graphlet%20AI.svg\", \"dimensions\": {\"maxWidth\": 100, \"maxHeight\": 100}}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dee9d6bf-d6f4-4104-9579-e11c4f844072",
   "metadata": {},
   "source": [
    "# Network Science on Citation Networks\n",
    "\n",
    "We are going to use the knowledge graph (property graph) we prepared in Part 1. Jst as a review, let me remind you what that dataset is...\n",
    "\n",
    "## High Energy Physics Theory Citation Network (arXiv)\n",
    "\n",
    "We built a simple, directional `nx.DiGraph` of a citation network where nodes are papers and citations are edges [High-energy physics theory citation network](https://snap.stanford.edu/data/cit-HepTh.html) from [Stanford SNAP](http://snap.stanford.edu/). A citation network describes how one academic paper cites another one.\n",
    "\n",
    "> Arxiv HEP-TH (high energy physics theory) citation graph is from the e-print arXiv and covers all the citations within a dataset of 27,770 papers with 352,807 edges. If a paper i cites paper j, the graph contains a directed edge from i to j. If a paper cites, or is cited by, a paper outside the dataset, the graph does not contain any information about this.\n",
    ">\n",
    "> The data covers papers in the period from January 1993 to April 2003 (124 months). It begins within a few months of the inception of the arXiv, and thus represents essentially the complete history of its HEP-TH section.\n",
    ">\n",
    "> The data was originally released as a part of [2003 KDD Cup](http://www.cs.cornell.edu/projects/kddcup/).\n",
    "\n",
    "J. Leskovec, J. Kleinberg and C. Faloutsos. [Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations.](http://www.cs.cmu.edu/~jure/pubs/powergrowth-kdd05.pdf) ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2005.\n",
    "\n",
    "## Dataset Citation\n",
    "\n",
    "```\n",
    "Paper: hep-th/0002031\n",
    "From: Maulik K. Parikh \n",
    "Date: Fri, 4 Feb 2000 17:04:51 GMT   (10kb)\n",
    "\n",
    "Title: Confinement and the AdS/CFT Correspondence\n",
    "Authors: D. S. Berman and Maulik K. Parikh\n",
    "Comments: 12 pages, 1 figure, RevTeX\n",
    "Report-no: SPIN-1999/25, UG-1999/42\n",
    "Journal-ref: Phys.Lett. B483 (2000) 271-276\n",
    "\\\\\n",
    "  We study the thermodynamics of the confined and unconfined phases of\n",
    "superconformal Yang-Mills in finite volume and at large N using the AdS/CFT\n",
    "correspondence. We discuss the necessary conditions for a smooth phase\n",
    "crossover and obtain an N-dependent curve for the phase boundary.\n",
    "\\\\\n",
    "```\n",
    "\n",
    "## Tools\n",
    "\n",
    "We use `networkx`, `pandas` and optionally you may use `cugraph` to re-implement parts of this course section using your GPU. The `rapids` docker image can help.\n",
    "\n",
    "```bash\n",
    "docker compose up rapids\n",
    "```\n",
    "\n",
    "This runs a Jupyter Notebook that has NVIDIA support enabled. This *should* work by the time you read this :)\n",
    "\n",
    "### About NetworkX\n",
    "\n",
    "The [networkx Algorithms documentation](https://networkx.org/documentation/stable/reference/algorithms/index.html) lists a fairly comprehensive set of tools available for the network scientist. We will be using networkx throughout the course.\n",
    "\n",
    "### About cuGraph\n",
    "\n",
    "The [NVIDIA RAPIDS cuGraph](https://docs.rapids.ai/api/cugraph/stable/) ([Github](https://github.com/rapidsai/cugraph)) is a GPU accelerated graph analytics library that is roughly compatible with `networkx`. It can rapidly compute expensive metrics compare to CPU, where processing is often limited to a single core. An NVIDIA GPU and cuGraph are optional in this course, but will be helpful as you use complex algorithms on large networks."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "25cb6a99-8098-4c63-8d44-33caba28c050",
   "metadata": {},
   "source": [
    "## Load and Test our Citation Graph\n",
    "\n",
    "Load the data and count the nodes and edges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4b04e501-4648-46c5-85fd-64f954ff5837",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "G: nx.DiGraph = nx.read_gexf(path=\"data/physics_labeled.gexf.gz\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "55cc009f-99ba-4b63-86e3-7629d1b76ba7",
   "metadata": {},
   "outputs": [],
   "source": [
    "G.number_of_nodes(), G.number_of_edges()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f24b55e4-46ac-4aad-a4e1-81e02f7d1d37",
   "metadata": {},
   "source": [
    "## Load the File to Net and Net to File Node ID Mappings\n",
    "\n",
    "We use these below, so we [pickled](https://wiki.python.org/moin/UsingPickle) them in Part 1. JSON can't handle numeric keys, or we would have used that :)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6aedb6f7-a3f2-4940-974c-9097177f6bf7",
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(\"data/citation/file_to_net.pkl\", \"rb\") as f:\n",
    "    file_to_net = pickle.load(f)\n",
    "\n",
    "# Everything ok? Yes!\n",
    "list(file_to_net.items())[0:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6029c7bd-8ac9-4ca1-9492-79568047be2a",
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(\"data/citation/net_to_file.pkl\", \"rb\") as f:\n",
    "    net_to_file = pickle.load(f)\n",
    "\n",
    "# Everything ok here too? Yes!\n",
    "list(net_to_file.items())[0:10]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ccf14753-ea1a-4735-abf8-d8260caa951d",
   "metadata": {},
   "source": [
    "## Convert our `str` Node / Edge IDs to `int` IDs\n",
    "\n",
    "We lost something when we saved in GEXF format and loaded the graph back. All our node and edge IDs are strings... we must convert them back to integers before we move on, as some libraries require this!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c8fedb3b-db59-4046-915c-6afc073cf759",
   "metadata": {},
   "outputs": [],
   "source": [
    "def convert_ids_to_int(G):\n",
    "    # Create a new directed graph\n",
    "    G_int = nx.DiGraph()\n",
    "    \n",
    "    # Create a mapping from string IDs to integer IDs\n",
    "    id_mapping = {str_id: int(str_id) for str_id in G.nodes()}\n",
    "    \n",
    "    # Copy nodes and attributes, converting IDs to integers\n",
    "    for str_id, data in G.nodes(data=True):\n",
    "        int_id = id_mapping[str_id]\n",
    "        G_int.add_node(int_id, **data)\n",
    "    \n",
    "    # Copy edges and attributes, converting IDs to integers\n",
    "    for str_id1, str_id2, data in G.edges(data=True):\n",
    "        int_id1, int_id2 = id_mapping[str_id1], id_mapping[str_id2]\n",
    "        G_int.add_edge(int_id1, int_id2, **data)\n",
    "    \n",
    "    return G_int\n",
    "\n",
    "# Convert G to use integer IDs\n",
    "G_int = convert_ids_to_int(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e3f21f79-9fcb-4570-9bde-c1fc1adf9c8a",
   "metadata": {},
   "outputs": [],
   "source": [
    "G_int.number_of_nodes(), G_int.number_of_edges()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6de3502c-af87-4973-b2e6-9fef1887c21d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let's test or integer index now... we pickled it instead of JSONized it so it would retain its integer keys and values!\n",
    "test_id = file_to_net[9711194]\n",
    "G_int.nodes[test_id]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3d1669eb-08ab-4485-a0dc-0365646aa71d",
   "metadata": {},
   "source": [
    "### `G_int` --> `G`\n",
    "\n",
    "Now we can assign our new integer graph back to `G` and use it below :)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4b785e84-5a60-4ab3-a8a9-ba6b66f40e93",
   "metadata": {},
   "outputs": [],
   "source": [
    "G = G_int"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9dc0c296-d40d-4f99-bf12-f29d5a624e8e",
   "metadata": {},
   "source": [
    "## Summarize the Properties of our DiGraph\n",
    "\n",
    "Let's check how many nodes and edges we have. This will help evaluate how we are doing when we parse the abstracts to add properties to our DiGraph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "db5c603f-d26b-4b6c-905d-bab3b46638f5",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "print(f\"Total nodes: {G.number_of_nodes():,}\")\n",
    "print(f\"Total edges: {G.number_of_edges():,}\")\n",
    "print(f\"Total components: {nx.number_connected_components(G.to_undirected()):,}\")\n",
    "print(f\"Undirected is weakly connected: {nx.is_weakly_connected(G)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "77d824a6-b246-4539-873d-e12fb33fd7b9",
   "metadata": {},
   "source": [
    "### Describe a NetworkX Graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "35015fd1-50f0-4076-8392-a32084068d0d",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def describe_graph(G):\n",
    "    \"\"\"Given a networkx Graph, describe its key properties.\"\"\"\n",
    "\n",
    "    print(f\"Number of nodes: {G.number_of_nodes():,}\")\n",
    "    print(f\"Number of edges: {G.number_of_edges():,}\")\n",
    "\n",
    "    # Compute various network properties\n",
    "    degrees = [deg for node, deg in nx.degree(G)]\n",
    "    avg_degree = sum(degrees) / G.number_of_nodes()\n",
    "    median_degree = np.median(degrees)\n",
    "    print(f\"Mean degree: {avg_degree:,.3f}\")\n",
    "    print(f\"Mediam degree: {median_degree:,.3f}\")\n",
    "\n",
    "    components = nx.connected_components(G.to_undirected())\n",
    "    largest_component = max(components, key=len)\n",
    "    print(f\"Number of connected components: {nx.number_connected_components(G.to_undirected()):,}\")\n",
    "    print(f\"Size of the largest component: {len(largest_component):,}\")\n",
    "\n",
    "    # If the network is directed, you can also print the following\n",
    "    if G.is_directed():\n",
    "        print(f\"Number of strongly connected components: {nx.number_strongly_connected_components(G):,}\")\n",
    "        print(f\"Number of weakly connected components: {nx.number_weakly_connected_components(G):,}\")\n",
    "\n",
    "    avg_clustering = nx.average_clustering(G)\n",
    "    median_clustering = np.median(list(nx.clustering(G).values()))\n",
    "    print(f\"Mean clustering coefficient: {avg_clustering:.6f}\")\n",
    "    print(f\"Median clustering coefficient: {median_clustering:.6f}\")\n",
    "\n",
    "    # try:\n",
    "    #     avg_shortest_path_length = nx.average_shortest_path_length(G)\n",
    "    #     print(f\"Average shortest path length: {avg_shortest_path_length}\")\n",
    "    # except nx.NetworkXError:\n",
    "    #     print(\"Graph is not connected, average shortest path length is not defined.\")\n",
    "\n",
    "describe_graph(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c861508c-20a0-463b-aff4-6c824db0a5c1",
   "metadata": {},
   "source": [
    "### Histogram of Connected Component Sizes\n",
    "\n",
    "143 weakly connected components - our graph is not one large hairball! Let's see what sizes our connected components are. Usually these are a power law distribution, with one large component taking up 30 or more percent of nodes and edges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d85de86d-b403-469e-afed-c5752210dc9d",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Get connected components and their sizes\n",
    "components = nx.connected_components(G.to_undirected())\n",
    "component_sizes = [len(c) for c in components]\n",
    "\n",
    "# Increase figure size\n",
    "plt.figure(figsize=(10,6))\n",
    "\n",
    "# Use seaborn to create the histogram\n",
    "sns.histplot(component_sizes, kde=True, bins=30, log_scale=True)\n",
    "plt.title('Histogram of Connected Component Sizes')\n",
    "plt.xlabel('Component Size')\n",
    "plt.ylabel('Count')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "31d950c6-6e7f-4b71-8348-5a1bb5399952",
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.connected_components(G.to_undirected())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e5acd03-8e92-440a-80a5-fc66b33004af",
   "metadata": {},
   "source": [
    "## Average Clustering Coefficient\n",
    "\n",
    "The clustering coefficient is an indicator of the interconnectedness or cohesion among nodes in a graph. It's a measure of the extent to which the immediate neighbors of a particular node link to each other.\n",
    "\n",
    "The range of a clustering coefficient is between 0 and 1:\n",
    "\n",
    "When the clustering coefficient is 0, it signifies a scenario where none of the nodes have direct connections with each other. This can be seen in graphs such as a tree or a radial network where nodes are only connected to a central hub, but not with each other.\n",
    "\n",
    "In contrast, a clustering coefficient of 1 indicates a fully connected graph. Here, each node in the graph is directly linked with all other nodes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5d7bbb44-99c0-4b62-856e-7cb40c9fe82b",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# A good start...\n",
    "print(f\"Mean degree: {G.number_of_edges()/G.number_of_nodes():.3f}\")\n",
    "print(f\"Median degree: {np.median([deg for node, deg in G.degree()]):.3f}\")\n",
    "\n",
    "clustering_coefficient = nx.average_clustering(G)\n",
    "print(f\"Graph clustering coefficient: {clustering_coefficient:.3f}\")\n",
    "print(f\"Median clustering coefficient: {np.median([coeff for node, coeff in nx.clustering(G).items()]):.3f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "10d90ed4-ab34-452f-9a7d-abd63ecd98ab",
   "metadata": {
    "tags": []
   },
   "source": [
    "An average clustering coefficient of 0.16 in our `nx.DiGraph` implies there is a relatively low degree of clustering or tight-knit communities. It suggests a network structure that is more spread out, with fewer connections among immediate neighbors of each node. Networks such as web pages or citation networks often present lower clustering coefficients, as these networks are characterized by a wide range of diverse connections that do not necessarily link back to each other. Citation networks are actually temporal networks and are constrained by the fact that papers can't cite future papers, but only past ones. They are therefore DAGs - directed, acyclic graphs.\n",
    "\n",
    "### Node Clustering Coefficients\n",
    "\n",
    "The clustering coefficient of a node is a measure of the degree to which nodes in a graph tend to cluster together. It provides an indication of how the neighbors of a _particular node_ are interconnected. It measures how close a node's neighbors are to being a complete graph or a clique. It is defined as the fraction of possible triangles that exist through the node, or equivalently, as the fraction of the node's neighbors that are also neighbors of each other.\n",
    "\n",
    "We're going to add a property to each node in the network for each node's clustering coefficient. You can find more on clustering coefficients in citation networks in [Modeling the clustering in citation networks](https://arxiv.org/abs/1104.4209)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "beb65251-2580-41d3-9297-c17c0c89be26",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "clustering_coeffs = nx.clustering(G)\n",
    "\n",
    "for node, clustering_coeff in clustering_coeffs.items():\n",
    "    G.nodes[node]['clustering_coefficient'] = clustering_coeff"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b92790ec-d942-4db9-a001-46b253096fb3",
   "metadata": {},
   "source": [
    "Let's look at how the clustering coefficient is distributed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "56e863c2-61aa-426b-ba8b-0d7cd965e5fd",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Get connected components and their sizes\n",
    "clustering_coeff_counts = [val + 1 for key, val in clustering_coeffs.items()]\n",
    "\n",
    "plt.figure(figsize=(12,8))\n",
    "\n",
    "# Use seaborn to create the histogram\n",
    "sns.histplot(clustering_coeff_counts, kde=True, bins=30, log_scale=False)\n",
    "plt.title('Histogram of Node Clustering Coefficients')\n",
    "plt.xlabel('Clustering Coefficient')\n",
    "plt.ylabel('Count')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b5d90d7c-8ddb-453d-b0a4-2e6b01623cd8",
   "metadata": {},
   "source": [
    "A clustering coefficient of around 0.2 indicates that most nodes have relatively low (but still significant) clustering coefficients - their neighbors are sparsely connected. How does this fit with the average degree of 12 and graph clustering coefficient of 0.16? 16% of the average node's connections are connected with one another. From the histogram which has a skewed but fairly normal distribution, it looks like the _typical_ node has these properties as well. These are characteristics of a [Small World Network](https://en.wikipedia.org/wiki/Small-world_network). Most citation graphs are [small world networks](https://en.wikipedia.org/wiki/Citation_graph). \n",
    "\n",
    "Note: NetworkX has a set of functions [`networkx.algorithms.smallworld`](https://networkx.org/documentation/stable/reference/algorithms/smallworld.html) that can determine the \"small worldiness of a network.\"\n",
    "\n",
    "Why do we care what kind of theoretical graph model fits our *real world* network. Because the field of network science is multidisciplinary and papers cover topics from physics to biology to sociology to microchip design. The type of network you have - often in the same settings as yours - has been rigorously studied. Reading a paper or two describing your graph gives you the context you need to extract insights, build models and auomate tasks using machine learning and artificial intelligence."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4c85f9ae-d8e9-417e-92e0-5e3fb68879f0",
   "metadata": {},
   "source": [
    "# Visualizing Networks in Graphistry\n",
    "\n",
    "[Graphistry](https://graphistry.com/) can handle hundreds of thousands of nodes and edges using GPU acceleration. They provide GPU acceleration via [Graphistry Hub](https://hub.graphistry.com/), so we don't need to have a GPU in our notebook computers. That being said... we will sample our network to our algorithms below run faster and avoid any problems on slower computers.\n",
    "\n",
    "Once we sample, let's take a first look at our network in Graphistry to see what it looks like! First we are going to use a sampling hack, and then we are going to use [littleballoffur](https://github.com/benedekrozemberczki/littleballoffur) to sample _properly_ (or at least how we expect!) in a variety of ways."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf65ff94-21ae-470a-a72b-988a1c524481",
   "metadata": {},
   "source": [
    "## Node Sampling Hack: PageRank Weighted Random Nodes\n",
    "\n",
    "The entire network of millions of nodes is too large for Graphistry. We will sample it down to about 15% of its original size and take a peek :)\n",
    "\n",
    "> The most obvious way to create a sample graph is to uniformly at random select a set of nodes N and a sample is then a graph induced by the set of nodes N. We call this algorithm the Random Node (RN) sampling.\n",
    "\n",
    "--Leskovec and Faloutsos, 2006\n",
    "\n",
    "We are going to randomly sample nodes to get a set of nodes, and then connect them with all incident edges, the induced subgraph of the sample nodes. Rather than sample uniformly, we will weight with nodes' probabilities by their normalized degrees and PageRank scores. This technique was suggested by [Jure Leskovec](https://dblp.org/pid/l/JureLeskovec.html) and [Christos Faloutsos](https://dblp.org/pid/f/CFaloutsos.html) in the paper [Sampling from Large Graphs](https://cs.stanford.edu/~jure/pubs/sampling-kdd06.pdf) which presents a range of techniques for sampling large graphs.\n",
    "\n",
    "One thing from this paper to note, is the minimum sample size to maintain a network's structural properties.\n",
    "\n",
    "> We show that a 15% sample is usually enough, to match the properties (S1–S9 and T1–T5) of the real graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "de93490c-a43f-4798-b88b-5badf8b5be2e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Degree-based probabilities\n",
    "degrees = [degree for (node_id, degree) in G.degree()]\n",
    "degree_probs = np.array(degrees) / np.sum(degrees)\n",
    "degree_probs, degree_probs.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3e54107e-6216-47aa-867a-ca3e593debc7",
   "metadata": {},
   "outputs": [],
   "source": [
    "# PageRank-based probabilities\n",
    "pagerank_probs = np.array(list(nx.pagerank(G).values()))\n",
    "pagerank_probs, pagerank_probs.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "96e10deb-c133-4199-abc9-ee2b9a8057a9",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Degree node ID sample\n",
    "degree_node_sample = np.random.choice(G.nodes(), size=5000, replace=False, p=degree_probs)\n",
    "degree_node_sample, degree_node_sample.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "34af7afc-f2fb-465f-9013-4900ad9461b5",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Degree sampled subgraph\n",
    "G_degree_sample = G.subgraph(degree_node_sample).copy()\n",
    "G_degree_sample.number_of_nodes(), G_degree_sample.number_of_edges()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f0bf41e3-a8f0-476d-bd53-d494cbfa471a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# PageRank node ID sample\n",
    "pagerank_node_sample = np.random.choice(G.nodes(), size=5000, replace=False, p=pagerank_probs)\n",
    "pagerank_node_sample, pagerank_node_sample.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f6f5ed47-5774-44f1-a53d-1685eeb6405a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# PageRank sampled subgraph\n",
    "G_pagerank_sample = G.subgraph(pagerank_node_sample).copy()\n",
    "G_pagerank_sample.number_of_nodes(), G_pagerank_sample.number_of_edges()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8389ecb2-388a-4aa6-87a0-66efd997c358",
   "metadata": {},
   "source": [
    "### Interpreting Sample Node / Edge Counts\n",
    "\n",
    "Note that while both degree and pagerank weighted random graph samples have 5,000 nodes the degree weighted sample has 65,000 edges and the PageRank weighted sample has just 34,000. That means the degree weighted sample is more biased towards hubs - high degree nodes."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75b297b8-986c-4e17-8ef9-6e442146e2c9",
   "metadata": {},
   "source": [
    "### Remove all Degree 0 Nodes from Both Subgraphs\n",
    "\n",
    "They hover around the outer edge and don't encode much information.\n",
    "\n",
    "Look at the node and edge counts. Note how there are more edges in the degree-weighted sample than the PageRank weighted sample. This is how Leskovec describes it - as being biased towards nodes with a higher degree."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5892eb74-e168-4801-9880-ef17c105a09b",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Remove degree sampled zero-degree ndoes\n",
    "degree_degree_gt_zero = [node for node, degree in G_degree_sample.degree() if degree > 0]\n",
    "G_degree_gt_zero = G_degree_sample.subgraph(degree_degree_gt_zero).copy()\n",
    "\n",
    "G_degree_gt_zero.number_of_nodes(), G_degree_gt_zero.number_of_edges()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ae895cfd-bcb3-455c-9dd9-cb10dc3f8ce1",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Remove PageRank sample zero-degree nodes\n",
    "pagerank_degree_gt_zero = [node for node, degree in G_pagerank_sample.degree() if degree > 0]\n",
    "G_pagerank_gt_zero = G_pagerank_sample.subgraph(pagerank_degree_gt_zero).copy()\n",
    "\n",
    "G_pagerank_gt_zero.number_of_nodes(), G_pagerank_gt_zero.number_of_edges()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6e7eb8ee-fe99-4f7e-bfbe-da54702cae60",
   "metadata": {},
   "source": [
    "## Comparing Degree and PageRank Weighted Sample Visualizations\n",
    "\n",
    "### Degree Weighted Random Sample"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "685e604e-5caa-48ef-b257-077c93e914ac",
   "metadata": {},
   "outputs": [],
   "source": [
    "g = (\n",
    "    graphistry.bind(\n",
    "        source=\"src\",\n",
    "        destination=\"dst\",\n",
    "        node=\"nodeid\",\n",
    "        point_title=\"Title\",\n",
    "        point_label=\"Title\",\n",
    "    )\n",
    "    .scene_settings(\n",
    "        edge_opacity=0.4,\n",
    "    )\n",
    "    .addStyle(\n",
    "        page={\n",
    "            \"title\": \"Degree Weighted Sample\",\n",
    "            \"favicon\": FAVICON_URL,\n",
    "        },\n",
    "        logo=LOGO,\n",
    "    )\n",
    "    .settings(\n",
    "        url_params=GRAPHISTRY_PARAMS,\n",
    "        height=800,\n",
    "    )\n",
    ")\n",
    "g.plot(G_degree_gt_zero)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "287597bc-5919-43ae-87d6-3052d3c7cd18",
   "metadata": {},
   "source": [
    "<center><img src=\"images/Graphistry_Figure_1.png\" /></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "42f361dd-1c1c-485d-a8e6-ade17483b2ca",
   "metadata": {},
   "source": [
    "### PageRank Weighted Sample"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8c78b72f-2000-492c-a1e1-fad49060ac9c",
   "metadata": {},
   "outputs": [],
   "source": [
    "g = (\n",
    "    graphistry.bind(\n",
    "        source=\"src\",\n",
    "        destination=\"dst\",\n",
    "        node=\"nodeid\",\n",
    "        point_title=\"Title\",\n",
    "        point_label=\"Title\",\n",
    "    )\n",
    "    .scene_settings(\n",
    "        edge_opacity=0.4,\n",
    "    )\n",
    "    .addStyle(\n",
    "        page={\n",
    "            \"title\": \"Degree Weighted Sample\",\n",
    "            \"favicon\": FAVICON_URL,\n",
    "        },\n",
    "        logo=LOGO,\n",
    "    )\n",
    "    .settings(\n",
    "        url_params=GRAPHISTRY_PARAMS,\n",
    "        height=800,\n",
    "    )\n",
    ")\n",
    "g.plot(G_pagerank_gt_zero)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7bcdfc63-2b48-4fe1-8092-c2472064926a",
   "metadata": {},
   "source": [
    "<center>\n",
    "<img src=\"images/Graphistry_Pagerank_Sample.png\" />\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2d1a13ff-d826-4492-ba46-4a8eff826b95",
   "metadata": {},
   "source": [
    "### More Sampling Below\n",
    "\n",
    "We aren't done yet, further down we use the PyPi module `littleballoffur` to try different sampling algorithms!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d213a1c5-742c-4dd3-ba31-8c71580fbabf",
   "metadata": {
    "tags": []
   },
   "source": [
    "# IMPORTANT: Select Which Sample to Use\n",
    "\n",
    "Set the `G` variable to whichever sample you would like to use below. You can comment these lines out to run the metrics on the entire graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "30eabfe1-1b84-44d5-a1e0-d5814c34b502",
   "metadata": {},
   "outputs": [],
   "source": [
    "# To preserve the original graph if we assign a sample to G\n",
    "G_orig = G.copy()\n",
    "\n",
    "# If things are slow in the following sections, run this line\n",
    "# G = G_pagerank_gt_zero.copy()\n",
    "# G = G_degree_gt_zero.copy()\n",
    "\n",
    "# Back to the original\n",
    "# G = G_orig"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0fe687cd-2b2b-4554-af67-d844c023f359",
   "metadata": {},
   "source": [
    "# Describing our Citation Network `nx.DiGraph`\n",
    "\n",
    "Now we can check a few theoretical properties of our DiGraph. I'll frame it in terms of questions and metrics.\n",
    "\n",
    "* Domain question: How many citations does each paper have across the entire network?\n",
    "* Metric 1: What is the average degree, in-degree and out-degree of the network?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f7a76395-2689-4c56-b821-add6de854184",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Extract degree, in-degree, and out-degree for each node\n",
    "# +1 is to avoid problems with log-scale display\n",
    "degree_sequence = [d + 1 for n, d in G.degree()]\n",
    "in_degree_sequence = [d + 1 for n, d in G.in_degree()]\n",
    "out_degree_sequence = [d + 1 for n, d in G.out_degree()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "43fd7308-16d6-469f-a296-7872845e8353",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "import seaborn as sns\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "# Increase figure size\n",
    "plt.figure(figsize=(10,6))\n",
    "\n",
    "# Create histogram of degree\n",
    "ax = sns.histplot(degree_sequence, bins=20, kde=True, log_scale=True)\n",
    "ax.set(xlabel='Degree')\n",
    "plt.title('Degree Histogram')\n",
    "plt.show()\n",
    "\n",
    "# Increase figure size\n",
    "plt.figure(figsize=(10,6))\n",
    "\n",
    "# Create histogram of in-degree\n",
    "ax = sns.histplot(in_degree_sequence, bins=20, kde=True, log_scale=True)\n",
    "ax.set(xlabel='In-Degree')\n",
    "plt.title('In-Degree Histogram')\n",
    "plt.show()\n",
    "\n",
    "# Increase figure size\n",
    "plt.figure(figsize=(10,6))\n",
    "\n",
    "# Create histogram of out-degree\n",
    "ax = sns.histplot(out_degree_sequence, bins=20, kde=True, log_scale=True)\n",
    "ax.set(xlabel='Out-Degree')\n",
    "plt.title('Out-Degree Histogram')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "12408801-a70c-4fc0-aa03-9e4f16998d72",
   "metadata": {},
   "source": [
    "## Tactical Decision: Removing Uncited Papers\n",
    "\n",
    "Uncited papers aren't very interesting - they have degree of zero - so aren't part of any connected component of a network. Let's filter them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f80321d8-337f-475d-9a95-225d8902cdd5",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "print(f\"Nodes before removal: {G.number_of_nodes():,}\")\n",
    "\n",
    "# Remove the isolated nodes\n",
    "G.remove_nodes_from(list(nx.isolates(G)))\n",
    "\n",
    "print(f\"Nodes after removal: {G.number_of_nodes():,}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "28c6b8dc-b90b-4605-ac23-05e9795733a5",
   "metadata": {},
   "source": [
    "# Bridges\n",
    "\n",
    "If removing an edge between two nodes breaks a single component into multiple components, that edge was a bridge. Let's check if our network has any bridges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5d26c570-051a-4504-aa9d-9766ebfe6772",
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.has_bridges(G.to_undirected())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c7115960-05bd-4570-85cd-7e6c7cf26e61",
   "metadata": {},
   "source": [
    "## Examining Bridges in Graphistry\n",
    "\n",
    "Let's examine bridges and local bridges in Graphistry by adding them as node properties to our network."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bff972d6-3695-41dc-aa19-2029638e77f7",
   "metadata": {},
   "outputs": [],
   "source": [
    "bridge_edges = nx.bridges(G.to_undirected())\n",
    "# nx.set_edge_attributes(G, bridge_edges, \"bridge\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1d2ef524-8d5d-4ef3-81e4-537b56e6cd6f",
   "metadata": {},
   "outputs": [],
   "source": [
    "list(G.edges(data=True))[:10]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "756a968c-1bfd-4026-b86f-48dac96cfea1",
   "metadata": {},
   "source": [
    "## Assortativity\n",
    "\n",
    "[Assortativity](https://en.wikipedia.org/wiki/Assortativity) in networks refers to a correlation pattern observed in real-world networks where nodes are preferentially connected to other nodes that are like (or unlike) them in some way. This is essentially a bias in connection preference.\n",
    "\n",
    "A related term is _assortative mixing_:\n",
    "\n",
    "> In the study of complex networks, assortative mixing, or assortativity, is a bias in favor of connections between network nodes with similar characteristics. In the specific case of social networks, assortative mixing is also known as homophily. The rarer disassortative mixing is a bias in favor of connections between dissimilar nodes.\n",
    "\n",
    "--Wikipedia, [Assortative Mixing](https://en.wikipedia.org/wiki/Assortative_mixing)\n",
    "\n",
    "This can be summarized via the assortativity coefficient.\n",
    "\n",
    "> The assortativity coefficient is the Pearson correlation coefficient of degree between pairs of linked nodes.\n",
    "\n",
    "--Wikipedia, [Assortativity](https://en.wikipedia.org/wiki/Assortativity)\n",
    "\n",
    "Pearson's is the covariance of two distributions divided by the product of their standard deviations. Assortativity adapts it for pairs of nodes while accounting for the degree of each node.\n",
    "\n",
    "<center><img src=\"images/pearsons_equation_no_cov.png\" width=\"500px\" alt=\"Equation for Pearson's Correlation Coefficient\" /></center>\n",
    "\n",
    "### Computing Degree Assortativity\n",
    "\n",
    "One type of assortativity is _degree assortativity_, which measures to what extent nodes connect to other nodes with similar degrees.\n",
    "\n",
    "It ranges from -1 to 1. We will use the NetworkX API [nx.algorithms.assortativity.degree_assortativity_coefficient](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.assortativity.degree_assortativity_coefficient.html#networkx.algorithms.assortativity.degree_assortativity_coefficient) to compute it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4be842af-e4a5-4f13-ad68-9c2f45c5334e",
   "metadata": {},
   "outputs": [],
   "source": [
    "degree_assort = nx.degree_assortativity_coefficient(G)\n",
    "degree_assort"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2c31f4ec-b718-40fb-95de-776a9dad3f11",
   "metadata": {},
   "source": [
    "The value for degree assortativity we computed above of 0.00172 indicates that overall nodes often associate with similar or dissimilar nodes by degree in roughly equal proportions. There is no correlation between the degree of nodes and their tendency to connect.\n",
    "\n",
    "In a citation network, a higher assortativity can mean that papers with many citations (high degree nodes) tend to cite other papers with many citations. This could reflect a phenomenon where \"popular\" or foundational papers are often cited together. A lower assortativity might suggest that highly-cited papers are citing less-cited papers, indicating a wider __dispersion__ of references and potentially more novel research that builds on less well-known work."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "26633034-e588-4d92-bf2c-9cbcf6f2eb31",
   "metadata": {},
   "source": [
    "### In-Degree Assortativity\n",
    "\n",
    "Let's check how often papers connect to similar papers according to how many in-bound citations they have."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a25511f7-f44f-4b57-ac81-980db37397e8",
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.degree_assortativity_coefficient(G, x=\"in\", y=\"in\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8333e4f7-f2dc-4f23-835d-cb8fda369153",
   "metadata": {},
   "source": [
    "You can see there is a higher positive correlation, but only around 0.1, indicating papers display a small amount assortative mixing with respect to the number of citations they receive."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "56917d7a-d17c-4041-8542-ce6f101158ec",
   "metadata": {},
   "source": [
    "### Out-Degree Assortativity\n",
    "\n",
    "And... how often do papers that cite many papers cite papers that themselves cite many papers? Conversely, how often do papers that cite only a few papers cite other papers that cite only a few papers? If out-degree assortativity is high, it might be interesting to incorporate this last question into a connected components analysis, since there might be interesting components of low citation papers all on their own, encoding their own areas of science :)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "82f95238-e8bc-4151-9d12-a8bb550c1a93",
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.degree_assortativity_coefficient(G, x=\"out\", y=\"out\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ac80b46f-1f06-4151-9d08-40eadf9fe42b",
   "metadata": {},
   "source": [
    "More of the same. Let's try answering the following questions:\n",
    "\n",
    "1) Is there assortative mixing between papers that are often cited and papers that themselves cite many papers?\n",
    "2) Is there assortative mixing between papers that cite many papers and papers that are often cited?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cd49da65-4e27-4e7a-85cb-fcab03f807a3",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 1) x=\"in\" [cited a lot], x=\"out\" [cite a lot]\n",
    "print(f'In / Out Degree Assortativity Coefficient: {nx.degree_assortativity_coefficient(G, x=\"in\", y=\"out\"):,.3f}')\n",
    "\n",
    "# 2) x=\"out\" [cite a lot], x=\"in\" [cited a lot]\n",
    "print(f'Out / In Degree Assortativity Coefficient: {nx.degree_assortativity_coefficient(G, x=\"out\", y=\"in\"):,.3f}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bee0e94a-0490-41a2-9795-e35d1cd69c30",
   "metadata": {},
   "source": [
    "Ok, we give up! While I hope you understand this tool, it isn't very illuminating here :)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f4451e20-5e22-454b-96a5-4b25f49463bf",
   "metadata": {},
   "source": [
    "## Dispersion\n",
    "\n",
    "In interpreting our degree assortativity, we mentioned _dispersion_, another network metric that indicates how well the neighbors of two nodes are connected to one another. Recall that _clustering coefficient_ indicates how well the neighbors of two nodes are _directly connected_. Dispersion is a similar measure that includes paths with lengths longer than 1.\n",
    "\n",
    "Let's consider a simple example with nodes A and B. Suppose A and B have a set of mutual contacts or neighbors. If these mutual contacts are also connected to each other, forming a tightly-knit community, the dispersion is low. However, if these mutual contacts aren't connected to each other, the dispersion is high.\n",
    "\n",
    "In a social network setting, a high dispersion between two individuals might mean that they connect different parts of a network, which can be an indication of a close or important relationship. For example, in a group of friends, a romantic couple might have a high dispersion because each person connects the other to a different social group, and their mutual friends don't necessarily know each other.\n",
    "\n",
    "Below we use the [nx.algorithms.centrality.dispersion](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.centrality.dispersion.html) to compute the mean dispersion between the paper [M Theory As A Matrix Model: A Conjecture, Banks et al, 1997](https://arxiv.org/abs/hep-th/9610043) and its 1,219 citation edges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8891c117-c2cb-4eea-8e1c-c6fd070f6ebe",
   "metadata": {},
   "outputs": [],
   "source": [
    "mean_dispersion = np.mean(list(nx.dispersion(G, file_to_net[9610043]).values()))\n",
    "print(f\"Mean Dispersion: {mean_dispersion:,.3f}\")\n",
    "\n",
    "median_dispersion = np.median(list(nx.dispersion(G, file_to_net[9610043]).values()))\n",
    "print(f\"Median Dispersion: {median_dispersion:,.3f}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1cccedab-6307-4a4e-8088-79e5f80d9d39",
   "metadata": {},
   "outputs": [],
   "source": [
    "# I crash notebook\n",
    "# shortest_path_lengths = list(nx.shortest_path_length(G))\n",
    "# shortest_path_lengths"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "67e2d67e-42ed-42ec-8483-47c482f72134",
   "metadata": {},
   "source": [
    "### Interpreting Dispersion = Hard\n",
    "\n",
    "Dispersion scores are relative to an individual network's context. We can't interpret the mean and median dispersion scores without putting them into the contxt of the other nodes' dispersions. Let's get the maximium dispersion and plot a histogram of mean dispersions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "19be7ef1-7576-4dd4-ab26-438fff0bc117",
   "metadata": {},
   "outputs": [],
   "source": [
    "dispersions = nx.dispersion(G)\n",
    "# dispersions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a7cc2466-4fd0-4de8-acef-505150aa4dce",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Process the outer dict for each node and its inner dict for all other nodes\n",
    "long_list_of_dispersions = np.concatenate([\n",
    "    list(inner_dict.values()) for inner_dict in dispersions.values()\n",
    "])\n",
    "long_list_of_dispersions, long_list_of_dispersions.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7df7b4d3-346e-4584-b6b9-48e4fa5d22f2",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Get the maximum dispersion using a nested list comprehension\n",
    "max_dispersion = np.max(\n",
    "    long_list_of_dispersions\n",
    ")\n",
    "\n",
    "print(f\"Maximum Dispersion: {max_dispersion:,.3f}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "40a29c24-11f5-4d1d-8068-22c4b4d16b39",
   "metadata": {},
   "outputs": [],
   "source": [
    "mean_dispersions_per_node = np.array([np.mean(list(dispersion_dict.values())) for dispersion_dict in dispersions.values()])\n",
    "mean_dispersions_per_node, mean_dispersions_per_node.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b4690b98-e6b7-4b18-9b9d-ad8a44a01c9b",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Increase figure size\n",
    "plt.figure(figsize=(10,6))\n",
    "\n",
    "# Use seaborn to create the histogram\n",
    "sns.histplot(mean_dispersions_per_node, kde=True, bins=30, log_scale=False)\n",
    "plt.title('Histogram of Node Mean Dispersions')\n",
    "plt.xlabel('Node Mean Dispersion Score')\n",
    "plt.ylabel('Count')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1b7e3ff5-d4d4-4514-8bf0-75430ff8c953",
   "metadata": {},
   "source": [
    "### Let's try that in log scale..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fb5dceaf-9ee0-4093-abbb-8fb1965b91bf",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Filter out dispersion scores of 0\n",
    "logable_mean_dispersions = [x + 0.01 for x in mean_dispersions_per_node if x > 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "416d9e25-58d3-490b-b236-8c215fa25d00",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Increase figure size\n",
    "plt.figure(figsize=(10,6))\n",
    "\n",
    "# Use seaborn to create the histogram\n",
    "sns.histplot(logable_mean_dispersions, kde=True, bins=30, log_scale=True)\n",
    "plt.title('Histogram of Node Mean Dispersions')\n",
    "plt.xlabel('Node Mean Dispersion Score')\n",
    "plt.ylabel('Count')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9ca8295c-ca78-4913-b190-857bbe2fbbb2",
   "metadata": {},
   "source": [
    "### Interpreting Node Mean Dispersions\n",
    "\n",
    "Nodes and their connections have a [log-normal distribution](https://en.wikipedia.org/wiki/Log-normal_distribution) of dispersion scores. For nodes that are connected, most dispersion scores range from 0.1 to 1.\n",
    "\n",
    "While this provides some additional detail, it isn't that enlightening in this case. We could drill-down to papers with a very high dispersion score to find network bridges, but this is left as an exercise to the student. In a citation graph a network bridge might link on area of science to another, something that few other papers manage."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b67e2e10-83e6-44c9-8a70-9baa2aa93b06",
   "metadata": {},
   "source": [
    "# Fitting a Random Graph Model to our Network\n",
    "\n",
    "These degree histograms don't exist in a vacuum. They can be compared to theoretical models of networks to help interpret them. We mean to learn about our network, not simply compute metrics.\n",
    "\n",
    "NetworkX has many random graph models in the form of [Graph Generators](https://networkx.org/documentation/stable/reference/generators.html) that can generate instances of a random graph. For small graphs, it is neccessary to iteratively generate and measure multiple instances of random graphs. For larger graphs a single instance can work. This is due to the \n",
    "\n",
    "## Erdös Reyni Graphs\n",
    "\n",
    "We begin with a random graph model often used as a baseline, not because it fits real-world networks.\n",
    "\n",
    "An Erdős–Rényi (ER) graph is a simple model of a random graph. This model is named after Paul Erdős and Alfréd Rényi, who first introduced one version of it.\n",
    "\n",
    "In the ER model, a graph is constructed by connecting nodes randomly. Each edge is included in the graph with probability p, independent of the other edges. Thus, the model has two parameters: the number of nodes n, and the edge probability p.\n",
    "\n",
    "The ER model can be used to generate either a G(n, M) graph or a G(n, p) graph.\n",
    "\n",
    "In the G(n, M) model, a graph is chosen uniformly at random from the collection of all graphs with n nodes and M edges.\n",
    "In the G(n, p) model, a graph is constructed by connecting nodes randomly where each possible edge occurs independently with probability p.\n",
    "The ER model is a simple model that does not capture many of the properties of real-world networks, such as their community structure and degree distribution.\n",
    "\n",
    "However, it is useful in network theory because of its analytical tractability and because it serves as a null model against which the properties of real-world networks can be compared."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "30cfb609-c7be-4bea-9974-fe49d4e694cc",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Calculate the edge probability parameter for the Erdos-Renyi model\n",
    "p = nx.density(G)\n",
    "print(f\"Citation network density: {p:.5f}\")\n",
    "\n",
    "# Create an Erdos-Renyi graph with the same number of nodes and the calculated edge probability\n",
    "G_er = nx.erdos_renyi_graph(G.number_of_nodes(), p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4dd968ef-7934-4cd9-9c2e-5619910a8599",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def plot_degrees(G, G_compare=None, compare_label=None):\n",
    "    \"\"\"Compute the degrees of a graph and compare them to a random graph model.\"\"\"\n",
    "\n",
    "    # Increase figure size\n",
    "    plt.figure(figsize=(10,6))\n",
    "    \n",
    "    # Create histogram of degrees in real citation graph\n",
    "    degree_sequence = [d + .01 for n, d in G.degree()]\n",
    "    ax = sns.histplot(degree_sequence, bins=20, kde=True, log_scale=True, label=\"Citation Graph\")\n",
    "    ax.set(xlabel='Degree')\n",
    "\n",
    "    # Increase figure size\n",
    "    plt.figure(figsize=(10,6))\n",
    "\n",
    "    if G_compare:\n",
    "        # Create histogram of degree and plot alongside\n",
    "        compare_degree_sequence = [d + 1 for n, d in G_compare.degree()]\n",
    "        ax = sns.histplot(compare_degree_sequence, bins=20, kde=True, log_scale=True, label=compare_label if compare_label else \"Random Graph Model\")\n",
    "        ax.set(xlabel='Degree')\n",
    "    \n",
    "        plt.title(f\"Degree Histogram Comparison\")\n",
    "    else:\n",
    "        plt.title(\"Degree Histogram\")\n",
    "\n",
    "    plt.legend()\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "57637f48-1b22-427f-8872-bd4a881b8da6",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Compare our graph with a random graph model\n",
    "plot_degrees(G, G_er, compare_label=\"Erdos Reyni\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d2a95e8f-281c-4fb5-914d-d99b9d0345d1",
   "metadata": {},
   "source": [
    "While narrower, this isn't completely dissimilar... and yet citation graphs are not known to look like random graph models. Let's check another. The [networkX Graph Generators documentation](https://networkx.org/documentation/stable/reference/generators.html) has a long list.\n",
    "\n",
    "### Barabasi-Albert Model\n",
    "\n",
    "Barabási-Albert Model (Preferential Attachment Model, Scale Free Network): This model generates a random graph where nodes are added to the network one at a time, and each new node attaches to existing nodes with a probability proportional to their degree.\n",
    "\n",
    "A scale free network is one where its degree distribution fits a power law. In log scale, they proceed from top-left to bottom-right. Barabasi-Albert networks model step-wise growth of networks where edges are added in a way that prefers nodes with a higher degree.\n",
    "\n",
    "<center><img alt=\"Random network vs a Scale Free network\" src=\"images/random-vs-scale-free-network.jpg\" /></center>\n",
    "\n",
    "--Network-based approaches for anticancer therapy (Review), Seo et al, 2013."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2a542baf-97c5-4a74-8eaf-b20ae98a71e6",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Number of iterations required (This should be smaller than the total number of nodes)\n",
    "n = G.number_of_nodes()\n",
    "\n",
    "# Number of edges to attach from a new node to existing nodes\n",
    "m = G.number_of_edges() // n\n",
    "\n",
    "print(f\"n: {n:,} m: {m:,}\")\n",
    "\n",
    "# Create a Barabasi-Albert graph with the same number of nodes and edges as the real graph\n",
    "G_ba = nx.barabasi_albert_graph(n, m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cfcba7ff-0446-47c0-ae55-e9ae153df9a8",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "print(f\"Total nodes: {G_ba.number_of_nodes():,}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0531abfe-0364-487e-bd5f-b3d9b9c9d285",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "plot_degrees(G, G_ba, compare_label=\"Barabasi-Albert\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "19adacbf-93d7-49fd-9daa-20b17e447040",
   "metadata": {},
   "source": [
    "### Price's Citation Graph Random Model\n",
    "\n",
    "Neither one of these fits the citation network very well. Some searching in the network science literature brings up this: Citation Graph Model. Wikipedia describes the first such model, Price's model as:\n",
    "\n",
    "Price's model (named after the physicist Derek J. de Solla Price) is a mathematical model for the growth of citation networks.[1][2] It was the first model which generalized the Simon model[3] to be used for networks, especially for growing networks. Price's model belongs to the broader class of network growing models (together with the Barabási–Albert model) whose primary target is to explain the origination of networks with strongly skewed degree distributions. The model picked up the ideas of the Simon model reflecting the concept of rich get richer, also known as the Matthew effect. Price took the example of a network of citations between scientific papers and expressed its properties. His idea was that the way an old vertex (existing paper) gets new edges (new citations) should be proportional to the number of existing edges (existing citations) the vertex already has. This was referred to as cumulative advantage, now also known as preferential attachment. Price's work is also significant in providing the first known example of a scale-free network (although this term was introduced later). His ideas were used to describe many real-world networks such as the Web."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bc2692c8-3d9a-43d3-951c-e19ac910f337",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def citation_graph(n, m):\n",
    "    \"\"\"\n",
    "    Create a citation graph with n nodes. Each new node attaches to m existing nodes.\n",
    "    \"\"\"\n",
    "    G = nx.DiGraph()\n",
    "    G.add_nodes_from(range(2 * m))  # Start with 2m nodes\n",
    "    G.add_edges_from((i, 2 * m) for i in range(2 * m))  # Each of the first 2m nodes links to the node 2m\n",
    "\n",
    "    for i in range(2 * m + 1, n):\n",
    "        # A new paper cites m existing papers. The probability of citing an existing paper is proportional to its in-degree.\n",
    "        nodes = list(G.nodes())\n",
    "        probabilities = [G.in_degree(n) for n in nodes]\n",
    "        cited_nodes = random.choices(nodes, probabilities, k=m)\n",
    "        for node in cited_nodes:\n",
    "            G.add_edge(node, i)\n",
    "\n",
    "    return G"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bbdb2ba0-13a8-4f4d-8e9d-9287546ee48a",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# # Must run on sample... slow\n",
    "# n = G.number_of_nodes()\n",
    "# m = (G.number_of_edges() // n)  # integer division\n",
    "\n",
    "# # Note: this can take a while\n",
    "# G_cite = citation_graph(n, m)\n",
    "\n",
    "# plot_degrees(G, G_cite, \"Price's Model\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a5b044e-33dc-4237-a5ff-cec4261b0885",
   "metadata": {},
   "source": [
    "### Random Graph Model Lessons\n",
    "\n",
    "We didn't fine the perfect random graph model using random graphs, but I hope these help you understand how to research what models might characterize your graph and what that means about it. As a data scientist, this is a valuable tool as it gives you the context you neex to make inferences about patterns in the network that can result in insight and clues for effective automation via machine learning. We could take this further and tune the parameters in Price's model or look for more citation network models that might fit better."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1ddfb1fa-aba4-4b0e-9e53-83514acdb8c1",
   "metadata": {},
   "source": [
    "## Configuration Models\n",
    "\n",
    "We've tried generating random graph models - even those with fitted parameters - to our network. None of them fit. We can make one that definitely will fit the degree distribution because that is how it is generated - the [Configuration Model](https://en.wikipedia.org/wiki/Configuration_model#:~:text=In%20network%20science%2C%20the%20configuration,to%20incorporate%20arbitrary%20degree%20distributions.).\n",
    "\n",
    "<center><img src=\"images/degree_sequence_and_different_realizations_in_the_configuration_model.jpg\" width=\"600px\" /></center>\n",
    "<p>Figure 1. Degree sequence and different network realizations in the configuration model[1], Wikipedia, <a href=\"https://en.wikipedia.org/wiki/Configuration_model#:~:text=In%20network%20science%2C%20the%20configuration,to%20incorporate%20arbitrary%20degree%20distributions.\">Configuration Model</a></p>\n",
    "\n",
    "We can use a configuration model or one of its more powerful extensions to generate random graphs that match the degree sequence - the degree histogram - of our network. This is a powerful technique as these networks can serve as a [random graph null model](https://en.wikipedia.org/wiki/Null_model)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aabd0e14-f572-4981-969f-1912c79cf7bd",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "# Assuming that G is your existing graph\n",
    "G_rand = nx.erdos_renyi_graph(30, 0.2)\n",
    "\n",
    "# Get the degree sequence of G\n",
    "degree_sequence = [d for n, d in G_rand.degree()]\n",
    "\n",
    "# Generate and draw 3 random graphs with the same degree sequence\n",
    "for i in range(3):\n",
    "    # Create a random graph from the degree sequence\n",
    "    H = nx.configuration_model(degree_sequence)\n",
    "\n",
    "    # In case of self-loops or parallel edges, \n",
    "    # we might want to create a simple graph with no self-loops or parallel edges.\n",
    "    H = nx.Graph(H)\n",
    "    H.remove_edges_from(nx.selfloop_edges(H))\n",
    "    \n",
    "    print(f\"Random Graph {i}\\n\")\n",
    "    describe_graph(H)\n",
    "    print()\n",
    "    \n",
    "    plt.figure()\n",
    "    nx.draw(H, with_labels=True)\n",
    "    plt.title(f'Random Graph {i+1}')\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6d40f009-dcab-46c9-978b-2d3ff5068148",
   "metadata": {},
   "source": [
    "### Fitting Configuration Models to our Network\n",
    "\n",
    "Let's try a variety of configuration models of different types and see how their properties compare to our citation network."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d415dd86-2c49-4f0d-a702-0b8f8e954d9e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# H = nx.Graph(nx.configuration_model([d for n, d in G.degree()]))\n",
    "# H = nx.watts_strogatz_graph(G.number_of_nodes(), 14, 0.40)\n",
    "\n",
    "print(\"Original graph G:\")\n",
    "describe_graph(G)\n",
    "\n",
    "print(\"\\nWatts Strogatz model H:\")\n",
    "# print(\"\\nConfiguration model H:\")\n",
    "describe_graph(H)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d4cb082c-ebd6-4e6d-a183-dfe14bdc48fc",
   "metadata": {},
   "outputs": [],
   "source": [
    "g = (\n",
    "    graphistry.bind(\n",
    "        source=\"src\",\n",
    "        destination=\"dst\",\n",
    "        node=\"nodeid\",\n",
    "    )\n",
    "    .scene_settings(\n",
    "        edge_opacity=0.4,\n",
    "        point_size=0.1,\n",
    "    )\n",
    "    .addStyle(\n",
    "        page={\n",
    "            \"title\": \"Watts Strogatz Network\",\n",
    "            \"favicon\": FAVICON_URL\n",
    "        },\n",
    "        logo=LOGO,\n",
    "    )\n",
    "    .settings(\n",
    "        url_params=GRAPHISTRY_PARAMS,\n",
    "        height=800,\n",
    "    )\n",
    ")\n",
    "g.plot(H)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d7f09e07-65a5-420b-b3fc-48327c372d59",
   "metadata": {},
   "source": [
    "<center><img src=\"images/Graphistry_Figure_3.png\" /></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "335c443b-4743-4751-8598-1520ed471ebf",
   "metadata": {},
   "source": [
    "### Moving On...\n",
    "\n",
    "You can see this still doesn't quite fit our model. We're going to examine a few of these networks using Grapistry to see how they differ."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3c54a308-7259-4ee3-8d4d-bd0a2bf86a78",
   "metadata": {},
   "source": [
    "## Centrality Metrics\n",
    "\n",
    "Question: What are the most important papers in the field of physics during this period, from 1992 to 2003?\n",
    "Metrics: Network centralities - metrics designed to determine the prominence of a node in its local neighborhood or the whole network.\n",
    "\n",
    "You can find a number of centrality metrics under the [documentation for centrality](https://networkx.org/documentation/stable/reference/algorithms/centrality.html) in networkx.\n",
    "\n",
    "We are going to compute several centralities and add them to our `networkx.DiGraph` as properties. Then we can visualize them to understand what they mean.\n",
    "\n",
    "### Local Centralities\n",
    "\n",
    "- Degree Centrality: the number of connections a node has. Variants: in-degree centrality and out-degree centrality, which count the number of in-bound and out-bound connections."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4996f743-f267-4b7c-89cc-3648075dd314",
   "metadata": {},
   "outputs": [],
   "source": [
    "relative_degrees = nx.degree_centrality(G)\n",
    "\n",
    "for node, relative_degree in relative_degrees.items():\n",
    "    G.nodes[node][\"relative_degree\"] = relative_degree\n",
    "    G.nodes[node][\"relative_degree_log10\"] = np.log10(relative_degree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "49d5e46f-9ba3-4258-8f83-6cbe9bbb3846",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "G.nodes[3]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4ff32a2a-7c8f-4b71-8ba7-1766c7138396",
   "metadata": {},
   "source": [
    "### Global Centralities\n",
    "\n",
    "- Eigenvector Centrality\n",
    "- Closeness Centrality\n",
    "- Betweenness Centrality\n",
    "\n",
    "#### So Many Centralities\n",
    "\n",
    "Check out the networkx [Centrality Algorithms documentation](https://networkx.org/documentation/stable/reference/algorithms/centrality.html) for a long list of other centralities. For a (not comprehnsive review) check out [Centrality Measures in Complex Networks: A Survey](https://arxiv.org/abs/2011.07190). I used to collect centrality algorithms, and had close to fifty in my list (sorry, now lost).\n",
    "\n",
    "#### Eigenvector Centrality\n",
    "\n",
    "This is a measure of the influence of a node in a network. It assigns relative scores to all nodes in the network based on the concept that connections to high-scoring nodes contribute more to the score of the node in question than equal connections to low-scoring nodes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3b2daf0f-dd0c-4650-be8c-946817502545",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Eigenvector centrality is problematic in disconnected graphs, so take the largest component...\n",
    "components = nx.connected_components(G.to_undirected())\n",
    "largest_component = max(components, key=len)\n",
    "G_big_component = G.subgraph(largest_component).copy()\n",
    "\n",
    "print(f\"Largest comonent size: {len(G_big_component):,}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2b7ba75d-b901-4420-bee0-2ba44c2b0b4d",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# ... and make it undirected, to ensure it is connected\n",
    "eigenvectors = nx.eigenvector_centrality_numpy(\n",
    "    G_big_component.to_undirected()\n",
    ")\n",
    "\n",
    "for node, score in eigenvectors.items():\n",
    "    G_big_component.nodes[node][\"eigenvector\"] = score\n",
    "    G_big_component.nodes[node][\"eigenvector_log10\"] = np.log10(score + 0.000001)  # can't be zero for log"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3bc41c65-f9f5-4170-a089-149c153eef25",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Initialize eigenvector_centrality property as 0 for all nodes\n",
    "nx.set_node_attributes(G, 0.0, \"eigenvector\")\n",
    "nx.set_node_attributes(G, 0.0, \"eigenvector_log10\")\n",
    "\n",
    "# Assign the eigenvector centrality values from subgraph to original graph\n",
    "nx.set_node_attributes(G, {node: eigenvectors[node] for node in G_big_component}, \"eigenvector\")\n",
    "nx.set_node_attributes(G, {node: np.log10(G.nodes[node]['eigenvector'] + 1e-10) for node in G.nodes()}, \"eigenvector_log10\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e8d273cc-db36-410a-b2fb-ef56e6c2c24a",
   "metadata": {},
   "outputs": [],
   "source": [
    "G.nodes[3]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a60c9c36-623b-41ef-86cc-491aecb9be9e",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### Closeness Centrality\n",
    "\n",
    "This measure calculates the average length of the shortest paths from a node to all other nodes in the network. Nodes with lower average shortest path lengths have higher closeness centrality and are often considered as being more central. A common interpretation of closeness centrality is that nodes with a high score are more likely to recieve information from other sources in the network than nodes with a low score.\n",
    "\n",
    "Be aware that closeness and betweenness centrality are expensive to compute. They may not be available on large networks, or very densely connected networks. You can use NVIDIA RAPIDS [cuGraph centrality methods] if you have an NVIDIA GPU. Most data science work on GPUs is done on NVIDIA compatible GPUs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4973663a-d4d6-402b-ba04-f91bf198c8dd",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# If this takes too long, be sure and run the above cell that substitutes G for G_\n",
    "closeness = nx.closeness_centrality(G)\n",
    "\n",
    "for node, score in closeness.items():\n",
    "    G.nodes[node][\"closeness\"] = score\n",
    "    G.nodes[node][\"closeness_log10\"] = np.log10(score + 1e-10)  # Add small epsilon to all values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "68ecf841-d408-496d-9372-d8da2e88c4cb",
   "metadata": {},
   "outputs": [],
   "source": [
    "G.nodes[3]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4b754a4f-b291-4579-87bb-d89279d9291d",
   "metadata": {},
   "source": [
    "#### Betweenness Centrality\n",
    "\n",
    "This measure considers a node's position within the network in terms of the paths between other nodes. Nodes that frequently lie on the shortest paths between other nodes in the network have a high betweenness centrality. These nodes serve as important points of control and coordination within the network.\n",
    "\n",
    "Betweenness centrality is so expensive it quickly becomes infeasible on large networks. GPUs can extend this capability in libraries like [NVIDIA RAPIDS cuGraph's](https://github.com/rapidsai/cugraph) [cugraph.betweenness_centrality](https://docs.rapids.ai/api/cugraph/legacy/api_docs/api/cugraph.betweenness_centrality.html) feature.\n",
    "\n",
    "A course with NVIDIA support and cuGraph is available. Please <a href=\"mailo:rjurney@graphlet.ai\" style=\"color: blue\">contact me at rjurney@graphlet.ai</a> if you'd like a private class covering cuGraph or other, related topics we don't explore."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8e2cfaae-a6f9-49d6-a6a8-9512850171e6",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# # Note: this is too slow to actually run on CPU! We need to use cuGraph on a GPU.\n",
    "# between = nx.betweenness_centrality(G)\n",
    "# # nx.set_node_attribute(G, between)\n",
    "\n",
    "# for node, score in between.items():\n",
    "#     G.nodes[node][\"betweenness\"] = score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2b4a6cef-95d4-4df4-8c28-db4b9e4371cc",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "G.nodes[3]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "428a73ce-8622-4d4e-97fb-0089e88682af",
   "metadata": {},
   "source": [
    "#### Betweenness Centrality in `networkit`\n",
    "\n",
    "While we can't use a GPU in this course with [`cugraph.centrality.betweenness_centrality`](https://docs.rapids.ai/api/cugraph/stable/api_docs/api/cugraph/cugraph.centrality.betweenness_centrality/) for technical reasons (you may not have an NVIDIA GPU), we can use [NetworKit](https://networkit.github.io/) to take advantage of multiple processor cores.\n",
    "\n",
    "NetworKit uses multiple CPU cores, check out 15 of them on my new Maxbook Pro :)\n",
    "\n",
    "<center><img src=\"images/NetworKit Compute Top.png\" /></center>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "53285dd0-7d71-4399-aa49-80d624734d1d",
   "metadata": {},
   "outputs": [],
   "source": [
    "from networkit.centrality import ApproxBetweenness, Closeness\n",
    "from networkit.nxadapter import nx2nk\n",
    "\n",
    "\n",
    "btwn = ApproxBetweenness(nx2nk(G))\n",
    "btwn.run()\n",
    "btwn_scores = btwn.scores()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "92c77029-51fd-4f0d-ba9a-37cb0e3e5b1c",
   "metadata": {},
   "outputs": [],
   "source": [
    "closeness = Closeness(nx2nk(G), True, True)\n",
    "closeness.run()\n",
    "closeness_scores = closeness.scores()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "27f191e5-65c7-448c-9a03-399d7b5acc5c",
   "metadata": {},
   "source": [
    "### Visualizing Metrics in Graphistry\n",
    "\n",
    "Let's zoom in on one section of the network to make it manageable and then look at just those nodes. Nodes are sized by degree by default in Graphistry. Let's click on one of the largest nodes and perform a snowball sample two hops out."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "63211c59-6cca-4268-aa08-b52948c0b16c",
   "metadata": {},
   "outputs": [],
   "source": [
    "g = (\n",
    "    graphistry.bind(\n",
    "        source=\"src\",\n",
    "        destination=\"dst\",\n",
    "        node=\"nodeid\",\n",
    "        point_title=\"Title\",\n",
    "        point_label=\"Title\",\n",
    "    )\n",
    "    .scene_settings(\n",
    "        edge_opacity=0.4,\n",
    "    )\n",
    "    .addStyle(\n",
    "        page={\n",
    "            \"title\": \"Simple Plot\",\n",
    "            \"favicon\": FAVICON_URL\n",
    "        },\n",
    "        logo=LOGO\n",
    "    )\n",
    "    .settings(\n",
    "        url_params=GRAPHISTRY_PARAMS,\n",
    "        height=800\n",
    "    )\n",
    ")\n",
    "g.plot(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ea74ff71-8878-47f1-aef2-146f14597390",
   "metadata": {},
   "source": [
    "#### Closeness vs Betweenness\n",
    "\n",
    "<center><img src=\"images/Graphistry_Figure_4.png\" /></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8a7608b4-d3d0-49e3-892e-204f1d5ece5e",
   "metadata": {},
   "source": [
    "#### Degree vs Clustering Coefficient\n",
    "\n",
    "<center>\n",
    "    <img src=\"images/Graphistry_Comparison_Viz.png\" />\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ee12f563-048e-4c6e-a0c6-6203216da27b",
   "metadata": {},
   "source": [
    "### Try other Centralities\n",
    "\n",
    "Now try additional centrality pairs like degree vs PageRank to see how they look!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ac410bd3-1ca0-4401-beba-1cd24624e794",
   "metadata": {},
   "source": [
    "## More on Sampling Networks\n",
    "\n",
    "> Large-scale networks, seen in contexts like social media or bioinformatics, bring forth considerable computational challenges due to their size and complexity. Traditional algorithms and infrastructures often struggle to efficiently compute global network measures, visualize data, and manage inherent noise in these large datasets. Network sampling, which involves selecting a representative subset of the network, offers a way to alleviate these issues. It enables feasible computation and interpretation of network properties. However, creating effective sampling strategies is crucial to maintain the original network's key characteristics, ensuring accurate inferences about the larger system.\n",
    "\n",
    "There are three major types of sampling a network: random sampling, snowball sampling and random walk sampling.\n",
    "\n",
    "- Random sampling selects random nodes from the network and includes edges between those nodes that are in the sample. This makes sense when your graph fits a random graph model like Erdos Reyni.\n",
    "- Snowball sampling creates an \"ego network\" which is centered on a single node of particular interest. It is useful when you want to investigate a region of a network. An ego (a node) may be of particular interest in the context of its alters (its neighbors) or a cluster or region of the graph may require your attention. Snowball sampling can \"zoom in\" to assist with visualization, which we will use below.\n",
    "\n",
    "## Snowball Sampling\n",
    "\n",
    "> In the context of network science, a snowball sample is a method of data collection that uses a cascading or \"snowball\" effect to discover and analyze nodes in a network. It's often used when you don't have access to the entire network data, or when the network is too large to feasibly analyze in its entirety.\n",
    ">\n",
    "> The process begins with a small set of \"seed\" nodes in the network. You identify all nodes that these seed nodes are directly connected to (i.e., their neighbors), and add them to your sample. This is often referred to as one \"hop\" or \"wave\" out from the seed nodes.\n",
    ">\n",
    "> But the process doesn't stop there, much like a snowball rolling down a hill and growing in size, you continue the process for these newly added nodes, finding all of their connected nodes, or neighbors, and adding them to your sample. This is the second hop, and you can continue this for as many \"hops\" as you want, each time expanding the number of nodes in your sample.\n",
    ">\n",
    "> When we say \"1.5 hop\" in the context of a snowball sampling of a network, it typically means that we start from a certain node (or set of nodes), then we include all the direct neighbors of this node (that's the first \"hop\"), and then for the \"0.5\" hop, we also include nodes that are connected to the nodes in the first hop but not include their connections (i.e., not going another full hop further). The idea behind this is to gather a slightly wider view of the network around our starting point, but without expanding to the full 2-hop neighborhood, which could significantly increase the size of the sample.\n",
    "\n",
    "--I am *pretty sure* I wrote this, with ChatGPT, a year ago..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ed22838d-77be-4e7a-8f87-6f7c1f8753cd",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def snowball_sample(graph, start_nodes, hops: int):\n",
    "    \"\"\"\n",
    "    Perform an n-hop snowball sample on the given graph.\n",
    "    \n",
    "    :param graph: The NetworkX graph.\n",
    "    :param start_nodes: The nodes to start the snowball sampling from.\n",
    "    :param n: The number of hops. Connections within the nodes are automatically included.\n",
    "    :return: A subgraph of the given graph that is the result of the n-hop snowball sampling.\n",
    "    \"\"\"\n",
    "    # First add all start_nodes to the sample (0 hops)\n",
    "    sampled_graph = graph.subgraph(start_nodes).copy()\n",
    "\n",
    "    # Then add all their neighbors (1 hop)\n",
    "    for i in range(0, n):\n",
    "        for node in start_nodes:\n",
    "            sampled_graph.add_nodes_from(graph.neighbors(node))\n",
    "            sampled_graph.add_edges_from((node, neighbor) for neighbor in graph.neighbors(node))\n",
    "\n",
    "    # Finally, add edges between the neighbors (.5 hops, as in a 1.5 hop snowball sample)\n",
    "    # We iterate over all nodes in the sampled graph and, for each, add edges to its neighbors that are also in the sampled graph\n",
    "    for node in list(sampled_graph.nodes):\n",
    "        neighbors = set(graph.neighbors(node))\n",
    "        sampled_neighbors = neighbors.intersection(set(sampled_graph.nodes))\n",
    "        sampled_graph.add_edges_from((node, sampled_neighbor) for sampled_neighbor in sampled_neighbors)\n",
    "\n",
    "    return sampled_graph"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3f775309-f329-4f3f-a10c-cf49b87ed245",
   "metadata": {},
   "source": [
    "## Snowball Sampling an Influential Paper\n",
    "\n",
    "The 1997 paper [M Theory As A Matrix Model: A Conjecture, Banks et al, 1997](https://arxiv.org/abs/hep-th/9610043) has a degree of 1,219. It is a highly influential paper and has now received 2,710. Let's start with it and do a snowball sample."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6b0bc483-a8a2-4394-a96b-17301352515d",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "G_orig.nodes[file_to_net[9610043]], file_to_net[9610043]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d7f3ee18-340e-4187-99cc-c2a2589b9d92",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Run a snowball sample in the largest component so we get a good sample\n",
    "components = [c for c in nx.weakly_connected_components(G)]\n",
    "component_index_sizes = [(i, len(c)) for i, c in enumerate(components)]\n",
    "biggest_component_index, max_size = max(component_index_sizes, key=lambda x: x[1])\n",
    "biggest_component_index, max_size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9edea84f-3401-47cb-b1a8-5d365e0a505e",
   "metadata": {},
   "outputs": [],
   "source": [
    "big_component_nodes = components[biggest_component_index]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3b894078-65e8-4643-9663-dd822b2df848",
   "metadata": {},
   "outputs": [],
   "source": [
    "G_big_component = G.subgraph(big_component_nodes)\n",
    "G_big_component.number_of_nodes(), G_big_component.number_of_edges()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "432aeb28-eda2-4627-91d4-735669259407",
   "metadata": {},
   "outputs": [],
   "source": [
    "# # Take a random snowball sample until we get one with a good amount of nodes, 100-1000\n",
    "# center_nodes = [np.random.choice(list(big_component_nodes)) for x in range(0,100)]\n",
    "\n",
    "# G_snowball = snowball_sample(G_big_component, center_nodes, 3)\n",
    "# G_snowball.number_of_nodes(), G_snowball.number_of_edges()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "39461a38-d2c0-41c1-8272-f4c344f9e03a",
   "metadata": {},
   "outputs": [],
   "source": [
    "from littleballoffur import SnowBallSampler\n",
    "\n",
    "\n",
    "snowball_sampler = SnowBallSampler(1000, 2)\n",
    "G_snowball = snowball_sampler.sample(G.to_undirected(), 469)\n",
    "G_snowball.number_of_nodes(), G_snowball.number_of_edges()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a69adf8-cc98-4539-90fb-308529691ec6",
   "metadata": {
    "tags": []
   },
   "source": [
    "We are going to load the snowball sample of `M Theory As A Matrix Model: A Conjecture` we created and investigate what the metrics we previously computed mean."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "05ef9df9-ac3f-4d65-b4c7-89b129f3bc74",
   "metadata": {},
   "outputs": [],
   "source": [
    "g = (\n",
    "    graphistry.bind(\n",
    "        source=\"src\",\n",
    "        destination=\"dst\",\n",
    "        node=\"nodeid\",\n",
    "        point_title=\"Title\",\n",
    "        point_label=\"Title\",\n",
    "    )\n",
    "    .scene_settings(\n",
    "        edge_opacity=0.4,\n",
    "    )\n",
    "    .addStyle(\n",
    "        page={\n",
    "            \"title\": \"Simple Plot\",\n",
    "            \"favicon\": FAVICON_URL\n",
    "        },\n",
    "        logo=LOGO\n",
    "    )\n",
    "    .settings(\n",
    "        url_params=GRAPHISTRY_PARAMS,\n",
    "        height=800,\n",
    "    )\n",
    ")\n",
    "g.plot(G_snowball)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "37297d6e-b083-40cc-9399-c3a6d7c2dd92",
   "metadata": {},
   "source": [
    "<center><img src=\"images/Graphistry_Figure_7.png\" /></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c2b13947-d406-4b21-a268-cf90649143b1",
   "metadata": {
    "tags": []
   },
   "source": [
    "# Beware of Supernodes!\n",
    "\n",
    "Network algorithms can be difficult to scale because comparing every node to every other node has n^2 complexity.\n",
    "\n",
    "<br /><center><img src=\"images/github_adjacency_rjurney.webp\" width=\"600px\" /></center><br />\n",
    "\n",
    "Supernodes are a DEAL STOPPER. What? To rephrase: a common obstacle in implmenting graph algorithms, using common tools or even simple graph processing is when on node has LOTS of connections and processing all of them would take until the end of time.\n",
    "\n",
    "## Addressing Supernodes\n",
    "\n",
    "You can usually efficiently compute the degree of the edges... it is just a `GROUP BY` / `MapReduce` of the node ID at either end followed by a `COUNT(*)`. This gives you in and out degree in a directional network - add them together to get total degree. As we did above, plot a histogram of node degrees. Inspect some of the nodes with the highest degree. Use the histogram to decide on a good cutoff point to filter the node out completely... if you can. Otherwise think about removing edges from that node that aren't important."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7260ae50-e883-419d-ac76-d4cf49e405b4",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(f\"Degree: {len(nx.degree(G))}, Degree^2: {len(nx.degree(G)) * len(nx.degree(G)):,}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "24be6f73-319c-4104-8bab-17f476faf904",
   "metadata": {},
   "source": [
    "# Sophisticated Sampling with `littleballoffur`\n",
    "\n",
    "<br />\n",
    "\n",
    "<center><img src=\"images/littleballoffur_logo_text.jpg\" width=\"700px\" /></center>\n",
    "\n",
    "<br /><br />\n",
    "\n",
    "The [littleballoffur](https://little-ball-of-fur.readthedocs.io/en/latest/notes/introduction.html) library has many sampling methods for both nodes and edges.\n",
    "\n",
    "Types of sampling include:\n",
    "\n",
    "## Node Sampling Methods\n",
    "\n",
    "* [RandomNodeSampler](https://little-ball-of-fur.readthedocs.io/en/latest/modules/node_sampling.html#littleballoffur.node_sampling.randomnodesampler.RandomNodeSampler)\n",
    "* [DegreeBasedSampler](https://little-ball-of-fur.readthedocs.io/en/latest/modules/node_sampling.html#littleballoffur.node_sampling.degreebasedsampler.DegreeBasedSampler)\n",
    "* [PageRankBasedSampler](https://little-ball-of-fur.readthedocs.io/en/latest/modules/node_sampling.html#littleballoffur.node_sampling.pagerankbasedsampler.PageRankBasedSampler)\n",
    "\n",
    "## Edge Sampling Methods\n",
    "\n",
    "* [RandomEdgeSampler](https://little-ball-of-fur.readthedocs.io/en/latest/modules/edge_sampling.html#littleballoffur.edge_sampling.randomedgesampler.RandomEdgeSampler)\n",
    "* [RandomNodeEdgeSampler](https://little-ball-of-fur.readthedocs.io/en/latest/modules/edge_sampling.html#littleballoffur.edge_sampling.randomnodeedgesampler.RandomNodeEdgeSampler)\n",
    "* [HybridNodeEdgeSampler](https://little-ball-of-fur.readthedocs.io/en/latest/modules/edge_sampling.html#littleballoffur.edge_sampling.hybridnodeedgesampler.HybridNodeEdgeSampler)\n",
    "* [RandomEdgeSamplerWithPartialInduction](https://little-ball-of-fur.readthedocs.io/en/latest/modules/edge_sampling.html#littleballoffur.edge_sampling.randomedgesamplerwithpartialinduction.RandomEdgeSamplerWithPartialInduction)\n",
    "* [RandomEdgeSamplerWithInduction](https://little-ball-of-fur.readthedocs.io/en/latest/modules/edge_sampling.html#littleballoffur.edge_sampling.randomedgesamplerwithinduction.RandomEdgeSamplerWithInduction)\n",
    "\n",
    "## Exploration Sampling\n",
    "\n",
    "> The common idea in this family of sampling techniques is that we first select a node uniformly at random and then explore the nodes in its the vicinity.\n",
    ">\n",
    "> --Sampling from Large Graphs, Leskovec, J; Faloutsos, C; 2006.\n",
    "\n",
    "* [DiffusionSampler](https://little-ball-of-fur.readthedocs.io/en/latest/modules/exploration_sampling.html#littleballoffur.exploration_sampling.diffusionsampler.DiffusionSampler)\n",
    "* ... too many to list :) [ChatGPT-4 dies when I ask it to do the information extraction]\n",
    "\n",
    "## Exercise: Sample `G_orig` and Visualize in Graphistry\n",
    "\n",
    "Try different sampling methods using `littleballoffur`. How do they affect the structre you see in Graphistry? What about the charts above? Visualize the graph returned by different parameters of our `G_orig` network. Try taking a new `G_my_sample` sampled network and replacing the `G` variable up top where we created the `G_orig` variabl the first time we did so.\n",
    "\n",
    "What changed? Can you tell? Try making all nodes the same size to focus on the topology and structre of the network. Ask for help if you need it!\n",
    "\n",
    "**NOTE: REMEMBER TO USE THE `G_orig` VARIABLE NOT `G` if you replaced it above.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ee01fc0f-d75e-47a2-9adb-ac685b2d5251",
   "metadata": {},
   "outputs": [],
   "source": [
    "# This is a better [more reliable, has unit tests] way to go than my own implementation above...\n",
    "from littleballoffur import PageRankBasedSampler, NonBackTrackingRandomWalkSampler, RandomWalkSampler, ForestFireSampler, RandomEdgeSampler\n",
    "\n",
    "\n",
    "sample_node_size = 10000\n",
    "sampler = PageRankBasedSampler(sample_node_size)\n",
    "\n",
    "# Most of these use undirected graphs\n",
    "G_new = sampler.sample(G_orig.to_undirected())\n",
    "G_new.number_of_nodes(), G_new.number_of_edges()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c2c2fa2e-b33a-4341-b2f6-d5b5cdeec632",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(f\"Original graph:\\n\")\n",
    "describe_graph(G_orig)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c3d1071f-79fa-4d93-aace-c02a18b5e1ae",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(f\"Sampled graph:\\n\")\n",
    "describe_graph(G_new)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1b7f94c6-3143-45ed-b2c3-5c46b5758698",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(f\"Snowball sampled graph:\\n\")\n",
    "describe_graph(G_snowball)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cf3aa709-003d-4e54-b257-9acb12d4667c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Our properties are still there... new_graph\n",
    "list(G_new.nodes(data=True))[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0d2da8d6-dd2b-478b-b767-dfe654634a80",
   "metadata": {},
   "outputs": [],
   "source": [
    "g = (\n",
    "    graphistry.bind(\n",
    "        source=\"src\",\n",
    "        destination=\"dst\",\n",
    "        node=\"nodeid\",\n",
    "        point_title=\"Title\",\n",
    "        point_label=\"Title\",\n",
    "    )\n",
    "    .scene_settings(\n",
    "        edge_opacity=0.4,\n",
    "    )\n",
    "    .addStyle(\n",
    "        page={\n",
    "            \"title\": \"Simple Plot\",\n",
    "            \"favicon\": FAVICON_URL\n",
    "        },\n",
    "        logo=LOGO\n",
    "    )\n",
    "    .settings(\n",
    "        url_params=GRAPHISTRY_PARAMS,\n",
    "        height=800,\n",
    "    )\n",
    ")\n",
    "g.plot(G_new)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22d20690-e866-433e-b39b-628f84dd322c",
   "metadata": {},
   "source": [
    "<center><img src=\"images/Graphistry_Figure_6.png\" /></center>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "65e15810-37cb-4cae-98e5-356b130d854e",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.11.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}