networkit.distance¶

class networkit.distance.APSP(G)¶

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.

Parameters:: G (networkit.Graph) – The graph.

getDistance(u, v)¶

Returns the length of the shortest path from source u to target v.

Parameters:

u (node) – Index of source node u.
v (node) – Index of target node v.

Returns:

The distance from u to v. Returned value is of type int, if the graph is unweighted - otherwise the return type is float.

Return type:

int or float

getDistances(asarray=None)¶

Returns a vector of vectors of distances between each node pair.

Parameters:: asarray (optional) – Return the result as a numpy array. Default: Falsy.
Returns:: The shortest-path distances from each node to any other node in the graph.
Return type:: list(list(float)) or np.ndarray

class networkit.distance.AStar(G, heu, source, target, storePred=True)¶

Bases: STSP

A* path-finding algorithm.

Parameters:

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

class networkit.distance.AdamicAdarDistance(G)¶

Bases: object

Calculate the adamic adar similarity.

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

distance(self, u, v)¶

Calculate the distance from node u to node v.

Parameters:

u (int) – Source node
v (int) – Target node

Returns:

Distance from node u to node v.

Return type:

float

getAttribute()¶

Get the Adamic Adar similiraty score for every edge.

Returns:: Adamic Adar similiraty score for every edge.
Return type:: list(float)

preprocess()¶

class networkit.distance.AlgebraicDistance(G, numberSystems=10, numberIterations=30, omega=0.5, norm=0, withEdgeScores=False)¶

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.

Parameters:

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

distance(u, v)¶

getEdgeScores()¶

preprocess()¶

class networkit.distance.AllSimplePaths(G, source, target, cutoff=None)¶

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.

forAllSimplePaths(callback)¶

More efficient path iterator. Iterates over all the simple paths.

Parameters:: callback (object) – Any callable object that takes the parameter path

getAllSimplePaths()¶

Returns all the simple paths from source to target.

Returns:: A list containing list of node indexes which represent all simple paths.
Return type:: list(list(int))

numberOfSimplePaths()¶

Returns the number of simple paths.

Returns:: The number of simple paths.
Return type:: int

run()¶

class networkit.distance.BFS(G, source, storePaths=True, storeNodesSortedByDistance=False, target=None)¶

Bases: SSSP

Simple breadth-first search on a Graph from a given source.

Parameters:

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.

class networkit.distance.BidirectionalBFS(G, source, target, storePre=True)¶

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.

Parameters:

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

