# networkit.centrality

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

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)

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)

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)

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)

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)

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

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) None

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.CoreDecomposition(G, normalized=False, enforceBucketQueueAlgorithm=False, storeNodeOrder=False)

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)

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

” 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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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

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)

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)

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)

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)

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
class networkit.centrality.LocalSquareClusteringCoefficient(G)

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)

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)

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
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)

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)

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)

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)

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)