Eigenvector centrality fails to converge on disconnected graphs

Direct Answer

NetworkX intentionally raises PowerIterationFailedConvergence on disconnected graphs because eigenvector centrality is mathematically undefined when multiple components share the dominant eigenvalue. The library does not auto-fallback; you must preprocess the graph or choose a different centrality measure.

Extracting the largest weakly connected component before calling eigenvector_centrality() is the standard, correct approach — it preserves relative centrality ordering within that component. Increasing max_iter or tightening tol cannot fix the fundamental spectral-gap problem; parameter tuning only helps connected graphs with a small gap.

Why Convergence Fails

Eigenvector centrality relies on the Perron–Frobenius theorem, which guarantees a unique positive eigenvector only for irreducible (strongly connected) matrices. A disconnected graph has multiple components, each with eigenvalue 1. Power iteration oscillates between component eigenvectors or converges to an arbitrary linear combination, so NetworkX aborts after max_iter (default 100) with PowerIterationFailedConvergence.

Recommended Workflow

1. Preprocess: For undirected graphs, use max(nx.connected_components(G), key=len). For directed graphs, use max(nx.weakly_connected_components(G), key=len) to get the largest weakly connected component.
2. Compute: Call nx.eigenvector_centrality(subgraph) on that component. It will converge with default parameters.
3. Verify: Compare results with nx.eigenvector_centrality_numpy(subgraph) (SciPy backend) — they should match.

When to Switch Measures

If discarding other components violates your analytical intent, use a centrality defined for disconnected graphs:

• PageRank (nx.pagerank(G, alpha=0.85)): Always converges via teleportation; semantics differ from eigenvector centrality.
• Degree centrality (nx.degree_centrality(G)): Trivial, always defined.
• Betweenness centrality (nx.betweenness_centrality(G)): Defined everywhere, more expensive.

eigenvector_centrality_numpy() may return a result on disconnected graphs but the component chosen is implementation-dependent and not documented as stable — avoid relying on it.

Verification Steps

import networkx as nx

# 1. Confirm failure on disconnected graph
G = nx.disjoint_union(nx.complete_graph(5), nx.complete_graph(3))
try:
    nx.eigenvector_centrality(G)
except nx.PowerIterationFailedConvergence:
    print("Expected failure")

# 2. Verify component extraction works
largest = max(nx.connected_components(G), key=len)
sub = G.subgraph(largest)
cent = nx.eigenvector_centrality(sub)
cent_np = nx.eigenvector_centrality_numpy(sub)
assert all(abs(cent[n] - cent_np[n]) < 1e-10 for n in sub)
print("Component extraction converges and matches numpy backend")

# 3. Compare PageRank vs eigenvector on connected graph
G_conn = nx.barabasi_albert_graph(100, 3)
ec = nx.eigenvector_centrality(G_conn)
pr = nx.pagerank(G_conn, alpha=0.85)
# Rankings will differ — inspect before substituting
print(sorted(ec.items(), key=lambda x: -x[1])[:5])
print(sorted(pr.items(), key=lambda x: -x[1])[:5])

One Diagnostic Detail Needed

Is your graph directed or undirected? For directed graphs, weakly connected components may still contain nodes with no incoming/outgoing edges that affect convergence. If directionality matters for your ranking, consider extracting the largest strongly connected component instead (nx.strongly_connected_components).