03_graph_exploration_and_sampling.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Graph exploration and sampling\n",
    "\n",
    "Here we experiment network exploration using the main graph samplers that can be found in the literature. The principle is the following: The initial graph is too large to be handled and we need to extract a representative part of it for analysis. We hope this reduced subgraph is representative of the large one, and, indeed, there are theoretical guarantees about that for each method. \n",
    "\n",
    "The different samplers are designed to preserve particular graph properties when subsampling. We will see what properties are associated to each sampler and learn to select the most adapted one depending on the application."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "import littleballoffur as lbof\n",
    "import matplotlib.pyplot as plt\n",
    "from collections import Counter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The main samplers are coded in the Python module called \"little ball of fur\" https://github.com/benedekrozemberczki/littleballoffur and we will use it here (`pip install littleballoffur`).\n",
    "The documentation can be found here:\n",
    "* https://little-ball-of-fur.readthedocs.io\n",
    "\n",
    "Let us load one of the datasets available in the module."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# load a graph\n",
    "#reader = lbof.GraphReader(\"facebook\")\n",
    "reader = lbof.GraphReader(\"github\")\n",
    "G = reader.get_graph()\n",
    "print('Number of nodes: {}, number of edges: {}.'.format(G.number_of_nodes(),G.number_of_edges()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us suppose this graph is too big for our analysis. We need to get a reduced version of it. We can define the size of this reduced dataset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# number of nodes in the subgraph\n",
    "number_of_nodes = int(0.01*G.number_of_nodes())\n",
    "print('Number of nodes in the subgraph:',number_of_nodes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There exist several ways for sampling a graph. When you have access to the full graph, you may sample at random edges or nodes, this is the first family. Alternatively, you can start from an initial group of nodes and collect  a part of the graph by exploring (following connections) from them. We shall focus on these latter approaches."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exploring the network"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### General principle\n",
    "For the applications we have in mind, we want to start the exploration from an initial set of nodes. For example, it could be a particular user or group of users in a social network that are posting about a topic we are interested in. We want to know more about this topic and related topics appearing in the exchanges. Our goal is to explore the network around this initial group. Hence we plan to use the exploration methods.\n",
    "\n",
    "The exploration scheme is show on the following figure. Starting from an initial node, the neighborhood is explored, selecting randomly a subset of edges (with possibly different probability weights for different edges). Then the process is iterated on the new nodes sampled.\n",
    "![spikyball](figures/spikyballfinal.png)\n",
    "\n",
    "<center>Left: snowball exploration, follows all edges. Right: spikyball exploration, follow a subset of edges at each step.</center>\n",
    "\n",
    "Among the most popular explorations are: \n",
    "- Metropolis-Hasting randow walk sampler ([paper](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.140.4864&rep=rep1&type=pdf)) and ([paper](https://core.ac.uk/download/pdf/192275476.pdf)),\n",
    "- Forest Fire sampler ([paper](https://cs.stanford.edu/people/jure/pubs/sampling-kdd06.pdf)).\n",
    "\n",
    "MHRW algorithm (with $k_v$ the degree of node $v$):\n",
    "![MHRW algorithm](figures/MHRWalgo.png)\n",
    "\n",
    "The Spikyball ([paper](https://www.mdpi.com/1999-4893/13/11/275)) add more flexibility to the previous sampling schemes while still keeping the exploration efficient. At each step of the exploration, all the out-going edges are collected. Depending on their weight and the number of theses connections on the initial and target nodes, some edges will be selected. You can influence the sampling toward:\n",
    "* nodes with high degree (parameter $\\alpha$),\n",
    "* nodes connected with large weights (parameter $\\beta$),\n",
    "* neighbors connected to several nodes already sampled (parameter $\\gamma$).\n",
    "\n",
    "\n",
    "![spikyball probability](figures/spikyballproba.png)\n",
    "\n",
    "One step of the exploration is illustrated on the following figure. The sampled graph is in the middle, in purple. The green nodes are the neighbors that can be selected for the next exploration step. Among all the out-going edges, only a part of them are selected, the ones that are straight lines.\n",
    "![graph exploration step](figures/explorationstep.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Application\n",
    "In the following, we experiment the exploration methods on toy graphs. The goal is to understand the different possibility to explore a network, the different parameters and their impact on the sampled network. The initial group of nodes is chosen at random within the exploration functions of `littleballoffur`. So we do not focus on a specific region of the network but rather on the way the exploration is performed. Later on, we will choose initial nodes and apply the exploration to real networks.\n",
    "\n",
    "We save the graphs in `gexf` file in order to visualize them with Gephi."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Metropolis Hasting random walk sampler\n",
    "sampler = lbof.MetropolisHastingsRandomWalkSampler(number_of_nodes = number_of_nodes)\n",
    "GMH = sampler.sample(G)\n",
    "nx.write_gexf(GMH, 'data/gmh.gexf')\n",
    "print('Subgraph with {} nodes and {} edges.'.format(GMH.number_of_nodes(),GMH.number_of_edges()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Forest Fire sampler\n",
    "sampler = lbof.ForestFireSampler(number_of_nodes = number_of_nodes)\n",
    "GFF = sampler.sample(G)\n",
    "nx.write_gexf(GFF, 'data/gff.gexf')\n",
    "print('Subgraph with {} nodes and {} edges.'.format(GFF.number_of_nodes(),GFF.number_of_edges()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A more general and flexible exploration approach called \"Spikyball\" ([paper](https://www.mdpi.com/1999-4893/13/11/275)) can be used."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Fireball sampler is similar to the Forest Fire sampler\n",
    "sampler = lbof.SpikyBallSampler(number_of_nodes = number_of_nodes, sampling_probability=0.1, mode='fireball', \n",
    "                                initial_nodes_ratio=0.001)\n",
    "GFB = sampler.sample(G)\n",
    "nx.write_gexf(GFB, 'data/gfb.gexf')\n",
    "print('Subgraph with {} nodes and {} edges.'.format(GFB.number_of_nodes(), GFB.number_of_edges()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Coreball sampler\n",
    "sampler = lbof.SpikyBallSampler(number_of_nodes = number_of_nodes, sampling_probability=0.1, mode='coreball',\n",
    "                                initial_nodes_ratio=0.001)\n",
    "GCB = sampler.sample(G)\n",
    "# Remove isolated nodes\n",
    "GCB = nx.Graph(GCB)\n",
    "GCB.remove_nodes_from(list(nx.isolates(GCB)))\n",
    "nx.write_gexf(GCB, 'data/gcb.gexf')\n",
    "print('Subgraph with {} nodes and {} edges.'.format(GCB.number_of_nodes(), GCB.number_of_edges()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Coreball 2 sampler\n",
    "sampler = lbof.SpikyBallSampler(number_of_nodes = number_of_nodes, sampling_probability=0.1, mode='coreball',\n",
    "                                initial_nodes_ratio=0.001, distrib_coeff=2)\n",
    "GCB2 = sampler.sample(G)\n",
    "# Remove isolated nodes\n",
    "GCB2 = nx.Graph(GCB2)\n",
    "GCB2.remove_nodes_from(list(nx.isolates(GCB2)))\n",
    "nx.write_gexf(GCB2, 'data/gcb2.gexf')\n",
    "print('Subgraph with {} nodes and {} edges.'.format(GCB2.number_of_nodes(), GCB2.number_of_edges()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise**: Visualize some of the sampled graphs with Gephi."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Visualisation of the graphs (from Gephi)\n",
    "Metropolis-Hasting RW, Forest Fire, Fireball and Coreball \n",
    "<table><tr>\n",
    "    <td><img src=\"figures/gmh.png\" alt=\"MetropolisHasting\" width=\"200\"> </td>\n",
    "    <td><img src=\"figures/gff.png\" alt=\"Forest Fire\" width=\"200\"></td>\n",
    "    <td><img src=\"figures/gfb.png\" alt=\"Fireball\" width=\"200\"></td>\n",
    "    <td><img src=\"figures/gcb.png\" alt=\"Coreball\" width=\"200\"></td>\n",
    "</tr></table>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Degree distribution\n",
    "Let us see what is the degree distribution of these networks."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# A function to plot the degree distribution of a given graph\n",
    "def plot_degree(G,glabel):\n",
    "    m=1 # minimal degree to display\n",
    "    degree_freq = nx.degree_histogram(G)\n",
    "    degrees = range(len(degree_freq))\n",
    "    plt.scatter(degrees[m:], degree_freq[m:],label=glabel)\n",
    "    return max(degrees),max(degree_freq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.figure(figsize=(12, 8)) \n",
    "mx1,my1 = plot_degree(GMH,'MH')\n",
    "mx2,my2 = plot_degree(GFF,'FF')\n",
    "mx3,my3 = plot_degree(GFB,'FB')\n",
    "mx4,my4 = plot_degree(GCB,'CB')\n",
    "mx5,my5 = plot_degree(GCB2,'CB2')\n",
    "\n",
    "plt.xlim(1, max([mx1,mx2,mx3,mx4,mx5]))\n",
    "plt.ylim(1, max([my1,my2,my3,my4,my5]))\n",
    "plt.yscale('log')\n",
    "plt.xscale('log')\n",
    "plt.xlabel('Degree')\n",
    "plt.ylabel('Frequency')\n",
    "plt.legend()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Remark 1:** this visualization is simple to code but not the most appropriate. A more precise curve could be obtained by grouping degrees in bins, with a range following a logaritmic scale."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Remark 2:** The size of the sampled graphs is good for visualization but too small for having good statistics on the degree distribution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A larger subgraph\n",
    "We increase the size of the sampled subgraph to have better statistics on the degree distribution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "number_of_nodes = 3000\n",
    "# MHRW\n",
    "sampler = lbof.MetropolisHastingsRandomWalkSampler(number_of_nodes = number_of_nodes)\n",
    "GMH = sampler.sample(G)\n",
    "print('MHRW subgraph with {} nodes and {} edges.'.format(GMH.number_of_nodes(),GMH.number_of_edges()))\n",
    "\n",
    "# FF\n",
    "sampler = lbof.ForestFireSampler(number_of_nodes = number_of_nodes)\n",
    "GFF = sampler.sample(G)\n",
    "print('FF subgraph with {} nodes and {} edges.'.format(GFF.number_of_nodes(),GFF.number_of_edges()))\n",
    "\n",
    "# Fireball\n",
    "sampler = lbof.SpikyBallSampler(number_of_nodes = number_of_nodes, sampling_probability=0.05, mode='fireball', \n",
    "                                initial_nodes_ratio=0.001)\n",
    "GFB = sampler.sample(G)\n",
    "print('FB subgraph with {} nodes and {} edges.'.format(GFB.number_of_nodes(), GFB.number_of_edges()))\n",
    "\n",
    "# Coreball\n",
    "sampler = lbof.SpikyBallSampler(number_of_nodes = number_of_nodes, sampling_probability=0.1, mode='coreball',\n",
    "                                initial_nodes_ratio=0.001)\n",
    "GCB = sampler.sample(G)\n",
    "print('CB subgraph with {} nodes and {} edges.'.format(GCB.number_of_nodes(), GCB.number_of_edges()))\n",
    "\n",
    "# Coreball 2\n",
    "sampler = lbof.SpikyBallSampler(number_of_nodes = number_of_nodes, sampling_probability=0.1, mode='coreball',\n",
    "                                initial_nodes_ratio=0.001, distrib_coeff=2)\n",
    "GCB2 = sampler.sample(G)\n",
    "print('CB2 subgraph with {} nodes and {} edges.'.format(GCB2.number_of_nodes(), GCB2.number_of_edges()))\n",
    "\n",
    "# Plot degree distribution\n",
    "plt.figure(figsize=(12, 8)) \n",
    "mx1,my1 = plot_degree(GMH,'MH')\n",
    "mx2,my2 = plot_degree(GFF,'FF')\n",
    "mx3,my3 = plot_degree(GFB,'FB')\n",
    "mx4,my4 = plot_degree(GCB,'CB')\n",
    "mx5,my5 = plot_degree(GCB2,'CB2')\n",
    "\n",
    "plt.xlim(1, max([mx1,mx2,mx3,mx4,mx5]))\n",
    "plt.ylim(1, max([my1,my2,my3,my4,my5]))\n",
    "plt.yscale('log')\n",
    "plt.xscale('log')\n",
    "plt.xlabel('Degree')\n",
    "plt.ylabel('Frequency')\n",
    "plt.legend()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Degrees in the initial graph\n",
    "How do the different methods perform with respect to node degrees in the initial graph? Do they collect more nodes with a high degree or not?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Add degree as a node property in the initial graph\n",
    "# Then we can collect it easily in the usbsampled graph\n",
    "nx.set_node_attributes(G,dict(G.degree()), name='degree')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# A function to plot the degree distribution of a given graph\n",
    "def plot_d_init(G,subgraph,glabel):\n",
    "    m=1 # minimal degree to display\n",
    "    d = [G.nodes[i]['degree'] for i in subgraph.nodes()]\n",
    "    counter_dic = Counter(d)\n",
    "    degrees = list(counter_dic.keys())\n",
    "    degree_freq = list(counter_dic.values())\n",
    "    #degree_freq, degrees = np.histogram(d,bins=50)\n",
    "    #print(len(degree_freq),len(degrees))\n",
    "    #degree_freq = nx.degree_histogram(G)\n",
    "    #degrees = range(len(degree_freq))\n",
    "    plt.scatter(degrees[m:], degree_freq[m:],label=glabel)\n",
    "    return max(degrees),max(degree_freq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.figure(figsize=(12, 8)) \n",
    "mx1,my1 = plot_d_init(G,GMH,'MH')\n",
    "mx2,my2 = plot_d_init(G,GFF,'FF')\n",
    "mx3,my3 = plot_d_init(G,GFB,'FB')\n",
    "mx4,my4 = plot_d_init(G,GCB,'CB')\n",
    "mx5,my5 = plot_d_init(G,GCB2,'CB2')\n",
    "\n",
    "plt.xlim(1, max([mx1,mx2,mx3,mx4,mx5]))\n",
    "plt.ylim(1, max([my1,my2,my3,my4,my5]))\n",
    "plt.yscale('log')\n",
    "plt.xscale('log')\n",
    "plt.xlabel('Degree')\n",
    "plt.ylabel('Frequency')\n",
    "plt.legend()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise\n",
    "Redo the experiments with different parameters for the fireball and coreball and a different graph.\n",
    "What are the best exploration methods\n",
    "* for collecting more high degree nodes? \n",
    "* for keeping the same degree distribution? \n",
    "* for exploring a larger part of the network?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}