Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2Eigenvalue spectrum of graphs.
3"""
5import networkx as nx
7__all__ = [
8 "laplacian_spectrum",
9 "adjacency_spectrum",
10 "modularity_spectrum",
11 "normalized_laplacian_spectrum",
12 "bethe_hessian_spectrum",
13]
16@nx._dispatchable(edge_attrs="weight")
17def laplacian_spectrum(G, weight="weight"):
18 """Returns eigenvalues of the Laplacian of G
20 Parameters
21 ----------
22 G : graph
23 A NetworkX graph
25 weight : string or None, optional (default='weight')
26 The edge data key used to compute each value in the matrix.
27 If None, then each edge has weight 1.
29 Returns
30 -------
31 evals : NumPy array
32 Eigenvalues
34 Notes
35 -----
36 For MultiGraph/MultiDiGraph, the edges weights are summed.
37 See :func:`~networkx.convert_matrix.to_numpy_array` for other options.
39 See Also
40 --------
41 laplacian_matrix
43 Examples
44 --------
45 The multiplicity of 0 as an eigenvalue of the laplacian matrix is equal
46 to the number of connected components of G.
48 >>> G = nx.Graph() # Create a graph with 5 nodes and 3 connected components
49 >>> G.add_nodes_from(range(5))
50 >>> G.add_edges_from([(0, 2), (3, 4)])
51 >>> nx.laplacian_spectrum(G)
52 array([0., 0., 0., 2., 2.])
54 """
55 import scipy as sp
57 return sp.linalg.eigvalsh(nx.laplacian_matrix(G, weight=weight).todense())
60@nx._dispatchable(edge_attrs="weight")
61def normalized_laplacian_spectrum(G, weight="weight"):
62 """Return eigenvalues of the normalized Laplacian of G
64 Parameters
65 ----------
66 G : graph
67 A NetworkX graph
69 weight : string or None, optional (default='weight')
70 The edge data key used to compute each value in the matrix.
71 If None, then each edge has weight 1.
73 Returns
74 -------
75 evals : NumPy array
76 Eigenvalues
78 Notes
79 -----
80 For MultiGraph/MultiDiGraph, the edges weights are summed.
81 See to_numpy_array for other options.
83 See Also
84 --------
85 normalized_laplacian_matrix
86 """
87 import scipy as sp
89 return sp.linalg.eigvalsh(
90 nx.normalized_laplacian_matrix(G, weight=weight).todense()
91 )
94@nx._dispatchable(edge_attrs="weight")
95def adjacency_spectrum(G, weight="weight"):
96 """Returns eigenvalues of the adjacency matrix of G.
98 Parameters
99 ----------
100 G : graph
101 A NetworkX graph
103 weight : string or None, optional (default='weight')
104 The edge data key used to compute each value in the matrix.
105 If None, then each edge has weight 1.
107 Returns
108 -------
109 evals : NumPy array
110 Eigenvalues
112 Notes
113 -----
114 For MultiGraph/MultiDiGraph, the edges weights are summed.
115 See to_numpy_array for other options.
117 See Also
118 --------
119 adjacency_matrix
120 """
121 import scipy as sp
123 return sp.linalg.eigvals(nx.adjacency_matrix(G, weight=weight).todense())
126@nx._dispatchable
127def modularity_spectrum(G):
128 """Returns eigenvalues of the modularity matrix of G.
130 Parameters
131 ----------
132 G : Graph
133 A NetworkX Graph or DiGraph
135 Returns
136 -------
137 evals : NumPy array
138 Eigenvalues
140 See Also
141 --------
142 modularity_matrix
144 References
145 ----------
146 .. [1] M. E. J. Newman, "Modularity and community structure in networks",
147 Proc. Natl. Acad. Sci. USA, vol. 103, pp. 8577-8582, 2006.
148 """
149 import scipy as sp
151 if G.is_directed():
152 return sp.linalg.eigvals(nx.directed_modularity_matrix(G))
153 else:
154 return sp.linalg.eigvals(nx.modularity_matrix(G))
157@nx._dispatchable
158def bethe_hessian_spectrum(G, r=None):
159 """Returns eigenvalues of the Bethe Hessian matrix of G.
161 Parameters
162 ----------
163 G : Graph
164 A NetworkX Graph or DiGraph
166 r : float
167 Regularizer parameter
169 Returns
170 -------
171 evals : NumPy array
172 Eigenvalues
174 See Also
175 --------
176 bethe_hessian_matrix
178 References
179 ----------
180 .. [1] A. Saade, F. Krzakala and L. Zdeborová
181 "Spectral clustering of graphs with the bethe hessian",
182 Advances in Neural Information Processing Systems. 2014.
183 """
184 import scipy as sp
186 return sp.linalg.eigvalsh(nx.bethe_hessian_matrix(G, r).todense())