Defined in File ForestCentrality.hpp
public NetworKit::Centrality
(Class Centrality)
Public Functions
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.
Run the algorithm.
Return an epsilon-approximation of the diagonal of the forest matrix.
Approximation of the diagonal of the forest matrix.