02_basic_graph_properties.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Basic but important graph properties\n",
    "\n",
    "We introduce here important properties of graphs. These properties provide information on the structure of a graph and help understand their specificities. A social network is very different from a grid graph or a tree graph, they have different geometry and carry different information. The algorithms presented here enable to distinguish and categorize them. We will see later on that the exploration, analysis and visualization of graphs face challenges that change depending on these geometries.\n",
    "\n",
    "We use standard methods already implemented in networkx. For more information, have a look at the networkx documentation and the page listing graph properties:\n",
    "* https://networkx.org/documentation/stable//index.html\n",
    "* https://networkx.org/documentation/stable//reference/algorithms/index.html\n",
    "\n",
    "Some of the properties are computationally intensive for large graphs (e.g. the ones based on the computation of all the shortest paths or the spectral methods) and we intentionally work with small graphs for pedagogical purposes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For this experiment we shall test with several graphs. 3 examples are listed below. Uncomment the one you want to choose."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Load our demo graph (or subgraph)\n",
    "#G = nx.read_gexf('data/Gproteinsubgraph.gexf')\n",
    "\n",
    "## Create a random graph\n",
    "N = 200  # number of nodes\n",
    "\n",
    "## Erdos Renyi random graph\n",
    "#p = 0.1  # probability of connection\n",
    "#G = nx.erdos_renyi_graph(N, p, seed=0)\n",
    "\n",
    "## Barabasi Albert graph (model of scale-free network)\n",
    "m = 4 # number of connections when adding a node\n",
    "G = nx.barabasi_albert_graph(N,m,seed=0)\n",
    "\n",
    "print('Number of nodes: {}, number of edges {}.'.format(G.number_of_nodes(),G.number_of_edges()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Networkx has a large list of algorithms to analyze graphs. The ouput can be a single value associated to the whole graph or a dictionary of values where keys are node ids and values are the results of the computation for each node. We shall have a look at some examples."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Node properties\n",
    "To evaluate the importance of a node in the network, several methods have been proposed in the literature. We review three of them:\n",
    "- the simple computation of the **degree** of the nodes\n",
    "- the **betweeness centrality** counting all the shortest paths passing through a node \n",
    "- the famous **Pagerank** which is more computationally efficient. \n",
    "\n",
    "All of them are standard methods one can find in `networkx`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "bc = nx.betweenness_centrality(G)\n",
    "pr = nx.pagerank(G)\n",
    "degree = dict(nx.degree(G))\n",
    "#\n",
    "node_props = pd.DataFrame({'degree' : degree, 'b. centrality' : bc, 'pagerank' : pr})\n",
    "node_props.index.name = 'Node id'\n",
    "print('DataFrame of some node properties:')\n",
    "node_props.sort_values('pagerank', ascending=False).head(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graph properties\n",
    "Some properties are more global and characterize the entire graph.\n",
    "![graph diameter](graphdiameter.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# The diameter is the length of the longest shortest path in the network\n",
    "diameter = nx.diameter(G)\n",
    "# The average shortest path length give a rough idea of the \"small-worldness\" of a graph\n",
    "av_shortest_path = nx.average_shortest_path_length(G)\n",
    "print('Graph diameter: {}. Average shortest path length: {}.'.format(diameter, av_shortest_path))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# The density is the ratio of edges over the number of possible edges if the graph were fully connected\n",
    "density = nx.density(G)\n",
    "# The average clustering coefficient counts the number of triangles and output a ratio\n",
    "cc = nx.average_clustering(G) \n",
    "print('Density: {}. Average clustering coeff.: {}'.format(density, cc))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **k-core** is a subgraph of nodes having at least degree `k`, in that subgraph. It gives an estimation of how hierarchical is the network. High degree nodes that are well connected together, forming a community, will be revealed by this approach."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# k-core\n",
    "for k in range(10):\n",
    "    print('k = {}, size of the subgraph: {} nodes.'.format(k,nx.k_core(G,k).number_of_nodes()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **degree distribution** is one of the main measure of a network structure. Usually, real-world networks are \"scale-free\": the degree distribution is decreasing as the degree increase, in a linear manner when plotted on a log-log scale."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "m=4 # minimal degree to display\n",
    "degree_freq = nx.degree_histogram(G)\n",
    "degrees = range(len(degree_freq))\n",
    "plt.figure(figsize=(12, 8)) \n",
    "#plt.loglog(degrees[m:], degree_freq[m:],'go')\n",
    "plt.scatter(degrees[m:], degree_freq[m:])\n",
    "plt.xlim(m, max(degrees))\n",
    "plt.ylim(1, max(degree_freq))\n",
    "plt.yscale('log')\n",
    "plt.xscale('log')\n",
    "plt.xlabel('Degree')\n",
    "plt.ylabel('Frequency')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Save the graph for visualization (with Gephi)\n",
    "In the next presentation we will see how to visualize a network and its properties with Gephi. We can save our networkx graph as a `gexf` file that can be read by Gephi."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.write_gexf(G, 'data/basic_graph.gexf')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 1\n",
    "Compute the graph properties for different small graphs and compare the results. You can find a large set of graphs to try here: https://networkx.org/documentation/stable//reference/generators.html"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 2\n",
    "Compute the properties for one or more large graphs and note the methods which scale and the ones which do not. Can you explain why?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}