Class ApproxSpanningEdge

Inheritance Relationships

Base Type

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.