# algebraic_connectivity#

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

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:
GNetworkX graph

An undirected graph.

weightobject, optional (default: None)

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

normalizedbool, optional (default: False)

Whether the normalized Laplacian matrix is used.

tolfloat, optional (default: 1e-8)

Tolerance of relative residual in eigenvalue computation.

methodstring, 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

seedinteger, random_state, or None (default)

Indicator of random number generation state. See Randomness.

Returns:
algebraic_connectivityfloat

Algebraic connectivity.

Raises:
NetworkXNotImplemented

If G is directed.

NetworkXError

If G has less than two nodes.

`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
```