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
Bases: object
Implements a cover of a set, i.e. an assignment of its elements to possibly overlapping subsets.
n (int or networkit.Partition, optional) – Used for initialization of the cover. Either a node or a partition. Default: 0
Add the (previously unassigned) element e to the set s.
s (int) – The input subset.
e (int) – The element to be added.
Assigns every element to a singleton set. Set id is equal to element id.
Check if cover assigns a valid subset to the element e.
e (int) – The input element.
True, if e is assigned to a valid subset, False otherwise.
bool
Add an additional element (node).
Id of added node.
int
Get the members of a specific subset s.
The list of members of subset s.
list(int)
Get the ids of nonempty subsets.
A list of ids of nonempty subsets.
list(int)
Check if two elements e1 and e2 belong to the same subset.
e1 (int) – The first element.
e2 (int) – The second element.
True if e1 and e2 belong to the same subset; False otherwise.
bool
Get a lower bound for the subset ids that have been assigned.
A lower bound.
int
Assigns the elements from both sets to a new set.
s (int) – The first subset.
t (int) – The second subset.
Move the element e to subset s, i.e. remove it from all other subsets and place it in the subset.
s (int) – The input subset.
e (int) – The element to be moved.
Get the current number of elements in this cover.
The current number of elements.
int
Get the current number of sets in this cover.
The number of sets in this cover.
int
Remove the element e from the set s.
s (int) – The input subset.
e (int) – The element to be removed.
Sets an upper bound for the subset ids that CAN be assigned.
upper (int) – Upper bound.
Get a map from subset id to size of the subset.
A map from subset id to size of the subset.
dict(int : int)
Get a list of subset sizes.
A list of subset sizes.
list(int)
Notes
Indices do not necessarily correspond to subset ids.
Get the ids of subsets in which the element e is contained.
e (int) – An element
A set of subset ids in which e is contained.
list(int)
Creates a singleton set containing the element e and returns the index of the new set.
e (int) – The input element.
The id of the new set.
int
Get an upper bound for the subset ids that have been assigned. (This is the maximum id + 1.)
An upper bound.
int
Bases: __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.KONECT
networkit.graphio.Format.LFR
networkit.graphio.Format.METIS
networkit.graphio.Format.NetworkitBinary
networkit.graphio.Format.SNAP
networkit.graphio.Format.MatrixMarket
networkit.graphio.Format.RB
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.
n (int, optional) – Number of nodes. Default: 0
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
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))).
u (int) – Endpoint of edge.
v (int) – Endpoint of edge.
w (float, optional) – Edge weight. Default: 1.0
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
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.
bool
Inserts edges from several sources based on the type of inputData.
If the graph is undirected, each pair (i,j) in inputData is inserted twice twice: once as (i,j) and once as (j,i).
Parameter inputData can be one of the following:
scipy.sparse.coo_matrix
(data, (i,j)) where data, i and j are of type np.ndarray
(i,j) where i and j are of type np.ndarray
Note
If only pairs of row and column indices (i,j) are given, each edge is given weight 1.0 (even in case of a weighted graph).
inputData (several) – Input data encoded as one of the supported formats.
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
Add a new node to the graph and return it.
The new node.
int
Add numberOfNewNodes many new nodes to the graph and return the id of the last node added.
numberOfNewNodes (int) – Number of nodes to be added.
The id of the last node added.
int
Attaches an edge attribute to the graph and returns it.
A = G.attachEdgeAttribute("attributeIdentifier", ofType)
All values are initially undefined for existing edges values can be set/get by
A[edgeId] = value # set
value = A[edgeId] # get
Getting undefined values raises a ValueError removing an edge makes all its attributes undefined
Notes
Using edge attributes is in experimental state. The API may change in future updates.
name (str) – Name for this attribute
ofType (type) – Type of the attribute (either int, float, or str)
The resulting edge attribute container.
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.
name (str) – Name for this attribute
ofType (type) – Type of the attribute (either int, float, or str)
The resulting node attribute container.
Check for invalid graph states, such as multi-edges.
True if graph contains invalid graph states.
bool
Compact the edge storage, this should be called after executing many edge deletions.
Get the number of neighbors of u.
Note
The existence of the node is not checked. Calling this function with a non-existing node results in a segmentation fault. Node existence can be checked by calling hasNode(u).
u (int) – The input Node.
The number of neighbors.
int
Get the number of in-neighbors of u.
Note
The existence of the node is not checked. Calling this function with a non-existing node results in a segmentation fault. Node existence can be checked by calling hasNode(u).
u (int) – The input Node.
The number of in-neighbors.
int
Get the number of out-neighbors of u.
Note
The existence of the node is not checked. Calling this function with a non-existing node results in a segmentation fault. Node existence can be checked by calling hasNode(u).
u (int) – The Input Node.i
The number of out-neighbors.
int
Detaches an edge attribute from the graph.
Notes
Using edge attributes is in experimental state. The API may change in future updates.
name (str) – The distinguished name for the attribute to detach.
Detaches a node attribute from the graph.
Notes
Using node attributes is in experimental state. The API may change in future updates.
name (str) – The distinguished name for the attribute to detach.
u (node) – Node Id from u.
v (node) – Node Id from v.
Id of the edge.
int
This iterator can be used to visit each edge in the order of their edge ids. For this to work, indexEdges() must have been called once before. If the graph has changed since the last call to indexEdges(), the edge ids may not be in the correct order. In this case, calling indexEdges(True) again will restore the correct order.
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).
This iterator can be used to visit each edge in the order of their edge ids. For this to work, indexEdges() must have been called once before. If the graph has changed since the last call to indexEdges(), the edge ids may not be in the correct order. In this case, calling indexEdges(True) again will restore the correct order.
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).
This iterator can be used to visit each edge in the order of their edge ids. For this to work, indexEdges() must have been called once before. If the graph has changed since the last call to indexEdges(), the edge ids may not be in the correct order. In this case, calling indexEdges(True) again will restore the correct order.
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).
Experimental node pair iterator interface
callback (object) – Any callable object that takes the parameters tuple(int, int). Parameter list refering to (node id, node id).
Experimental node iterator interface
callback (object) – Any callable object that takes the parameter node.
Experimental node iterator interface
Gets an edge attribute that is already attached to the graph and returns it.
A = G.getEdgeAttribute("attributeIdentifier", ofType)
Notes
Using edge attributes is in experimental state. The API may change in future updates.
name (str) – Name for this attribute
ofType (type) – Type of the attribute (either int, float, or str)
The resulting edge attribute container.
Gets a node attribute that is already attached to the graph and returns it.
A = G.getNodeAttribute("attributeIdentifier", ofType)
Notes
Using node attributes is in experimental state. The API may change in future updates.
name (str) – Name for this attribute
ofType (type) – Type of the attribute (either int, float, or str)
The resulting node attribute container.
Checks if undirected edge {u,`v`} exists in the graph.
u (int) – Endpoint of edge.
v (int) – Endpoint of edge.
True if the edge exists, False otherwise.
bool
Returns true if edges have been indexed
If edges have been indexed
bool
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 (int) – Id of node queried.
Indicates whether node u is part of the graph.
bool
Increase the weight of an edge. If the edge does not exist, it will be inserted.
u (int) – Endpoint of edge.
v (int) – Endpoint of edge.
w (float) – Edge weight.
Assign integer ids to edges.
force (bool, optional) – Force re-indexing of edges. Default: False
Returns whether a graph is directed.
True if graph is directed.
bool
If the node u is isolated.
u (int) – The input node.
Indicates whether the node is isolated.
bool
Returns whether a graph is weighted.
True if this graph supports edge weights other than 1.0.
bool
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).
Iterates over the edges of the graph and their weights.
Iterates over a range of the in-neighbors of a node.
u (int) – The input node.
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.
u (int) – The input node.
Iterates over a range of the neighbors of a node.
u (int) – The input node.
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.
u (int) – The input node.
Iterates over the nodes of the graph.
Get the number of edges in the graph.
The number of edges.
int
Get the number of nodes in the graph.
The number of nodes.
int
Get number of self-loops, i.e. edges {v, v}.
Number of self-loops.
int
Removes all the edges in the graph.
Removes the undirected edge {u,`v`}.
u (int) – Endpoint of edge.
v (int) – Endpoint of edge.
Removes all multi-edges from the graph.
Remove a node u and all incident edges from the graph.
Incoming as well as outgoing edges will be removed.
u (int) – Id of node to be removed.
Removes all self-loops from the graph.
Restores a previously deleted node u with its previous id in the graph.
u (int) – The input node.
Set the weight of an edge. If the edge does not exist, it will be inserted.
u (int) – Endpoint of edge.
v (int) – Endpoint of edge.
w (float) – Edge weight.
Sorts the adjacency arrays by node id. While the running time is linear this temporarily duplicates the memory.
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.
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.
Get the sum of all edge weights.
The sum of all edge weights.
float
Get an upper bound for the edge ids in the graph.
An upper bound for the edge ids in the graph.
int
Get an upper bound for the node ids in the graph.
An upper bound for the node ids in the graph.
int
Get edge weight of edge {u , v}. Returns 0 if edge does not exist.
u (int) – Endpoint of edge.
v (int) – Endpoint of edge.
Edge weight of edge {u , v} or 0 if edge does not exist.
float
Returns the weighted out-degree of u.
For directed graphs this is the sum of weights of all outgoing edges of u.
u (int) – The input Node.
countSelfLoopsTwice (bool, optional) – If set to True, self-loops will be counted twice. Default: False
The weighted out-degree of u.
float
Returns the weighted in-degree of u.
For directed graphs this is the sum of weights of all ingoing edges of u.
u (int) – The input node.
countSelfLoopsTwice (bool, optional) – If set to True, self-loops will be counted twice. Default: False
The weighted in-degree of u.
float
graphFromInputData(inputData, n=0, bool_t weighted=False, bool_t directed=False, bool_t edgesIndexed=False):
Creates a graph based on inputData (edge data). Input data is given in triplet format (also known
as ijk or coo format). See here for more details: https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.coo_array.html
If the resulting graph is undirected (default case), each pair (i,j) in inputData is
inserted twice twice: once as (i,j) and once as (j,i).
Parameter inputData can be one of the following:
scipy.sparse.coo_matrix
(data, (i,j)) where data, i and j are of type np.ndarray
(i,j) where i and j are of type np.ndarray
Note
If only pairs of row and column indices (i,j) are given, each edge is given weight 1.0 (even in case of a weighted graph).
There is no check if n is the correct size. If the parameter is used, make sure that it is at least the
maximum index from the coordinate data.
inputData (several) – Input data encoded as one of the supported formats.
n (int, optional) – Number of nodes for the created graph. If n is not given, the nodes are added on the fly during building of the graph. For better performance, it is advised to correctly set the number of nodes. Default: 0
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
Bases: RuntimeError
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.
size (int, optional) – Maximum index of an element. Default: 0
Add a (previously unassigned) element e to the set s.
s (int) – The index of the subset.
e (int) – The element to add.
Assigns every element to a singleton set. Set id is equal to element id.
Change subset IDs to be consecutive, starting at 0.
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
Check if partition assigns a valid subset to the element e.
e (int) – The input element.
True if the assigned subset is valid; False otherwise.
bool
Extend the data structure and create a slot for one more element.
Initializes the entry to none and returns the index of the entry.
The index of the new element.
int
Get the members of the subset s.
s (int) – The input subset.
A list containing the members of s.
list(int)
Get the human-readable identifier.
The name of this partition.
str
Get the ids of nonempty subsets.
A set of ids of nonempty subsets.
list(int)
Get the actual vector representing the partition data structure.
List containing information about partitions.
list(int)
Check if two elements e1 and e2 belong to the same subset.
e1 (int) – The first Element.
e2 (int) – The second Element.
True if e1 and e2 belong to same subset, False otherwise.
bool
Get a lower bound for the subset ids that have been assigned.
The lower bound.
int
Assigns the elements from both sets to a new set and returns the id of it.
s (int) – Set to merge.
t (int) – Set to merge.
Id of newly created set.
int
Move the (previously assigned) element e to the set `s.
s (int) – The index of the subset.
e (int) – The element to move.
Number of elements in the partition.
int
Get the current number of sets in this partition.
The current number of sets.
int
Set a human-readable identifier name for the instance.
name (str) – The input name.
Sets an upper bound for the subset ids that can be assigned.
upper (int) – Highest assigned subset id + 1.
Get the set (id) in which the element e is contained.
e (int) – Index of element.
The index of the set in which e is contained.
int
Get a map from subset id to size of the subset.
A map from subset id to size of the subset.
dict(int : int)
Get a list of subset sizes. Indices do not necessarily correspond to subset ids.
A list of subset sizes.
list(int)
Creates a singleton set containing the element e.
e (int) – The index of the element.
Return an upper bound for the subset ids that have been assigned. (This is the maximum id + 1.)
The upper bound.
int
Get the number of currently running threads.
Number of threads.
int
Get the current log level.
The current loglevel.
logLevel
Get the maximum number of available threads
Max number of threads.
int
alias of GraphTools
This function collects some basic information about the given graph and prints it to the terminal.
Read graph file in various formats and return a graph.
fileformat (networkit.graphio.Format or None) – A supported file format. If None is passed, this function will try to guess the format. May fail and throw an exception.
*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 Format.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.
Read all graph files contained in a directory whose filename contains the pattern, return a dictionary of name to Graph object.
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 Format.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.
Set the current loglevel
loglevel (str) – The new loglevel. Possible values: TRACE, DEBUG, INFO, WARN, ERROR, FATAL, QUIET
Set the number of OpenMP threads
nThreads (int) – Number of threads.
Switch locations in log statements on or off
flag (bool) – Sets whether to also log file, function and line of code. Default: False.
Set the random seed that is used in NetworKit.
Note that there is a separate random number generator per thread.
seed (int) – The seed
useThreadId (bool) – If the thread id shall be added to the seed
This function is run once on module import to configure initial settings
Write graph to various output formats.
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 Format.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.