networkit.centrality¶

class networkit.centrality.ApproxBetweenness(G, epsilon=0.01, delta=0.1, universalConstant=1.0)

Bases: Centrality

Approximation of betweenness centrality according to algorithm described in Matteo Riondato and Evgenios M. Kornaropoulos: Fast Approximation of Betweenness Centrality through Sampling

The algorithm approximates the betweenness of all vertices so that the scores are within an additive error epsilon with probability at least $$(1- delta)$$. The values are normalized by default. The run() method takes O(m) time per sample, where m is the number of edges of the graph. The number of samples is proportional to universalConstant/epsilon^2. Although this algorithm has a theoretical guarantee, the algorithm implemented in Estimate Betweenness usually performs better in practice. Therefore, we recommend to use EstimateBetweenness if no theoretical guarantee is needed.

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

• epsilon (double, optional) – Maximum additive error. Default: 0.01

• delta (double, optional) – Probability that the values are within the error guarantee. Default: 0.1

• universalConstant (double, optional) – The universal constant to be used in computing the sample size. It is 1 by default. Some references suggest using 0.5, but there is no guarantee in this case. Default: 1.0

class networkit.centrality.ApproxCloseness(G, nSamples, epsilon=0.1, normalized=False, type=networkit.centrality.ClosenessType.OUTBOUND)

Bases: Centrality

Approximation of closeness centrality according to algorithm described in Cohen et al., Computing Classic Closeness Centrality, at Scale.

The algorithm approximates the closeness of all nodes in both directed and undirected graphs using a hybrid estimator. First, it takes nSamples samples. For these sampled nodes, the closeness is computed exactly. The pivot of each of the remaining nodes is the closest sampled node to it. If a node lies very close to its pivot, a sampling approach is used. Otherwise, a pivoting approach is used. Notice that the input graph has to be connected.

Parameter type can be one of the following:

• networkit.centrality.ClosenessType.INBOUND

• networkit.centrality.ClosenessType.OUTBOUND

• networkit.centrality.ClosenessType.SUM

Parameters:
• G (networkit.Graph) – Input graph (undirected).

• nSamples (int) – User defined number of samples.

• epsilon (float, optional) – Parameter used for the error guarantee; it is also used to control when to use sampling and when to use pivoting. Default: 0.1

• normalized (bool, optional) – Normalize centrality values in interval [0,1]. Default: False

• type (networkit.centrality.ClosenessType, optional) – Use in- or outbound centrality or the sum of both (see paper) for computing closeness on directed graph. If G is undirected, this can be ignored. Default: networkit.centrality.ClosenessType.OUTBOUND

getSquareErrorEstimates()

Return a list containing the square error estimates for all nodes.

Returns:

A list of square error estimate values.

Return type:

list(float)

class networkit.centrality.ApproxElectricalCloseness(G, eps=0.1, kappa=0.3)

Bases: Centrality

Approximates the electrical closeness of all the vertices of the graph by approximating the diagonal of the laplacian’s pseudoinverse of G. Every element of the diagonal is guaranteed to have a maximum absolute error of eps. Based on “Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis”, Angriman et al., ESA 2020. The algorithm does two steps: solves a linear system and samples uniform spanning trees (USTs). The parameter kappa balances the tolerance of solver for the linear system and the number of USTs to be sampled. A high value of kappa raises the tolerance (solver converges faster) but more USTs need to be sampled, vice versa for a low value of kappa.

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

• eps (float, optional) – Maximum absolute error of the elements in the diagonal. Default: 0.1

• kappa (float, optional) – Balances the tolerance of the solver for the linear system and the number of USTs to be sampled. Default: 0.3

computeExactDiagonal(tol=1e-9)

Compute and return the nearly-exact values of the diagonal of the laplacian’s pseudoinverse. The values are computed by solving $$Lx = e_u - 1 / n$$ for every vertex u of the graph with a LAMG solver.

Parameters:

tol (float) – Tolerance for the LAMG solver. Default: 1e-9

Returns:

Nearly-exact values of the diagonal of the laplacian’s pseudoinverse.

Return type:

list(float)

getDiagonal()

Return an epsilon-approximation of the diagonal of the laplacian’s pseudoinverse.

Returns:

Approximation of the diagonal of the laplacian’s pseudoinverse.

Return type:

list(float)

class networkit.centrality.ApproxGroupBetweenness(G, groupSize, epsilon)

Bases: Algorithm

Constructs the ApproxGroupBetweenness class for a given undirected Graph G.

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

• groupSize (int) – The desired size of the group.

• epsilon (float) – Determines the accuracy of the approximation.

groupMaxBetweenness()

Get a vector of nodes containing the set of nodes with apporoximated maximum group betweenness.

Returns:

The group of nodes with highest approximated group betweenness.

Return type:

list(int)

scoreOfGroup(group)

Returns the score of the given group.

Parameters:

group (list(int)) – Set of nodes.

Returns:

The score of the given group.

Return type:

int

class networkit.centrality.ApproxSpanningEdge(G, eps=0.1)

Bases: Algorithm

Computes an epsilon-approximation of the spanning edge centrality of every edge of the input graph with probability $$(1 - 1/n)$$, based on “Efficient Algorithms for Spanning Tree Centrality”, Hayashi et al., IJCAI, 2016. This implementation also supports multi-threading.

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

• eps (float, optional) – Maximum additive error. Default: 0.1

scores()

Return the spanning edge approximation for each edge of the graph in ascending edge ID order.

Returns:

Spanning edge approximation for each edge of the input graph.

Return type:

list

class networkit.centrality.Betweenness(G, normalized=False, computeEdgeCentrality=False)

Bases: Centrality

Constructs the Betweenness class for the given Graph G. If the betweenness scores should be normalized, then set normalized to True. The run() method takes O(nm) time, where n is the number of nodes and m is the number of edges of the graph.

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

• normalized (bool, optional) – Set this parameter to True if scores should be normalized in the interval [0,1]. Default: False

• computeEdgeCentrality (bool, optional) – Set this to true if edge betweenness scores should be computed as well. Default: False

edgeScores()

Get a vector containing the betweenness score for each edge in the graph in ascending edge ID order.

Returns:

The betweenness scores calculated by run().

Return type:

list(float)

class networkit.centrality.Centrality

Bases: Algorithm

