randomized_partitioning

randomized_partitioning(G, seed=None, p=0.5, weight=None)

Compute a random partitioning of the graph nodes and its cut value.

A partitioning is calculated by observing each node and deciding to add it to the partition with probability p, returning a random cut and its corresponding value (the sum of weights of edges connecting different partitions).

Parameters:

GNetworkX graph

seedinteger, random_state, or None (default)

Indicator of random number generation state. See Randomness.

pscalar

Probability for each node to be part of the first partition. Should be in [0,1]

weightobject

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

Returns:

cut_sizescalar

Value of the minimum cut.

partitionpair of node sets

A partitioning of the nodes that defines a minimum cut.