{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# NetworkX\n", "\n", "This Jupyter notebook provides an example of using the Python packages [gravis](https://pypi.org/project/gravis) and [NetworkX](https://networkx.org). The .ipynb file can be found [here](https://github.com/robert-haas/gravis/tree/master/examples).\n", "\n", "## References\n", "\n", "- [NetworkX website](https://networkx.org)\n", " - [Documentation](https://networkx.org/documentation/stable/)\n", " - [Tutorial](https://networkx.org/documentation/stable/tutorial.html)\n", " - [API reference](https://networkx.org/documentation/stable/reference/index.html)\n", " - [Examples](https://networkx.org/documentation/stable/auto_examples/index.html)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Installation\n", "\n", "- With [pip](https://pypi.org/project/networkx/): `pip install networkx`\n", "- With [conda](https://anaconda.org/search?q=networkx): `conda install networkx`" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Import" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import os \n", "\n", "import networkx as nx\n", "import networkx.algorithms.community\n", "\n", "import matplotlib.pyplot as plt\n", "import gravis as gv" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Quick start\n", "\n", "### Example 1\n", "\n", "- Uses a graph stored in the package\n", "- Visualizes edge weights as line widths" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Create a graph from a stored example\n", "graph = nx.les_miserables_graph()\n", "\n", "# It comes with an edge property named \"weight\" which can be used as edge size\n", "gv.d3(graph, edge_size_data_source='weight', use_edge_size_normalization=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 2\n", "\n", "- Uses a graph generator to create a random graph\n", "- Calculates quantitative measures (centralities) for nodes and edges\n", "- Infers structure (community detection) in the graph\n", "- Depicts the information by various visual elements" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def assign_properties(g):\n", " # Centrality calculation\n", " node_centralities = nx.eigenvector_centrality(g)\n", " edge_centralities = nx.edge_betweenness_centrality(g)\n", "\n", " # Community detection\n", " communities = nx.algorithms.community.greedy_modularity_communities(g)\n", " \n", " # Graph properties\n", " g.graph['node_border_size'] = 1.5\n", " g.graph['node_border_color'] = 'white'\n", " g.graph['edge_opacity'] = 0.9\n", "\n", " # Node properties: Size by centrality, shape by size, color by community\n", " colors = ['red', 'blue', 'green', 'orange', 'pink', 'brown', 'yellow', 'cyan', 'magenta', 'violet']\n", " for node_id in g.nodes:\n", " node = g.nodes[node_id]\n", " node['size'] = 10 + node_centralities[node_id] * 100\n", " node['shape'] = 'rectangle' if node['size'] > 30 else 'circle'\n", " for community_counter, community_members in enumerate(communities):\n", " if node_id in community_members:\n", " break\n", " node['color'] = colors[community_counter % len(colors)]\n", "\n", " # Edge properties: Size by centrality, color by community (within=community color, between=black)\n", " for edge_id in g.edges:\n", " edge = g.edges[edge_id]\n", " source_node = g.nodes[edge_id[0]]\n", " target_node = g.nodes[edge_id[1]]\n", " edge['size'] = edge_centralities[edge_id] * 100\n", " edge['color'] = source_node['color'] if source_node['color'] == target_node['color'] else 'black'\n", "\n", "\n", "# Create a graph with a generator function\n", "g = nx.powerlaw_cluster_graph(n=250, m=2, p=0.9)\n", "\n", "# Assign node and edge properties\n", "assign_properties(g)\n", "\n", "# Plot it\n", "gv.d3(g, zoom_factor=0.2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Graph construction\n", "\n", "- API reference: [Graph creation](https://networkx.github.io/documentation/stable/reference/introduction.html#graph-creation)\n", "\n", "### 1) Manual graph construction\n", "\n", "- Tutorial: [Creating a graph](https://networkx.github.io/documentation/stable/tutorial.html#creating-a-graph)\n", "- API reference\n", " - [Introduction: Basic graph types](https://networkx.github.io/documentation/stable/reference/introduction.html#networkx-basics)\n", " - [Graph types](https://networkx.github.io/documentation/stable/reference/classes/index.html)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### 1.a) Graph\n", "\n", "undirected, with self-loops, without parallel edges, with attributes\n", "\n", "- [Graph](https://networkx.github.io/documentation/stable/reference/classes/graph.html)\n", " - [add_node](https://networkx.github.io/documentation/stable/reference/classes/generated/networkx.Graph.add_node.html#networkx.Graph.add_node)\n", " - [add_nodes_from](https://networkx.github.io/documentation/stable/reference/classes/generated/networkx.Graph.add_nodes_from.html#networkx.Graph.add_nodes_from)\n", " - [add_edge](https://networkx.github.io/documentation/stable/reference/classes/generated/networkx.Graph.add_edge.html#networkx.Graph.add_edge)\n", " - [add_edges_from](https://networkx.github.io/documentation/stable/reference/classes/generated/networkx.Graph.add_edges_from.html#networkx.Graph.add_edges_from)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "ug = nx.Graph()\n", "\n", "\n", "# Node with automatic id\n", "# ~ Not supported ~\n", "\n", "# Node with user-defined id (=any hashable Python object except None)\n", "ug.add_node('a')\n", "\n", "# Node + attribute\n", "ug.add_node('b', size=20)\n", "\n", "# Node + attributes\n", "ug.add_node('c', size=30, color='orange')\n", "\n", "\n", "# Nodes\n", "ug.add_nodes_from(['d', 'e']) # argument: iterable of user-defined ids\n", "\n", "# Nodes + attributes\n", "ug.add_nodes_from([\n", " ('f', {'size': 10, 'color': 'red'}),\n", " ('g', {'size': 15, 'color': 'blue'}),\n", " ('h', {'size': 20, 'color': 'green'})\n", "])\n", "\n", "\n", "# Edge (nodes may already exist but do not need to)\n", "ug.add_edge('a', 'b')\n", "\n", "# Edge + attribute\n", "ug.add_edge('b', 'c', size=3)\n", "\n", "# Edge + attributes\n", "ug.add_edge('c', 'd', size=4, color='orange')\n", "\n", "\n", "# Edges\n", "ug.add_edges_from([('d', 'e'), ('e', 'f')])\n", "\n", "# Edges + attributes\n", "ug.add_edges_from([\n", " ('f', 'g', {'size': 2.2, 'color': 'red'}),\n", " ('g', 'h', {'size': 4.4, 'color': 'blue'}),\n", " ('h', 'a', {'size': 4.4, 'color': 'green'}),\n", " ('a', 'a'),\n", "])\n", "\n", "\n", "gv.d3(ug, graph_height=200)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### 1.b) DiGraph\n", "\n", "directed, with self-loops, without parallel edges, with attributes\n", "\n", "- [DiGraph](https://networkx.github.io/documentation/stable/reference/classes/digraph.html)\n", " - [add_node](https://networkx.github.io/documentation/stable/reference/classes/generated/networkx.DiGraph.add_node.html#networkx.DiGraph.add_node)\n", " - [add_nodes_from](https://networkx.github.io/documentation/stable/reference/classes/generated/networkx.DiGraph.add_nodes_from.html#networkx.DiGraph.add_nodes_from)\n", " - [add_edge](https://networkx.github.io/documentation/stable/reference/classes/generated/networkx.DiGraph.add_edge.html#networkx.DiGraph.add_edge)\n", " - [add_edges_from](https://networkx.github.io/documentation/stable/reference/classes/generated/networkx.DiGraph.add_edges_from.html#networkx.DiGraph.add_edges_from)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "dg = nx.DiGraph(ug)\n", "\n", "gv.d3(dg, graph_height=200)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### 1.c) MultiGraph\n", "\n", "undirected, with self-loops, with parallel edges, with attributes\n", "\n", "- [MultiGraph](https://networkx.github.io/documentation/stable/reference/classes/multigraph.html)\n", " - [add_node](https://networkx.github.io/documentation/stable/reference/classes/generated/networkx.MultiGraph.add_node.html#networkx.MultiGraph.add_node)\n", " - [add_nodes_from](https://networkx.github.io/documentation/stable/reference/classes/generated/networkx.MultiGraph.add_nodes_from.html#networkx.MultiGraph.add_nodes_from)\n", " - [add_edge](https://networkx.github.io/documentation/stable/reference/classes/generated/networkx.MultiGraph.add_edge.html#networkx.MultiGraph.add_edge)\n", " - [add_edges_from](https://networkx.github.io/documentation/stable/reference/classes/generated/networkx.MultiGraph.add_edges_from.html#networkx.MultiGraph.add_edges_from)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "umg = nx.MultiGraph()\n", "\n", "\n", "# Nodes\n", "umg.add_nodes_from([\n", " ('a'),\n", " ('b', {'size': 20}),\n", " ('c', {'size': 30, 'color': 'orange'}),\n", " ('d'),\n", " ('e'),\n", " ('f', {'size': 10, 'color': 'red'}),\n", " ('g', {'size': 15, 'color': 'blue'}),\n", " ('h', {'size': 20, 'color': 'green'}),\n", "])\n", "\n", "\n", "# Edges\n", "umg.add_edges_from([\n", " ('a', 'b'),\n", " ('b', 'c', {'size': 3}),\n", " ('c', 'd', {'size': 4, 'color': 'orange'}),\n", " ('d', 'e'),\n", " ('e', 'f'),\n", " ('f', 'g', {'size': 2.2, 'color': 'red'}),\n", " ('g', 'h', {'size': 4.4, 'color': 'blue'}),\n", " ('h', 'a', {'size': 4.4, 'color': 'green'}),\n", " ('a', 'a'),\n", " ('a', 'a'),\n", " ('a', 'b'),\n", " ('b', 'a'),\n", "])\n", "\n", "\n", "gv.d3(umg, graph_height=200, edge_curvature=0.8)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### 1.d) MultiDiGraph\n", "\n", "directed, with self-loops, with parallel edges, with attributes\n", "\n", "- [MultiDiGraph](https://networkx.github.io/documentation/stable/reference/classes/multidigraph.html)\n", " - [add_node](https://networkx.github.io/documentation/stable/reference/classes/generated/networkx.MultiDiGraph.add_node.html#networkx.MultiDiGraph.add_node)\n", " - [add_nodes_from](https://networkx.github.io/documentation/stable/reference/classes/generated/networkx.MultiDiGraph.add_nodes_from.html#networkx.MultiDiGraph.add_nodes_from)\n", " - [add_edge](https://networkx.github.io/documentation/stable/reference/classes/generated/networkx.MultiDiGraph.add_edge.html#networkx.MultiDiGraph.add_edge)\n", " - [add_edges_from](https://networkx.github.io/documentation/stable/reference/classes/generated/networkx.MultiDiGraph.add_edges_from.html#networkx.MultiDiGraph.add_edges_from)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "dmg = nx.MultiDiGraph(umg)\n", "\n", "gv.d3(dmg, graph_height=200, edge_curvature=0.8)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Assign attributes to a created graph" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "g = nx.Graph()\n", "g.add_edges_from([(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": [ "g.graph['background_color'] = 'gray'\n", "g.graph['node_shape'] = 'rectangle'\n", "g.graph['node_label_color'] = 'white'\n", "g.graph['edge_opacity'] = 0.3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Node attributes" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Nodes\n", "for i, node_id in enumerate(g.nodes):\n", " g.nodes[node_id]['size'] = 5 + i*5\n", " g.nodes[node_id]['color'] = 'lightblue'\n", "\n", "# Node\n", "g.nodes[3]['color'] = 'darkred'\n", "g.nodes[3]['shape'] = 'hexagon'\n", "g.nodes[3]['size'] = 40\n", "g.nodes[3]['opacity'] = 0.3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Edge attributes" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Edges\n", "for i, edge_id in enumerate(g.edges):\n", " g.edges[edge_id]['size'] = 1 + i\n", " g.edges[edge_id]['color'] = 'lightgreen'\n", "\n", "# Edge\n", "g.edges[(3, 4)]['size'] = 1\n", "g.edges[(3, 4)]['color'] = 'darkred'" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "gv.d3(g, graph_height=200)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2) Algorithmic graph construction\n", "\n", "- Tutorial: [Graph generators and operations](https://networkx.github.io/documentation/stable/tutorial.html#graph-generators-and-graph-operations)\n", "- API reference: [Graph generators](https://networkx.github.io/documentation/stable/reference/generators.html)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "n = 8\n", "e = 12" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Generators for classic graphs\n", "g = nx.complete_graph(n)\n", "g = nx.complete_bipartite_graph(n, n)\n", "g = nx.barbell_graph(n, n)\n", "g = nx.lollipop_graph(n, n)\n", "\n", "# Stochastic graph generators\n", "g = nx.erdos_renyi_graph(100, 0.15)\n", "g = nx.watts_strogatz_graph(30, 3, 0.1)\n", "g = nx.barabasi_albert_graph(100, 5)\n", "g = nx.random_lobster(100, 0.9, 0.9)\n", "\n", "# Nice for demonstrating community structures\n", "g = nx.dorogovtsev_goltsev_mendes_graph(n)\n", "g = nx.connected_caveman_graph(l=5, k=6)\n", "\n", "# Nice for demonstrating forces (and node degree centrality)\n", "g = nx.star_graph(n)\n", "g = nx.wheel_graph(n)\n", "g = nx.turan_graph(n, 2)\n", "g = nx.complete_graph(n)\n", "\n", "# Nice for demonstrating edge betweenness\n", "g = nx.barbell_graph(n, 1)\n", "g = nx.hexagonal_lattice_graph(3, 4)\n", "g = nx.triangular_lattice_graph(4, 8)\n", "\n", "# Random graphs\n", "g = nx.erdos_renyi_graph(n=n, p=0.02)\n", "g = nx.fast_gnp_random_graph(n=n, p=2/1000)\n", "g = nx.newman_watts_strogatz_graph(n=n, k=5, p=0.05)\n", "g = nx.watts_strogatz_graph(n=n, k=5, p=0.3)\n", "g = nx.barabasi_albert_graph(n=n, m=2)\n", "g = nx.dual_barabasi_albert_graph(n=n, m1=1, m2=2, p=0.6)\n", "g = nx.powerlaw_cluster_graph(n=n, m=2, p=0.7)\n", "g = nx.random_lobster(n=n, p1=0.95, p2=0.75)\n", "g = nx.duplication_divergence_graph(n=n, p=0.4)\n", "g = nx.havel_hakimi_graph(deg_sequence=[6]*10+[4]*10)\n", "\n", "# Geometrically nice layouts (reminding of soap bubble physics)\n", "g = nx.dodecahedral_graph()\n", "g = nx.moebius_kantor_graph()\n", "g = nx.circular_ladder_graph(n)\n", "g = nx.circulant_graph(n, [2, 1])\n", "g = nx.lollipop_graph(n, 5)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Directed\n", "g = nx.directed_havel_hakimi_graph(in_deg_sequence=[2]*20+[3]*10+[2]*10, out_deg_sequence=[2]*30+[3]*10)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3) Graph loading from an internal collection\n", "\n", "- API reference: [Graph generators](https://networkx.github.io/documentation/stable/reference/generators.html)\n", "\n", "- Book: [An atlas of graphs](https://global.oup.com/academic/product/an-atlas-of-graphs-9780198526506?cc=at&lang=en&) (\"Graph atlas\")" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Graph atlas\n", "g = nx.graph_atlas(986)\n", "\n", "# Classical small graphs\n", "g = nx.cubical_graph()\n", "g = nx.diamond_graph()\n", "g = nx.dodecahedral_graph()\n", "g = nx.icosahedral_graph()\n", "g = nx.octahedral_graph()\n", "g = nx.tetrahedral_graph()\n", "g = nx.truncated_cube_graph()\n", "g = nx.truncated_tetrahedron_graph()\n", "\n", "g = nx.bull_graph()\n", "g = nx.chvatal_graph()\n", "g = nx.desargues_graph()\n", "g = nx.frucht_graph()\n", "g = nx.heawood_graph()\n", "g = nx.hoffman_singleton_graph()\n", "g = nx.house_graph()\n", "g = nx.house_x_graph()\n", "g = nx.krackhardt_kite_graph()\n", "g = nx.moebius_kantor_graph()\n", "g = nx.pappus_graph()\n", "g = nx.petersen_graph()\n", "g = nx.sedgewick_maze_graph()\n", "g = nx.tutte_graph()\n", "\n", "# Social networks\n", "g = nx.les_miserables_graph()\n", "g = nx.karate_club_graph()\n", "g = nx.davis_southern_women_graph()\n", "g = nx.florentine_families_graph()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 4) Graph import and export\n", "\n", "- [Reading and writing graphs](https://networkx.github.io/documentation/stable/reference/readwrite/index.html)\n", "\n", "#### Import" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "filepath = os.path.join('data', 'networkx_graph.gml')\n", "g = nx.read_gml(filepath)\n", "\n", "# methods for other formats\n", "nx.read_adjlist\n", "nx.read_multiline_adjlist\n", "nx.read_edgelist\n", "nx.read_gexf\n", "nx.read_gpickle\n", "nx.read_graphml\n", "nx.json_graph.adjacency_graph\n", "nx.json_graph.cytoscape_graph\n", "nx.json_graph.node_link_graph\n", "nx.json_graph.jit_graph\n", "nx.json_graph.tree_graph\n", "nx.read_leda\n", "nx.read_pajek\n", "nx.read_shp" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Export" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "filepath = os.path.join('data', 'networkx_graph.gml')\n", "nx.write_gml(g, filepath)\n", "\n", "# methods for other formats\n", "nx.write_adjlist\n", "nx.write_multiline_adjlist\n", "nx.write_edgelist\n", "nx.write_gexf\n", "nx.write_gpickle\n", "nx.write_graphml\n", "nx.write_pajek\n", "nx.write_shp" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 5) Graph modification that results in a new graph\n", "\n", "- API reference: [Operators](https://networkx.github.io/documentation/stable/reference/algorithms/operators.html)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Basic graph inspection\n", "\n", "- API reference: [Graph reporting](https://networkx.github.io/documentation/stable/reference/introduction.html#graph-reporting)\n", "\n", "### 1) Graph and its properties" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "g = nx.les_miserables_graph()\n", "\n", "print('Type:', type(g))\n", "print('Directed:', g.is_directed())\n", "print('Number of nodes:', g.number_of_nodes())\n", "print('Number of edges:', g.number_of_edges())\n", "print('Attributes:', g.graph)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2) Nodes and their properties" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for node in g.nodes:\n", " attributes = g.nodes[node]\n", " degree = g.degree(node)\n", " print('Type:', type(node), type(attributes))\n", " print('Id:', node)\n", " print('Attributes:', attributes)\n", " print('Degree:', degree)\n", " break\n", "\n", "print()\n", "for node, attributes in g.nodes.data():\n", " print('Type:', type(node), type(attributes))\n", " print('Id:', node)\n", " print('Attributes:', attributes)\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, target = edge\n", " attributes = g.edges[edge]\n", " print('Type:', type(source), type(target), type(attributes))\n", " print('Source:', source)\n", " print('Target:', target)\n", " print('Attributes:', )\n", " break\n", "\n", "print()\n", "for source, target, attributes in g.edges.data():\n", " print('Type:', type(source), type(target), type(attributes))\n", " print('Source:', source)\n", " print('Target:', target)\n", " print('Attributes:', attributes)\n", " break" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Calculating graph measures and metrics\n", "\n", "- Tutorial: [Analyzing graphs](https://networkx.github.io/documentation/stable/tutorial.html#analyzing-graphs)\n", "- API reference: [Algorithms](https://networkx.github.io/documentation/stable/reference/algorithms/index.html)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Centrality\n", "\n", "- API reference\n", " - [Centrality](https://networkx.github.io/documentation/stable/reference/algorithms/centrality.html)\n", " - [Link analysis](https://networkx.github.io/documentation/stable/reference/algorithms/link_analysis.html)\n", " - [Vitality](https://networkx.github.io/documentation/stable/reference/algorithms/vitality.html)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "g = nx.barbell_graph(8, 1)\n", "dg = nx.directed_havel_hakimi_graph([1, 1, 2, 3, 3], [1, 1, 2, 3, 3])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Graph measures: single scalar value" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "scalar = nx.estrada_index(g)\n", "scalar = nx.global_reaching_centrality(g)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Node measures: dict (node -> value)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "node_dict = nx.degree_centrality(g)\n", "node_dict = nx.in_degree_centrality(dg)\n", "node_dict = nx.out_degree_centrality(dg)\n", "\n", "node_dict = nx.eigenvector_centrality(g)\n", "node_dict = nx.eigenvector_centrality_numpy(g)\n", "\n", "node_dict = nx.katz_centrality(g)\n", "node_dict = nx.katz_centrality_numpy(g)\n", "\n", "node_dict = nx.closeness_centrality(g)\n", "#nx.incremental_closeness_centrality(g)\n", "\n", "node_dict = nx.current_flow_closeness_centrality(g)\n", "node_dict = nx.information_centrality(g)\n", "\n", "node_dict = nx.betweenness_centrality(g)\n", "\n", "node_dict = nx.current_flow_betweenness_centrality(g)\n", "node_dict = nx.approximate_current_flow_betweenness_centrality(g)\n", "\n", "node_dict = nx.communicability_betweenness_centrality(g)\n", "\n", "node_dict = nx.load_centrality(g)\n", "\n", "\n", "node_dict = nx.subgraph_centrality(g)\n", "node_dict = nx.subgraph_centrality_exp(g)\n", "\n", "node_dict = nx.harmonic_centrality(g)\n", "\n", "#nx.percolation_centrality(g)\n", "node_dict = nx.second_order_centrality(g)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "node_dict_dict = nx.dispersion(g)\n", "node_list = nx.voterank(g)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Edge measures: dict (edge -> value)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "edge_dict = nx.edge_betweenness_centrality(g)\n", "edge_dict = nx.edge_current_flow_betweenness_centrality(g)\n", "edge_dict = nx.edge_load_centrality(g)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "node_dict = nx.pagerank(g)\n", "node_np_matrix = nx.google_matrix(g)\n", "\n", "node_tuple_dict = nx.hits(g)\n", "node_np_matrix = nx.hub_matrix(g)\n", "node_np_matrix = nx.authority_matrix(g)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "node_dict = nx.closeness_vitality(g) # value can be -inf" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Groups of nodes" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Cliques\n", "\n", "- API reference: [Clique](https://networkx.github.io/documentation/stable/reference/algorithms/clique.html)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# TODO" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Cores\n", "\n", "- API reference: [Cores](https://networkx.github.io/documentation/stable/reference/algorithms/core.html)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# TODO" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Components\n", "\n", "- API reference\n", " - [Component](https://networkx.github.io/documentation/stable/reference/algorithms/component.html)\n", " - [Connectivity](https://networkx.github.io/documentation/stable/reference/algorithms/connectivity.html)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# TODO" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Communities\n", "\n", "- API reference\n", " - [Communities](https://networkx.github.io/documentation/stable/reference/algorithms/community.html)\n", " - [Linear algebra](https://networkx.github.io/documentation/stable/reference/linalg.html)\n", " - Modularity matrix\n", " - Spectrum" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "g = nx.barbell_graph(8, 1)\n", "\n", "# TODO" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Partitions via centrality measures\n", "- Girvan–Newman method" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "generator = networkx.algorithms.community.girvan_newman(g)\n", "result1 = next(generator)\n", "result2 = next(generator)\n", "result3 = next(generator)\n", "\n", "print(result1)\n", "print(result2)\n", "print(result3)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for node_id in g.nodes:\n", " g.nodes[node_id][\"color\"] = 'red' if node_id in result2[0] else 'green' if node_id in result2[1] else 'blue'\n", "\n", "gv.d3(g, use_y_positioning_force=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- Clauset-Newman-Moore greedy modularity maximization" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "result = networkx.algorithms.community.greedy_modularity_communities(g)\n", "result" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Bisection: Partition a graph into two blocks\n", "\n", "- Kernighan–Lin algorithm" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "result = networkx.algorithms.community.kernighan_lin_bisection(g)\n", "result" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Find k-clique communities\n", "\n", "- percolation method" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "iterator = networkx.algorithms.community.k_clique_communities(g, 3)\n", "result = list(iterator)\n", "result" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Label propagation\n", "\n", "- Asynchronous label propagation" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# TODO: networkx.algorithms.community.asyn_lpa_communities(g)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "generator = networkx.algorithms.community.label_propagation_communities(g)\n", "result = list(generator)\n", "result" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Fluid Communities\n", "\n", "- Asynchronous Fluid Communities algorithm" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "iterator = networkx.algorithms.community.asyn_fluidc(g, k=3)\n", "result = list(iterator)\n", "result" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for node_id in g.nodes:\n", " g.nodes[node_id][\"color\"] = 'red' if node_id in result[0] else 'green' if node_id in result[1] else 'blue'\n", "\n", "gv.d3(g, use_y_positioning_force=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Validation of partitions" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "networkx.algorithms.community.is_partition(g, result3)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Quality measure of partitions" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "networkx.algorithms.community.coverage(g, result3)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "networkx.algorithms.community.performance(g, result3)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "nx.connected_components(g)\n", "nx.clustering(g)\n", "nx.all_pairs_shortest_path(g)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Paths and distances\n", "\n", "- API reference\n", " - [Cycles](https://networkx.github.io/documentation/stable/reference/algorithms/cycles.html)\n", " - [Simple paths](https://networkx.github.io/documentation/stable/reference/algorithms/simple_paths.html)\n", " - [Shortest paths](https://networkx.github.io/documentation/stable/reference/algorithms/shortest_paths.html)\n", " - [Voronoi cells](https://networkx.github.io/documentation/stable/reference/algorithms/voronoi.html)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# TODO" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Global properties\n", "\n", "- API reference\n", " - [Assortativity](https://networkx.github.io/documentation/stable/reference/algorithms/assortativity.html)\n", " - [Clustering](https://networkx.github.io/documentation/stable/reference/algorithms/clustering.html)\n", " - [Communicability](https://networkx.github.io/documentation/stable/reference/algorithms/communicability_alg.html)\n", " - [Distance Measures](https://networkx.github.io/documentation/stable/reference/algorithms/distance_measures.html)\n", " - [Non-randomness](https://networkx.github.io/documentation/stable/reference/algorithms/non_randomness.html)\n", " - [Reciprocity](https://networkx.github.io/documentation/stable/reference/algorithms/reciprocity.html)\n", " - [Rich club](https://networkx.github.io/documentation/stable/reference/algorithms/rich_club.html)\n", " - [Small-world](https://networkx.github.io/documentation/stable/reference/algorithms/smallworld.html)\n", " - [s metric](https://networkx.github.io/documentation/stable/reference/algorithms/smetric.html)\n", " - [Tree](https://networkx.github.io/documentation/stable/reference/algorithms/tree.html)\n", " - [Triadic census](https://networkx.github.io/documentation/stable/reference/algorithms/triads.html)\n", " - [Wiener index](https://networkx.github.io/documentation/stable/reference/algorithms/wiener.html)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# TODO" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Graph visualization\n", "\n", "- Tutorial: [Drawing graphs](https://networkx.github.io/documentation/stable/tutorial.html#drawing-graphs)\n", "- API reference\n", " - [Introduction: Drawing](https://networkx.github.io/documentation/stable/reference/introduction.html#drawing)\n", " - [Drawing](https://networkx.github.io/documentation/stable/reference/drawing.html)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Layout calculation\n", "\n", "- API reference: [Graph layout](https://networkx.github.io/documentation/stable/reference/drawing.html#module-networkx.drawing.layout)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "graph = nx.les_miserables_graph()\n", "\n", "layout = nx.circular_layout(graph, scale=500)\n", "#layout = nx.kamada_kawai_layout(graph, scale=500)\n", "#layout = nx.spring_layout(graph, scale=500)\n", "\n", "for node_id, (x, y) in layout.items():\n", " node = graph.nodes[node_id]\n", " node['x'] = x\n", " node['y'] = y\n", "\n", "gv.d3(graph, layout_algorithm_active=False, show_menu=False)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Plotting" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "g = nx.petersen_graph()\n", "\n", "plt.subplot(121)\n", "nx.draw(g, with_labels=True, font_weight='bold', font_color='white')\n", "\n", "plt.subplot(122)\n", "nx.draw_shell(g, nlist=[range(5, 10), range(5)], with_labels=True, font_weight='bold', font_color='white')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Further topics\n", "\n", "- [Covering](https://networkx.github.io/documentation/stable/reference/algorithms/covering.html)\n", "- [Cut](https://networkx.github.io/documentation/stable/reference/algorithms/cuts.html)\n", "- [Flow](https://networkx.github.io/documentation/stable/reference/algorithms/flow.html)\n", "- [Graph traversal](https://networkx.github.io/documentation/stable/reference/algorithms/traversal.html)\n", "- Graph comparison\n", " - [Matching](https://networkx.github.io/documentation/stable/reference/algorithms/matching.html)\n", " - [Similarity](https://networkx.github.io/documentation/stable/reference/algorithms/similarity.html)" ] } ], "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 }