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 https://github.com/networkit/networkit/blob/master/notebooks/User-Guide.ipynb

class networkit.Cover(n=0)

Bases: object

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

Parameters

n (int or networkit.Partition, optional) – Used for initialization of the cover. Either a node or a partition. Default: 0

addToSubset(s, e)

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

Parameters
  • s (int) – The input subset.

  • e (int) – The element to be added.

allToSingletons()

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

contains(e)

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

Parameters

e (int) – The input element.

Returns

True, if e is assigned to a valid subset, False otherwise.

Return type

bool

extend()

Add an additional element (node).

Returns

Id of added node.

Return type

int

getMembers(s)

Get the members of a specific subset s.

Returns

The list of members of subset s.

Return type

list(int)

getSubsetIds()

Get the ids of nonempty subsets.

Returns

A list of ids of nonempty subsets.

Return type

list(int)

inSameSubset(e1, e2)

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

Parameters
  • e1 (int) – The first element.

  • e2 (int) – The second element.

Returns

True if e1 and e2 belong to the same subset; False otherwise.

Return type

bool

lowerBound()

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

Returns

A lower bound.

Return type

int

mergeSubsets(s, t)

Assigns the elements from both sets to a new set.

Parameters
  • s (int) – The first subset.

  • t (int) – The second subset.

moveToSubset(s, e)

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

Parameters
  • s (int) – The input subset.

  • e (int) – The element to be moved.

numberOfElements()

Get the current number of elements in this cover.

Returns

The current number of elements.

Return type

int

numberOfSubsets()

Get the current number of sets in this cover.

Returns

The number of sets in this cover.

Return type

int

removeFromSubset(s, e)

Remove the element e from the set s.

Parameters
  • s (int) – The input subset.

  • e (int) – The element to be removed.

setUpperBound(upper)

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

Parameters

upper (int) – Upper bound.

subsetSizeMap()

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

Returns

dict(int ` – A map from subset id to size of the subset.

Return type

` int)

subsetSizes()

Get a list of subset sizes.

Returns

A list of subset sizes.

Return type

list(int)

Notes

Indices do not necessarily correspond to subset ids.

subsetsOf(e)

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

Parameters

e (int) – An element

Returns

A set of subset ids in which e is contained.

Return type

list(int)

toSingleton(e)

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

Parameters

e (int) – The input element.

Returns

The id of the new set.

Return type

int

upperBound()

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

Returns

An upper bound.

Return type

int

class networkit.Format(value)

Bases: networkit.graphio.__AutoNumber

Simple enumeration class to list supported file types. Possible values:

  • networkit.graphio.Format.DOT

  • networkit.graphio.Format.EdgeList

  • networkit.graphio.Format.EdgeListCommaOne

  • networkit.graphio.Format.EdgeListSpaceZero

  • networkit.graphio.Format.EdgeListSpaceOne

  • networkit.graphio.Format.EdgeListTabZero

  • networkit.graphio.Format.EdgeListTabOne

  • networkit.graphio.Format.GraphML

  • networkit.graphio.Format.GraphToolBinary

  • networkit.graphio.Format.GraphViz

  • networkit.graphio.Format.GEXF

  • networkit.graphio.Format.GML

  • networkit.graphio.Format.KONEC

  • networkit.graphio.Format.LFR

  • networkit.graphio.Format.METIS

  • networkit.graphio.Format.NetworkitBinary

  • networkit.graphio.Format.SNAP

DOT = 12
EdgeList = 13
EdgeListCommaOne = 10
EdgeListSpaceOne = 3
EdgeListSpaceZero = 2
EdgeListTabOne = 5
EdgeListTabZero = 4
GEXF = 8
GML = 9
GraphML = 7
GraphToolBinary = 16
GraphViz = 11
KONECT = 15
LFR = 14
MAT = 17
METIS = 6
NetworkitBinary = 19
SNAP = 1
ThrillBinary = 18
class networkit.Graph(n=0, weighted=False, directed=False, edgesIndexed=False)

Bases: object

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

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.

Parameters
  • n (int, optional) – Number of nodes.

  • weighted (bool, optional) – If set to True, the graph can have edge weights other than 1.0. Default: False

  • directed (bool, optional) – If set to True, the graph will be directed. Default: False

  • edgesIndexed (bool, optional) – If set to True, the graph’s edges will be indexed. Default: False

addEdge(u, v, w=1.0, addMissing=False, checkMultiEdge=False)

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. If one or both end-points do not exists and addMissing is set, they are silently added.

Note