class networkit.distance.BidirectionalDijkstra(G, source, target, storePred=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.

class networkit.distance.CommuteTimeDistance(G, tol=0.1)¶

Bases: Algorithm

Computes the Euclidean Commute Time Distance (ECTD) between each pair of nodes for an undirected unweighted graph.

CommuteTimeDistance(G)

Parameters:

G (networkit.Graph) – The graph.
tol (float, optional) – Tolerance for computation (higher tolerance leads to faster running times). Default: 0.1

distance(u, v)¶

Returns the ECTD between node u and node v.

Parameters:

u (int) – Index of node u.
v (int) – Index of node v.

Returns:

ECTD between node u and v.

Return type:

float

runApproximation()¶: Computes approximation of the ECTD.

runParallelApproximation()¶: Computes approximation (in parallel) of the ECTD.

runSinglePair(u, v)¶

Returns the ECTD between node u and node v, without preprocessing.

Parameters:

u (int) – Index of node u.
v (int) – Index of node v.

Returns:

ECTD (without preprocessing) between node u and v.

Return type:

float

runSingleSource(u)¶

Returns the sum of the ECTDs from u, without preprocessing.

Parameters:: u (int) – Index of node u.
Returns:: Sum of the ECTDs from u, without preprocessing.
Return type:: float

class networkit.distance.Diameter(G, algo=networkit.DiameterAlgo.AUTOMATIC, error=-1., nSamples=0)¶

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

Parameters:

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

getDiameter()¶

Returns:: Diameter of the graph.
Return type:: float

class networkit.distance.DiameterAlgo¶

Bases: object

AUTOMATIC = 0¶

Automatic = 0¶

ESTIMATED_PEDANTIC = 4¶

ESTIMATED_RANGE = 2¶

ESTIMATED_SAMPLES = 3¶

EXACT = 1¶

EstimatedPedantic = 4¶

EstimatedRange = 2¶

EstimatedSamples = 3¶

Exact = 1¶

class networkit.distance.Dijkstra(G, source, storePaths=True, storeNodesSortedByDistance=False, target=None)¶

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.

Parameters:

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.

class networkit.distance.DynAPSP(G)¶

Bases: APSP, DynAlgorithm

All-Pairs Shortest-Paths algorithm for dynamic graphs. Computes all pairwise shortest-path distances in G.

Parameters:: G (networkit.Graph) – The graph.

class networkit.distance.DynBFS(G, source)¶

Bases: DynSSSP

Dynamic version of BFS.

Parameters:

G (networkit.Graph) – The graph.
source (int) – The source node of the breadth-first search.

class networkit.distance.DynDijkstra(G, source)¶

Bases: DynSSSP

Dynamic version of Dijkstra. Create DynDijkstra for G and a source node.

Parameters:

G (networkit.Graph) – The graph.
source (int) – The source node of the Dijkstra search.

class networkit.distance.DynPrunedLandmarkLabeling(G)¶

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.

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

query(u, v)¶

Returns the shortest-path distance between the two nodes.

Parameters:

u (node) – Source node.
v (node) – Target node.

Returns:

The shortest-path distances from the source node to the target node.

Return type:

int

class networkit.distance.DynSSSP(G, source, storePredecessors, target)¶

Bases: SSSP, DynAlgorithm

Base class for single source shortest path algorithms in dynamic graphs.

modified()¶

Returns True or False depending on whether the node previoulsy specified with setTargetNode(t) has been modified by the update or not.

Returns:: Indicator for whether the target node was modified or not.
Return type:: bool

setTargetNode(t)¶

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.

Parameters:: t (int) – Target node to be observed during update.

class networkit.distance.Eccentricity¶

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.

static getValue(G, v)¶

Get eccentricity value of node v from graph G.

Parameters:: G (networkit.Graph) – The input graph.
Returns:: First index is the farthest node v from u, and the second index is the length of the shortest path from u to v.
Return type:: tuple(int, float)

class networkit.distance.EffectiveDiameter(G, ratio=0.9)¶

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.

Parameters:

G (networkit.Graph) – The graph.
ratio (float, optional) – The percentage of nodes that shall be within stepwidth; default = 0.9

getEffectiveDiameter()¶

Returns:: The effective diameter
Return type:: float

class networkit.distance.EffectiveDiameterApproximation(G, ratio=0.9, k=64, r=7)¶

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

Parameters:

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

getEffectiveDiameter()¶

Returns:: The approximated effective diameter
Return type:: float

class networkit.distance.HopPlotApproximation(G, maxDistance=0, k=64, r=7)¶

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

Parameters:

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

getHopPlot()¶

Returns the approximated hop-plot of the graph.

Returns:: Number of connected nodes for each distance
Return type:: dict(int : float)

class networkit.distance.JaccardDistance(G, triangles)¶

Bases: object

The Jaccard distance measure assigns to each edge the jaccard coefficient of the neighborhoods of the two adjacent nodes.

getAttribute()¶

Get the Jaccard distance for every edge.

Returns:: Jaccard distance for every edge.
Return type:: list(float)

class networkit.distance.JaccardSimilarityAttributizer(G, triangles)¶

Bases: object

The Jaccard similarity measure assigns to each edge (1 - the jaccard coefficient of the neighborhoods of the two adjacent nodes).

Parameters:

G (networkit.Graph) – The graph to calculate Jaccard similarities for.
triangles (list(int)) – Previously calculated edge triangle counts.

getAttribute()¶

Get the Jaccard similiraty score for every edge.

Returns:: Jaccard similiraty score for every edge.
Return type:: list(float)

class networkit.distance.MultiTargetBFS(G, source, targets)¶

Bases: STSP

Simple breadth-first search on a Graph from a given source to multiple targets.

Parameters:

G (networkit.Graph) – The graph.
source (int) – The source node of the breadth-first search.
targets (list(int)) – List of target nodes.

class networkit.distance.MultiTargetDijkstra(G, source, targets)¶

Bases: STSP

Dijkstra’s SSSP algorithm from a single source node to multiple target nodes.

Parameters:

G (networkit.Graph) – The graph.
source (int) – The source node of the Dijkstra search.
targets (list(int)) – List of target nodes.

class networkit.distance.NeighborhoodFunction(G)¶

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.

Parameters:: G (networkit.Graph) – The graph.

getNeighborhoodFunction()¶

Returns the neighborhood function of the graph.

Returns:: The i-th element denotes the number of node pairs that have a distance at most (i+1).
Return type:: list(int)

class networkit.distance.NeighborhoodFunctionApproximation(G, k=64, r=7)¶

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

Parameters:

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

getNeighborhoodFunction()¶

Returns the neighborhood function of the graph.

Returns:: The i-th element denotes the number of node pairs that have a distance at most (i+1).
Return type:: list(int)

class networkit.distance.NeighborhoodFunctionHeuristic(G, nSamples=0, strategy=SelectionStrategy.SPLIT)¶

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

Parameters:

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

getNeighborhoodFunction()¶

Returns the neighborhood function of the graph.

Returns:: The i-th element denotes the number of node pairs that have a distance at most (i+1).
Return type:: list(int)

class networkit.distance.PrunedLandmarkLabeling(G)¶

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.

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

query(u, v)¶

Returns the shortest-path distance between the two nodes.

Parameters:

u (node) – Source node.
v (node) – Target node.

Returns:

The shortest-path distances from the source node to the target node.

Return type:

int

class networkit.distance.ReverseBFS(G, source, storePaths=True, storeNodesSortedByDistance=False, target=None)¶

Bases: SSSP

Simple reverse breadth-first search on a Graph from a given source.

Parameters:

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.

class networkit.distance.SPSP(G, sources)¶

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.

Parameters:

G (networkit.Graph) – The graph.
sources (list(int)) – Set of source nodes.

getDistance(u, v)¶

Returns the length of the shortest path from source u to target v.

Parameters:

u (node) – Index of source node.
v (node) – Index of target node.

Returns:

The distance from u to v.

Return type:

float

setSources(sources)¶

Sets the source nodes.

Parameters:: sources (list(int)) – List of the new source nodes.

setTargets(targets)¶

Sets the target nodes.

Parameters:: targets (list(int)) – List of the new target nodes.

class networkit.distance.SSSP(G, source, storePaths, storeNodesSortedByDistance, target)¶

Bases: Algorithm

Base class for single source shortest path algorithms.

distance(t)¶

Returns the distance from the source node to t.

Parameters:: t (int) – Target node.
Returns:: Distance from the source node to t.
Return type:: float

getDistances(asarray=None)¶

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.

Parameters:: asarray (optional) – Return the result as a numpy array. Default: None
Returns:: The weighted distances from the source node to any other node in the graph.
Return type:: list or np.ndarray

getNodesSortedByDistance()¶

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.

Returns:: Nodes ordered in increasing distance from the source.
Return type:: list

getPath(t, forward=True)¶

Returns a shortest path from source to t and an empty path if source and t are not connected.

Parameters:

t (int) – Target node.
forward (bool, optional) – If True (default) the path is directed from source to t, otherwise the path is reversed.

Returns:

A shortest path from source to t or an empty path.

Return type:

list

getPaths(t, forward=True)¶

Returns all shortest paths from source to t and an empty set if source and t are not connected.

Parameters:

t (int) – Target node.
forward (bool, optional) – If True (default) the path is directed from source to t, otherwise the path is reversed.

Return type:

All shortest paths from source node to target node t.

getPredecessors(t)¶

Returns the predecessor nodes of t on all shortest paths from source to t.

Parameters:: t (int) – Target node.
Returns:: The predecessors of t on all shortest paths from source to t.
Return type:: list

numberOfPaths(t)¶

Returns the number of paths from the source node to t.

Parameters:: t (int) – Target node.
Returns:: The number of paths from the source node to t.
Return type:: int

setSource(s)¶

Sets a new source node.

Parameters:: s (int) – New source node.

setTarget(t)¶

Sets a new target node.

Parameters:: t (int) – New target node.

class networkit.distance.STSP(G, source, target, storePred)¶

Bases: Algorithm

Abstract base class for source-target shortest path algorithms.

getDistance()¶

Returns the distance from the source node to the target node

Returns:: The distance from source to the target node.
Return type:: float

getDistances()¶

In case of multiple target nodes: returns the distance from the source node to the target nodes.

Returns:: Distances from the source to the target nodes.
Return type:: list(float)

getPath()¶

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.

Returns:: A shortest path from the source node to the target node.
Return type:: list(int)

getPredecessors()¶

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.

Returns:: The list of predecessors from a target to a source.
Return type:: list(int)

setSource(newSource)¶

Sets the source node.

Parameters:: newSource (int) – The new source node.

setTarget(newTarget)¶

Sets the target node.

Parameters:: newTarget (int) – The new target node.

setTargets(newTargets)¶

Sets multiple target nodes.

Parameters:: newTargets (list(int)) – The new target nodes.

class networkit.distance.SelectionStrategy¶

Bases: object

RANDOM = 0¶

SPLIT = 1¶

class networkit.distance.Volume¶

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

static volume(G, r, samples=500)¶

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.

Parameters:

G (networkit.Graph) – the graph
r (float) – the radius (or radii)
samples (int, optional) – The number of samples. Default: 500

Returns:

float – Number of nodes within a given radius.
list(float) – Number of nodes within every given radii.