networkx.linalg.algebraicconnectivity.algebraic_connectivity¶
-
algebraic_connectivity
(G, weight='weight', normalized=False, tol=1e-08, method='tracemin_pcg')[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 (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_chol’ Cholesky factorization ‘tracemin_lu’ LU factorization
Returns: algebraic_connectivity – Algebraic connectivity.
Return type: Raises: NetworkXNotImplemented
– If G is directed.NetworkXError
– If G has less than two nodes.
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.See also
laplacian_matrix()