By default it is not checked whether this edge already exists, thus it is possible to create multi-edges. Multi-edges are not supported and will NOT be handled consistently by the graph data structure. To enable set checkMultiEdge to True. Note that this increases the runtime of the function by O(max(deg(u), deg(v))).

Parameters
  • u (int) – Endpoint of edge.

  • v (int) – Endpoint of edge.

  • w (float, optional) – Edge weight.

  • addMissing (bool, optional) – Add missing endpoints if necessary (i.e., increase numberOfNodes). Default: False

  • checkMultiEdge (bool, optional) – Check if edge is already present in the graph. If detected, do not insert the edge. Default: False

Returns

Indicates whether the edge has been added. Is False in case checkMultiEdge is set to True and the new edge would have been a multi-edge.

Return type

bool

addNode()

Add a new node to the graph and return it.

Returns

The new node.

Return type

int

addNodes(numberOfNewNodes)

Add numberOfNewNodes many new nodes to the graph and return the id of the last node added.

Parameters

numberOfNewNodes (int) – Number of nodes to be added.

Returns

The id of the last node added.

Return type

int

attachNodeAttribute(name, ofType)

Attaches a node attribute to the graph and returns it.

A = G.attachNodeAttribute("attributeIdentifier", ofType)

All values are initially undefined for existing nodes values can be set/get by

A[node] = value # set
value = A[node] # get

Getting undefined values raises a ValueError removing a node makes all its attributes undefined

Notes

Using node attributes is in experimental state. The API may change in future updates.

Parameters
  • name (str) – Name for this attribute

  • ofType (type) – Type of the attribute (either int, float, or str)

Returns

The resulting node attribute container.

Return type

networkit.graph.NodeAttribute

checkConsistency()

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

Returns

True if graph contains invalid graph states.

Return type

bool

compactEdges()

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

degree(u)

Get the number of neighbors of v.

Parameters

v (int) – The input Node.

Returns

The number of neighbors.

Return type

int

degreeIn(u)

Get the number of in-neighbors of v.

Parameters

v (int) – The input Node.

Returns

The number of in-neighbors.

Return type

int

degreeOut(u)

Get the number of out-neighbors of v.

Parameters

v (int) – The Input Node.i

Returns

The number of out-neighbors.

Return type

int

detachNodeAttribute(name)

Detaches a node attribute from the graph.

Notes

Using node attributes is in experimental state. The API may change in future updates.

Parameters

name (str) – The distinguished name for the attribute to detach.

edgeId(u, v)
Returns

Id of the edge.

Return type

int

forEdges(callback)

Experimental edge iterator interface

Parameters

callback (object) – Any callable object that takes the parameter tuple(int, int, float, int). Parameter list refering to (node id, node id, edge weight, edge id).

forEdgesOf(u, callback)

Experimental incident (outgoing) edge iterator interface

Parameters
  • u (int) – The node of which incident edges shall be passed to the callback

  • callback (object) – Any callable object that takes the parameter tuple(int, int, float, int). Parameter list refering to (node id, node id, edge weight, edge id).

forInEdgesOf(u, callback)

Experimental incident edge iterator interface

Parameters
  • u (int) – The node of which incident edges shall be passed to the callback

  • callback (object) – Any callable object that takes the parameter tuple(int, int, float, int). Parameter list refering to (node id, node id, edge weight, edge id).

forNodePairs(callback)

Experimental node pair iterator interface

Parameters

callback (object) – Any callable object that takes the parameters tuple(int, int). Parameter list refering to (node id, node id).

forNodes(callback)

Experimental node iterator interface

Parameters

callback (object) – Any callable object that takes the parameter node.

forNodesInRandomOrder(callback)

Experimental node iterator interface

hasEdge(u, v)

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

Parameters
  • u (int) – Endpoint of edge.

  • v (int) – Endpoint of edge.

Returns

True if the edge exists, False otherwise.

Return type

bool

hasEdgeIds()

Returns true if edges have been indexed

Returns

If edges have been indexed

Return type

bool

