Class ApproxCloseness

Inheritance Relationships

Base Type

Class Documentation

class ApproxCloseness : public NetworKit::Centrality

Approximation of closeness centrality according to algorithm described in Cohen et al., Computing Classic Closeness Centrality, at Scale

Public Types

enum ClosenessType


enumerator INBOUND
enumerator OUTBOUND
enumerator SUM
using CLOSENESS_TYPE = ClosenessType

Public Functions

ApproxCloseness(const Graph &G, count nSamples, double epsilon = 0.1, bool normalized = false, CLOSENESS_TYPE type = OUTBOUND)

Constructs an instance of the ApproxCloseness class for graph using nSamples during the run() method. The epsilon parameter (standard = 0.1) is used to control the switch between sampling and pivoting. Using epsilon = 0, the algorithm only uses sampling. (see Cohen, Edith, et al. “Computing classic closeness centrality, at scale.” Proceedings of the second ACM conference on Online social networks. ACM, 2014.). The running time is proportional to nSamples * m, where m is the number of edges. Notice: the input graph has to be connected.

  • graph – input graph

  • nSamples – user defined number of samples

  • epsilon – Value in [0, infty) controlling the switch between sampling and pivoting. When using 0, only sampling is used. Standard is 0.1.

  • normalized – normalize centrality values in interval [0,1]

  • type – use in- or outbound centrality or the sum of both (see paper) for computing closeness on directed graph. If G is undirected, this can be ignored.

virtual void run() override

Computes closeness approximation on the graph passed in constructor.

virtual double maximum() override

Returns the maximum possible Closeness a node can have in a graph with the same amount of nodes (=a star)

std::vector<double> getSquareErrorEstimates()

The square error when closeness centrality has been computed for an undirected graph.