User Tools

Site Tools


algorithms:minimumcutset

Minimum Cut Set

The Minimum Cut Set algorithm finds a partition of the network into two disconnected parts such as the sum of the weights of the cut is minimum. If no weight is provided, a default value of 1 is assumed and the algorithm searches the minimum number of links whose removal disconnects the graph. The network must be undirected and connected with no parallel edges.

The Minimum Cut Set of a network may not be unique. Since the algorithm starts from a single node, varying this initial node can lead to different cut sets.

This metric creates a new node property to identify the two parts of the partition. It also creates a link property that identifies the links that belong to the Minimum Cut Set (the links that would have to be removed).

Input parameter Type Default Description
Initial Node*textCompulsoryNode Label of the initial node.
Property name*textMinimumCutSetName of the link and node property (output).
Link WeighttextNoneLink property acting as weight for the distance calculations. Must be positive numbers.

* Required Field

The Minimum Cut Set calculation is very tough, one of the most computationally expensive in BeGraph. We do not recommend it usage for large network unless it is really neccesary.

The next plot shows the minimum cut set (red nodes) and the links that should be removed to disconnect the network (red links). Although the network has around 1500 nodes and 2100 links, the computation took around one hour.



References

  • M.E.J. Newman, Networks, an introduction, Oxford University Press, 2010, ISBN: 978-0-19-920665-0, sec. 10.5.
  • Wikipedia: Minimum Cut
algorithms/minimumcutset.txt · Last modified: 2019/01/28 17:29 by systems