hasNode(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.

Parameters

u (int) – Id of node queried.

Returns

Indicates whether node u is part of the graph.

Return type

bool

increaseWeight(u, v, w)

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

Parameters
  • u (int) – Endpoint of edge.

  • v (int) – Endpoint of edge.

  • w (float) – Edge weight.

indexEdges(force=False)

Assign integer ids to edges.

Parameters

force (bool, optional) – Force re-indexing of edges.

isDirected()

Returns whether a graph is directed.

Returns

True if graph is directed.

Return type

bool

isIsolated(u)

If the node u is isolated.

Parameters

u (int) – The input node.

Returns

Indicates whether the node is isolated.

Return type

bool

isWeighted()

Returns whether a graph is weighted.

Returns

True if this graph supports edge weights other than 1.0.

Return type

bool

iterEdges()

Iterates over the edges of the graph.

For each node u in the graph in ascending node id order, the iterator yields the out-edges of u in directed graphs and the edges (u,v) in which u < v for undirected graphs.

It does not follow the order of edge ids (if present).

iterEdgesWeights()

Iterates over the edges of the graph and their weights.

iterInNeighbors(u)

Iterates over a range of the in-neighbors of a node.

Parameters

u (int) – The input node.

iterInNeighborsWeights(u)

Iterates over a range of the in-neighbors of a node including the edge weights. The iterator is not safe to use with unweighted graphs. To avoid unsafe behavior a runtime error will be thrown.

Parameters

u (int) – The input node.

iterNeighbors(u)

Iterates over a range of the neighbors of a node.

Parameters

u (int) – The input node.

iterNeighborsWeights(u)

Iterates over a range of the neighbors of a node including the edge weights. The iterator is not safe to use with unweighted graphs. To avoid unsafe behavior a runtime error will be thrown.

Parameters

u (int) – The input node.

iterNodes()

Iterates over the nodes of the graph.

numberOfEdges()

Get the number of edges in the graph.

Returns

The number of edges.

Return type

int

numberOfNodes()

Get the number of nodes in the graph.

Returns

The number of nodes.

Return type

int

numberOfSelfLoops()

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

Returns

Number of self-loops.

Return type

int

removeAllEdges()

Removes all the edges in the graph.

removeEdge(u, v)

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

Parameters
  • u (int) – Endpoint of edge.

  • v (int) – Endpoint of edge.

removeMultiEdges()

Removes all multi-edges from the graph.

removeNode(u)

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

Incoming as well as outgoing edges will be removed.

Parameters

u (int) – Id of node to be removed.

removeSelfLoops()

Removes all self-loops from the graph.

restoreNode(u)

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

Parameters

u (int) – The input node.

setWeight(u, v, w)

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

Parameters
  • u (int) – Endpoint of edge.

  • v (int) – Endpoint of edge.

  • w (float) – Edge weight.

sortEdges()

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

swapEdge(s1, t1, s2, 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

No check is performed if the swap is actually possible, i.e. does not generate duplicate edges.

Parameters
  • s1 (int) – Source node of the first edge.

  • t1 (int) – Target node of the first edge.

  • s2 (int) – Source node of the second edge.

  • t2 (int) – Target node of the second edge.

totalEdgeWeight()

Get the sum of all edge weights.

Returns

The sum of all edge weights.

Return type

float

upperEdgeIdBound()

Get an upper bound for the edge ids in the graph.

Returns

An upper bound for the edge ids in the graph.

Return type

int

upperNodeIdBound()

Get an upper bound for the node ids in the graph.

Returns

An upper bound for the node ids in the graph.

Return type

int

weight(u, v)

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

Parameters
  • u (int) – Endpoint of edge.

  • v (int) – Endpoint of edge.

Returns

Edge weight of edge {u , v} or 0 if edge does not exist.

Return type

float

weightedDegree(u, countSelfLoopsTwice=False)

Returns the weighted out-degree of u.

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

Parameters
  • u (int) – The input Node.

  • countSelfLoopsTwice (bool, optional) – If set to True, self-loops will be counted twice. Default: False

Returns

The weighted out-degree of u.

Return type

float

weightedDegreeIn(u, countSelfLoopsTwice=False)

Returns the weighted in-degree of u.

For directed graphs this is the sum of weights of all ingoing edges of u.

Parameters
  • u (int) – The input node.

  • countSelfLoopsTwice (bool, optional) – If set to True, self-loops will be counted twice. Default: False

Returns

The weighted in-degree of u.

Return type

float

exception networkit.MissingDependencyError(package)

Bases: RuntimeError

class networkit.Partition(z=0)

Bases: object

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

Create a new partition data structure for z elements.

Parameters

size (int, optional) – Maximum index of an element. Default: 0

addToSubset(s, e)

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

Parameters
  • s (int) – The index of the subset.

  • e (int) – The element to add.

allToSingletons()

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

compact(userTurbo=False)

Change subset IDs to be consecutive, starting at 0.

Parameters

useTurbo (bool, optional) – If set to True, the C++ core uses a vector instead of a map to assign new ids which results in a shorter running time but possibly a large space overhead. Default: False

contains(e)

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

Parameters

e (int) – The input element.

Returns

True if the assigned subset is valid; False otherwise.

Return type

bool

extend()

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

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

Returns

The index of the new element.

Return type

int

getMembers(s)

Get the members of the subset s.

Parameters

s (int) – The input subset.

Returns

A list containing the members of s.

Return type

list(int)

getName()

Get the human-readable identifier.

Returns

The name of this partition.

Return type

str

getSubsetIds()

Get the ids of nonempty subsets.

Returns

A set of ids of nonempty subsets.

Return type

list(int)

getVector()

Get the actual vector representing the partition data structure.

Returns

List containing information about partitions.

Return type

list(int)

inSameSubset(e1, e2)

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

Parameters
  • e1 (int) – The first Element.

  • e2 (int) – The second Element.

Returns

True if e1 and e2 belong to same subset, False otherwise.

Return type

bool

lowerBound()

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

Returns

The lower bound.

Return type

int

mergeSubsets(s, t)

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

Parameters
  • s (int) – Set to merge.

  • t (int) – Set to merge.

Returns

Id of newly created set.

Return type

int

moveToSubset(s, e)

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

Parameters
  • s (int) – The index of the subset.

  • e (int) – The element to move.

numberOfElements()
Returns

Number of elements in the partition.

Return type

int

numberOfSubsets()

Get the current number of sets in this partition.

Returns

The current number of sets.

Return type

int

setName(name)

Set a human-readable identifier name for the instance.

Parameters

name (str) – The input name.

setUpperBound(upper)

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

Parameters

upper (int) – Highest assigned subset id + 1.

subsetOf(e)

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

Parameters

e (int) – Index of element.

Returns

The index of the set in which e is contained.

Return type

int

subsetSizeMap()

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

Returns

dict(int ` – A map from subset id to size of the subset.

Return type

` int)

subsetSizes()

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

Returns

A list of subset sizes.

Return type

list(int)

toSingleton(e)

Creates a singleton set containing the element e.

Parameters

e (int) – The index of the element.

upperBound()

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

Returns

The upper bound.

Return type

int

networkit.getCurrentNumberOfThreads()

Get the number of currently running threads.

Returns

Number of threads.

Return type

int

networkit.getLogLevel()

Get the current log level.

Returns

The current loglevel.

Return type

logLevel

networkit.getMaxNumberOfThreads()

Get the maximum number of available threads

Returns

Max number of threads.

Return type

int

networkit.graphtools

alias of networkit.graphtools.GraphTools

networkit.overview(G)

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

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

Read graph file in various formats and return a graph.

Parameters
  • fileformat (networkit.graphio.Format) – A supported file format.

  • *kargs (tuple()) – Additional input parameter (depending on the file format).

  • **kwargs (dict()) – Additional input parameter (depending on the file format). In case of a custom edge list, pass the generic Fromat.EdgeList accompanied by the defining paramaters as follows: separator, firstNode, commentPrefix, continuous, directed. commentPrefix, continuous=True and directed 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
  • dirPath (str) – Path, which contains input graphs.

  • pattern (str) – Unix-style string pattern for file selection.

  • fileformat (networkit.graphio.Format) – A supported file format.

  • some (int, optional) – Restrict number of graphs to be read. Default: None

  • exclude (str, optional) – Unix-style string pattern for file exclusion. Default: None

  • **kwargs (dict()) – Additional input parameter (depending on the file format). In case of a custom edge list, pass the generic Fromat.EdgeList accompanied by the defining paramaters as follows: separator, firstNode, commentPrefix, continuous, directed. commentPrefix, continuous=True and directed are optional because of their default values. firstNode is not needed when continuous=True.

networkit.setLogLevel(loglevel)

Set the current loglevel

Parameters

loglevel (str) – The new loglevel. Possible values: TRACE, DEBUG, INFO, WARN, ERROR, FATAL, QUIET

networkit.setNumberOfThreads(nThreads)

Set the number of OpenMP threads

networkit.setPrintLocation(flag)

Switch locations in log statements on or off

Parameters

flag (bool) – Sets whether to also log file, function and line of code. Default: False.

networkit.setSeed(seed, useThreadId)

Set the random seed that is used in NetworKit.

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

Parameters
  • seed (int) – 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, *kargs, **kwargs)

Write graph to various output formats.

Parameters
  • G (networkit.Graph) – The input graph.

  • path (str) – Output file path.

  • fileformat (networkit.graphio.Format) – A supported file format.

  • *kargs (tuple()) – Additional input parameter (depending on the file format).

  • **kwargs (dict()) – Additional input parameter (depending on the file format). In case of a custom edge list, pass the generic Fromat.EdgeList accompanied by the defining paramaters as follows: separator, firstNode, commentPrefix, continuous, directed. commentPrefix, continuous=True and directed are optional because of their default values. firstNode is not needed when continuous=True.