normalized_cut_size

normalized_cut_size(G, S, T=None, weight=None)

Returns the normalized size of the cut between two sets of nodes.

The normalized cut size is the cut size times the sum of the reciprocal sizes of the volumes of the two sets. [1]

Parameters:

GNetworkX graph

Scollection

A collection of nodes in G.

Tcollection

A collection of nodes in G.

weightobject

Edge attribute key to use as weight. If not specified, edges have weight one.

Returns:

number

The normalized cut size between the two sets S and T.

See also

conductance

cut_size

edge_expansion

volume

Notes

In a multigraph, the cut size is the total weight of edges including multiplicity.

References

[1]

David Gleich. Hierarchical Directed Spectral Graph Partitioning. <https://www.cs.purdue.edu/homes/dgleich/publications/Gleich%202005%20-%20hierarchical%20directed%20spectral.pdf>

---

Additional backends implement this function

graphblas : OpenMP-enabled sparse linear algebra backend.