Warning
This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.
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.