networkit

NetworKit – an interactive tool suite for high-performance network analysis.

NetworKit is an open-source software package for high-performance analysis of large complex networks. Complex networks are equally attractive and challenging targets for data mining, and novel algorithmic solutions, including parallelization, are required to handle data sets containing billions of connections. Our goal for NetworKit is to package results of our algorithm engineering efforts and put them into the hands of domain experts. NetworKit is a hybrid combining the performance of kernels written in C++ with a convenient Python frontend. The package targets shared-memory platforms with OpenMP support. The current feature set includes various analytics kernels such as connected components, diameter, clustering coefficients, community detection, k-core decomposition, degree assortativity and multiple centrality indices, as well as a collection of graph generators. Scaling to massive networks is enabled by techniques such as parallel and sampling-based approximation algorithms. NetworKit is geared towards large networks and satisfies three important criteria: High performance, interactive workflows and integration into the Python ecosystem of tools for data analysis and scientific computation.

Usage examples can be found on http://nbviewer.ipython.org/urls/networkit.iti.kit.edu/data/uploads/docs/NetworKit_UserGuide.ipynb

class networkit.Cover

Bases: object

Implements a cover of a set, i.e. an assignment of its elements to possibly overlapping subsets.

addToSubset(self, s, e)

Add the (previously unassigned) element e to the set s.

s : index
A subset
e : index
An element
allToSingletons(self)

Assigns every element to a singleton set. Set id is equal to element id.

contains(self, index e)

Check if cover assigns a valid subset to the element e.

e : index
An element.
bool
True, if e is assigned to a valid subset, False otherwise.
getMembers(self, s)

Get the members of a specific subset s.

set
The set of members of subset s.
getSubsetIds(self)

Get the ids of nonempty subsets.

set
A set of ids of nonempty subsets.
inSameSubset(self, index e1, index e2)

Check if two elements e1 and e2 belong to the same subset.

e1 : index
An element.
e2 : index
An element.
bool
True, if e1 and e2 belong to the same subset, False otherwise.
lowerBound(self)

Get a lower bound for the subset ids that have been assigned.

index
A lower bound.
mergeSubsets(self, index s, index t)

Assigns the elements from both sets to a new set.

s : index
A subset
t : index
A subset
moveToSubset(self, index s, index e)

Move the element e to subset s, i.e. remove it from all other subsets and place it in the subset.

s : index
A subset
e : index
An element
numberOfElements(self)

Get the current number of elements in this cover.

count
The current number of elements.
numberOfSubsets(self)

Get the current number of sets in this cover.

count
The number of sets in this cover.
removeFromSubset(self, s, e)

Remove the element e from the set s.

s : index
A subset
e : index
An element
setUpperBound(self, index upper)
subsetSizeMap(self)

Get a map from subset id to size of the subset.

dict
A map from subset id to size of the subset.
subsetSizes(self)

Get a list of subset sizes.

list
A list of subset sizes.

Indices do not necessarily correspond to subset ids.

subsetsOf(self, e)

Get the ids of subsets in which the element e is contained.

e : index
An element
set
A set of subset ids in which e is contained.
toSingleton(self, index e)

Creates a singleton set containing the element e and returns the index of the new set.

e : index
An element
index
The index of the new set.
upperBound(self)

Get an upper bound for the subset ids that have been assigned. (This is the maximum id + 1.)

index
An upper bound.
class networkit.Format

Bases: networkit.graphio.__AutoNumber

Simple enumeration class to list supported file types. Currently supported file types: SNAP, EdgeListSpaceZero, EdgeListSpaceOne, EdgeListTabZero, EdgeListTabOne, METIS, GraphML, GEXF, GML, EdgeListCommaOne, GraphViz, DOT, EdgeList, LFR, KONEC, GraphToolBinary

class networkit.Graph

Bases: object

An undirected graph (with optional weights) and parallel iterator methods.

Graph(n=0, weighted=False, directed=False)

Create a graph of n nodes. The graph has assignable edge weights if weighted is set to True. If weighted is set to False each edge has edge weight 1.0 and any other weight assignment will be ignored.

n : count, optional
Number of nodes.
weighted : bool, optional
If set to True, the graph can have edge weights other than 1.0.
directed : bool, optional
If set to True, the graph will be directed.
BFSEdgesFrom(self, node start, callback)

Experimental BFS search interface that passes edges that are part of the BFS tree to the callback

start: node
The start node from which the BFS shall be started
callback : object
Any callable object that takes the parameter (node, node)
BFSfrom(self, start, callback)

Experimental BFS search interface

