networkit.distance

class networkit.distance.APSP(G)

Bases: networkit.base.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: networkit.distance.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.

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.

  • numberIterations (int, optional) – Number of iterations in each system.

  • omega (float, optional) – Attenuation factor in [0,1] influencing convergence speed.

  • norm (int, optional) – The norm factor of the extended algebraic distance.

  • withEdgeScores (bool, optional) – Calculate array of scores for edges {u,v} that equal ad(u,v)

distance()
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: networkit.distance.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.

  • storeNodesSortedByDistance (bool, optional) – Controls whether to store nodes sorted by distance.

  • 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: networkit.distance.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.

getHops()

Returns the distance (i.e., number of hops) from the source to the target node.

Returns

Number of hops from the source to the target node.

Return type

int

class networkit.distance.BidirectionalDijkstra(G, source, target, storePred=True)

Bases: networkit.distance.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: networkit.base.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).

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: networkit.base.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.

  • nSamples (int, optional) – Number of samples (influencing the quality of the output) used for diameter algorithm EstimatedSamples.

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: networkit.distance.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.

  • storeNodesSortedByDistance (bool, optional) – Controls whether to store nodes sorted by distance.

  • 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: networkit.distance.APSP

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

Parameters

G (networkit.Graph) – The graph.

update(ev)

Updates shortest paths with the edge insertion.

Parameters

ev (networkit.dynamics.GraphEvent) – A graph event.

updateBatch(batch)

Updates shortest paths with a batch of edge insertions.

Parameters

batch (list(networkit.dynamics.GraphEvent)) – List of graph events.

class networkit.distance.DynBFS(G, source)

Bases: networkit.distance.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: networkit.distance.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.DynSSSP(G, source, storePredecessors, target)

Bases: networkit.distance.SSSP

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.

update(ev)

Updates shortest paths with the edge insertion.

Parameters

ev (networkit.dynamics.GraphEvent) – A graph event.

updateBatch(batch)

Updates shortest paths with a batch of edge insertions.

Parameters

batch (list(networkit.dynamics.GraphEvent)) – List of graph events.

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: networkit.base.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: networkit.base.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: networkit.base.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: networkit.distance.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: networkit.distance.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: networkit.base.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: networkit.base.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: networkit.base.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).

  • 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.ReverseBFS(G, source, storePaths=True, storeNodesSortedByDistance=False, target=None)

Bases: networkit.distance.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.

  • storeNodesSortedByDistance (bool, optional) – Controls whether to store nodes sorted by distance.

  • 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: networkit.base.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: networkit.base.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: Falsy.

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: networkit.base.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

Returns

  • float – Number of nodes within a given radius.

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