Class ForestCentrality

Inheritance Relationships

Base Type

Class Documentation

class ForestCentrality : public NetworKit::Centrality

Public Functions

explicit ForestCentrality(const Graph &G, node root, double epsilon = 0.1, double kappa = 0.3)

Approximates the forest closeness centrality of all the vertices of a graph by approximating the diagonal of the forest matrix of G. Every element of the diagonal is guaranteed to have a maximum absolute error of 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

kappa balances the tolerance of the linear sytem solver 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. 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 – The input graph. Must be an augmented graph (an augmented graph can be crated with GraphTools::createAugmentedGraph.

  • root – Root node of the augmented graph.

  • epsilon – Maximum absolute error of the elements in the diagonal.

  • kappa – Balances the tolerance of the linear system solver and the number of USTs to be sampled.

virtual void run() override

Run the algorithm.

inline const std::vector<double> &getDiagonal() const

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


Approximation of the diagonal of the forest matrix.

inline count getNumberOfSamples() const noexcept

Return the number of sampled USTs.


Number of sampled USTs.