Bases: Algorithm
All-Pairs Shortest-Paths algorithm (implemented running Dijkstra’s algorithm from each node, or BFS if G is unweighted). Computes all pairwise shortest-path distances in G.
G (networkit.Graph) – The graph.
Returns the length of the shortest path from source u to target v.
u (node) – Index of source node u.
v (node) – Index of target node v.
The distance from u to v. Returned value is of type int, if the graph is unweighted - otherwise the return type is float.
int or float
Returns a vector of vectors of distances between each node pair.
asarray (optional) – Return the result as a numpy array. Default: Falsy.
The shortest-path distances from each node to any other node in the graph.
list(list(float)) or np.ndarray
Bases: STSP
A* path-finding algorithm.
G (networkit.Graph) – The input graph.
heu (list(float)) – List of lower bounds of the distance of each node to the target.
source (int) – The source node.
target (int) – The target node.
storePred (bool, optional) – If True, the algorithm will also store the predecessors and reconstruct a shortest path from source and target. Default: True
Bases: object
Calculate the adamic adar similarity.
G (networkit.Graph) – The input graph.
Calculate the distance from node u to node v.
u (int) – Source node
v (int) – Target node
Distance from node u to node v.
float
Get the Adamic Adar similiraty score for every edge.
Adamic Adar similiraty score for every edge.
list(float)
Bases: object
Algebraic distance assigns a distance value to pairs of nodes according to their structural closeness in the graph. Algebraic distances will become small within dense subgraphs.
G (networkit.Graph) – The graph to calculate Jaccard distances for.
numberSystems (int, optional) – Number of vectors/systems used for algebraic iteration. Default: 10
numberIterations (int, optional) – Number of iterations in each system. Default: 30
omega (float, optional) – Attenuation factor in [0,1] influencing convergence speed. Default: 0.5
norm (int, optional) – The norm factor of the extended algebraic distance. Default: 0
withEdgeScores (bool, optional) – Calculate array of scores for edges {u,v} that equal ad(u,v). Default: False
Bases: object
Algorithm to compute all existing simple paths from a source node to a target node. The maximum length of the paths can be fixed through ‘cutoff’. CAUTION: This algorithm could take a lot of time on large networks (many edges), especially if the cutoff value is high or not specified.
More efficient path iterator. Iterates over all the simple paths.
callback (object) – Any callable object that takes the parameter path
Returns all the simple paths from source to target.
A list containing list of node indexes which represent all simple paths.
list(list(int))
Returns the number of simple paths.
The number of simple paths.
int
Bases: SSSP
Simple breadth-first search on a Graph from a given source.
G (networkit.Graph) – The graph.
source (int) – The source node of the breadth-first search.
storePaths (bool, optional) – Controls whether to store paths and number of paths. Default: True
storeNodesSortedByDistance (bool, optional) – Controls whether to store nodes sorted by distance. Default: False
target (int or None, optional) – Terminate search when the target has been reached. In default-mode, this target is set to None.
Bases: STSP
Implements a bidirectional breadth-first search on a graph from two given source and target nodes. Explores the graph from both the source and target nodes until the two explorations meet.
G (networkit.Graph) – The input graph.
source (int) – The source node.
target (int) – The target node.
storePred (bool, optional) – If True, the algorithm will also store the predecessors and reconstruct a shortest path from source and target. Default: True
Bases: STSP
Bidirectional implementation of the Dijkstra algorithm from two given source and target nodes. Explores the graph from both the source and target nodes until the two explorations meet.
Bases: Algorithm
Computes the Euclidean Commute Time Distance (ECTD) between each pair of nodes for an undirected unweighted graph.
CommuteTimeDistance(G)
G (networkit.Graph) – The graph.
tol (float, optional) – Tolerance for computation (higher tolerance leads to faster running times). Default: 0.1
Returns the ECTD between node u and node v.
u (int) – Index of node u.
v (int) – Index of node v.
ECTD between node u and v.
float
Computes approximation of the ECTD.
Computes approximation (in parallel) of the ECTD.
Returns the ECTD between node u and node v, without preprocessing.
u (int) – Index of node u.
v (int) – Index of node v.
ECTD (without preprocessing) between node u and v.
float
Returns the sum of the ECTDs from u, without preprocessing.
u (int) – Index of node u.
Sum of the ECTDs from u, without preprocessing.
float
Bases: Algorithm
Calculate the Diameter of the graph based different possible algorithms.
Parameter algo
can be one of the following:
networkit.distance.DiameterAlgo.AUTOMATIC
networkit.distance.DiameterAlgo.EXACT
networkit.distance.DiameterAlgo.ESTIMATED_RANGE
networkit.distance.DiameterAlgo.ESTIMATED_SAMPLES
networkit.distance.DiameterAlgo.ESTIMATED_PEDANTIC
G (networkit.Graph) – The input graph.
algo (networkit.distance.DiameterAlgo, optional) – Algorithm which should be used for diameter computation. Default: networkit.distance.DiameterAlgo.AUTOMATIC
error (float, optional) – Possible error used for diameter algorithm EstimatedRange. Default: -1
nSamples (int, optional) – Number of samples (influencing the quality of the output) used for diameter algorithm EstimatedSamples. Default: 0
Diameter of the graph.
float
Bases: object
Bases: SSSP
Dijkstra’s SSSP algorithm. Returns list of weighted distances from node source, i.e. the length of the shortest path from source to any other node.
G (networkit.Graph) – The graph.
source (int) – The source node of the Dijkstra search.
storePaths (bool, optional) – Controls whether to store paths and number of paths. Default: True
storeNodesSortedByDistance (bool, optional) – Controls whether to store nodes sorted by distance. Default: False
target (int or None, optional) – Terminate search when the target has been reached. In default-mode, this target is set to None.
Bases: APSP
, DynAlgorithm
All-Pairs Shortest-Paths algorithm for dynamic graphs. Computes all pairwise shortest-path distances in G.
G (networkit.Graph) – The graph.
Bases: DynSSSP
Dynamic version of BFS.
G (networkit.Graph) – The graph.
source (int) – The source node of the breadth-first search.
Bases: DynSSSP
Dynamic version of Dijkstra. Create DynDijkstra for G and a source node.
G (networkit.Graph) – The graph.
source (int) – The source node of the Dijkstra search.
Bases: Algorithm
, DynAlgorithm
Dynamic Pruned Landmark Labeling algorithm based on the paper “Fully Dynamic 2-Hop Cover Labeling “ from D’Angelo et al., ACM JEA 2019. The algorithm computes distance labels by performing pruned breadth-first searches from each vertex. Distance labels can be updated efficiently after edge insertions. Note: this algorithm only works for unweighted graphs and only supports edge insertions.
G (networkit.Graph) – The input graph.
Returns the shortest-path distance between the two nodes.
u (node) – Source node.
v (node) – Target node.
The shortest-path distances from the source node to the target node.
int
Bases: SSSP
, DynAlgorithm
Base class for single source shortest path algorithms in dynamic graphs.
Returns True or False depending on whether the node previoulsy specified with setTargetNode(t) has been modified by the update or not.
Indicator for whether the target node was modified or not.
bool
Set a target node to be observed during the update. If a node t is set as target before the update, the function modified() will return True or False depending on whether node t has been modified by the update.
t (int) – Target node to be observed during update.
Bases: object
The eccentricity of a node u is defined as the distance to the farthest node from node u. In other words, it is the longest shortest-path starting from node u.
Get eccentricity value of node v from graph G.
G (networkit.Graph) – The input graph.
First index is the farthest node v from u, and the second index is the length of the shortest path from u to v.
tuple(int, float)
Bases: Algorithm
Calculates the effective diameter of a graph. The effective diameter is defined as the number of edges on average to reach a given ratio of all other nodes.
G (networkit.Graph) – The graph.
ratio (float, optional) – The percentage of nodes that shall be within stepwidth; default = 0.9
The effective diameter
float
Bases: Algorithm
Calculates the effective diameter of a graph. The effective diameter is defined as the number of edges on average to reach a given ratio of all other nodes.
Implementation after the ANF algorithm presented in the paper “A Fast and Scalable Tool for Data Mining in Massive Graphs”[1]
[1] by Palmer, Gibbons and Faloutsos which can be found here: http://www.cs.cmu.edu/~christos/PUBLICATIONS/kdd02-anf.pdf
G (networkit.Graph) – The graph.
ratio (float, optional) – The percentage of nodes that shall be within stepwidth, default = 0.9
k (int, optional) – Number of parallel approximations, bigger k -> longer runtime, more precise result; default = 64
r (int, optional) – Number of additional bits, important in tiny graphs; default = 7
The approximated effective diameter
float
Bases: Algorithm
Computes an approxmation of the hop-plot of a given graph. The hop-plot is the set of pairs (d, g(g)) for each natural number d and where g(d) is the fraction of connected node pairs whose shortest connecting path has length at most d.
Implementation after the ANF algorithm presented in the paper “A Fast and Scalable Tool for Data Mining in Massive Graphs”[1]
[1] by Palmer, Gibbons and Faloutsos which can be found here: http://www.cs.cmu.edu/~christos/PUBLICATIONS/kdd02-anf.pdf
G (networkit.Graph) – The graph.
maxDistance (float, optional) – Maximum distance between considered nodes set to 0 or negative to get the hop-plot for the entire graph so that each node can reach each other node.
k (int, optional) – Number of parallel approximations, bigger k -> longer runtime, more precise result; default = 64
r (int, optional) – Number of additional bits, important in tiny graphs; default = 7
Returns the approximated hop-plot of the graph.
Number of connected nodes for each distance
dict(int :
float)
Bases: object
The Jaccard distance measure assigns to each edge the jaccard coefficient of the neighborhoods of the two adjacent nodes.
Get the Jaccard distance for every edge.
Jaccard distance for every edge.
list(float)
Bases: object
The Jaccard similarity measure assigns to each edge (1 - the jaccard coefficient of the neighborhoods of the two adjacent nodes).
G (networkit.Graph) – The graph to calculate Jaccard similarities for.
triangles (list(int)) – Previously calculated edge triangle counts.
Get the Jaccard similiraty score for every edge.
Jaccard similiraty score for every edge.
list(float)
Bases: STSP
Simple breadth-first search on a Graph from a given source to multiple targets.
G (networkit.Graph) – The graph.
source (int) – The source node of the breadth-first search.
targets (list(int)) – List of target nodes.
Bases: STSP
Dijkstra’s SSSP algorithm from a single source node to multiple target nodes.
G (networkit.Graph) – The graph.
source (int) – The source node of the Dijkstra search.
targets (list(int)) – List of target nodes.
Bases: Algorithm
Computes the neighborhood function exactly. The neighborhood function N of a graph G for a given distance t is defined as the number of node pairs (u,v) that can be reached within distance t.
G (networkit.Graph) – The graph.
Returns the neighborhood function of the graph.
The i-th element denotes the number of node pairs that have a distance at most (i+1).
list(int)
Bases: Algorithm
Computes an approximation of the neighborhood function. The neighborhood function N of a graph G for a given distance t is defined as the number of node pairs (u,v) that can be reached within distance t.
Implementation after the ANF algorithm presented in the paper “A Fast and Scalable Tool for Data Mining in Massive Graphs”[1]
[1] by Palmer, Gibbons and Faloutsos which can be found here: http://www.cs.cmu.edu/~christos/PUBLICATIONS/kdd02-anf.pdf
G (networkit.Graph) – The graph.
k (int, optional) – Number of approximations, bigger k -> longer runtime, more precise result; default = 64
r (int, optional) – Number of additional bits, important in tiny graphs; default = 7
Returns the neighborhood function of the graph.
The i-th element denotes the number of node pairs that have a distance at most (i+1).
list(int)
Bases: Algorithm
Computes a heuristic of the neighborhood function. The algorithm runs nSamples breadth-first searches and scales the results up to the actual amount of nodes.
Parameter strategy
can be one of the following:
networkit.distance.SelectionStrategy.RANDOM
networkit.distance.SelectionStrategy.SPLIT
G (networkit.Graph) – The graph.
nSamples (int, optional) – The amount of samples, set to zero for heuristic of max(sqrt(m), 0.15*n). Default: 0
strategy (networkit.distance.SelectionStrategy, optional) – The strategy to select the samples, accepts RANDOM (0) or SPLIT (1). Default: networkit.distance.SelectionStrategy.SPLIT
Returns the neighborhood function of the graph.
The i-th element denotes the number of node pairs that have a distance at most (i+1).
list(int)
Bases: Algorithm
Pruned Landmark Labeling algorithm based on the paper “Fast exact shortest-path distance queries on large networks by pruned landmark labeling” from Akiba et al., ACM SIGMOD 2013. The algorithm computes distance labels by performing pruned breadth-first searches from each vertex. Labels are used to quickly retrieve shortest-path distances between node pairs. Note: this algorithm only works for unweighted graphs.
G (networkit.Graph) – The input graph.
Returns the shortest-path distance between the two nodes.
u (node) – Source node.
v (node) – Target node.
The shortest-path distances from the source node to the target node.
int
Bases: SSSP
Simple reverse breadth-first search on a Graph from a given source.
G (networkit.Graph) – The graph.
source (int) – The source node of the breadth-first search.
storePaths (bool, optional) – Controls whether to store paths and number of paths. Default: True
storeNodesSortedByDistance (bool, optional) – Controls whether to store nodes sorted by distance. Default: False
target (int or None, optional) – Terminate search when the target has been reached. In default-mode, this target is set to None.
Bases: Algorithm
Some-Pairs Shortest-Paths algorithm (implemented running Dijkstra’s algorithm from each source node, or BFS if G is unweighted). Computes pairwise shortest-path distances from the source nodes to all the nodes in G.
G (networkit.Graph) – The graph.
sources (list(int)) – Set of source nodes.
Returns the length of the shortest path from source u to target v.
u (node) – Index of source node.
v (node) – Index of target node.
The distance from u to v.
float
Sets the source nodes.
sources (list(int)) – List of the new source nodes.
Sets the target nodes.
targets (list(int)) – List of the new target nodes.
Bases: Algorithm
Base class for single source shortest path algorithms.
Returns the distance from the source node to t.
t (int) – Target node.
Distance from the source node to t.
float
Returns a list of weighted distances from the source node, i.e. the length of the shortest path from the source node to any other node.
asarray (optional) – Return the result as a numpy array. Default: None
The weighted distances from the source node to any other node in the graph.
list or np.ndarray
Returns a list of nodes ordered in increasing distance from the source.
For this functionality to be available, storeNodesSortedByDistance has to be set to true in the constructor. There are no guarantees regarding the ordering of two nodes with the same distance to the source.
Nodes ordered in increasing distance from the source.
list
Returns a shortest path from source to t and an empty path if source and t are not connected.
t (int) – Target node.
forward (bool, optional) – If True (default) the path is directed from source to t, otherwise the path is reversed.
A shortest path from source to t or an empty path.
list
Returns all shortest paths from source to t and an empty set if source and t are not connected.
t (int) – Target node.
forward (bool, optional) – If True (default) the path is directed from source to t, otherwise the path is reversed.
All shortest paths from source node to target node t.
Returns the predecessor nodes of t on all shortest paths from source to t.
t (int) – Target node.
The predecessors of t on all shortest paths from source to t.
list
Returns the number of paths from the source node to t.
t (int) – Target node.
The number of paths from the source node to t.
int
Sets a new source node.
s (int) – New source node.
Sets a new target node.
t (int) – New target node.
Bases: Algorithm
Abstract base class for source-target shortest path algorithms.
Returns the distance from the source node to the target node
The distance from source to the target node.
float
In case of multiple target nodes: returns the distance from the source node to the target nodes.
Distances from the source to the target nodes.
list(float)
Returns a shortest path from the source node to the target node (without including them). Note: the shortest path can be constructed only if the algorithm is executed with @a storePred set to true.
A shortest path from the source node to the target node.
list(int)
Returns the predecessor nodes from the target node to the source node, Note: predecessors are stored only if the algorithm is executed with storePred set to true.
The list of predecessors from a target to a source.
list(int)
Sets the source node.
newSource (int) – The new source node.
Sets the target node.
newTarget (int) – The new target node.
Sets multiple target nodes.
newTargets (list(int)) – The new target nodes.
Bases: object
The volume of a graph and its meaning is explained in the following publication:
Franz-Benjamin Mocnik: “The Polynomial Volume Law of Complex Networks in the Context of Local and Global Optimization”, Scientific Reports 8(11274) 2018. doi: 10.1038/s41598-018-29131-0
Number of nodes within a given radius. If the radius is a list containing many radii, a list containing the number for every radius is returned.
G (networkit.Graph) – the graph
r (float) – the radius (or radii)
samples (int, optional) – The number of samples. Default: 500
float – Number of nodes within a given radius.
list(float) – Number of nodes within every given radii.