Class IsolatedInterpartitionConductance

Inheritance Relationships

Base Type

Class Documentation

class IsolatedInterpartitionConductance : public NetworKit::LocalPartitionEvaluation

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

The conductance of a partition is defined as the weight of the cut divided by the volume (the sum of the degrees) of the nodes in the partition or the nodes in the rest of the graph, whatever is smaller. Small values thus indicate that the cut is small compared to the volume of the smaller of the separated parts. For the whole partitions usually the maximum or the unweighted average is used.

See also Experiments on Density-Constrained Graph Clustering, Robert Gorke, 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.