Skip to main content
`Ctrl`+`K`

# algebraic_connectivity

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

  Returns the algebraic connectivity of an undirected graph.

  The algebraic connectivity of a connected undirected graph is the second smallest eigenvalue of its Laplacian matrix.

  Parameters:
    G NetworkX graph

      An undirected graph.

    weight object, optional (default: None)

      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:
    algebraic_connectivity float

      Algebraic connectivity.

  Raises:
    NetworkXNotImplemented

      If G is directed.

    NetworkXError

      If G has less than two nodes.

  See also

  `laplacian_matrix`

  Notes

  Edge weights are interpreted by their absolute values. For MultiGraph’s, weights of parallel edges are summed. Zero-weighted edges are ignored.

  Examples

  For undirected graphs algebraic connectivity can tell us if a graph is connected or not `G` is connected iff `algebraic_connectivity(G) > 0`:

      >>> G = nx.complete_graph(5)
      >>> nx.algebraic_connectivity(G) > 0
      True
      >>> G.add_node(10)  # G is no longer connected
      >>> nx.algebraic_connectivity(G) > 0
      False