Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

fiedler_vector

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

Return the Fiedler vector of a connected undirected graph.

The Fiedler vector of a connected undirected graph is the eigenvector corresponding to the second smallest eigenvalue of the Laplacian matrix of of the graph.

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:

fiedler_vector : NumPy array of floats.

Fiedler vector.

Raises:

NetworkXNotImplemented

If G is directed.

NetworkXError

If G has less than two nodes or is not connected.

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.