networkx.linalg.algebraicconnectivity.fiedler_vector

fiedler_vector(G, weight='weight', normalized=False, tol=1e-08, method='tracemin_pcg', seed=None)

Returns 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 (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

• seed (integer, random_state, or None (default)) – Indicator of random number generation state. See Randomness.

Returns

fiedler_vector – Fiedler vector.

Return type

NumPy array of floats.

Raises

• NetworkXNotImplemented – If G is directed.

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

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()