Skip to main content
`Ctrl`+`K`

# 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:
    G NetworkX graph
    seed integer, random_state, or None (default)

      Indicator of random number generation state. See Randomness.

    p scalar

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

    weight object

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

  Returns:
    cut_size scalar

      Value of the minimum cut.

    partition pair 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})