Class ForestCentrality¶

Inheritance Relationships¶

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.

Parameters:

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

Returns:

Approximation of the diagonal of the forest matrix.

inline count getNumberOfSamples() const noexcept¶

Return the number of sampled USTs.

Returns:

Number of sampled USTs.