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.
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
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
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
Return a list containing the square error estimates for all nodes.
A list of square error estimate values.
list(float)
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.
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
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.
tol (float) – Tolerance for the LAMG solver. Default: 1e-9
Nearly-exact values of the diagonal of the laplacian’s pseudoinverse.
list(float)
Return an epsilon-approximation of the diagonal of the laplacian’s pseudoinverse.
Approximation of the diagonal of the laplacian’s pseudoinverse.
list(float)
Bases: Algorithm
Constructs the ApproxGroupBetweenness class for a given undirected Graph G.
G (networkit.Graph) – The input graph.
groupSize (int) – The desired size of the group.
epsilon (float) – Determines the accuracy of the approximation.
Get a vector of nodes containing the set of nodes with apporoximated maximum group betweenness.
The group of nodes with highest approximated group betweenness.
list(int)
Returns the score of the given group.
group (list(int)) – Set of nodes.
The score of the given group.
int
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.
G (networkit.Graph) – The input graph.
eps (float, optional) – Maximum additive error. Default: 0.1
Return the spanning edge approximation for each edge of the graph in ascending edge ID order.
Spanning edge approximation for each edge of the input graph.
list
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.
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
Get a vector containing the betweenness score for each edge in the graph in ascending edge ID order.
The betweenness scores calculated by run().
list(float)
Bases: Algorithm
Abstract base class for centrality measures
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.
Centralization value.
float
Return the maximum theoretical centrality score.
The maximum theoretical centrality score for the given graph.
float
Returns the ranking of nodes according to their score.
A list of pairs sorted into descending order. Each pair contains a node and the corresponding score
list(tuple(int, float))
Returns the score of node v for the centrality algorithm.
v (int) – Node index.
The score of node v.
float
Returns the scores of all nodes for the centrality algorithm.
The list of all scores.
list(float)
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
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.
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 ]
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).
A vector of all adopted/infected nodes.
list(int)
Returns complex path (sub)graph of G starting in the node start. Only available when called in mode ComplexPathMode.SINGLE_NODE.
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.
A vector containing complex path lengths for all nodes.
list(float)
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.
Bases: Centrality
Computes k-core decomposition of a graph. The graph may not contain self-loops.
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
Get the k-cores as cover.
The k-cores as sets of nodes, indexed by k.
list(int)
Get the node order. This is only possible when storeNodeOrder was set.
The nodes sorted by increasing core number.
list(int)
Get the k-shells as a partition object.
The k-shells.
networkit.Partition
Get maximum core number.
The maximum core number.
int
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.
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
Bases: Algorithm, DynAlgorithm
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.
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
Get number of path samples used in last calculation.
Number of samples.
int
Get a vector of pairs sorted into descending order. Each pair contains a node and the corresponding score calculated by run().
A list of pairs.
list(tuple(int, float))
Get the betweenness score of node v calculated by run().
v (int) – A node.
The betweenness score of node v.
float
Get a vector containing the betweenness score for each node in the graph.
The betweenness scores calculated by run().
list(float)
Bases: Algorithm, DynAlgorithm
The algorithm computes the betweenness centrality of all nodes and updates them after an edge insertion.
G (networkit.Graph) – The input graph.
Get a vector of pairs sorted into descending order. Each pair contains a node and the corresponding score calculated by run().
A list of pairs.
list(tuple(int, float))
Get the betweenness score of node v calculated by run().
v (int) – A node.
The betweenness score of node v.
float
Get a vector containing the betweenness score for each node in the graph.
The betweenness scores calculated by run().
list(float)
Bases: Algorithm, DynAlgorithm
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”
G (networkit.Graph) – The graph
x (int) – The node for which you want to update betweenness
Returns the distance between node u and node v.
Distance between u and v.
float
Returns the number of shortest paths between node u and node v.
Number of shortest paths between u and v.
int
Returns the number of shortest paths between node u and node v that go through x.
Number of shortest paths between u and v that go through x.
int
Returns the betweenness centrality score of node x.
Betweenness centrality score of x.
float
Bases: Centrality
” DynKatzCentrality(G, k, groupOnly=False, tolerance=1e-9)
Finds the top-k nodes with highest Katz centrality.
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
Returns true if the bounds are sharp enough to rank two nodes against each other.
u (int) – Node in the graph.
v (int) – Node in the graph.
True if the bounds are sharp enough to rank two nodes against each other.
bool
Returns the (upper) bound of the centrality of node v.
v (int) – Node in the graph.
Upper bound of node v.
float
Returns the top n nodes.
n (int, optional) – If set, retrieve n top-nodes. If not set, all nodes are retrieved. Default: 0
List of nodes with top-n centrality-scores.
list(int)
Bases: Algorithm, DynAlgorithm
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).
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
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.
includeTrail (bool, optional) – Whether or not to include trail nodes. Default: False
The ranking.
int
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.
includeTrail (bool, optional) – Whether or not to include trail nodes. Default: False
The k nodes with highest harmonic closeness.
list(int)
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.
includeTrail (bool, optional) – Whether or not to include trail centrality value. Default: False
The k highest closeness harmonic scores.
list(float)
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.
G (networkit.Graph) – The input graph.
tol (float, optional) – The tolerance for convergence.
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.
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
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.
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
Return an epsilon-approximation of the diagonal of the forest matrix.
Approximation of the diagonal of the laplacian’s pseudoinverse.
list(float)
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
networkit.centrality.BoundStrategy.ADAPTIVE_GEOMETRIC
Parameter gs can be one of the following:
networkit.centrality.GreedyStrategy.LAZY
networkit.centrality.GreedyStrategy.STOCHASTIC
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
Returns the GedWalk score of the computed group.
The GedWalk score of the computed group.
float
Returns the computed group.
The computed group.
list(int)
Returns the GedWalk score of the input group.
group (list(int)) – The input group.
epsilon (float, optional) – The precision of the score to be computed. Default: 0.1
An epsilon-approximation of the GedWalk score of the input group.
float
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.
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
Computes farness (i.e., inverse of the closeness) for a given group (stopping after H iterations if H > 0).
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
Farness value for node group.
float
Returns the group with maximum closeness centrality.
The group of k nodes with maximum closeness centrality.
list(int)
Computes the group closeness score of the given group.
group (list(int)) – List of nodes.
The group closeness score of the given group.
float
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.
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
Returns the computed group.
The computed group.
list(int)
Return the total number of iterations performed by the algorithm.
Total number of iterations performed by the algorithm.
int
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.
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.
Returns the computed group.
The computed group.
list(int)
Return the total number of iterations performed by the algorithm.
Total number of iterations performed by the algorithm.
int
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.
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
Returns the computed group.
The computed group.
list(int)
Return the total number of vertex exchanges performed by the algorithm.
Total number of vertex exchanges performed by the algorithm.
int
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.
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
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).
The number of nodes outside the group that can be reached in one hop from at least one node in the group.
int
Returns the group with maximum degree centrality.
The group of k nodes with highest degree centrality.
list(int)
Returns the score of the given group.
group (list(int)) – List of nodes.
The score of the given group.
int
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.
G (networkit.Graph) – The input graph.
k (int, optional) – Size of the group of nodes. Default: 1
Returns the computed group.
The computed group.
list(int)
Computes the group-harmonic score of the input group.
graph (networkit.Graph) – The input graph.
inputGroup (list(int)) – The input group of nodes.
The group-harmonic score of the input group.
float
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.
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
Bases: Centrality
Constructs the K-Path Centrality class for the given Graph G.
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.
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
Returns the total number of samples.
The total number of shortest paths sampled by the algorithm.
int
Returns the upper bound of the required number of samples.
Upper bound of the number of shortest paths to be sampled.
int
Returns the ranking of the nodes according to their approximated betweenness centrality.
A list of pairs (node, betweenness) representing the top-k ranking.
list(int, float)
Returns the approximated betweenness centrality score of all the nodes of the graph.
A list with the approximated betweenness centrality score of each node of the graph.
list(float)
Returns Nodes of the graph sorted by their approximated betweenness centrality.
A list with the top-k nodes with highest approximated betweenness centrality.
list(int)
Returns the sorted list of approximated betweenness centrality scores.
A list with the top-k scores of the nodes with highest approximated betweenness centrality.
list(float)
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).
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
Property edgeDirection can be one of the following:
networkit.centrality.EdgeDirection.IN_EDGES
networkit.centrality.EdgeDirection.OUT_EDGES
Default: networkit.centrality.EdgeDirection.IN_EDGES
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.
G (networkit.Graph) – The input graph.
normalized (bool, optional) – Whether scores should be normalized by the energy of the full graph. Default: 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.
G (networkit.Graph) – The input graph.
turbo (bool, optional) – If the turbo mode shall be activated. Default: False
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.
G (networkit.Graph) – The graph.
P (networkit.Partition) – The partition to use.
Bases: Centrality
Constructs the LocalSquareClusteringCoefficient class for the given Graph G.
G (networkit.Graph) – The input graph.
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
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
Property maxIterations sets a stopping criteria based on number
of runs. Default: unlimited
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
Returns the number of iterations performed by the algorithm.
Number of iterations performed by the algorithm. Default: unlimited
int
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)
G (networkit.Graph) – The input graph.
P (networkit.Partition) – Partition for graph G.
Returns intra clustering for node u.
u (int) – Node in the graph.
Intra clustering value for node u.
float
Returns permanence centrality for node u.
u (int) – Node in the graph.
Permanence centrality value for node u.
float
Bases: SpectralCentrality
Compute Eigenvector centrality using algebraic meh
G (networkit.Graph) – The graph of which to compute the centrality.
normalized (bool, optional) – Whether to normalize the results or not. Default: False
Returns the norm factor.
Norm factor.
float
Prepare the computation of SciPyEVZ.
Bases: SpectralCentrality
Compute Eigenvector centrality using algebraic meh
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
Returns the norm factor.
Norm factor.
float
Prepare the computation of SciPyPageRank.
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) }\)
G (networkit.Graph) – The input graph.
Bases: Algorithm
Computes the Spanning Edge centrality for the edges of the graph.
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
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.
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.
Get a vector containing the SEC score for each edge in the graph in ascending edge ID order.
The SEC scores.
list(float)
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.
G (networkit.Graph) – The graph of which to compute the centrality.
normalized (bool, optional) – Whether to normalize the results or not. Default: False
Not implemented yet.
Not implemented yet.
Return a ranking of nodes by SpectralCentrality.
Ranking for nodes according to SpectralCentrality.
list(float)
Runs computation of spectral centrality.
Get a vector containing the SpectralCentrality score.
The SpectralCentrality scores.
list(float)
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)\).
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
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.
nodeList (list()) – List containing a subset of nodes from the graph.
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.
includeTrail (bool, optional) – Whether or not to include trail nodes. Default: False
The k nodes with highest closeness.
list(int)
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.
includeTrail (bool, optional) – Whether or not to include trail centrality value. Default: False
The k highest closeness scores.
list(int)
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).
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
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.
nodeList (list()) – List containing a subset of nodes from the graph.
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.
includeTrail (bool, optional) – Whether or not to include trail nodes. Default: False
The k nodes with highest harmonic closeness.
list(int)
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.
includeTrail (bool, optional) – Whether or not to include trail centrality value. Default: False
The k highest closeness harmonic scores.
list(int)
Returns ranks of all nodes sorted by their ID.
ranking (list(tuple(int, float))) – Ordered list of tuples (node, score).
For each node (sorted by node ID), the ranking of the node
list(int)
Return a ranking of nodes by the specified centrality type
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
Ranking for nodes according to centrality algorithm.
list(int)
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)\).
rx (list(tuple(int, float))) – Ranking - ordered list of tuples (node, score).
ry (list(tuple(int, float))) – Ranking - ordered list of tuples (node, score).
Rank errors ordered by node ID
list(int)
Return the centrality scores of nodes using the specified centrality type
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
Scores for nodes according to centrality algorithm.
list(int)