Class ApproxSpanningEdge¶

Inheritance Relationships¶

Class Documentation¶

class ApproxSpanningEdge : public NetworKit::Algorithm¶

Public Functions

ApproxSpanningEdge(const Graph &G, double eps = 0.1)¶

Computes an epsilon-approximation of the spanning edge centrality of every edge of the input graph with probability (1 - 1/n), based on “Efficient Algorithms for Spanning Tree

Centrality”, Hayashi et al., IJCAI, 2016. This implementation also supports multi-threading.

Parameters:

• G – An undirected graph.

• eps – Maximum additive error.

~ApproxSpanningEdge() override = default¶

virtual void run() override¶

Executes the algorithm.

std::vector<double> scores() const¶

Return the spanning edge approximation for each edge of the graph.

Returns:

Spanning edge approximation for each edge of the input graph.