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.
- Raises:
- NetworkXNotImplemented
If the graph is directed or is a multigraph.
Examples
>>> G = nx.complete_graph(5) >>> cut_size, partition = nx.approximation.randomized_partitioning(G, seed=1) >>> cut_size 6 >>> partition ({0, 3, 4}, {1, 2})