{ "cells": [ { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%load_ext autoreload\n", "%autoreload 2\n", "%matplotlib inline\n", "%config InlineBackend.figure_format = 'retina'\n", "import warnings\n", "warnings.filterwarnings('ignore')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Introduction" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from IPython.display import YouTubeVideo\n", "\n", "YouTubeVideo(id=\"-oimHbVDdDA\", width=560, height=315)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Because of the relational structure in a graph,\n", "we can begin to think about \"importance\" of a node\n", "that is induced because of its relationships\n", "to the rest of the nodes in the graph.\n", "\n", "Before we go on, let's think about\n", "a pertinent and contemporary example.\n", "\n", "### An example: contact tracing\n", "\n", "At the time of writing (April 2020),\n", "finding important nodes in a graph has actually taken on a measure of importance\n", "that we might not have appreciated before.\n", "With the COVID-19 virus spreading,\n", "contact tracing has become quite important.\n", "In an infectious disease contact network,\n", "where individuals are nodes and\n", "contact between individuals of some kind are the edges,\n", "an \"important\" node in this contact network\n", "would be an individual who was infected\n", "who also was in contact with many people\n", "during the time that they were infected.\n", "\n", "### Our dataset: \"Sociopatterns\"\n", "\n", "The dataset that we will use in this chapter is the \"[sociopatterns network][sociopatterns]\" dataset.\n", "Incidentally, it's also about infectious diseases. \n", "\n", "[sociopatterns]: http://www.sociopatterns.org/datasets/infectious-sociopatterns-dynamic-contact-networks/\n", "\n", "Note to readers: We originally obtained the dataset in 2014\n", "from the Konect website.\n", "It is unfortunately no longer available.\n", "The sociopatterns.org website hosts an edge list of a slightly different format,\n", "so it will look different from what we have here.\n", "\n", "From the original description on Konect, here is the description of the dataset:\n", "\n", "> This network describes the face-to-face behavior of people\n", "> during the exhibition INFECTIOUS: STAY AWAY in 2009\n", "> at the Science Gallery in Dublin.\n", "> Nodes represent exhibition visitors;\n", "> edges represent face-to-face contacts that were active for at least 20 seconds.\n", "> Multiple edges between two nodes are possible and denote multiple contacts.\n", "> The network contains the data from the day with the most interactions.\n", "\n", "To simplify the network, we have represented only the last contact between individuals." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from nams import load_data as cf\n", "G = cf.load_sociopatterns_network()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It is loaded as an undirected graph object:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "type(G)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "As usual, before proceeding with any analysis,\n", "we should know basic graph statistics." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "len(G.nodes()), len(G.edges())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## A Measure of Importance: \"Number of Neighbors\"\n", "\n", "One measure of importance of a node is\n", "the number of **neighbors** that the node has.\n", "What is a **neighbor**?\n", "We will work with the following definition:\n", "\n", "> The neighbor of a node is connected to that node by an edge.\n", "\n", "Let's explore this concept, using the NetworkX API.\n", "\n", "Every NetworkX graph provides a `G.neighbors(node)` class method,\n", "which lets us query a graph for the number of neighbors\n", "of a given node:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "G.neighbors(7)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It returns a generator that doesn't immediately return\n", "the exact neighbors list.\n", "This means we cannot know its exact length,\n", "as it is a generator.\n", "If you tried to do:\n", "\n", "```python\n", "len(G.neighbors(7))\n", "```\n", "\n", "you would get the following error:\n", "\n", "```python\n", "---------------------------------------------------------------------------\n", "TypeError Traceback (most recent call last)\n", " in \n", "----> 1 len(G.neighbors(7))\n", "\n", "TypeError: object of type 'dict_keyiterator' has no len()\n", "```\n", "\n", "Hence, we will need to cast it as a list in order to know\n", "both its length\n", "and its members:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "list(G.neighbors(7))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In the event that some nodes have an extensive list of neighbors,\n", "then using the `dict_keyiterator` is potentially a good memory-saving technique,\n", "as it lazily yields the neighbors." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise: Rank-ordering the number of neighbors a node has\n", "\n", "Since we know how to get the list of nodes that are neighbors of a given node,\n", "try this following exercise:\n", "\n", "> Can you create a ranked list of the importance of each individual, based on the number of neighbors they have?\n", "\n", "Here are a few hints to help:\n", "\n", "- You could consider using a `pandas Series`. This would be a modern and idiomatic way of approaching the problem.\n", "- You could also consider using Python's `sorted` function." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from nams.solutions.hubs import rank_ordered_neighbors\n", "\n", "#### REPLACE THE NEXT FEW LINES WITH YOUR ANSWER\n", "# answer = rank_ordered_neighbors(G)\n", "# answer" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The original implementation looked like the following" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from nams.solutions.hubs import rank_ordered_neighbors_original\n", "# rank_ordered_neighbors_original??" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "And another implementation that uses generators:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from nams.solutions.hubs import rank_ordered_neighbors_generator\n", "# rank_ordered_neighbors_generator??" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Generalizing \"neighbors\" to arbitrarily-sized graphs\n", "\n", "The concept of neighbors is simple and appealing,\n", "but it leaves us with a slight point of dissatisfaction:\n", "it is difficult to compare graphs of different sizes.\n", "Is a node more important solely because it has more neighbors?\n", "What if it were situated in an extremely large graph?\n", "Would we not expect it to have more neighbors?\n", "\n", "As such, we need a normalization factor.\n", "One reasonable one, in fact, is\n", "_the number of nodes that a given node could **possibly** be connected to._\n", "By taking the ratio of the number of neighbors a node has\n", "to the number of neighbors it could possibly have,\n", "we get the **degree centrality** metric.\n", "\n", "Formally defined, the degree centrality of a node (let's call it $d$)\n", "is the number of neighbors that a node has (let's call it $n$)\n", "divided by the number of neighbors it could _possibly_ have (let's call it $N$):\n", "\n", "$$d = \\frac{n}{N}$$\n", "\n", "NetworkX provides a function for us to calculate degree centrality conveniently:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import networkx as nx\n", "import pandas as pd\n", "dcs = pd.Series(nx.degree_centrality(G))\n", "dcs" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "`nx.degree_centrality(G)` returns to us a dictionary of key-value pairs,\n", "where the keys are node IDs\n", "and values are the degree centrality score.\n", "To save on output length, I took the liberty of casting it as a pandas Series\n", "to make it easier to display.\n", "\n", "Incidentally, we can also sort the series\n", "to find the nodes with the highest degree centralities:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "dcs.sort_values(ascending=False)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Does the list order look familiar?\n", "It should, since the numerator of the degree centrality metric\n", "is identical to the number of neighbors,\n", "and the denominator is a constant.\n", "\n", "## Distribution of graph metrics\n", "\n", "One important concept that you should come to know\n", "is that the distribution of node-centric values\n", "can characterize classes of graphs.\n", "\n", "What do we mean by \"distribution of node-centric values\"?\n", "One would be the degree distribution,\n", "that is, the collection of node degree values in a graph.\n", "\n", "Generally, you might be familiar with plotting a histogram\n", "to visualize distributions of values,\n", "but in this book, we are going to avoid histograms like the plague.\n", "I detail a lot of reasons in a [blog post][ecdf] I wrote in 2018,\n", "but the main points are that:\n", "\n", "1. It's easier to lie with histograms.\n", "1. You get informative statistical information (median, IQR, extremes/outliers)\n", "more easily.\n", "\n", "[ecdf]: https://ericmjl.github.io/blog/2018/7/14/ecdfs/\n", "\n", "### Exercise: Degree distribution\n", "\n", "In this next exercise, we are going to get practice visualizing these values\n", "using empirical cumulative distribution function plots.\n", "\n", "I have written for you an ECDF function that you can use already.\n", "Its API looks like the following:\n", "\n", "```python\n", "x, y = ecdf(list_of_values)\n", "```\n", "\n", "giving you `x` and `y` values that you can directly plot.\n", "\n", "The exercise prompt is this:\n", "\n", "> Plot the ECDF of the degree centrality and degree distributions.\n", "\n", "First do it for **degree centrality**:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from nams.functions import ecdf\n", "from nams.solutions.hubs import ecdf_degree_centrality\n", "\n", "#### REPLACE THE FUNCTION CALL WITH YOUR ANSWER\n", "ecdf_degree_centrality(G)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now do it for **degree**:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from nams.solutions.hubs import ecdf_degree\n", "\n", "#### REPLACE THE FUNCTION CALL WITH YOUR ANSWER\n", "ecdf_degree(G)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The fact that they are identically-shaped\n", "should not surprise you!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise: What about that denominator?\n", "\n", "The denominator $N$ in the degree centrality definition\n", "is \"the number of nodes that a node could _possibly_ be connected to\".\n", "Can you think of two ways $N$ be defined?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from nams.solutions.hubs import num_possible_neighbors\n", "\n", "#### UNCOMMENT TO SEE MY ANSWER\n", "# print(num_possible_neighbors())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise: Circos Plotting\n", "\n", "Let's get some practice with the `nxviz` API.\n", "\n", "> Visualize the graph `G`, while ordering and colouring them by the 'order' node attribute." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "tags": [] }, "outputs": [], "source": [ "from nams.solutions.hubs import circos_plot\n", "\n", "#### REPLACE THE NEXT LINE WITH YOUR ANSWER\n", "circos_plot(G)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "And here's an alternative view using an arc plot." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "tags": [] }, "outputs": [], "source": [ "import nxviz as nv\n", "nv.arc(G, sort_by=\"order\", node_color_by=\"order\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise: Visual insights\n", "\n", "Since we know that node colour and order\n", "are by the \"order\" in which the person entered into the exhibit,\n", "what does this visualization tell you?" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "tags": [] }, "outputs": [], "source": [ "from nams.solutions.hubs import visual_insights\n", "\n", "#### UNCOMMENT THE NEXT LINE TO SEE MY ANSWER\n", "# print(visual_insights())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise: Investigating degree centrality and node order\n", "\n", "One of the insights that we might have gleaned from visualizing the graph\n", "is that the nodes that have a high degree centrality\n", "might also be responsible for the edges that criss-cross the Circos plot.\n", "To test this, plot the following:\n", "\n", "- x-axis: node degree centrality\n", "- y-axis: maximum difference between the neighbors' `order`s (a node attribute) and the node's `order`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from nams.solutions.hubs import dc_node_order\n", "\n", "dc_node_order(G)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The somewhat positive correlation between the degree centrality might tell us that this trend holds true.\n", "A further applied question would be to ask what behaviour of these nodes would give rise to this pattern.\n", "Are these nodes actually exhibit staff?\n", "Or is there some other reason why they are staying so long?\n", "This, of course, would require joining in further information\n", "that we would overlay on top of the graph\n", "(by adding them as node or edge attributes)\n", "before we might make further statements." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Reflections\n", "\n", "In this chapter, we defined a metric of node importance: the degree centrality metric.\n", "In the example we looked at, it could help us identify\n", "potential infectious agent superspreaders in a disease contact network.\n", "In other settings, it might help us spot:\n", "\n", "- message amplifiers/influencers in a social network, and \n", "- potentially crowded airports that have lots of connections into and out of it (still relevant to infectious disease spread!)\n", "- and many more!\n", "\n", "What other settings can you think of in which the number of neighbors that a node has can become\n", "a metric of importance for the node?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Solutions\n", "\n", "Here are the solutions to the exercises above." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "tags": [] }, "outputs": [], "source": [ "from nams.solutions import hubs\n", "import inspect\n", "\n", "print(inspect.getsource(hubs))" ] } ], "metadata": { "kernelspec": { "display_name": "nams", "language": "python", "name": "nams" }, "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.8.10" } }, "nbformat": 4, "nbformat_minor": 4 }