Class SpanningEdgeCentrality

Inheritance Relationships

Base Type

Class Documentation

class SpanningEdgeCentrality : public NetworKit::Centrality

SpanningEdgeCentrality edge centrality.

Public Functions

SpanningEdgeCentrality(const Graph &G, double tol = 0.1)

Constructs the SpanningEdgeCentrality class for the given Graph G.

  • G – The graph.

  • tol – constant used for the approximation: with probability at least 1-1/n, the approximated scores are within a factor 1+tol from the exact scores

~SpanningEdgeCentrality() override = default


virtual void run() override

Compute spanning edge centrality scores exactly for all edges. 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.

void runApproximation()

Compute approximation by JL projection. 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.

void runParallelApproximation()

Compute approximation by JL projection in parallel. This solves k linear systems in parallel, where k is log(n)/(tol^2).

uint64_t TLX_DEPRECATED(runApproximationAndWriteVectors(const std::string &graphPath))

This method is deprecated and will not be supported in future releases. Use runApproximation() instead.




Elapsed time in milliseconds.

uint64_t getSetupTime() const

The elapsed time to setup the solver in milliseconds.

double runForEdge(node u, node v)

Compute value for one edge only. This requires a single linear system, so the empricial running time is O(m).

  • u[in] Endpoint of edge.

  • v[in] Endpoint of edge.

Protected Attributes

double tol
Lamg<CSRMatrix> lamg
uint64_t setupTime