{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# graph-tool\n", "\n", "This Jupyter notebook provides an example of using the Python packages [gravis](https://pypi.org/project/gravis) and [graph-tool](https://graph-tool.skewed.de). The .ipynb file can be found [here](https://github.com/robert-haas/gravis/tree/master/examples).\n", "\n", "## References\n", "\n", "- [graph-tool website](https://graph-tool.skewed.de)\n", " - [Documentation](https://graph-tool.skewed.de/static/doc/index.html)\n", " - [Quickstart](https://graph-tool.skewed.de/static/doc/quickstart.html)\n", " - [Cookbook](https://graph-tool.skewed.de/static/doc/demos/index.html)\n", " - [API reference](https://graph-tool.skewed.de/static/doc/modules.html)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Installation\n", "\n", "- With [pip](https://pypi.org/project/graph-tool/): Not possible without manual compilation of C++ dependencies (Boost, CGAL, expat)\n", "- With [conda](https://anaconda.org/search?q=graph-tool): `conda install -c conda-forge graph-tool`" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Import" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import os\n", "\n", "import graph_tool as gt\n", "import graph_tool.centrality\n", "import graph_tool.collection\n", "import graph_tool.draw\n", "import graph_tool.generation\n", "import graph_tool.inference\n", "\n", "import gravis as gv" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Quick start" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": false }, "outputs": [], "source": [ "def assign_properties(g):\n", " # Centrality calculation\n", " node_centralities, edge_centralities = gt.centrality.betweenness(g)\n", "\n", " # Community detection\n", " communities = gt.inference.minimize_blockmodel_dl(g).get_blocks()\n", "\n", " # Graph properties\n", " g.graph_properties['edge_opacity'] = g.new_graph_property('double', val=0.75) # verbose syntax\n", " g.gp['arrow_size'] = g.new_gp('int', val=3) # shorter syntax\n", " g.gp['node_border_color'] = g.new_gp('string', val='black')\n", " g.gp['node_border_size'] = g.new_gp('float', val=0.5)\n", "\n", " # Node properties: Size by centrality, color by community, hover message by name\n", " colors = ['red', 'blue', 'green', 'orange', 'pink', 'brown', 'yellow', 'cyan', 'magenta', 'violet']\n", " g.vertex_properties['size'] = g.new_vertex_property('double')\n", " g.vp['color'] = g.new_vp('string')\n", " for node in g.vertices():\n", " g.vertex_properties['size'][node] = 7 + node_centralities[node] * 5000\n", " g.vertex_properties['color'][node] = colors[communities[node] % len(colors)]\n", " g.vp['hover'] = g.new_vp('string', vals=g.vp['name'])\n", "\n", " # Edge properties: Size by centrality\n", " g.edge_properties['size'] = g.new_edge_property('string')\n", " for edge in g.edges():\n", " g.edge_properties['size'][edge] = str(0.05 + edge_centralities[edge] * 1000)\n", "\n", "\n", "# Create a graph from a stored example\n", "g = gt.collection.data['serengeti-foodweb']\n", "\n", "# Assign properties\n", "assign_properties(g)\n", "\n", "# Plot it\n", "gv.d3(g, zoom_factor=0.8, show_node_label=False)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Generate a mathematical graph\n", "g = gt.generation.lattice([10, 20], periodic=True)\n", "\n", "# Plot it\n", "gv.d3(g, zoom_factor=0.2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Graph construction\n", "\n", "### 1) Manual graph construction\n", "\n", "- Quickstart: [Creating and manipulating graphs](https://graph-tool.skewed.de/static/doc/quickstart.html#creating-and-manipulating-graphs)\n", "- API: [Graph](https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph)\n", " - [add_vertex](https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.add_vertex)\n", " - [add_edge](https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.add_edge)\n", " - [add_edge_list](https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.add_edge_list)\n", "\n", "#### 1.a) Graph (with directed=False)\n", "\n", "undirected, with self-loops, with parallel edges, with attributes (after explicit declaration)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "ug = gt.Graph(directed=False)\n", "\n", "\n", "# Node with automatic id (starts from 0)\n", "n0 = ug.add_vertex()\n", "\n", "# Node with user-defined id\n", "# ~ Not supported ~\n", "\n", "# Node + attribute\n", "# ~ Not supported ~\n", "\n", "\n", "# Nodes\n", "nodes = ug.add_vertex(6) # argument: number of nodes with automatic ids\n", "n1, n2, n3, n4, n5, n6 = nodes\n", "\n", "\n", "# Edge (nodes may already exist but do not need to, except add_missing=False)\n", "e0 = ug.add_edge(n0, n1, add_missing=False)\n", "e1 = ug.add_edge(n6, 7)\n", "\n", "\n", "# Edges\n", "edges = ug.add_edge_list([\n", " (1, 2),\n", " (n2, 3),\n", " (n3, n4),\n", " (4, 5),\n", " (n5, n6),\n", " (7, 0),\n", " (0, 0),\n", " (n0, n0),\n", " (0, n1),\n", " (0, 1),\n", "])\n", "\n", "\n", "gv.d3(ug, graph_height=200)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### 1.b) Graph (with directed=True)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "dg = gt.Graph(directed=True)\n", "\n", "for source, target in ug.edges():\n", " dg.add_edge(source, target)\n", "\n", "gv.d3(dg, graph_height=200)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Assign attributes to a created graph\n", "\n", "- [Tutorial: Property maps](https://graph-tool.skewed.de/static/doc/quickstart.html#property-maps)\n", " - Property maps are a way of **associating additional information to** the **vertices**, **edges** or to the **graph** itself.\n", " - Three types of property maps: VertexPropertyMap, EdgePropertyMap, and GraphPropertyMap\n", " - Each created property map has an associated **value type**, which must be chosen from the predefined set\n", " - bool, int, long, float, string, vector, ...\n", " - New property maps can be created for a given graph by calling one of the methods\n", " - `new_vertex_property()` alias `new_vp()`\n", " - `new_edge_property()` alias `new_ep()`\n", " - `new_graph_property()` alias `new_gp()`\n", " - Any created property map can be **made “internal”** to the corresponding graph (=copied and saved to a file together with the graph), by including them in the **graph’s dictionary-like attributes**\n", " - `vertex_properties` alias `vp`\n", " - `edge_properties` alias `ep`\n", " - `graph_properties` alias `gp`" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "g = gt.Graph(directed=False)\n", "edges = g.add_edge_list([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 0)])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Graph attributes" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# verbose\n", "g.graph_properties['background_color'] = g.new_graph_property(value_type='string', val='gray')\n", "\n", "# shorter\n", "g.gp['node_shape'] = g.new_gp('string', 'rectangle')\n", "g.gp['node_label_color'] = g.new_gp('string', 'white')\n", "g.gp['edge_opacity'] = g.new_gp('float', 0.3)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Node attributes" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Nodes\n", "num_nodes = len(list(g.vertices()))\n", "g.vertex_properties['size'] = g.new_vertex_property(value_type='int', vals=[5 + i*5 for i in range(num_nodes)])\n", "g.vp['color'] = g.new_vp('string', ['lightblue'] * num_nodes)\n", "\n", "# Node\n", "g.vertex_properties['shape'] = g.new_vertex_property('string') # verbose\n", "g.vp['opacity'] = g.new_vp('float') # shorter\n", "g.vp['color'][3] = 'darkred'\n", "g.vp['shape'][3] = 'hexagon'\n", "g.vp['size'][3] = 40\n", "g.vp['opacity'][3] = 0.3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Edge attributes" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Edges\n", "num_edges = len(list(g.edges()))\n", "g.edge_properties['size'] = g.new_edge_property(value_type='int', vals=[1 + i for i in range(num_edges)])\n", "g.ep['color'] = g.new_ep('string', ['lightgreen'] * num_edges)\n", "\n", "# Edge\n", "e34 = g.edge(3, 4)\n", "g.edge_properties['size'][e34] = 1\n", "g.ep['color'][e34] = 'darkred'" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "gv.d3(g, graph_height=200, use_centering_force=False)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2) Algorithmic graph creation\n", "\n", "- [Docs: graph_tool.generation - Random graph generation](https://graph-tool.skewed.de/static/doc/generation.html#graph_tool.generation)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "n = 20" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "g = gt.generation.price_network(n)\n", "g = gt.generation.lattice([10, 20], periodic=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3) Graph loading from an internal collection" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Neural network of the C. elegans worm\n", "g = gt.collection.data['celegansneural']" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 4) Graph import and export\n", "\n", "#### Import\n", "\n", "- [API: load_graph](https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.load_graph)\n", "- [API: load](https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.load)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "filepath = os.path.join('data', 'graph-tool_graph.xml.gz')\n", "g = gt.load_graph(filepath)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Export\n", "\n", "- [API: save](https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.save)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "filepath = os.path.join('data', 'graph-tool_graph.xml.gz')\n", "g.save(filepath)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Basic graph inspection\n", "\n", "### 1) Graph and its properties" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "v0 = g.vertex(0)\n", "g.vertex_index[v0]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2) Nodes and their properties" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": true }, "outputs": [], "source": [ "for node in g.vertices():\n", " node_id = node\n", " #attributes = node.attributes()\n", " #degree = node.degree()\n", " print('Type:', type(node))#, type(attributes))\n", " print('Id:', node_id)\n", " #print('Attributes:', attributes)\n", " #print('Degree:', degree)\n", " break" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3) Edges and their properties" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for edge in g.edges():\n", " source = edge.source()\n", " target = edge.target()\n", " #attributes = edge.attributes()\n", " print('Type:', type(edge), type(source), type(target))#, type(attributes))\n", " print('Source:', source)\n", " print('Target:', target)\n", " print(str(source))\n", " #print('Attributes:', )\n", " break" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Calculating graph measures and metrics\n", "\n", "### 1) Quantitative measures\n", "\n", "#### Centrality\n", "\n", "- [API: graph_tool.centrality](https://graph-tool.skewed.de/static/doc/centrality.html): Centrality measures" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# PageRank of each vertex\n", "node_property_map = gt.centrality.pagerank(g)\n", "\n", "# closeness centrality for each vertex\n", "node_property_map = gt.centrality.closeness(g)\n", "\n", "# Katz centrality of each vertex in the graph\n", "node_property_map = gt.centrality.katz(g)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Eigenvector centrality of each vertex in the graph, as well as the largest eigenvalue\n", "largest_eigenvalue, node_property_map = gt.centrality.eigenvector(g)\n", "\n", "# Authority and hub centralities of each vertex in the graph\n", "largest_eigenvalue, node_property_map1, node_property_map2 = gt.centrality.hits(g)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Betweenness centrality for each vertex and edge\n", "node_property_map_betweenness, edge_property_map = gt.centrality.betweenness(g)\n", "\n", "# central point dominance of the graph, given the betweenness centrality of each vertex\n", "scalar = gt.centrality.central_point_dominance(g, node_property_map_betweenness)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "trust_map = g.new_edge_property('double')\n", "\n", "# Eigentrust centrality of each vertex in the graph\n", "node_property_map_matrix = gt.centrality.eigentrust(g, trust_map)\n", "\n", "# Pervasive trust transitivity between chosen (or all) vertices in the graph\n", "node_property_map_matrix = gt.centrality.trust_transitivity(g, trust_map)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2) Structure inference\n", "\n", "#### Community detection and graph partitioning\n", "\n", "- [Cookbook: Inferring modular network structure](https://graph-tool.skewed.de/static/doc/demos/inference/inference.html)\n", "- [API: graph_tool.inference](https://graph-tool.skewed.de/static/doc/inference.html#): Statistical inference of generative network models" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "g = gt.collection.data['celegansneural']" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "state = gt.inference.minimize_blockmodel_dl(g)\n", "node_property_map = state.get_blocks()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "state = gt.inference.minimize_nested_blockmodel_dl(g)\n", "state.print_summary()\n", "levels = state.get_levels()\n", "node_property_map = levels[0].get_blocks()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "state = gt.inference.EMBlockState(g, B=3) # B is number of desired blocks\n", "node_property_map_expectations = state.get_vertex_marginals()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# TODO: more algorithms" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Minimum spanning tree\n", "\n", "- [API: min_spanning_tree](https://graph-tool.skewed.de/static/doc/topology.html#graph_tool.topology.min_spanning_tree)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "edge_map = gt.topology.min_spanning_tree(g)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Graph visualization\n", "\n", "- [API: graph_tool.draw](https://graph-tool.skewed.de/static/doc/draw.html): Graph drawing and layout\n", "\n", "### Static plots" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "gt.draw.graph_draw(g, vertex_text=g.vertex_index, vertex_font_size=14, output_size=(800, 800))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Dynamic animations" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# TODO" ] } ], "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.7.12" } }, "nbformat": 4, "nbformat_minor": 2 }