Class IsolatedInterpartitionExpansion

Inheritance Relationships

Base Type

Class Documentation

class IsolatedInterpartitionExpansion : public NetworKit::LocalPartitionEvaluation

Isolated inter-partition expansion is a measure for how well a partition (communtiy/cluster) is separated from the rest of the graph.

The expansion of a partition is defined as the weight of the cut divided by number of nodes in the partition or in the rest of the graph, whatever is smaller. Small values thus indicate that the cut is small compared to the size of the smaller of the separated parts. For the whole partitions usually the maximum or the unweighted average is used. Note that expansion values can be larger than 1.

See also Experiments on Density-Constrained Graph Clustering, Robert Grke, Andrea Kappes and Dorothea Wagner, JEA 2015: http://dx.doi.org/10.1145/2638551

Public Functions

virtual void run() override

Execute the algorithm. The algorithm is not parallel.

inline virtual bool isSmallBetter() const override
Returns:

true - smaller values are better than larger values.

LocalPartitionEvaluation(const Graph &G, const Partition &P)

Initialize the partition evaluation method.

Parameters:
  • G – The graph on which the evaluation shall be performed

  • P – The partition that shall be evaluated.