fiedler_vector#
- fiedler_vector(G, weight='weight', normalized=False, tol=1e-08, method='tracemin_pcg', seed=None)[source]#
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 the graph.
- 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:
- fiedler_vectorNumPy 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.
Examples
Given a connected graph the signs of the values in the Fiedler vector can be used to partition the graph into two components.
>>> G = nx.barbell_graph(5, 0) >>> nx.fiedler_vector(G, normalized=True, seed=1) array([-0.32864129, -0.32864129, -0.32864129, -0.32864129, -0.26072899, 0.26072899, 0.32864129, 0.32864129, 0.32864129, 0.32864129])
The connected components are the two 5-node cliques of the barbell graph.