Class ApproxElectricalCloseness¶

Inheritance Relationships¶

Class Documentation¶

class ApproxElectricalCloseness : public NetworKit::Centrality¶

Public Functions

ApproxElectricalCloseness(const Graph &G, double epsilon = 0.1, double kappa = 0.3)¶

Approximates the electrical closeness of all the vertices of the graph by approximating the diagonal of the laplacian’s pseudoinverse of G. Every element of the diagonal is guaranteed to have a maximum absolute error of epsilon

. Based on “Approximation of the

Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis”, Angriman et al., ESA

1. The algorithm does two steps: solves a linear system and samples uniform spanning trees (USTs). The parameter kappa balances the tolerance of solver for the linear system 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.

Parameters:

• G – The input graph.

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

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

~ApproxElectricalCloseness() override = default¶

virtual void run() override¶

Run the algorithm.

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

Return an epsilon-approximation of the diagonal of the laplacian’s pseudoinverse.

Returns:

Approximation of the diagonal of the laplacian’s pseudoinverse.

std::vector<double> computeExactDiagonal(double tol = 1e-9) const¶

Compute and return the nearly-exact values of the diagonal of the laplacian’s pseudoinverse. The values are computed by solving Lx = e_u - 1 / n for every vertex u of the graph with a LAMG solver.

Parameters:

tol – Tolerance for the LAMG solver.

Returns:

Nearly-exact values of the diagonal of the laplacian’s pseudoinverse.