algebraic_connectivity¶

algebraic_connectivity(G, weight='weight', normalized=False, tol=1e-08, method='tracemin')[source]¶

Return 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 The data key used to determine the weight of each edge. If None, then each edge has unit weight. Default value: None. normalized : bool, optional Whether the normalized Laplacian matrix is used. Default value: False. tol : float, optional Tolerance of relative residual in eigenvalue computation. Default value: 1e-8. method : string, optional Method of eigenvalue computation. It should be one of ‘tracemin’ (TraceMIN), ‘lanczos’ (Lanczos iteration) and ‘lobpcg’ (LOBPCG). Default value: ‘tracemin’. 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_chol’ Cholesky factorization ‘tracemin_lu’ LU factorization
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.

To use Cholesky factorization in the TraceMIN algorithm, the scikits.sparse package must be installed.