networkit.centrality

This module contains algorithms for the calculation of centrality, i.e. ranking nodes by their structural importance to the network

class 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.

G : Graph
the graph
epsilon : double, optional
maximum additive error
delta : double, optional
probability that the values are within the error guarantee
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.
numberOfSamples(self)
class 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.

G : 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.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 = 0
OUTBOUND = 1
SUM = 2
getSquareErrorEstimates(self)

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

vector
A vector of doubles.
class 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,

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 : Graph
The graph.
normalized : bool, optional
Set this parameter to True if scores should be normalized in the interval [0,1].
computeEdgeCentrality: bool, optional
Set this to true if edge betweenness scores should be computed as well.
edgeScores(self)

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

vector
The betweenness scores calculated by run().
class networkit.centrality.Closeness(G, normalized=False, checkConnectedness=True)

Bases: _NetworKit.Centrality

Constructs the Closeness class for the given Graph G. If the Closeness 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. NOTICE: the graph has to be connected.
G : Graph
The graph.
normalized : bool, optional
Set this parameter to True if scores should be normalized in the interval [0,1]. Normalization only for unweighted networks.
checkConnectedness : bool, optional
turn this off if you know the graph is connected
class 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.

G : Graph
The graph.
normalized : boolean
Divide each core number by the maximum degree.
enforceBucketQueueAlgorithm : boolean
enforce switch to sequential algorithm
storeNodeOrder : boolean
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.
getCover(self)

Get the k-cores as cover.

vector
The k-cores as sets of nodes, indexed by k.
getNodeOrder(self)

Get the node order.

This is only possible when storeNodeOrder was set.

list
The nodes sorted by increasing core number.
getPartition(self)

Get the k-shells as a partition object.

Partition
The k-shells
maxCoreNumber(self)

Get maximum core number.

index
The maximum core number.
class 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.

G : Graph
The graph.
normalized : bool, optional
Normalize centrality values in the interval [0,1].
class networkit.centrality.DynApproxBetweenness

Bases: object

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

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.

G : Graph
the graph
epsilon : double, optional
maximum additive error
delta : double, optional
probability that the values are within the error guarantee
storePredecessors : bool, optional
store lists of predecessors?
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.
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().

vector
A vector of pairs.
run(self)
score(self, v)

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

v : node
A node.
double
The betweenness score of node `v.
scores(self)

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

vector
The betweenness scores calculated by run().
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.

class networkit.centrality.DynBetweenness

Bases: object

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

DynBetweenness(G)

G : Graph
the graph
ranking(self)

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

vector
A vector of pairs.
run(self)
score(self, v)

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

v : node
A node.
double
The betweenness score of node `v.
scores(self)

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

vector
The betweenness scores calculated by run().
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.

class 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.

G : Graph
The graph.
tol : double, optional
The tolerance for convergence.
class 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.

G : 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.KPathCentrality(G, alpha=0.2, k=0)

Bases: _NetworKit.Centrality

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

G : Graph
The graph.
alpha : double, in interval [-0.5, 0.5]

tradeoff between runtime and precision -0.5: maximum precision, maximum runtime

0.5: lowest precision, lowest runtime

k: maximum length of paths

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

G : Graph
The graph.
alpha : double
Damping of the matrix vector product result
beta : double
Constant value added to the centrality of each vertex
tol : double
The tolerance for convergence.
class 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

G : Graph
The graph.
turbo : bool
If the turbo mode shall be activated.
class 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)

G : Graph
The graph.
P : Partition
The partition to use
class networkit.centrality.PageRank

Bases: _NetworKit.Centrality

Compute PageRank as node centrality measure.

PageRank(G, damp=0.85, tol=1e-9)

G : Graph
Graph to be processed.
damp : double
Damping factor of the PageRank algorithm.
tol : double, optional
Error tolerance for PageRank iteration.
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.

G : Graph
The graph.
damp:
Damping factor of the PageRank algorithm (0.85 by default)
pr : ndarray
The N x N page rank matrix of graph.
class 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)
class networkit.centrality.SciPyEVZ(G, normalized=False)

Bases: networkit.centrality.SpectralCentrality

Compute Eigenvector centrality using algebraic meh

G : graph
The graph of which to compute the centrality
normalized : boolean
Whether to normalize the results or not
normFactor()
prepareSpectrum()
class networkit.centrality.SciPyPageRank(G, damp=0.95, normalized=False)

Bases: networkit.centrality.SpectralCentrality

normFactor()
prepareSpectrum()
class 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.
class networkit.centrality.SpanningEdgeCentrality

Bases: object

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

SpanningEdgeCentrality(G, tol = 0.1)

G : Graph
The graph.
tol: double
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.
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.

vector
The SEC scores.
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.

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()
class 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)$$
rx : list
ranking - ordered list of tuples (node, score)
ry: list
ranking - ordered list of tuples (node, score)

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.

matrix : sparse matrix
The matrix to compute the eigenvectors of
cutoff : int
The maximum (or minimum) magnitude of the eigenvectors needed
reverse : boolean
If set to true, the smaller eigenvalues will be computed before the larger ones
pr : ( [ float ], [ ndarray ] )
A tuple of ordered lists, the first containing the eigenvalues in descending (ascending) magnitude, the second one holding the corresponding eigenvectors