Class LocalClusteringCoefficient¶

Inheritance Relationships¶

Class Documentation¶

class LocalClusteringCoefficient : public NetworKit::Centrality¶

Public Functions

LocalClusteringCoefficient(const Graph &G, bool turbo = false)¶

Constructs the LocalClusteringCoefficient class for the given Graph G. If the local clustering coefficient scores should be normalized, then set normalized to true. The graph may not contain self-loops.

There are two algorithms available. The trivial (parallel) algorithm needs only a small amount of additional memory. The turbo mode adds a (sequential, but fast) pre-processing step using ideas from [0]. This reduces the running time significantly for most graphs. However, the turbo mode needs O(m) additional memory. In practice this should be a bit less than half of the memory that is needed for the graph itself. The turbo mode is particularly effective for graphs with nodes of very high degree and a very skewed degree distribution.

[0] Triangle Listing Algorithms: Back from the Diversion Mark Ortmann and Ulrik Brandes * 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX). 2014, 1-8

Parameters:

• G – The graph.

• turbo – If the turbo mode shall be activated. TODO running time

virtual void run() override¶

Computes the local clustering coefficient on the graph passed in constructor.

virtual double maximum() override¶

Get the theoretical maximum of centrality score in the given graph.

Returns:

The maximum centrality score.

Protected Attributes

bool turbo¶