Abstract base class for centrality measures

centralization()

Compute the centralization of a network with respect to some centrality measure. The centralization of any network is a measure of how central its most central node is in relation to how central all the other nodes are. Centralization measures then (a) calculate the sum in differences in centrality between the most central node in a network and all other nodes; and (b) divide this quantity by the theoretically largest such sum of differences in any network of the same size.

Returns:

Centralization value.

Return type:

float

maximum()

Return the maximum theoretical centrality score.

Returns:

The maximum theoretical centrality score for the given graph.

Return type:

float

ranking()

Returns the ranking of nodes according to their score.

Returns:

A list of pairs sorted into descending order. Each pair contains a node and the corresponding score

Return type:

list(tuple(int, float))

score(v)

Returns the score of node v for the centrality algorithm.

Parameters:

v (int) – Node index.

Returns:

The score of node v.

Return type:

float

scores()

Returns the scores of all nodes for the centrality algorithm.

Returns:

The list of all scores.

Return type:

list(float)

class networkit.centrality.Closeness(G, normalized, checkConnectedness) Closeness(G, normalized, variant)
class networkit.centrality.Closeness(G, normalized, variant)

Bases: Centrality

Constructs the Closeness class for the given Graph G. If the Closeness scores should not be normalized, set normalized to False. The run() method takes O(nm) time, where n is the number of nodes and m is the number of edges of the graph.

Parameter variant can be one of the following:

• networkit.centrality.ClosenessVariant.STANDARD

• networkit.centrality.ClosenessVariant.GENERALIZED

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

• normalized (bool) – Set this parameter to False if scores should not be normalized into an interval of [0,1]. Normalization only works for unweighted graphs.

• checkConnectedness (bool) – Set this parameter to True to also check if the graph is connected before computing closeness. Set this parameter to False to not check if the graph is connected (note: the standard definition of closeness works for connected graphs, choose this if the input graph is known to be connected).

• ClosenessVariant (networkit.centrality.ClosenessVariant) – Set this parameter to networkit.centrality.ClosenessVariant.Standard to use the standard definition of closeness, that is defined for connected graphs only; in this case, checkConnectedness is automatically set to True. Set this parameter to networkit.centrality.ClosenessVariant.Generalized to use the generalized definition of closeness, that is defined for also non-connected graphs; in this case, checkConnectedness is automatically set to False.

class networkit.centrality.ComplexPaths(G, threshold, mode, start)

Bases: Algorithm

