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
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.
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.
getMembers
(self, s)Get the members of a specific subset s.
getSubsetIds
(self)Get the ids of nonempty subsets.
inSameSubset
(self, index e1, index e2)Check if two elements e1 and e2 belong to the same subset.
lowerBound
(self)Get a lower bound for the subset ids that have been assigned.
mergeSubsets
(self, index s, index t)Assigns the elements from both sets to a new set.
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.
numberOfElements
(self)Get the current number of elements in this cover.
numberOfSubsets
(self)Get the current number of sets in this cover.
removeFromSubset
(self, s, e)Remove the element e from the set s.
setUpperBound
(self, index upper)subsetSizeMap
(self)Get 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.
subsetsOf
(self, e)Get the ids of subsets in which the element e is contained.
toSingleton
(self, index e)Creates a singleton set containing the element e and returns 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.)
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
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.
BFSEdgesFrom
(self, node start, callback)Experimental BFS search interface that passes edges that are part of the BFS tree to the callback
BFSfrom
(self, start, callback)Experimental BFS search interface
DFSEdgesFrom
(self, node start, callback)Experimental DFS search interface that passes edges that are part of the DFS tree to the callback
DFSfrom
(self, node start, callback)Experimental DFS search interface
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. Caution: It is not checked whether this edge already exists, thus it is possible to create multi-edges.
addNode
(self)Add a new node to the graph and return it.
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
degree
(self, u)Get the number of neighbors of v.
degreeIn
(self, u)degreeOut
(self, u)density
(self)Get the density of the graph.
double
edgeId
(self, node u, node v)edges
(self)Get list of edges as node pairs.
forEdges
(self, callback)Experimental edge iterator interface
forEdgesOf
(self, node u, callback)Experimental incident (outgoing) edge iterator interface
forInEdgesOf
(self, node u, callback)Experimental incident incoming edge iterator interface
forNodePairs
(self, callback)Experimental node pair iterator interface
forNodes
(self, callback)Experimental node iterator interface
forNodesInRandomOrder
(self, callback)Experimental node iterator interface
getCoordinate
(self, v)Get the coordinates of node v. Parameters ———- v : node
Node.
getName
(self)Get the name of the graph.
hasEdge
(self, u, v)Checks if undirected edge {u,`v`} exists in the graph.
hasEdgeIds
(self)Returns true 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.
increaseWeight
(self, u, v, w)Increase the weight of an edge. If the edge does not exist, it will be inserted.
indexEdges
(self, bool force=False)Assign integer ids to edges.
initCoordinates
(self)isDirected
(self)isIsolated
(self, u)If the node u is isolated
isWeighted
(self)merge
(self, Graph G)G : Graph
neighbors
(self, u)Get list of neighbors of u.
nodes
(self)Get list of all nodes.
numberOfEdges
(self)Get the number of edges in the graph.
numberOfNodes
(self)Get the number of nodes in the graph.
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.
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.
randomNeighbor
(self, u)Get a random neighbor of v and none if degree is zero.
randomNode
(self)Get a random node of the graph.
removeEdge
(self, u, v)Removes the undirected edge {u,`v`}.
removeNode
(self, u)Remove a node v and all incident edges from the graph.
Incoming as well as outgoing edges will be removed.
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.
setCoordinate
(self, v, value)Set the coordinates of node v. Parameters ———- v : node
Node.
setName
(self, name)Set name of graph to name.
setWeight
(self, u, v, w)Set the weight of an edge. If the edge does not exist, it will be inserted.
size
(self)Get the size of the graph.
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.
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.
toString
(self)Get 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.
transpose
(self)Return the transpose of this (directed) graph.
directed graph.
upperEdgeIdBound
(self)Get an upper bound for the edge ids in the graph
upperNodeIdBound
(self)Get 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.
weightedDegree
(self, v)Returns the weighted degree of v.
For directed graphs this is the sum of weights of all outgoing edges of v.
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.
addToSubset
(self, s, e)Add a (previously unassigned) element e to the set s.
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.
contains
(self, index e)Check if partition assigns a valid subset to the element e.
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.
getMembers
(self, s)Get the members of the subset s.
getName
(self)Get the human-readable identifier.
getSubsetIds
(self)Get the ids of nonempty subsets.
getVector
(self)Get the actual vector representing the partition data structure.
inSameSubset
(self, index e1, index e2)Check if two elements e1 and e2 belong to the same subset.
lowerBound
(self)Get a lower bound for the subset ids that have been assigned.
mergeSubsets
(self, index s, index t)Assigns the elements from both sets to a new set and returns the id of it.
moveToSubset
(self, index s, index e)Move the (previously assigned) element e to the set `s.
numberOfElements
(self)numberOfSubsets
(self)Get the current number of sets in this partition.
setName
(self, string name)Set a human-readable identifier name for the instance.
setUpperBound
(self, index upper)Sets an upper bound for the subset ids that can be assigned.
subsetOf
(self, e)Get the set (id) in which the element e is contained.
subsetSizeMap
(self)Get 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.
toSingleton
(self, index e)Creates a singleton set containing the element e.
upperBound
(self)Return an upper bound for the subset ids that have been assigned. (This is the maximum id + 1.)
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.
pattern: unix-style string pattern
fileformat: An element of the Format enumeration
some: restrict number of graphs to be read
“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.
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