randomized_partitioning#
- randomized_partitioning(G, seed=None, p=0.5, weight=None)[source]#
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.