Skip to main content
`Ctrl`+`K`

# spectral_bisection

spectral_bisection(G, weight='weight', normalized=False, tol=1e-08, method='tracemin_pcg', seed=None)

  Bisect the graph using the Fiedler vector.

  This method uses the Fiedler vector to bisect a graph. The partition is defined by the nodes which are associated with either positive or negative values in the vector.

  Parameters:
    G NetworkX Graph
    weight str, optional (default: weight)

      The data key used to determine the weight of each edge. If None, then each edge has unit weight.

    normalized bool, optional (default: False)

      Whether the normalized Laplacian matrix is used.

    tol float, optional (default: 1e-8)

      Tolerance of relative residual in eigenvalue computation.

    method string, optional (default: ‘tracemin_pcg’)

      Method of eigenvalue computation. It must be one of the tracemin options shown below (TraceMIN), ‘lanczos’ (Lanczos iteration) or ‘lobpcg’ (LOBPCG).

      The TraceMIN algorithm uses a linear system solver. The following values allow specifying the solver to be used.

      Value | Solver
      --- | ---
      ‘tracemin_pcg’ | Preconditioned conjugate gradient method
      ‘tracemin_lu’ | LU factorization

    seed integer, random_state, or None (default)

      Indicator of random number generation state. See Randomness.

  Returns:
    bisection tuple of sets

      Sets with the bisection of nodes

  References

  [1]

  M. E. J Newman ‘Networks: An Introduction’, pages 364-370 Oxford University Press 2011.

  Examples

      >>> G = nx.barbell_graph(3, 0)
      >>> nx.spectral_bisection(G)
      ({0, 1, 2}, {3, 4, 5})