Network Science with Python and NetworkX Quick Start Guide

Minimum cuts

More sophisticated measures of resilience are based on the concept of minimum cuts. A minimum cut or min-cut is the number of nodes (or edges) that need to be removed to separate the network into two unconnected parts. Minimum cuts can be found either between two specific nodes, or over all pairs of nodes.

In NetworkX, the minimum cut between two nodes is found using the minimum_st_node_cut() function. Note that this function is in the connectivity package and needs to be imported separately in addition to the base networkx package. The following code finds the minimum node cut between Mr. Hi and John A. in the karate club network:

import networkx.algorithms.connectivity as nxconnxcon.minimum_st_node_cut(G_karate, mr_hi, john_a) ...