This module contains algorithms for the calculation of centrality, i.e. ranking nodes by their structural importance to the network
networkit.centrality.
ApproxBetweenness
Bases: _NetworKit.Centrality
Approximation of betweenness centrality according to algorithm described in Matteo Riondato and Evgenios M. Kornaropoulos: Fast Approximation of Betweenness Centrality through Sampling
ApproxBetweenness(G, epsilon=0.01, delta=0.1, 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 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.
numberOfSamples
(self)networkit.centrality.
ApproxBetweenness2
Bases: _NetworKit.Centrality
DEPRECATED: Use EstimateBetweenness instead.
Estimation of betweenness centrality according to algorithm described in Sanders, Geisberger, Schultes: Better Approximation of Betweenness Centrality
ApproxBetweenness2(G, nSamples, normalized=False, parallel=False)
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.
networkit.centrality.
ApproxCloseness
Bases: _NetworKit.Centrality
Approximation of closeness centrality according to algorithm described in Cohen et al., Computing Classic Closeness Centrality, at Scale.
ApproxCloseness(G, nSamples, epsilon=0.1, normalized=False, type=OUTBOUND)
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.
- G : Graph
- input graph (undirected)
- nSamples : count
- user defined number of samples
- epsilon : double, optional
- parameter used for the error guarantee; it is also used to control when to use sampling and when to use pivoting
- normalized : bool, optional
- normalize centrality values in interval [0,1]
- type : _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.
INBOUND
= 0OUTBOUND
= 1SUM
= 2getSquareErrorEstimates
(self)Return a vector containing the square error estimates for all nodes.
networkit.centrality.
Betweenness
Bases: _NetworKit.Centrality
Betweenness(G, normalized=False, computeEdgeCentrality=False)
Constructs the Betweenness class for the given Graph G. If the betweenness scores should be normalized,
of nodes and m is the number of edges of the graph.
edgeScores
(self)Get a vector containing the betweenness score for each edge in the graph.
networkit.centrality.
Closeness
(G, normalized=True, checkConnectedness=True)Bases: _NetworKit.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. NOTICE: the graph has to be connected.
networkit.centrality.
CoreDecomposition
Bases: _NetworKit.Centrality
Computes k-core decomposition of a graph.
CoreDecomposition(G)
Create CoreDecomposition class for graph G. The graph may not contain self-loops.
getCover
(self)Get the k-cores as cover.
getNodeOrder
(self)Get the node order.
This is only possible when storeNodeOrder was set.
getPartition
(self)Get the k-shells as a partition object.
maxCoreNumber
(self)Get maximum core number.
networkit.centrality.
DegreeCentrality
Bases: _NetworKit.Centrality
Node centrality index which ranks nodes by their degree. Optional normalization by maximum degree. The run() method runs in O(m) time, where m is the number of edges in the graph.
DegreeCentrality(G, normalized=False)
Constructs the DegreeCentrality class for the given Graph G. If the scores should be normalized, then set normalized to True.
networkit.centrality.
DynApproxBetweenness
Bases: object
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.
getNumberOfSamples
(self)Get number of path samples used in last calculation.
ranking
(self)Get a vector of pairs sorted into descending order. Each pair contains a node and the corresponding score calculated by run().
run
(self)score
(self, v)Get the betweenness score of node v calculated by run().
scores
(self)Get a vector containing the betweenness score for each node in the graph.
update
(self, ev)Updates the betweenness centralities after the edge insertions.
ev : GraphEvent.
updateBatch
(self, batch)Updates the betweenness centralities after the batch batch of edge insertions.
batch : list of GraphEvent.
networkit.centrality.
DynBetweenness
Bases: object
DynBetweenness(G)
ranking
(self)Get a vector of pairs sorted into descending order. Each pair contains a node and the corresponding score calculated by run().
run
(self)score
(self, v)Get the betweenness score of node v calculated by run().
scores
(self)Get a vector containing the betweenness score for each node in the graph.
update
(self, ev)Updates the betweenness centralities after the edge insertions.
ev : GraphEvent.
updateBatch
(self, batch)Updates the betweenness centralities after the batch batch of edge insertions.
batch : list of GraphEvent.
networkit.centrality.
DynBetweennessOneNode
Bases: object
Dynamic exact algorithm for updating the betweenness of a specific node
DynBetweennessOneNode(G, x)
The algorithm aupdates the betweenness of a node after an edge insertions (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”
getDistance
(self, u, v)Returns the distance between node u and node v.
getSigma
(self, u, v)Returns the number of shortest paths between node u and node v.
getSigmax
(self, u, v)Returns the number of shortest paths between node u and node v that go through x.
getbcx
(self)Returns the betweenness centrality score of node x
run
(self)update
(self, ev)Updates the betweenness centralities after the batch batch of edge insertions.
ev : edge insertion.
updateBatch
(self, batch)Updates the betweenness centrality of node x after the batch batch of edge insertions.
batch : list of GraphEvent.
networkit.centrality.
EigenvectorCentrality
Bases: _NetworKit.Centrality
Computes the leading eigenvector of the graph’s adjacency matrix (normalized in 2-norm). Interpreted as eigenvector centrality score.
EigenvectorCentrality(G, tol=1e-9)
Constructs the EigenvectorCentrality class for the given Graph G. tol defines the tolerance for convergence.
networkit.centrality.
EstimateBetweenness
Bases: _NetworKit.Centrality
Estimation of betweenness centrality according to algorithm described in Sanders, Geisberger, Schultes: Better Approximation of Betweenness Centrality
EstimateBetweenness(G, nSamples, normalized=False, parallel=False)
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.
networkit.centrality.
GroupCloseness
Bases: object
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.
GroupCloseness(G, k=1, H=0)
G: An unweighted graph. k: Size of the group. H: 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).
computeFarness
(self, S, H=0)groupMaxCloseness
(self)run
(self)Computes group with maximum closeness.
networkit.centrality.
KPathCentrality
(G, alpha=0.2, k=0)Bases: _NetworKit.Centrality
Constructs the K-Path Centrality class for the given Graph G.
tradeoff between runtime and precision -0.5: maximum precision, maximum runtime
0.5: lowest precision, lowest runtime
k: maximum length of paths
networkit.centrality.
KatzCentrality
(G, alpha=5e-4, beta=0.1, tol=1e-8)Bases: _NetworKit.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).
networkit.centrality.
LocalClusteringCoefficient
(G, turbo=False)Bases: _NetworKit.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 [0]. 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.
[0] Triangle Listing Algorithms: Back from the Diversion Mark Ortmann and Ulrik Brandes 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX). 2014, 1-8
networkit.centrality.
LocalPartitionCoverage
Bases: _NetworKit.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.
LocalPartitionCoverage(G, P)
networkit.centrality.
PageRank
Bases: _NetworKit.Centrality
Compute PageRank as node centrality measure.
PageRank(G, damp=0.85, tol=1e-9)
networkit.centrality.
PageRankMatrix
(G, damp=0.85)Builds the PageRank matrix of the undirected Graph G. This matrix corresponds with the PageRank matrix used in the C++ backend.
networkit.centrality.
PermanenceCentrality
Bases: object
Permanence centrality
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
Tanmoy Chakraborty, Sriram Srinivasan, Niloy Ganguly, Animesh Mukherjee, and Sanjukta Bhowmick. 2014. On the permanence of vertices in network communities. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD ‘14). ACM, New York, NY, USA, 1396-1405. DOI: http://dx.doi.org/10.1145/2623330.2623707
FIXME: does not use the common centrality interface yet.
getIntraClustering
(self, node u)getPermanence
(self, node u)run
(self)networkit.centrality.
SciPyEVZ
(G, normalized=False)Bases: networkit.centrality.SpectralCentrality
Compute Eigenvector centrality using algebraic meh
normFactor
()prepareSpectrum
()networkit.centrality.
SciPyPageRank
(G, damp=0.95, normalized=False)Bases: networkit.centrality.SpectralCentrality
normFactor
()prepareSpectrum
()networkit.centrality.
Sfigality
Bases: _NetworKit.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:
$$sigma(u) =
rac{| { v: {u,v} in E, deg(u) < deg(v) } |}{ deg(u) }$$
- G : Graph
- The graph.
networkit.centrality.
SpanningEdgeCentrality
Bases: object
Computes the Spanning Edge centrality for the edges of the graph.
SpanningEdgeCentrality(G, tol = 0.1)
run
(self)This method computes Spanning Edge Centrality exactly. This solves a linear system for each edge, so the empirical running time is O(m^2), where m is the number of edges in the graph.
runApproximation
(self)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
(self)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
(self)Get a vector containing the SEC score for each edge in the graph.
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.
normFactor
()Method that must be implemented to return a correct normalization factor
prepareSpectrum
()Method that must be implemented to set the following values: self.eigenvectors = list of eigenvectors desired for centrality measure self.eigenvalues = list of corresponding eigenvalues
ranking
()run
()scores
()networkit.centrality.
TopCloseness
Bases: object
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.
TopCloseness(G, k=1, first_heu=True, sec_heu=True)
G: An unweighted graph. k: 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: If true, the neighborhood-based lower bound is computed and nodes are sorted according to it. If false, nodes are simply sorted by degree. sec_heu: If true, the BFSbound is re-computed at each iteration. If false, BFScut 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).
run
(self)Computes top-k closeness.
topkNodesList
(self)topkScoresList
(self)networkit.centrality.
adjacencyEigenvector
(G, order, reverse=False)networkit.centrality.
rankPerNode
(ranking)ranking: ordered list of tuples (node, score)
for each node (sorted by node ID), the ranking of the node
networkit.centrality.
ranking
(G, algorithm=<class '_NetworKit.Betweenness'>, normalized=False)Return a ranking of nodes by the specified centrality type
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)$$
list of rank errors ordered by node ID
networkit.centrality.
scores
(G, algorithm=<class '_NetworKit.Betweenness'>, normalized=False)Return the centrality scores of nodes using the specified centrality type
networkit.centrality.
symmetricEigenvectors
(matrix, cutoff=-1, reverse=False)Computes eigenvectors and -values of symmetric matrices.