Class SpanningEdgeCentrality¶

Inheritance Relationships¶

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.

Parameters:

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

Destructor.

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.

Parameters:

directory –

Returns:

Elapsed time in milliseconds.

uint64_t getSetupTime() const¶

Returns:

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

Parameters:

• u – [in] Endpoint of edge.

• v – [in] Endpoint of edge.

Protected Attributes

double tol¶

Lamg<CSRMatrix> lamg¶

uint64_t setupTime¶