The ComplexPathAlgorithm analysis the spread of complex contagions in a given graph. Returns the complex contagion paths of a given phenomenon (determined by the threshold) for single nodes or the entire graph, according to: [ Guilbeault, D., Centola, D. Topological measures for

identifying and predicting the spread of complex contagions. Nat Commun 12, 4430 (2021). https://doi.org/10.1038/s41467-021-24704-6 ]

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

• threshold (int) – The complex path width: minimal number of neighbors.

:param Parameter mode can be one of the following: :param - ComplexPathMode.allNodes: from every start node(default). :type - ComplexPathMode.allNodes: Calculate complex path lengths :param - ComplexPathMode.singleNode: from node start. :type - ComplexPathMode.singleNode: Calculate complex path graph :param start: Start node for ComplexPathMode.singleNode. :type start: node

Returns all nodes in the complex subgraph with at least threshold neighbors (those who are adopted/infected when starting in start).

Returns:

A vector of all adopted/infected nodes.

Return type:

list(int)

getComplexGraph()

Returns complex path (sub)graph of G starting in the node start. Only available when called in mode ComplexPathMode.SINGLE_NODE.

Return type:

Graph

getPLci()

Returns complex path lengths for every node in G either with absolute length, or scaled to [0,1] when normalize() was called before run(). Only available when called in mode ComplexPathMode.ALL_NODES.

Returns:

A vector containing complex path lengths for all nodes.

Return type:

list(float)

normalize()

When called before run() all complex path lengths returned by getPLci() are scaled to [0,1]. Only available when called in mode ComplexPathMode.ALL_NODES.

class networkit.centrality.CoreDecomposition(G, normalized=False, enforceBucketQueueAlgorithm=False, storeNodeOrder=False)

Bases: Centrality

Computes k-core decomposition of a graph. The graph may not contain self-loops.

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

• normalized (bool, optional) – Divide each core number by the maximum degree. Default: False

• enforceBucketQueueAlgorithm (bool, optional) – Enforce switch to sequential algorithm. Default: False

• storeNodeOrder (bool, optional) – If set to True, the order of the nodes in ascending order of the cores is stored and can later be returned using getNodeOrder(). Enforces the sequential bucket priority queue algorithm. Default: False

getCover()

Get the k-cores as cover.

Returns:

The k-cores as sets of nodes, indexed by k.

Return type:

list(int)

getNodeOrder()

Get the node order. This is only possible when storeNodeOrder was set.

Returns:

The nodes sorted by increasing core number.

Return type:

list(int)

getPartition()

Get the k-shells as a partition object.

Returns:

The k-shells.

Return type:

networkit.Partition

maxCoreNumber()

Get maximum core number.

Returns:

The maximum core number.

Return type:

int

class networkit.centrality.DegreeCentrality(G, normalized=False, outDeg=True, ignoreSelfLoops=True)

Bases: Centrality

Node centrality index which ranks nodes by their degree. Optional normalization by maximum degree. run() runs in O(n) time if ignoreSelfLoops is false or the graph has no self-loops; otherwise it runs in O(m).

Constructs the DegreeCentrality class for the given Graph G. If the scores should be normalized, then set normalized to True.

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

• normalized (bool, optional) – Normalize centrality values in the interval [0,1]. Default: False

• outdeg (bool, optional) – If set to true, computes the centrality based on out-degrees, otherwise based on the in-degrees. Default: True

• ignoreSelfLoops (bool, optional) – If set to true, self loops will not be taken into account. Default: True

class networkit.centrality.DynApproxBetweenness(G, epsilon=0.01, delta=0.1, storePredecessors=True, universalConstant=1.0)

The algorithm approximates the betweenness of all vertices so that the scores are within an additive error epsilon with probability at least $$(1 - delta)$$. The values are normalized by default.

The algorithm approximates the betweenness of all vertices so that the scores are within an additive error epsilon with probability at least $$(1 - delta)$$. The values are normalized by default.

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

• epsilon (float, optional) – Maximum additive error. Default: 0.01

• delta (float, optional) – Probability that the values are within the error guarantee. Default: 0.1

• storePredecessors (bool, optional) – Store lists of predecessors. Default: True

• universalConstant (float, optional) – The universal constant to be used in computing the sample size. It is 1 by default. Some references suggest using 0.5, but there is no guarantee in this case. Default: 1.0

getNumberOfSamples()

Get number of path samples used in last calculation.

Returns:

Number of samples.

Return type:

int

ranking()

Get a vector of pairs sorted into descending order. Each pair contains a node and the corresponding score calculated by run().

Returns:

A list of pairs.

Return type:

list(tuple(int, float))

score(v)

Get the betweenness score of node v calculated by run().

Parameters:

v (int) – A node.

Returns:

The betweenness score of node v.

Return type:

float

scores()

Get a vector containing the betweenness score for each node in the graph.

Returns:

The betweenness scores calculated by run().

Return type:

list(float)

class networkit.centrality.DynBetweenness(G)

The algorithm computes the betweenness centrality of all nodes and updates them after an edge insertion.

Parameters:

G (networkit.Graph) – The input graph.

ranking()

Get a vector of pairs sorted into descending order. Each pair contains a node and the corresponding score calculated by run().

Returns:

A list of pairs.

Return type:

list(tuple(int, float))

score(v)

Get the betweenness score of node v calculated by run().

Parameters:

v (int) – A node.

Returns:

The betweenness score of node v.

Return type:

float

scores()

Get a vector containing the betweenness score for each node in the graph.

Returns:

The betweenness scores calculated by run().

Return type:

list(float)

class networkit.centrality.DynBetweennessOneNode(G, x)

Dynamic exact algorithm for updating the betweenness of a specific node. The algorithm updates the betweenness of a node after an edge insertion (faster than updating it for all nodes), based on the algorithm proposed by Bergamini et al. “Improving the betweenness centrality of a node by adding links”

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

• x (int) – The node for which you want to update betweenness

getDistance(u, v)

Returns the distance between node u and node v.

Returns:

Distance between u and v.

Return type:

float

getSigma(u, v)

Returns the number of shortest paths between node u and node v.

Returns:

Number of shortest paths between u and v.

Return type:

int

getSigmax(u, v)

Returns the number of shortest paths between node u and node v that go through x.

Returns:

Number of shortest paths between u and v that go through x.

Return type:

int

getbcx()

Returns the betweenness centrality score of node x.

Returns:

Betweenness centrality score of x.

Return type:

float

class networkit.centrality.DynKatzCentrality

Bases: Centrality

” DynKatzCentrality(G, k, groupOnly=False, tolerance=1e-9)

Finds the top-k nodes with highest Katz centrality.

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

• k (float) – The number k for which we want to find the top-k nodes with highest Katz centrality.

• groupOnly (bool, optional) – Set whether the update will only update top-k nodes. Default: False

• tolerance (float, optional) – The tolerance for convergence. Default: 1e-9

areDistinguished(u, v)

Returns true if the bounds are sharp enough to rank two nodes against each other.

Parameters:
• u (int) – Node in the graph.

• v (int) – Node in the graph.

Returns:

True if the bounds are sharp enough to rank two nodes against each other.

Return type:

bool

bound(v)

Returns the (upper) bound of the centrality of node v.

Parameters:

v (int) – Node in the graph.

Returns:

Upper bound of node v.

Return type:

float

top(n=0)

Returns the top n nodes.

Parameters:

n (int, optional) – If set, retrieve n top-nodes. If not set, all nodes are retrieved. Default: 0

Returns:

List of nodes with top-n centrality-scores.

Return type:

list(int)

class networkit.centrality.DynTopHarmonicCloseness(G, k=1, useBFSbound=True)

Finds the top k nodes with highest harmonic closeness centrality faster than computing it for all nodes and updates them after a single or multiple edge update. The implementation is based on “Computing Top-k Closeness Centrality in Fully-dynamic Graphs”, Bisenius et al., ALENEX18. The implementation is based on the static algorithms by Borassi et al. (complex networks) and Bergamini et al. (large-diameter networks).

Notes

The worst case running time of the algorithm is O(nm), where n is the number of nodes and m is the number of edges. However, for most networks the empirical running time is O(m).

Parameters:
• G (networkit.Graph) – An unweighted graph.

• k (int, optional) – Number of nodes with highest closeness that have to be found. For example, if k = 10, the top 10 nodes with highest closeness will be computed. Default: 1

• useBFSbound (bool, optional) – If true, the BFSbound is re-computed at each iteration. If false, BFScut is used. Default: True

ranking(includeTrail=False)

Returns: the ranking of the k most central nodes in the graph. WARNING: closeness centrality of some nodes below the top-k could be equal to the k-th closeness, we call them trail. Set the parameter includeTrail to true to also include those nodes but consider that the resulting vector could be longer than k.

Parameters:

includeTrail (bool, optional) – Whether or not to include trail nodes. Default: False

Returns:

The ranking.

Return type:

int

topkNodesList(includeTrail=False)

Returns: a list with the k nodes with highest harmonic closeness. WARNING: closeness centrality of some nodes below the top-k could be equal to the k-th closeness, we call them trail. Set the parameter includeTrail to true to also include those nodes but consider that the resulting vector could be longer than k.

Parameters:

includeTrail (bool, optional) – Whether or not to include trail nodes. Default: False

Returns:

The k nodes with highest harmonic closeness.

Return type:

list(int)

topkScoresList(includeTrail=False)

Returns: a list with the scores of the k nodes with highest harmonic closeness. WARNING: closeness centrality of some nodes below the top-k could be equal to the k-th closeness, we call them trail. Set the parameter includeTrail to true to also include those centrality values but consider that the resulting vector could be longer than k.

Parameters:

includeTrail (bool, optional) – Whether or not to include trail centrality value. Default: False

Returns:

The k highest closeness harmonic scores.

Return type:

list(float)

class networkit.centrality.EigenvectorCentrality(G, tol=1e-9)

Bases: Centrality

Computes the leading eigenvector of the graph’s adjacency matrix (normalized in 2-norm). Interpreted as eigenvector centrality score.

Constructs the EigenvectorCentrality class for the given Graph G. tol defines the tolerance for convergence.

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

• tol (float, optional) – The tolerance for convergence.

class networkit.centrality.EstimateBetweenness(G, nSamples, normalized=False, parallel=False)

Bases: Centrality

Estimation of betweenness centrality according to algorithm described in Sanders, Geisberger, Schultes: Better Approximation of Betweenness Centrality

The algorithm estimates the betweenness of all nodes, using weighting of the contributions to avoid biased estimation. The run() method takes O(m) time per sample, where m is the number of edges of the graph. There is no proven theoretical guarantee on the quality of the approximation. However, the algorithm was shown to perform well in practice. If a guarantee is required, use ApproxBetweenness.

Parameters:
• G (networkit.Graph) – Input graph

• nSamples (count) – User defined number of samples

• normalized (bool, optional) – Normalize centrality values in interval [0,1]

• parallel (bool, optional) – Run in parallel with additional memory cost z + 3z * t

class networkit.centrality.ForestCentrality(G, root, eps=0.1, kappa=0.3)

Bases: Centrality

Approximates the forest closeness centrality of all the vertices of a graph by approximating the diagonal of the forest matrix of @a G. Every element of the diagonal is guaranteed to have a maximum absolute error of @a epsilon. Based on “New Approximation Algorithms for Forest Closeness Centrality - for Individual Vertices and Vertex Groups”, van der Grinten et al, SDM 2021. The algorithm runs in two steps: (i) solving a linear system and (ii) sampling uniform spanning trees (USTs). The parameter @a kappa balances the tolerance of the linear sytem solver and the number of USTs to be sampled. A high value of @a kappa raises the tolerance (solver converges faster) but more USTs need to be sampled, vice versa for a low value of @a kappa. Note: the algorithm requires an augmented graph as input (see the reference paper for details). An augmented graphs can be generated with graphtools.createAugmentedGraph.

Parameters:
• G (networkit.Graph) – The input graph. Must be an augmented graph; an augmented graph can be crated with graphtools.createAugmentedGraph.

• root (int) – Root node of the augmented graph.

• epsilon (float, optional) – Maximum absolute error of the elements in the diagonal. Default: 0.1

• kappa (float, optional) – Balances the tolerance of the linear system solver and the number of USTs to be sampled. Default: 0.3

getDiagonal()

Return an epsilon-approximation of the diagonal of the forest matrix.

Returns:

Approximation of the diagonal of the laplacian’s pseudoinverse.

Return type:

list(float)

class networkit.centrality.GedWalk(Graph G, k = 1, epsilon = 0.1, alpha = -1.0, bs = networkit.centrality.BoundStrategy.GEOMETRIC, gs = networkit.centrality.GreedyStrategy.LAZY, spectralDelta = 0.5)

Bases: Algorithm

Finds a group of k vertices with at least ((1 - 1/e) * opt - epsilon) GedWalk centrality score, where opt is the highest possible score. The algorithm is based on the paper “Group Centrality Maximization for Large-scale Graphs”, Angriman et al., ALENEX20. It implements two independent greedy strategies (lazy and stochastic). Furthermore, it allows to compute the GedWalk score of a given set of nodes.

Parameter bs can be one of the following:

• networkit.centrality.BoundStrategy.NO

• networkit.centrality.BoundStrategy.SPECTRAL

• networkit.centrality.BoundStrategy.GEOMETRIC

Parameter gs can be one of the following:

• networkit.centrality.GreedyStrategy.LAZY

• networkit.centrality.GreedyStrategy.STOCHASTIC

Parameters:
• G (networkit.Graph) – A (weakly) connected graph.

• k (int, optional) – The desired group size. Default: 1

• epsilon (float, optional) – Precision of the algorithm. Default: 0.1

• alpha (float, optional) – Exponent to compute the GedWalk score. Default: -1.0

• bs (networkit.centrality.BoundStrategy, optional) – Bound strategy to compute the GedWalk bounds. Default: networkit.centrality.BoundStrategy.GEOMETRIC

• gs (networkit.centrality.GreedyStrategy, optional) – Greedy strategy to be used (lazy or stochastic). Default: networkit.centrality.GreedyStrategy.LAZY

• spectralDelta (float, optional) – Delta to be used for the spectral bound. Default: 0.5

getApproximateScore()

Returns the GedWalk score of the computed group.

Returns:

The GedWalk score of the computed group.

Return type:

float

groupMaxGedWalk()

Returns the computed group.

Returns:

The computed group.

Return type:

list(int)

scoreOfGroup(group, epsilon=0.1)

Returns the GedWalk score of the input group.

Parameters:
• group (list(int)) – The input group.

• epsilon (float, optional) – The precision of the score to be computed. Default: 0.1

Returns:

An epsilon-approximation of the GedWalk score of the input group.

Return type:

float

class networkit.centrality.GroupCloseness(G, k=1, H=0)

Bases: Algorithm

Finds the group of nodes with highest (group) closeness centrality. The algorithm is the one proposed in Bergamini et al., ALENEX 2018 and finds a solution that is a (1-1/e)-approximation of the optimum. The worst-case running time of this approach is quadratic, but usually much faster in practice.

Parameters:
• G (networkit.Graph) – An unweighted graph.

• k (int, optional) – Size of the group. Default: 1

• H (int, optional) – If equal 0, simply runs the algorithm proposed in Bergamini et al.. If > 0, interrupts all BFSs after H iterations (suggested for very large networks). Default: 0

computeFarness(S, H=0)

Computes farness (i.e., inverse of the closeness) for a given group (stopping after H iterations if H > 0).

Parameters:
• S (list(int)) – Group to compute farness on.

• H (int, optional) – If equal 0, simply runs the algorithm proposed in Bergamini et al.. If > 0, interrupts after H iterations (suggested for very large networks). Default: 0

Returns:

Farness value for node group.

Return type:

float

groupMaxCloseness()

Returns the group with maximum closeness centrality.

Returns:

The group of k nodes with maximum closeness centrality.

Return type:

list(int)

scoreOfGroup(group)

Computes the group closeness score of the given group.

Parameters:

group (list(int)) – List of nodes.

Returns:

The group closeness score of the given group.

Return type:

float

class networkit.centrality.GroupClosenessGrowShrink(Graph G, group, extended = False, insertions = 0)

Bases: Algorithm

Finds a group of nodes with high group closeness centrality. This is the Grow-Shrink algorithm presented in Angriman et al. “Local Search for Group Closeness Maximization on Big Graphs” IEEE BigData 2019. The algorithm takes as input a connected, unweighted, undirected graph and an arbitrary group of nodes, and improves the group closeness of the given group by performing vertex exchanges.

Parameters:
• G (networkit.Graph) – A connected, undirected, unweighted graph.

• group (list(int)) – The initial group of nodes.

• extended (bool, optional) – Set this parameter to true for the Extended Grow-Shrink algorithm (i.e., swaps are not restricted to only neighbors of the group). Default: False

• insertions (int, optional) – Number of consecutive node insertions and removal per iteration. Let this parameter to zero to use Diameter(G)/sqrt(k) nodes (where k is the size of the group). Default: 0

groupMaxCloseness()

Returns the computed group.

Returns:

The computed group.

Return type:

list(int)

numberOfIterations()

Return the total number of iterations performed by the algorithm.

Returns:

Total number of iterations performed by the algorithm.

Return type:

int

class networkit.centrality.GroupClosenessLocalSearch(Graph G, group, runGrowShrink, maxIterations)

Bases: Algorithm

Local search approximation algorithm for Group Closeness Maximization presented in “Group-Harmonic and Group-Closeness Maximization – Approximation and Engineering”, Angriman et al., ALENEX 2021. The algorithm evaluates all possible swaps between a vertex in the group and the vertices outside, and performs a swap iff the decrement in farness is at least $$(1 - 1 / (k \cdot (n - k)))$$, where k is the number of vertices in the group. Thus, even in a best-case scenario the time complexity of this algorithm is $$O(n \cdot k)$$. To keep the number of swaps low, it is recommended to use this algorithm as a refinement step of an already good solution computed by a faster algorithm e.g., greedy (GroupCloseness), or GrowShrink (GroupClosenessGrowShrink). In undirected graphs the approximation ratio is 1/5, on directed graphs it has not been demonstrated.

Parameters:
• G (networkit.Graph) – A connected, undirected, unweighted graph.

• group (list(int)) – The initial group of nodes.

• useGrowShrink (bool) – Whether or not to run the GrowShrink algorithm on the initial group.

• maxIterations (int) – Maximum number of swaps allowed. Prevents the algorithm from performing too many swaps by giving up the approximation guarantee.

groupMaxCloseness()

Returns the computed group.

Returns:

The computed group.

Return type:

list(int)

numberOfIterations()

Return the total number of iterations performed by the algorithm.

Returns:

Total number of iterations performed by the algorithm.

Return type:

int

class networkit.centrality.GroupClosenessLocalSwaps(Graph G, group, maxSwaps = 0)

Bases: Algorithm

Finds a group of nodes with high group closeness centrality. This is the LS-restrict algorithm presented in Angriman et al. “Local Search for Group Closeness Maximization on Big Graphs” IEEE BigData 2019. The algorithm takes as input a graph and an arbitrary group of nodes, and improves the group closeness of the given group by performing vertex exchanges.

Parameters:
• G (networkit.Graph) – An undirected, unweighted graph.

• group (list(int)) – The initial group of nodes.

• maxSwaps (int, optional) – Maximum number of vertex exchanges allowed. Default: 0

groupMaxCloseness()

Returns the computed group.

Returns:

The computed group.

Return type:

list(int)

numberOfSwaps()

Return the total number of vertex exchanges performed by the algorithm.

Returns:

Total number of vertex exchanges performed by the algorithm.

Return type:

int

class networkit.centrality.GroupDegree(G, k=1, countGroupNodes=True)

Bases: Algorithm

Finds the group with the highest group degree centrality according to the definition proposed in ‘The centrality of groups and classes’ by Everett et al. (The Journal of mathematical sociology, 1999). This is a submodular but non monotone function so the algorithm can find a solution that is at least 1/2 of the optimum. Worst-case running time is quadratic, but usually faster in real-world networks. The countGroupNodes option also count the nodes inside the group in the score, this make the group degree monotone and submodular and the algorithm is guaranteed to return a $$(1 - 1/e)$$-approximation of the optimal solution.

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

• k (int, optional) – Size of the group of nodes. Default: 1

• countGroupNodes (bool, optional) – If nodes inside the group should be counted in the centrality score. Default: True

getScore()

Returns the score of the group with maximum degree centrality (i.e. the number of nodes outside the group that can be reached in one hop from at least one node in the group).

Returns:

The number of nodes outside the group that can be reached in one hop from at least one node in the group.

Return type:

int

groupMaxDegree()

Returns the group with maximum degree centrality.

Returns:

The group of k nodes with highest degree centrality.

Return type:

list(int)

scoreOfGroup(vector[node] group)

Returns the score of the given group.

Parameters:

group (list(int)) – List of nodes.

Returns:

The score of the given group.

Return type:

int

class networkit.centrality.GroupHarmonicCloseness(Graph G, k = 1)

Bases: Algorithm

Approximation algorithm for the group-harmonic maximization problem. The computed solutions have a guaranteed $$\lambda(1 - \frac{1}{2e})$$ (directed graphs) and $$\lambda(1 - \frac{1}{e})/2$$ (undirected graphs) approximation ratio, where $$\lambda$$ is the ratio between the minimal and the maximal edge weight. The algorithm is the one proposed in Angriman et al., ALENEX 2021.

Notes

The worst-case running time of this approach is quadratic, but usually much faster in practice.

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

• k (int, optional) – Size of the group of nodes. Default: 1

groupMaxHarmonicCloseness()

Returns the computed group.

Returns:

The computed group.

Return type:

list(int)

static scoreOfGroup(Graph graph, vector[node] inputGroup)

Computes the group-harmonic score of the input group.

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

• inputGroup (list(int)) – The input group of nodes.

Returns:

The group-harmonic score of the input group.

Return type:

float

class networkit.centrality.HarmonicCloseness(G, normalized=True)

Bases: Centrality

Constructs the HarmonicCloseness class for the given Graph G. If the harmonic closeness scores should not be normalized, set normalized to False. The run() method takes O(nm) time, where n is the number of nodes and m is the number of edges of the graph.

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

• normalized (bool, optional) – Set this parameter to False if scores should not be normalized into an interval of [0,1]. Normalization only for unweighted graphs. Default: True

class networkit.centrality.KPathCentrality(G, alpha=0.2, k=0)

Bases: Centrality

Constructs the K-Path Centrality class for the given Graph G.

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

• alpha (float, optional) – Tradeoff between runtime and precision with -0.5: maximum precision, maximum runtime and 0.5: lowest precision, lowest runtime. Default: 0.2

• k (int, optional) – maximum length of paths. Default: 0

Bases: Algorithm

KadabraBetweenness(Graph G, err = 0.01, delta = 0.1, deterministic = False, k = 0, unionSample = 0, startFactor = 100

Approximation of the betweenness centrality and computation of the top-k nodes with highest betweenness centrality according to the algorithm described in Borassi M. and Natale M. (2016): KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation. Parallel implementation by Van der Grinten A., Angriman E., and Meyerhenke H.: Parallel Adaptive Sampling with almost no Synchronization, Euro-Par 2019. https://link.springer.com/chapter/10.1007/978-3-030-29400-7_31 ArXiv pre-print: https://arxiv.org/abs/1903.09422.

If k = 0 the algorithm approximates the betweenness centrality of all vertices of the graph so that the scores are within an additive error err with probability at least $$(1 - err * delta)$$. Otherwise, the algorithm computes the exact ranking of the top-k nodes with highest betweenness centrality. The algorithm relies on an adaptive random sampling technique of shortest paths and the number of samples in the worst case is $$w = ((log(D - 2) + log(2/delta))/err^2$$ samples, where D is the diameter of the graph. Thus, the worst-case performance is $$O(w * (|E| + |V|))$$, but performs better in practice.

Notes

In order to work properly, the Kadabra algorithm requires a random seed to be previously set with ‘useThreadId’ set to True. To do this, call the setSeed(<your_seed>, True) fuction within the Random module.

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

• err (float, optional) – Maximum additive error guaranteed when approximating the betweenness centrality of all nodes. Default: 0.01

• delta (float, optional) – Probability that the values of the betweenness centrality are within the error guarantee. Default: 0.1

• deterministic (bool, optional) – If True, the algorithm guarantees that the results of two different executions is the same for a fixed random seed, regardless of the number of threads. Note that this guarantee leads to increased computational and memory complexity. Default: False

• k (int, optional) – The number of top-k nodes to be computed. Set it to zero to approximate the betweenness centrality of all the nodes. Default: 0

• unionSample (int, optional) – Algorithm parameter. Default: 0

• startFactor (int, optional) – Algorithm parameter. Default: 100

getNumberOfIterations()

Returns the total number of samples.

Returns:

The total number of shortest paths sampled by the algorithm.

Return type:

int

getOmega()

Returns the upper bound of the required number of samples.

Returns:

Upper bound of the number of shortest paths to be sampled.

Return type:

int

ranking()

Returns the ranking of the nodes according to their approximated betweenness centrality.

Returns:

A list of pairs (node, betweenness) representing the top-k ranking.

Return type:

list(int, float)

scores()

Returns the approximated betweenness centrality score of all the nodes of the graph.

Returns:

A list with the approximated betweenness centrality score of each node of the graph.

Return type:

list(float)

topkNodesList()

Returns Nodes of the graph sorted by their approximated betweenness centrality.

Returns:

A list with the top-k nodes with highest approximated betweenness centrality.

Return type:

list(int)

topkScoresList()

Returns the sorted list of approximated betweenness centrality scores.

Returns:

A list with the top-k scores of the nodes with highest approximated betweenness centrality.

Return type:

list(float)

class networkit.centrality.KatzCentrality(G, alpha=0, beta=0.1, tol=1e-8)

Bases: Centrality

Constructs a KatzCentrality object for the given Graph G. Each iteration of the algorithm requires O(m) time. The number of iterations depends on how long it takes to reach the convergence (and therefore on the desired tolerance tol).

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

• alpha (float, optional) – Damping of the matrix vector product result, must be non negative. Leave this parameter to 0 to use the default value $$1 / (max_degree + 1)$$. Default: 0

• beta (float, optional) – Constant value added to the centrality of each vertex. Default: 0.1

• tol (float, optional) – The tolerance for convergence. Default: 1e-8

edgeDirection

Property edgeDirection can be one of the following:

• networkit.centrality.EdgeDirection.IN_EDGES

• networkit.centrality.EdgeDirection.OUT_EDGES

Default: networkit.centrality.EdgeDirection.IN_EDGES

class networkit.centrality.LaplacianCentrality(G, normalized=False)

Bases: Centrality

Computes the Laplacian centrality of the graph.

Notes

The implementation is a simplification of the original algorithm proposed by Qi et al. in “Laplacian centrality: A new centrality measure for weighted networks”.

See https://dl.acm.org/citation.cfm?id=2181343.2181780 for details.

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

• normalized (bool, optional) – Whether scores should be normalized by the energy of the full graph. Default: False

class networkit.centrality.LocalClusteringCoefficient(G, turbo=False)

Bases: Centrality

Constructs the LocalClusteringCoefficient class for the given Graph G. If the local clustering coefficient values should be normalized, then set normalized to True. The graph may not contain self-loops.

There are two algorithms available. The trivial (parallel) algorithm needs only a small amount of additional memory. The turbo mode adds a (sequential, but fast) pre-processing step using ideas from Triangle Listing Algorithms: Back from the Diversion (Mark Ortmann and Ulrik Brandes). This reduces the running time significantly for most graphs. However, the turbo mode needs O(m) additional memory. In practice this should be a bit less than half of the memory that is needed for the graph itself. The turbo mode is particularly effective for graphs with nodes of very high degree and a very skewed degree distribution.

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

• turbo (bool, optional) – If the turbo mode shall be activated. Default: False

class networkit.centrality.LocalPartitionCoverage(G, P)

Bases: Centrality

The local partition coverage is the amount of neighbors of a node u that are in the same partition as u. The running time of the run() method is O(m), where m is the number of edges in the graph.

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

• P (networkit.Partition) – The partition to use.

class networkit.centrality.LocalSquareClusteringCoefficient(G)

Bases: Centrality

Constructs the LocalSquareClusteringCoefficient class for the given Graph G.

Parameters:

G (networkit.Graph) – The input graph.

class networkit.centrality.PageRank(G, damp=0.85, tol=1e-9, normalized=False, distributeSinks=SinkHandling.NoSinkHandling)

Bases: Centrality

Compute PageRank as node centrality measure. In the default mode this computation is in line with the original paper “The PageRank citation ranking: Bringing order to the web.” by L. Brin et al (1999). In later publications (“PageRank revisited.” by M. Brinkmeyer et al. (2005) amongst others) sink-node handling was added for directed graphs in order to comply with the theoretical assumptions by the underlying Markov chain model. This can be activated by setting the matching parameter to true. By default this is disabled, since it is an addition to the original definition.

Page-Rank values can also be normalized by post-processed according to “Comparing Apples and Oranges: Normalized PageRank for Evolving Graphs” by Berberich et al. (2007). This decouples the PageRank values from the size of the input graph. To enable this, set the matching parameter to true. Note that, sink-node handling is automatically activated if normalization is used.

Parameter distributeSinks can be one of the following:

• networkit.centrality.SinkHandling.NO_SINK_HANDLING

• networkit.centrality.SinkHandling.DISTRIBUTE_SINKS

Parameters:
• G (networkit.Graph) – Graph to be processed.

• damp (float, optional) – Damping factor of the PageRank algorithm. Default: 0.85

• tol (float, optional) – Error tolerance for PageRank iteration. Default: 1e-8

• distributeSinks (networkit.centrality.SinkHandling, optional) – Set to distribute PageRank values for sink nodes. Default: SinkHandling.NO_SINK_HANDLING

• normalized (bool, optional) – If the results should be normalized by the lower bound of scores. This decouples the PageRank values from the size of the input graph. Default: False

maxIterations

Property maxIterations sets a stopping criteria based on number of runs. Default: unlimited

norm

Property norm can be one of the following:

• networkit.centrality.Norm.L1_NORM

• networkit.centrality.Norm.L2_NORM

Set this property before calling run() to change norm computation. Default: networkit.centrality.Norm.L2_NORM

numberOfIterations()

Returns the number of iterations performed by the algorithm.

Returns:

Number of iterations performed by the algorithm. Default: unlimited

Return type:

int

class networkit.centrality.PermanenceCentrality(Graph G, Partition P)

Bases: Algorithm

This centrality measure measure how well a vertex belongs to its community. The values are calculated on the fly, the partion may be changed in between the requests. For details see On the permanence of vertices in network communities (Tanmoy Chakraborty, Sriram Srinivasan, Niloy Ganguly, Animesh Mukherjee, and Sanjukta Bhowmick. 2014)

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

• P (networkit.Partition) – Partition for graph G.

getIntraClustering(u)

Returns intra clustering for node u.

Parameters:

u (int) – Node in the graph.

Returns:

Intra clustering value for node u.

Return type:

float

getPermanence(u)

Returns permanence centrality for node u.

Parameters:

u (int) – Node in the graph.

Returns:

Permanence centrality value for node u.

Return type:

float

class networkit.centrality.SciPyEVZ(G, normalized=False)

Compute Eigenvector centrality using algebraic meh

Parameters:
• G (networkit.Graph) – The graph of which to compute the centrality.

• normalized (bool, optional) – Whether to normalize the results or not. Default: False

normFactor()

Returns the norm factor.

Returns:

Norm factor.

Return type:

float

prepareSpectrum()

Prepare the computation of SciPyEVZ.

class networkit.centrality.SciPyPageRank(G, damp=0.95, normalized=False)

Compute Eigenvector centrality using algebraic meh

Parameters:
• G (networkit.Graph) – The graph of which to compute the centrality.

• damp (float, optional) – Damping factor used for computation. Default: 0.95

• normalized (bool, optional) – Whether to normalize the results or not. Default: False

normFactor()

Returns the norm factor.

Returns:

Norm factor.

Return type:

float

prepareSpectrum()

Prepare the computation of SciPyPageRank.

class networkit.centrality.Sfigality(G)

Bases: Centrality

Sfigality is a new type of node centrality measures that is high if neighboring nodes have a higher degree, e.g. in social networks, if your friends have more friends than you. Formally this means: $$\sigma(u) = \frac{| \{ v: \{u,v\} \in E, deg(u) < deg(v) \} |}{ deg(u) }$$

Parameters:

G (networkit.Graph) – The input graph.

class networkit.centrality.SpanningEdgeCentrality(G, tol=0.1)

Bases: Algorithm

Computes the Spanning Edge centrality for the edges of the graph.

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

• tol (float, optional) – Tolerance used for the approximation: with probability at least 1-1/n, the approximated scores are within a factor 1+tol from the exact scores. Default: 0.1

runApproximation()

Computes approximation of the Spanning Edge Centrality. This solves k linear systems, where k is $$log(n)/(tol^2)$$. The empirical running time is $$O(km)$$, where n is the number of nodes and m is the number of edges.

runParallelApproximation()

Computes approximation (in parallel) of the Spanning Edge Centrality. This solves k linear systems, where k is $$log(n)/(tol^2)$$. The empirical running time is $$O(km)$$, where n is the number of nodes and m is the number of edges.

scores()

Get a vector containing the SEC score for each edge in the graph in ascending edge ID order.

Returns:

The SEC scores.

Return type:

list(float)

class networkit.centrality.SpectralCentrality(G, normalized=False)

Bases: object

Abstract class to compute the spectral centrality of a graph. This class needs to be supplied with methods to generate the correct matrices and do the correct normalization.

Parameters:
• G (networkit.Graph) – The graph of which to compute the centrality.

• normalized (bool, optional) – Whether to normalize the results or not. Default: False

normFactor()

Not implemented yet.

prepareSpectrum()

Not implemented yet.

ranking()

Return a ranking of nodes by SpectralCentrality.

Returns:

Ranking for nodes according to SpectralCentrality.

Return type:

list(float)

run()

Runs computation of spectral centrality.

scores()

Get a vector containing the SpectralCentrality score.

Returns:

The SpectralCentrality scores.

Return type:

list(float)

class networkit.centrality.TopCloseness(G, k=1, first_heu=True, sec_heu=True)

Bases: Algorithm

Finds the top k nodes with highest closeness centrality faster than computing it for all nodes, based on “Computing Top-k Closeness Centrality Faster in Unweighted Graphs”, Bergamini et al., ALENEX16. The algorithms is based on two independent heuristics, described in the referenced paper. We recommend to use $$first_heu = true$$ and $$second_heu = false$$ for complex networks and $$first_heu = true$$ and $$second_heu = true$$ for street networks or networks with large diameters.

Notes

The worst case running time of the algorithm is $$O(nm)$$, where n is the number of nodes and m is the number of edges. However, for most networks the empirical running time is $$O(m)$$.

Parameters:
• G (networkit.Graph) – An unweighted graph.

• k (int) – Number of nodes with highest closeness that have to be found. For example, if k = 10, the top 10 nodes with highest closeness will be computed.

• first_heu (bool, optional) – If true, the neighborhood-based lower bound is computed and nodes are sorted according to it. If false, nodes are simply sorted by degree. Default: True

• sec_heu (bool, optional) – If true, the BFSbound is re-computed at each iteration. If false, BFScut is used. Default: True

restrictTopKComputationToNodes(nodeList)

Restricts the top-k closeness computation to a subset of nodes. If the given list is empty, all nodes in the graph will be considered. Note: Actual existence of included nodes in the graph is not checked.

Parameters:

nodeList (list()) – List containing a subset of nodes from the graph.

topkNodesList(includeTrail=False)

Returns: a list with the k nodes with highest closeness. WARNING: closeness centrality of some nodes below the top-k could be equal to the k-th closeness, we call them trail. Set the parameter includeTrail to true to also include those nodes but consider that the resulting vector could be longer than k.

Parameters:

includeTrail (bool, optional) – Whether or not to include trail nodes. Default: False

Returns:

The k nodes with highest closeness.

Return type:

list(int)

topkScoresList(includeTrail=False)

Returns: a list with the scores of the k nodes with highest closeness. WARNING: closeness centrality of some nodes below the top-k could be equal to the k-th closeness, we call them trail. Set the parameter includeTrail to true to also include those centrality values but consider that the resulting vector could be longer than k.

Parameters:

includeTrail (bool, optional) – Whether or not to include trail centrality value. Default: False

Returns:

The k highest closeness scores.

Return type:

list(int)

class networkit.centrality.TopHarmonicCloseness(G, k=1, useNBbound=False)

Bases: Algorithm

Finds the top k nodes with highest harmonic closeness centrality faster than computing it for all nodes. The implementation is based on “Computing Top-k Centrality Faster in Unweighted Graphs”, Bergamini et al., ALENEX16. The algorithm also works with weighted graphs but only if with the NBcut variation. We recommend to use useNBbound = False for complex (weighted) networks (or networks with small diameter) and useNBbound = True for unweighted street networks (or networks with large diameters).

Notes

Notice that the worst case running time of the algorithm is O(nm), where n is the number of nodes and m is the number of edges. However, for most real-world networks the empirical running time is O(m).

Parameters:
• G (networkit.Graph) – The graph. If useNBbound is set to ‘True’, edge weights will be ignored.

• k (int, optional) – Number of nodes with highest closeness that have to be found. For example, if k = 10, the top 10 nodes with highest closeness will be computed. Default: 1

• useNBbound (bool, optional) – If True, the NBbound is re-computed at each iteration. If False, NBcut is used. The worst case running time of the algorithm is $$O(nm)$$, where n is the number of nodes and m is the number of edges. However, for most networks the empirical running time is $$O(m)$$. Default: False

restrictTopKComputationToNodes(nodeList)

Restricts the top-k closeness computation to a subset of nodes. If the given list is empty, all nodes in the graph will be considered. Note: Actual existence of included nodes in the graph is not checked.

Parameters:

nodeList (list()) – List containing a subset of nodes from the graph.

topkNodesList(includeTrail=False)

Returns a list with the k nodes with highest harmonic closeness. WARNING: closeness centrality of some nodes below the top-k could be equal to the k-th closeness, we call them trail. Set the parameter includeTrail to true to also include those nodes but consider that the resulting vector could be longer than k.

Parameters:

includeTrail (bool, optional) – Whether or not to include trail nodes. Default: False

Returns:

The k nodes with highest harmonic closeness.

Return type:

list(int)

topkScoresList(includeTrail=False)

Returns a list with the scores of the k nodes with highest harmonic closeness. WARNING: closeness centrality of some nodes below the top-k could be equal to the k-th closeness, we call them trail. Set the parameter includeTrail to true to also include those centrality values but consider that the resulting vector could be longer than k.

Parameters:

includeTrail (bool, optional) – Whether or not to include trail centrality value. Default: False

Returns:

The k highest closeness harmonic scores.

Return type:

list(int)

networkit.centrality.rankPerNode(ranking)

Returns ranks of all nodes sorted by their ID.

Parameters:

ranking (list(tuple(int, float))) – Ordered list of tuples (node, score).

Returns:

For each node (sorted by node ID), the ranking of the node

Return type:

list(int)

networkit.centrality.ranking(G, algorithm=networkit.centrality.Betweenness, normalized=False)

Return a ranking of nodes by the specified centrality type

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

• algorithm (networkit.centrality.Centrality, optional) – Instance of centrality algorithm to run. Default: networkit.centrality.Betweenness

• normalized (bool, optional) – Set whether the ranking values should be normalized. Default: False

Returns:

Ranking for nodes according to centrality algorithm.

Return type:

list(int)

networkit.centrality.relativeRankErrors(rx, ry)

Let $$r_x(u)$$ be the rank of node u in ranking x. The relative rank error of node u is defined as $$r_x(u) / r_y(u)$$.

Parameters:
• rx (list(tuple(int, float))) – Ranking - ordered list of tuples (node, score).

• ry (list(tuple(int, float))) – Ranking - ordered list of tuples (node, score).

Returns:

Rank errors ordered by node ID

Return type:

list(int)

networkit.centrality.scores(G, algorithm=Betweenness, normalized=False)

Return the centrality scores of nodes using the specified centrality type

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

• algorithm (networkit.centrality.Centrality, optional) – Instance of centrality algorithm to run. Default: networkit.centrality.Betweenness

• normalized (bool, optional) – Set whether the ranking values should be normalized. Default: False

Returns:

Scores for nodes according to centrality algorithm.

Return type:

list(int)