{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# NetworKit\n", "\n", "This Jupyter notebook provides an example of using the Python packages [gravis](https://pypi.org/project/gravis) and [NetworKit](https://networkit.github.io). The .ipynb file can be found [here](https://github.com/robert-haas/gravis/tree/master/examples).\n", "\n", "## References\n", "\n", "- [NetworKit website](https://networkit.github.io)\n", " \n", " - [Get started](https://networkit.github.io/get_started.html)\n", " - [Notebooks](https://github.com/networkit/networkit/tree/master/notebooks) (usage examples)\n", " - [User guide](https://github.com/networkit/networkit/blob/master/notebooks/User-Guide.ipynb)\n", " - [Features](https://networkit.github.io/features.html)\n", " - Network Analytics\n", " - Community Detection\n", " - Graph Generators\n", " - [Datasets](https://networkit.github.io/datasets.html)\n", " - [Documentation](https://networkit.github.io/dev-docs/index.html)\n", " - [API reference](https://networkit.github.io/dev-docs/python_api/modules.html) for Python" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Installation\n", "\n", "- With [pip](https://pypi.org/project/networkit/): `pip install networkit`\n", "- With [conda](https://anaconda.org/search?q=networkit): `conda install -c conda-forge networkit`" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Import" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import os\n", "import warnings\n", "warnings.simplefilter(\"ignore\") # ignore some deprecation warnings" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import networkit as nk\n", "\n", "import gravis as gv" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Quick start\n", "\n", "- Notebook: [User guide](https://github.com/networkit/networkit/blob/master/notebooks/User-Guide.ipynb)\n", "\n", "### Example 1" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def calculate_properties(g):\n", " # Centrality calculation\n", " node_centralities = nk.centrality.PageRank(g).run().scores()\n", " g.indexEdges()\n", " edge_centralities = nk.centrality.Betweenness(g, computeEdgeCentrality=True, normalized=True).run().edgeScores()\n", " \n", " # Community detection\n", " \n", " \n", " # Graph properties\n", " graph_metadata = {'edge_opacity': 0.5}\n", "\n", " # Node properties: Size by centrality, color by community\n", " node_metadata = {node_id: {'size': 5 + val*2000} for node_id, val in enumerate(node_centralities)}\n", "\n", " # Edge properties: Size by centrality, color by community (within=community color, between=black)\n", " edges = []\n", " g.forEdges(lambda s, t, ea, eb: edges.append('({}, {})'.format(s, t)))\n", " edge_metadata = {edge_id: {'size': 0.5 + val*50} for edge_id, val in zip(edges, edge_centralities)}\n", " \n", " # Properties can not be stored in a NetworKit graph, so they are collected in a list instead\n", " data = [g, graph_metadata, node_metadata, edge_metadata]\n", " return data\n", "\n", "\n", "# Create a graph with a generator function\n", "g = nk.generators.HyperbolicGenerator(250).generate()\n", "\n", "# Calculate properties (not stored in graph!)\n", "data = calculate_properties(g)\n", "\n", "# Plot it\n", "gv.d3(data, zoom_factor=0.2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Graph construction\n", "\n", "### 1) Manual graph construction\n", "\n", "- API reference\n", " - [Graph](https://networkit.github.io/dev-docs/python_api/networkit.html#networkit.Graph)\n", " - [addNode](https://networkit.github.io/dev-docs/python_api/networkit.html#networkit.Graph.addNode)\n", " - [addNodes](https://networkit.github.io/dev-docs/python_api/networkit.html#networkit.Graph.addNodes)\n", " - [addEdge](https://networkit.github.io/dev-docs/python_api/networkit.html#networkit.Graph.addEdge)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### 1.a) Graph (with directed=False)\n", "\n", "undirected, with self-loops, with parallel edges, without attributes" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "ug = nk.Graph(directed=False)\n", "\n", "\n", "# Node with automatic id (starts from 0)\n", "ug.addNode()\n", "ug.addNode()\n", "ug.addNode()\n", "ug.addNode()\n", "ug.addNode()\n", "ug.addNode()\n", "ug.addNode()\n", "ug.addNode()\n", "\n", "# Node with user-defined id\n", "# ~ Not supported ~\n", "\n", "\n", "# Nodes\n", "# ~ Not supported (despite addNodes in API reference) ~\n", "\n", "\n", "# Edge (nodes need to already exist)\n", "ug.addEdge(0, 1)\n", "ug.addEdge(1, 2)\n", "ug.addEdge(2, 3)\n", "ug.addEdge(3, 4)\n", "ug.addEdge(4, 5)\n", "ug.addEdge(5, 6)\n", "ug.addEdge(6, 7)\n", "ug.addEdge(7, 0)\n", "ug.addEdge(0, 0)\n", "ug.addEdge(0, 0)\n", "ug.addEdge(0, 1)\n", "ug.addEdge(0, 1)\n", "\n", "\n", "# Edges\n", "# ~ Not supported (despite addEdge description in API reference) ~\n", "\n", "\n", "gv.d3(ug, graph_height=200)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### 1.b) Graph (with directed=True)\n", "\n", "directed, with self-loops, with parallel edges, without attributes" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "dg = nk.Graph(directed=True)\n", "\n", "\n", "for node in ug.iterNodes():\n", " dg.addNode()\n", "\n", "for source, target in ug.iterEdges():\n", " dg.addEdge(source, target)\n", "\n", "\n", "gv.d3(dg, graph_height=200)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Assign attributes to a created graph\n", "\n", "- [StackOverflow](https://stackoverflow.com/questions/56012624/is-it-possible-to-create-a-property-graph-in-networkit): NetworKit does not allow to store any user-defined attributes within the graph object. Edges can have weights though." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2) Algorithmic graph construction\n", "\n", "- Notebook: [Generators](https://github.com/networkit/networkit/blob/master/notebooks/Generators.ipynb)\n", "- API reference: [networkit.generators](https://networkit.github.io/dev-docs/python_api/generators.html)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "num_nodes = 50\n", "num_clusters = 4\n", "\n", "generator = nk.generators.PowerlawDegreeSequence(minDeg=2, maxDeg=10, gamma=-2)\n", "generator.run()\n", "# degree_sequence = [1, 2, 3, 4, 5] * 10\n", "degree_sequence = generator.getDegreeSequence(num_nodes)\n", "\n", "\n", "# BTER graph generator implementation in FEASTPACK using GNU Octave\n", "# g = nk.generators.BTERReplicator(g).generate() # FileNotFoundError\n", "\n", "\n", "# Barabasi-Albert model (with faster Batagelj-Brandes algorithm)\n", "g = nk.generators.BarabasiAlbertGenerator(k=2, nMax=num_nodes, n0=0, batagelj=True).generate()\n", "\n", "\n", "# Chung-Lu model - arg1: expected degree sequence\n", "g = nk.generators.ChungLuGenerator(degree_sequence).generate()\n", "\n", "\n", "# A clustered random graph - arg1: number of nodes, arg2: number of edges,\n", "# arg3: intra-cluster edge probability, arg4: inter-cluster edge probability\n", "generator = nk.generators.ClusteredRandomGraphGenerator(n=num_nodes, k=num_clusters, pin=0.5, pout=0.02)\n", "c = generator.getCommunities() # generated ground truth clustering\n", "g = generator.generate()\n", "\n", "\n", "# EdgeSwitchingMarkovChainGenerator\n", "g = nk.generators.ConfigurationModelGenerator(degree_sequence).generate()\n", "\n", "\n", "# Dorogovtsev-Mendes model\n", "g = nk.generators.DorogovtsevMendesGenerator(num_nodes).generate()\n", "generator = nk.generators.DynamicDorogovtsevMendesGenerator(num_nodes)\n", "#generator.generate(2)\n", "#g = generator.getGraph()\n", "\n", "\n", "# Forest fire model\n", "generator = nk.generators.DynamicForestFireGenerator(p=0.1, directed=True, r=1.0)\n", "graph_event = generator.generate(1)\n", "# TODO: How to get a graph?\n", "\n", "\n", "# A dynamically growing path\n", "generator = nk.generators.DynamicPathGenerator(num_nodes)\n", "#g = generator.getGraph()\n", "# TODO\n", "\n", "\n", "# Edge-Switching Markov-Chain method (=random simple graph with exactly the given degree sequence)\n", "g = nk.generators.EdgeSwitchingMarkovChainGenerator(degree_sequence).generate()\n", "\n", "\n", "# Erdős–Rényi model G(n,p)\n", "g = nk.generators.ErdosRenyiGenerator(num_nodes, 0.1, directed=False).generate()\n", "\n", "\n", "# Havel-Hakimi model\n", "g = nk.generators.HavelHakimiGenerator(degree_sequence).generate()\n", "\n", "\n", "# Hyperbolic generator\n", "average_degree = 6\n", "power_law_exponent = 3\n", "temperature = 0\n", "g = nk.generators.HyperbolicGenerator(\n", " num_nodes, k=average_degree, gamma=power_law_exponent, T=temperature).generate()\n", "# graph_event_generator = nk.generators.DynamicHyperbolicGenerator(\n", "# num_nodes, average_degree, gamma=power_law_exponent, T=temperature)\n", "\n", "\n", "# LFR clustered graph generator\n", "generator = nk.generators.LFRGenerator(num_nodes)\n", "generator.setDegreeSequence(degree_sequence)\n", "generator.setCommunitySizeSequence(degree_sequence)\n", "generator.setMu(1.2)\n", "generator.run()\n", "gg = generator.getGraph()\n", "\n", "\n", "# Mocnik model (random spatial graphs)\n", "g = nk.generators.MocnikGeneratorBasic(dim=3, n=num_nodes, k=2.0).generate()\n", "g = nk.generators.MocnikGenerator(dim=3, n=num_nodes, k=2.0, weighted=True).generate()\n", "\n", "\n", "# resembles an assumed geometric distribution of nodes in a P2P network\n", "# graph_event_generator = nk.generators.DynamicPubWebGenerator(num_nodes)\n", "g = nk.generators.PubWebGenerator(\n", " num_nodes, numberOfDenseAreas=2, neighborhoodRadius=12.5, maxNumberOfNeighbors=8).generate()\n", "\n", "# regular ring lattice\n", "g = nk.generators.RegularRingLatticeGenerator(num_nodes, nNeighbors=2).generate()\n", "\n", "# R-MAT (recursive matrix) graphs\n", "g = nk.generators.RmatGenerator(scale=5, edgeFactor=2.2, a=0.3, b=0.3, c=0.2, d=0.2).generate()\n", "\n", "# Watts-Strogatz model (regular ring lattice, then edges are rewired)\n", "rewiring_probability = 0.1\n", "g = nk.generators.WattsStrogatzGenerator(nNodes=num_nodes, nNeighbors=2, p=rewiring_probability).generate()\n", "\n", "\n", "gv.d3(g)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3) Graph loading from an internal collection" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# TODO" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 4) Graph import and export\n", "\n", "- Notebook: [Graph IO](https://github.com/networkit/networkit/blob/master/notebooks/IONotebook.ipynb)\n", "\n", "#### Import" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "filepath = os.path.join('data', 'networkit_graph.gml')\n", "g = nk.graphio.readGraph(filepath, nk.Format.GML)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Export" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "filepath = os.path.join('data', 'networkit_graph.gml')\n", "nk.graphio.writeGraph(g, filepath, nk.Format.GML)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 5) Graph modification that results in a new graph\n", "\n", "- Notebooks\n", " - [Link prediction](https://github.com/networkit/networkit/blob/master/notebooks/LinkPrediction.ipynb)\n", " - [Randomization](https://github.com/networkit/networkit/blob/master/notebooks/Randomization.ipynb)\n", " - [Sparsification](https://github.com/networkit/networkit/blob/master/notebooks/Sparsification.ipynb)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Basic graph inspection\n", "\n", "- Notebook: [Graph](https://github.com/networkit/networkit/blob/master/notebooks/GraphNotebook.ipynb)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "g = nk.generators.BarabasiAlbertGenerator(k=2, nMax=10).generate()\n", "\n", "gv.d3(g, graph_height=200)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1) Graph and its properties" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print('Class:', type(g))\n", "print()\n", "print('Directed:', g.isDirected())\n", "print('Number of nodes:', g.numberOfNodes())\n", "print('Number of edges:', g.numberOfEdges())\n", "print('Number of self-loops:', g.numberOfSelfLoops())" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "nk.overview(g)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2) Nodes and their properties" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def func_called_for_each_node(node):\n", " print(node, end=' ')\n", "\n", "g.forNodes(func_called_for_each_node)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3) Edges and their properties" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def func_called_for_each_edge(source, target, edge_weight, edge_id):\n", " my_edge_id = '({}, {})'.format(source, target)\n", " print(my_edge_id, end=' ')\n", " \n", "g.forEdges(func_called_for_each_edge)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Calculating graph measures and metrics" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Centrality\n", "\n", "- Notebooks\n", " - [Centrality](https://github.com/networkit/networkit/blob/master/notebooks/Centrality.ipynb)\n", " - [Group Centrality](https://github.com/networkit/networkit/blob/master/notebooks/GroupCentrality.ipynb)\n", "- API reference\n", " - [networkit.centrality](https://networkit.github.io/dev-docs/python_api/centrality.html)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "centrality_values = nk.centrality.ApproxBetweenness(g).run().scores()\n", "centrality_values = nk.centrality.ApproxCloseness(g, nSamples=10).run().scores()\n", "centrality_values = nk.centrality.Betweenness(g).run().scores()\n", "centrality_values = nk.centrality.Closeness(g, True, nk.centrality.ClosenessVariant.Standard).run().scores()\n", "centrality_values = nk.centrality.Closeness(g, True, nk.centrality.ClosenessVariant.Generalized).run().scores()\n", "centrality_values = nk.centrality.DegreeCentrality(g).run().scores()\n", "centrality_values = nk.centrality.DynApproxBetweenness(g).run().scores()\n", "centrality_values = nk.centrality.DynBetweenness(g).run().scores()\n", "centrality_values = nk.centrality.EigenvectorCentrality(g).run().scores()\n", "centrality_values = nk.centrality.EstimateBetweenness(g, nSamples=10).run().scores()\n", "centrality_values = nk.centrality.HarmonicCloseness(g).run().scores()\n", "centrality_values = nk.centrality.KPathCentrality(g).run().scores()\n", "# centrality_values = nk.centrality.KadabraBetweenness(g).run().scores() # slow\n", "centrality_values = nk.centrality.KatzCentrality(g).run().scores()\n", "centrality_values = nk.centrality.LaplacianCentrality(g).run().scores()\n", "centrality_values = nk.centrality.LocalClusteringCoefficient(g).run().scores()\n", "centrality_values = nk.centrality.PageRank(g).run().scores()\n", "# centrality_values = nk.centrality.SciPyEVZ(g).run().scores() # scipy dependency\n", "# centrality_values = nk.centrality.SciPyPageRank(g).run().scores() # scipy dependency\n", "centrality_values = nk.centrality.Sfigality(g).run().scores()\n", "centrality_values = nk.centrality.SpanningEdgeCentrality(g).run().scores()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "top_centrality_values = nk.centrality.TopCloseness(g, k=5).run().topkScoresList()\n", "top_centrality_values = nk.centrality.TopHarmonicCloseness(g, k=5).run().topkScoresList()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "group_centrality_values = nk.centrality.ApproxGroupBetweenness(g, groupSize=4, epsilon=0.1).run().groupMaxBetweenness()\n", "\n", "group = nk.centrality.GroupCloseness(g).run().groupMaxCloseness()\n", "group_score = nk.centrality.GroupCloseness(g).run().scoreOfGroup(group)\n", "\n", "group = nk.centrality.GroupDegree(g).run().groupMaxDegree()\n", "group_score = nk.centrality.GroupDegree(g).run().scoreOfGroup(group)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "partition = nk.community.detectCommunities(g, inspect=False)\n", "partition_centrality_values = nk.centrality.LocalPartitionCoverage(g, partition).run().scores()\n", "node_centrality_value = nk.centrality.PermanenceCentrality(g, partition).run().getPermanence(0)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "node = nk.centrality.DynBetweennessOneNode(g, node=0).run()\n", "# node = nk.centrality.DynKatzCentrality(g, 0).run() # slow\n", "node = nk.centrality.DynTopHarmonicCloseness(g, 0).run()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "matrix = nk.centrality.PageRankMatrix(g)\n", "# eigenvector = nk.centrality.adjacencyEigenvector(g, False) # scipy dependency\n", "# eigenvectors = nk.centrality.symmetricEigenvectors(matrix) # scipy dependency" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "ranking1 = nk.centrality.ranking(g, algorithm=nk.centrality.Betweenness, normalized=False)\n", "ranking2 = nk.centrality.ranking(g, algorithm=nk.centrality.ApproxBetweenness, normalized=False)\n", "ranks = nk.centrality.rankPerNode(ranking1)\n", "rank_erros = nk.centrality.relativeRankErrors(ranking1, ranking2)\n", "\n", "scores = nk.centrality.scores(g, algorithm=nk.centrality.Betweenness)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Groups of nodes" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Cliques" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# TODO" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Cores" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# TODO" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Components\n", "\n", "- Notebook: [Components](https://github.com/networkit/networkit/blob/master/notebooks/Components.ipynb)\n", "- API reference: [networkit.components](https://networkit.github.io/dev-docs/python_api/components.html)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# TODO" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Communities\n", "\n", "- Notebook: [Community](https://github.com/networkit/networkit/blob/master/notebooks/Community.ipynb)\n", "- API reference: [networkit.community](https://networkit.github.io/dev-docs/python_api/community.html)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "cm = nk.community.detectCommunities(g, inspect=False)\n", "communities = cm.getVector()\n", "modularity_value = nk.community.Modularity().getQuality(cm, g)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# TODO" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Paths and distances\n", "\n", "- Notebook: [Distance](https://github.com/networkit/networkit/blob/master/notebooks/Distance.ipynb)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# TODO" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Global properties" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "g.totalEdgeWeight()\n", "\n", "# TODO" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Graph visualization" ] }, { "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 }