Class CutClustering¶

Inheritance Relationships¶

Class Documentation¶

class CutClustering : public NetworKit::CommunityDetectionAlgorithm¶

Cut clustering algorithm as defined in Flake, Gary William; Tarjan, Robert E.; Tsioutsiouliklis, Kostas. Graph Clustering and Minimum Cut Trees. Internet Mathematics 1 (2003), no. 4, 385—408.

Public Functions

CutClustering(const Graph &G, edgeweight alpha)¶

Initialize cut clustering algorithm with parameter alpha.

A value of 0 gives a clustering with one cluster with all nodes, A value that equals to the largest edge weight gives singleton clusters.

Parameters:

alpha – The parameter for the cut clustering

virtual void run() override¶

Apply algorithm to graph

Warning: due to numerical errors the resulting clusters might not be correct. This implementation uses the Edmonds-Karp algorithm for the cut calculation.

Public Static Functions

static std::map<edgeweight, Partition> getClusterHierarchy(const Graph &G)¶

Get the complete hierarchy with all possible parameter values.

Each reported parameter value is the lower bound for the range in which the corresponding clustering is calculated by the cut clustering algorithm.

Warning: all reported parameter values are slightly too high in order to avoid wrong clusterings because of numerical inaccuracies. Furthermore the completeness of the hierarchy cannot be guaranteed because of these inaccuracies. This implementation hasn’t been optimized for performance.

Parameters:

G – The Graph instance for which the hierarchy shall be calculated

Returns:

The hierarchy as map