01_introduction_to_graphs.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction to graphs with Python and the networkx module\n",
    "\n",
    "* Dataset: [TUDataset](https://chrsmrrs.github.io/datasets/docs/datasets/)\n",
    "* Tools: [pandas](https://pandas.pydata.org), [numpy](http://www.numpy.org), [networkx](https://networkx.github.io)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Importing packages"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By convention, the first lines of code are always about importing the packages we'll use."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import networkx as nx\n",
    "import numpy as np\n",
    "import zipfile"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tutorials on pandas can be found at:\n",
    "* https://pandas.pydata.org/pandas-docs/stable/user_guide/10min.html\n",
    "* https://pandas.pydata.org/pandas-docs/stable/getting_started/tutorials.html\n",
    "\n",
    "Tutorials on numpy can be found at:\n",
    "* https://numpy.org/doc/stable/user/quickstart.html\n",
    "* <http://www.scipy-lectures.org/intro/numpy/index.html>\n",
    "* <http://www.scipy-lectures.org/advanced/advanced_numpy/index.html>\n",
    "\n",
    "A tutorial on networkx can be found at:\n",
    "* https://networkx.org/documentation/stable/tutorial.html"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Importing the data\n",
    "\n",
    "We will play with a collection of protein graphs available on the [TU Dortmund Dataset repository](https://chrsmrrs.github.io/datasets/). For simplicity, the zipped protein dataset has been added to the tutorial repository, in the `data/` folder and will be loaded from there. This dataset contains a collection of 1113 graphs with a binary label for each. Each node has a single attribute and a label.\n",
    "This dataset is described in \n",
    "* P. D. Dobson and A. J. Doig. Distinguishing enzyme structures from non-enzymes without alignments. J. Mol. Biol., 330(4):771–783, Jul 2003. \n",
    "* K. M. Borgwardt, C. S. Ong, S. Schoenauer, S. V. N. Vishwanathan, A. J. Smola, and H. P. Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(Suppl 1):i47–i56, Jun 2005 \n",
    "* Feragen, A., Kasenburg, N., Petersen, J., de Bruijne, M., Borgwardt, K.M.: Scalable kernels for graphs with continuous attributes. In: C.J.C. Burges, L. Bottou, Z. Ghahramani, K.Q. Weinberger (eds.) NIPS, pp. 216-224 (2013)\n",
    "\n",
    "### Data description\n",
    "Each protein is represented as a graph of secondary structure elements (SSEs). The nodes are structure elements such as helices, sheets and turns. They are connected to their nearest neighbor SSEs either in the proteins sequence or in space. Each node has a label indicating the structure of the SSE (an helix, a sheet or a turn). In addition, a node attribute is given under the form of a float number, representing some chemical properties of the structure. Note that the property is not clear from the dataset. There is only one property while the litterature refers to several.\n",
    "\n",
    "Each protein (graph) has a binary label to indicate if it is enzime / non-enzime.\n",
    "\n",
    "### Some proteins visualized using Gephi and a force atlas layout\n",
    "![Proteins as graphs, visualized with Gephi](Proteinsgraph.png)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# The data is compressed in a zip file\n",
    "# import zipfile\n",
    "archive = zipfile.ZipFile('data/PROTEINS.zip', 'r')\n",
    "\n",
    "# We use pandas to read csv files (after being uncompressed by zipfile)\n",
    "# There are 5 data files, each one containing different information about the graphs\n",
    "\n",
    "# Connections between nodes\n",
    "edges = pd.read_csv(archive.open('PROTEINS/PROTEINS_A.txt'), names=['Source','Target'])\n",
    "# Indicator associated to each node: indicates the graph it belongs to (from the 1113 possible graphs)\n",
    "graph_ind = pd.read_csv(archive.open('PROTEINS/PROTEINS_graph_indicator.txt'), names=['Graph_indicator'])\n",
    "graph_ind.index = np.arange(1, len(graph_ind) + 1) # correct for first node labelled 1 instead of 0\n",
    "# Label for each graph\n",
    "graph_labels = pd.read_csv(archive.open('PROTEINS/PROTEINS_graph_labels.txt'), names=['Label'])\n",
    "graph_labels.index = np.arange(1, len(graph_labels) + 1) # correct for first graph labelled 1 instead of 0\n",
    "# Attribute for each node of the dataset\n",
    "node_attributes = pd.read_csv(archive.open('PROTEINS/PROTEINS_node_attributes.txt'), names=['Node_attribute'])\n",
    "node_attributes.index = np.arange(1, len(node_attributes) + 1) # correct for first node labelled 1 instead of 0\n",
    "# Label for each node\n",
    "node_labels = pd.read_csv(archive.open('PROTEINS/PROTEINS_node_labels.txt'), names=['Label'])\n",
    "node_labels.index = np.arange(1, len(node_labels) + 1) # correct for first node labelled 1 instead of 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Graph and data](graphdata.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Data exploration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "edges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph_ind"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can see we have 1113 different graphs, and 43470 nodes in total."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(graph_labels)\n",
    "print('-----')\n",
    "print('How many unique graph labels are there? What are their values?')\n",
    "print(graph_labels['Label'].unique())\n",
    "print(graph_labels['Label'].value_counts())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(node_labels)\n",
    "print('-----')\n",
    "print('How many unique node labels are there? What are their values?')\n",
    "print(node_labels['Label'].value_counts())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(node_attributes)\n",
    "print('-----')\n",
    "print('How many unique node attributes are there? What are their values?')\n",
    "print(node_attributes['Node_attribute'].value_counts())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How to access individual values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "edges.iloc[0, :]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "edges.iloc[0, 0], edges.iloc[0, 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "edges.loc[0, 'Target']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "Selecting a single graph and displaying its nodes labels"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "node_labels[ graph_ind['Graph_indicator'] == 1 ]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The graph\n",
    "Now the data is has the appropriate shape, we may build the graph using `networkx`. It is a simple iteration over the rows of the dataframe, using `nx.add_edge`. Alternatively, you may use `nx.add_edge_from` with a list of edges as input."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# A simple command to create the graph from the edge list.\n",
    "graph = nx.Graph() # Graph class is for undirected graph\n",
    "_ = [graph.add_edge(source, target) for source, target in zip(edges['Source'], edges['Target'])]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also use the `add_edges_from` function instead of a list comprehension"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph = nx.Graph()\n",
    "graph.add_edges_from(edges[['Source', 'Target']].itertuples(name=None, index=False))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And finally, the dataframe can be used directly to create the graph thanks to the `from_pandas_edgelist` function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph = nx.from_pandas_edgelist(edges, source='Source', target='Target', create_using=nx.Graph())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In addition, let us add some attributes to the nodes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "node_props = node_attributes.to_dict()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#node_props"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for key in node_props:\n",
    "    nx.set_node_attributes(graph, node_props[key], key)\n",
    "    print(key)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us check if it is correctly recorded:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(graph.nodes[1], graph.nodes[2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# let us add node labels and graph indicator too as node properties\n",
    "node_l = node_labels.to_dict()\n",
    "nx.set_node_attributes(graph, node_l[\"Label\"], \"Label\")\n",
    "\n",
    "node_gi = graph_ind.to_dict()\n",
    "nx.set_node_attributes(graph, node_gi['Graph_indicator'], 'Graph_indicator')\n",
    "\n",
    "# Exercice: make a function containing this for loop to load attibutes from dataframes to the networkx graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(graph.nodes[1], graph.nodes[2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Graph and data](graphdata2.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** \n",
    "* Have a look a the [networkx documentation](https://networkx.org/documentation/stable/tutorial.html) and display the number of nodes and edges of the graph.\n",
    "* Display the neighbors of node '1', then the 2-hops neighbors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us use some convenient functions of networkx. Our global graph contains all the subgraphs of the dataset. Let us check that `graph` is a disconnected graph, i.e. is made of subgraphs that are not connected to each other."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print('Is the graph connected?')\n",
    "nx.is_connected(graph)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We separate each small graph from the others and make a list of them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "S = [graph.subgraph(c).copy() for c in nx.connected_components(graph)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "idx = 0\n",
    "Gs = S[idx]\n",
    "print('The graph with index {} in the list has {} nodes.'.format(idx, Gs.number_of_nodes()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graph visualization\n",
    "\n",
    "To conclude, let us visualize the graph. We will use networkx for that."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following line is a [magic command](https://ipython.readthedocs.io/en/stable/interactive/magics.html). It enables plotting inside the notebook."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You may also try `%matplotlib notebook` for a zoomable version of plots."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us draw the graph with two different [layout algorithms](https://en.wikipedia.org/wiki/Graph_drawing#Layout_methods). As you will see, networkx and matplotlib are not very convenient for plotting graphs. We will see other visualization tools later on."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "color_list = list(nx.get_node_attributes(Gs,'Label').values())\n",
    "#color_list = list(nx.get_node_attributes(Gs,'Node_attribute').values())\n",
    "#color_list = list(nx.get_node_attributes(Gs,'Graph_indicator').values())\n",
    "nx.draw_spectral(Gs, node_color = color_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#nx.get_node_attributes(Gs,'Label')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# A different visualization\n",
    "color_list = list(nx.get_node_attributes(Gs,'Node_attribute').values())\n",
    "nx.draw_spring(Gs, node_color = color_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# You may also visualize names with the following command,\n",
    "# but in our case the graph is too big and labels overlap:\n",
    "#\n",
    "labels = nx.get_node_attributes(Gs,'Label')\n",
    "nx.draw_spring(Gs, labels=labels)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Saving the graph\n",
    "Save the graph to disk in the `gexf` format, readable by Gephi and other tools that manipulate graphs. You may now explore the graph using [gephi](https://gephi.org/) and compare the visualizations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Global graph\n",
    "nx.write_gexf(graph, 'data/Gprotein.gexf')\n",
    "# first subgraph\n",
    "nx.write_gexf(Gs, 'data/Gproteinsubgraph.gexf')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note: the `gexf` format allows one to save node and edge properties, except if the properties have a complex structure such as python lists or dictionaries. In that case, these structures must be converted to strings (using json) before saving the graph."
   ]
  },
  {
   "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
}