Class ApproxCloseness¶

Inheritance Relationships¶

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¶

Values:

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.

Parameters:

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

Returns:

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