start: node or list[node]
One or more start nodes from which the BFS shall be started
callback : object
Any callable object that takes the parameter (node, count) (the second parameter is the depth)
DFSEdgesFrom(self, node start, callback)

Experimental DFS search interface that passes edges that are part of the DFS tree to the callback

start: node
The start node from which the DFS shall be started
callback : object
Any callable object that takes the parameter (node, node)
DFSfrom(self, node start, callback)

Experimental DFS search interface

start: node
The start node from which the DFS shall be started
callback : object
Any callable object that takes the parameter node
addEdge(self, u, v, w=1.0)

Insert an undirected edge between the nodes u and v. If the graph is weighted you can optionally set a weight for this edge. The default weight is 1.0.

u : node
Endpoint of edge.
v : node
Endpoint of edge.
w : edgeweight, optional
Edge weight.
addNode(self)

Add a new node to the graph and return it.

node
The new node.
append(self, Graph G)

Appends another graph to this graph as a new subgraph. Performs node id remapping.

G : Graph

checkConsistency(self)

Check for invalid graph states, such as multi-edges.

compactEdges(self)

Compact the edge storage, this should be called after executing many edge deletions.

copyNodes(self)

Copies all nodes to a new graph

Graph
Graph with the same nodes (without edges)
degree(self, u)

Get the number of neighbors of v.

v : node
Node.
count
The number of neighbors.
degreeIn(self, u)
degreeOut(self, u)
density(self)

Get the density of the graph.

double

edgeId(self, node u, node v)
edgeid
id of the edge
edges(self)

Get list of edges as node pairs.

list
List of edges as node pairs.
forEdges(self, callback)

Experimental edge iterator interface

callback : object
Any callable object that takes the parameter (node, node, edgeweight, edgeid)
forEdgesOf(self, node u, callback)

Experimental incident (outgoing) edge iterator interface

u : node
The node of which incident edges shall be passed to the callback
callback : object
Any callable object that takes the parameter (node, node, edgeweight, edgeid)
forInEdgesOf(self, node u, callback)

Experimental incident incoming edge iterator interface

u : node
The node of which incident edges shall be passed to the callback
callback : object
Any callable object that takes the parameter (node, node, edgeweight, edgeid)
forNodePairs(self, callback)

Experimental node pair iterator interface

callback : object
Any callable object that takes the parameters (node, node)
forNodes(self, callback)

Experimental node iterator interface

callback : object
Any callable object that takes the parameter node
forNodesInRandomOrder(self, callback)

Experimental node iterator interface

callback : object
Any callable object that takes the parameter node
getCoordinate(self, v)
DEPRECATED: Coordinates should be handled outside the Graph class
like general node attributes.

Get the coordinates of node v. Parameters ———- v : node

Node.
pair[float, float]
x and y coordinates of v.
getName(self)

Get the name of the graph.

string
The name of the graph.
hasEdge(self, u, v)

Checks if undirected edge {u,`v`} exists in the graph.

u : node
Endpoint of edge.
v : node
Endpoint of edge.
bool
True if the edge exists, False otherwise.
hasEdgeIds(self)

Returns true if edges have been indexed

bool
if edges have been indexed
hasNode(self, u)

Checks if the Graph has the node u, i.e. if u hasn’t been deleted and is in the range of valid ids.

u : node
Node
bool
If the Graph has the node u
increaseWeight(self, u, v, w)

Increase the weight of an edge. If the edge does not exist, it will be inserted.

u : node
Endpoint of edge.
v : node
Endpoint of edge.
w : edgeweight
Edge weight.
indexEdges(self, bool force=False)

Assign integer ids to edges.

force : bool
Force re-indexing of edges.
initCoordinates(self)
DEPRECATED: Coordinates should be handled outside the Graph class
like general node attributes.
isDirected(self)
isIsolated(self, u)

If the node u is isolated

u : node
Node.
bool
If the node is isolated
isWeighted(self)
bool
True if this graph supports edge weights other than 1.0.
merge(self, Graph G)
Modifies this graph to be the union of it and another graph.
Nodes with the same ids are identified with each other.

G : Graph

neighbors(self, u)

Get list of neighbors of u.

