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