u : node
Node.
list
List of neighbors of `u.
nodes(self)

Get list of all nodes.

list
List of all nodes.
numberOfEdges(self)

Get the number of edges in the graph.

count
The number of edges.
numberOfNodes(self)

Get the number of nodes in the graph.

count
The number of nodes.
numberOfSelfLoops(self)

Get number of self-loops, i.e. edges {v, v}. Returns ——- count

number of self-loops.
randomEdge(self, bool uniformDistribution=False)

Get a random edge of the graph.

uniformDistribution : bool
If the distribution of the edge shall be uniform
pair
Random random edge.

Fast, but not uniformly random if uniformDistribution is not set, slow and uniformly random otherwise.

randomEdges(self, count numEdges)

Returns a list with numEdges random edges. The edges are chosen uniformly at random.

numEdges : count
The number of edges to choose.
list of pairs
The selected edges.
randomNeighbor(self, u)

Get a random neighbor of v and none if degree is zero.

v : node
Node.
node
A random neighbor of `v.
randomNode(self)

Get a random node of the graph.

node
A random node.
removeEdge(self, u, v)

Removes the undirected edge {u,`v`}.

u : node
Endpoint of edge.
v : node
Endpoint of edge.
removeNode(self, u)

Remove a node v and all incident edges from the graph.

Incoming as well as outgoing edges will be removed.

u : node
Node.
removeSelfLoops(self)

Removes all self-loops from the graph.

restoreNode(self, u)

Restores a previously deleted node u with its previous id in the graph.

u : node
Node.
setCoordinate(self, v, value)
DEPRECATED: Coordinates should be handled outside the Graph class
like general node attributes.

Set the coordinates of node v. Parameters ———- v : node

Node.
value : pair[float, float]
x and y coordinates of v.
setName(self, name)

Set name of graph to name.

name : string
The name.
setWeight(self, u, v, w)

Set the weight of an edge. If the edge does not exist, it will be inserted.

u : node
Endpoint of edge.
v : node
Endpoint of edge.
w : edgeweight
Edge weight.
size(self)

Get the size of the graph.

tuple
a pair (n, m) where n is the number of nodes and m is the number of edges
sortEdges(self)

Sorts the adjacency arrays by node id. While the running time is linear this temporarily duplicates the memory.

subgraphFromNodes(self, nodes)

Create a subgraph induced by the set nodes.

nodes : list
A subset of nodes of G which induce the subgraph.
Graph
The subgraph induced by nodes.

The returned graph G’ is isomorphic (structurally identical) to the subgraph in G, but node indices are not preserved.

swapEdge(self, node s1, node t1, node s2, node t2)

Changes the edge (s1, t1) into (s1, t2) and the edge (s2, t2) into (s2, t1).

If there are edge weights or edge ids, they are preserved. Note that no check is performed if the swap is actually possible, i.e. does not generate duplicate edges.

s1 : node
Source node of the first edge
t1 : node
Target node of the first edge
s2 : node
Source node of the second edge
t2 : node
Target node of the second edge
toString(self)

Get a string representation of the graph.

string
A string representation of the graph.
toUndirected(self)

Return an undirected version of this graph.

undirected graph.
toUnweighted(self)

Return an unweighted version of this graph.

graph.
totalEdgeWeight(self)

Get the sum of all edge weights.

edgeweight
The sum of all edge weights.
transpose(self)

Return the transpose of this (directed) graph.

directed graph.
upperEdgeIdBound(self)

Get an upper bound for the edge ids in the graph

count
An upper bound for the edge ids in the graph
upperNodeIdBound(self)

Get an upper bound for the node ids in the graph

count
An upper bound for the node ids in the graph
weight(self, u, v)

Get edge weight of edge {u , v}. Returns 0 if edge does not exist.

u : node
Endpoint of edge.
v : node
Endpoint of edge.
edgeweight
Edge weight of edge {u , v} or 0 if edge does not exist.
weightedDegree(self, v)

Returns the weighted degree of v.

For directed graphs this is the sum of weights of all outgoing edges of v.

v : node
Node.
double
The weighted degree of v.
class networkit.Partition

Bases: object

Implements a partition of a set, i.e. a subdivision of the set into disjoint subsets.

Partition(z=0)

Create a new partition data structure for z elements.

size : index, optional
Maximum index of an element. Default is 0.
addToSubset(self, s, e)

Add a (previously unassigned) element e to the set s.

s : index
The index of the subset.
e : index
The element to add.
allToSingletons(self)

Assigns every element to a singleton set. Set id is equal to element id.

compact(self, useTurbo=False)

Change subset IDs to be consecutive, starting at 0.

useTurbo : bool
Default: false. If set to true, a vector instead of a map to assign new ids which results in a shorter running time but possibly a large space overhead.
contains(self, index e)

Check if partition assigns a valid subset to the element e.

e : index
The element.
bool
True if the assigned subset is valid, False otherwise.
extend(self)

Extend the data structure and create a slot for one more element.

Initializes the entry to none and returns the index of the entry.

index
The index of the new element.
getMembers(self, s)

Get the members of the subset s.

s : index
The subset.
set
A set containing the members of `s.
getName(self)

Get the human-readable identifier.

string
The name of this partition.
getSubsetIds(self)

Get the ids of nonempty subsets.

set
A set of ids of nonempty subsets.
getVector(self)

Get the actual vector representing the partition data structure.

vector
Vector containing information about partitions.
inSameSubset(self, index e1, index e2)

Check if two elements e1 and e2 belong to the same subset.

e1 : index
An Element.
e2 : index
An Element.
bool
True if e1 and e2 belong to same subset, False otherwise.
lowerBound(self)

Get a lower bound for the subset ids that have been assigned.

index
The lower bound.
mergeSubsets(self, index s, index t)

Assigns the elements from both sets to a new set and returns the id of it.

s : index
Set to merge.
t : index
Set to merge.
index
Id of newly created set.
moveToSubset(self, index s, index e)

Move the (previously assigned) element e to the set `s.

s : index
The index of the subset.
e : index
The element to move.
numberOfElements(self)
count
Number of elements in the partition.
numberOfSubsets(self)

Get the current number of sets in this partition.

count
The current number of sets.
setName(self, string name)

Set a human-readable identifier name for the instance.

name : string
The name.
setUpperBound(self, index upper)

Sets an upper bound for the subset ids that can be assigned.

upper : index
Highest assigned subset id + 1
subsetOf(self, e)

Get the set (id) in which the element e is contained.

e : index
Index of element.
index
The index of the set in which e is contained.
subsetSizeMap(self)

Get a map from subset id to size of the subset.

dict
A map from subset id to size of the subset.
subsetSizes(self)

Get a list of subset sizes. Indices do not necessarily correspond to subset ids.

vector
A vector of subset sizes.
toSingleton(self, index e)

Creates a singleton set containing the element e.

e : index
The index of the element.
upperBound(self)

Return an upper bound for the subset ids that have been assigned. (This is the maximum id + 1.)

index
The upper bound.
networkit.enableNestedParallelism()

Enable nested parallelism for OpenMP

networkit.getCurrentNumberOfThreads()

Get the number of currently running threads

networkit.getLogLevel()

Get the current log level

networkit.getMaxNumberOfThreads()

Get the maximum number of available threads

networkit.overview(G)

This function collects some basic information about the given graph and prints it to the terminal.

networkit.readGraph(path, fileformat, **kwargs)

Read graph file in various formats and return a NetworKit::Graph Parameters:

  • fileformat: An element of the Format enumeration. Currently supported file types:

SNAP, EdgeListSpaceZero, EdgeListSpaceOne, EdgeListTabZero, EdgeListTabOne, METIS, GraphML, GEXF, GML, EdgeListCommaOne, GraphViz, DOT, EdgeList, LFR, KONECT, GraphToolBinary - **kwargs: in case of a custom edge list, pass the genereic Fromat.EdgeList accompanied by

the defining paramaters as follows: “separator=CHAR, firstNode=NODE, commentPrefix=STRING, continuous=BOOL, directed=BOOL” commentPrefix=’#’, continuous=True and directed=False are optional because of their default values; firstNode is not needed when continuous=True.
networkit.readGraphs(dirPath, pattern, fileformat, some=None, exclude=None, **kwargs)
Read all graph files contained in a directory whose filename contains the pattern, return a dictionary of name to Graph object.
Parameters:
  • pattern: unix-style string pattern

  • fileformat: An element of the Format enumeration

  • some: restrict number of graphs to be read

  • **kwargs: in case of a custom edge list, provide the defining paramaters as follows:

    “separator=CHAR, firstNode=NODE, commentPrefix=STRING, continuous=BOOL” commentPrefix and continuous are optional

networkit.setLogLevel(loglevel)

Set the current loglevel

networkit.setNumberOfThreads(nThreads)

Set the number of OpenMP threads

networkit.setPrintLocation(flag)

Switch locations in log statements on or off

networkit.setSeed(uint64_t seed, bool useThreadId)

Set the random seed that is used in NetworKit.

Note that there is a separate random number generator per thread.

seed : uint64_t
The seed
useThreadId : bool
If the thread id shall be added to the seed
networkit.setup()

This function is run once on module import to configure initial settings

networkit.writeGraph(G, path, fileformat, **kwargs)

Write graph to various output formats.

Paramaters: - G: a graph - path: output path - fileformat: an element of the Format enumeration