|
""" |
|
Eigenvalue spectrum of graphs. |
|
""" |
|
|
|
import networkx as nx |
|
|
|
__all__ = [ |
|
"laplacian_spectrum", |
|
"adjacency_spectrum", |
|
"modularity_spectrum", |
|
"normalized_laplacian_spectrum", |
|
"bethe_hessian_spectrum", |
|
] |
|
|
|
|
|
@nx._dispatchable(edge_attrs="weight") |
|
def laplacian_spectrum(G, weight="weight"): |
|
"""Returns eigenvalues of the Laplacian of G |
|
|
|
Parameters |
|
---------- |
|
G : graph |
|
A NetworkX graph |
|
|
|
weight : string or None, optional (default='weight') |
|
The edge data key used to compute each value in the matrix. |
|
If None, then each edge has weight 1. |
|
|
|
Returns |
|
------- |
|
evals : NumPy array |
|
Eigenvalues |
|
|
|
Notes |
|
----- |
|
For MultiGraph/MultiDiGraph, the edges weights are summed. |
|
See :func:`~networkx.convert_matrix.to_numpy_array` for other options. |
|
|
|
See Also |
|
-------- |
|
laplacian_matrix |
|
|
|
Examples |
|
-------- |
|
The multiplicity of 0 as an eigenvalue of the laplacian matrix is equal |
|
to the number of connected components of G. |
|
|
|
>>> G = nx.Graph() # Create a graph with 5 nodes and 3 connected components |
|
>>> G.add_nodes_from(range(5)) |
|
>>> G.add_edges_from([(0, 2), (3, 4)]) |
|
>>> nx.laplacian_spectrum(G) |
|
array([0., 0., 0., 2., 2.]) |
|
|
|
""" |
|
import scipy as sp |
|
|
|
return sp.linalg.eigvalsh(nx.laplacian_matrix(G, weight=weight).todense()) |
|
|
|
|
|
@nx._dispatchable(edge_attrs="weight") |
|
def normalized_laplacian_spectrum(G, weight="weight"): |
|
"""Return eigenvalues of the normalized Laplacian of G |
|
|
|
Parameters |
|
---------- |
|
G : graph |
|
A NetworkX graph |
|
|
|
weight : string or None, optional (default='weight') |
|
The edge data key used to compute each value in the matrix. |
|
If None, then each edge has weight 1. |
|
|
|
Returns |
|
------- |
|
evals : NumPy array |
|
Eigenvalues |
|
|
|
Notes |
|
----- |
|
For MultiGraph/MultiDiGraph, the edges weights are summed. |
|
See to_numpy_array for other options. |
|
|
|
See Also |
|
-------- |
|
normalized_laplacian_matrix |
|
""" |
|
import scipy as sp |
|
|
|
return sp.linalg.eigvalsh( |
|
nx.normalized_laplacian_matrix(G, weight=weight).todense() |
|
) |
|
|
|
|
|
@nx._dispatchable(edge_attrs="weight") |
|
def adjacency_spectrum(G, weight="weight"): |
|
"""Returns eigenvalues of the adjacency matrix of G. |
|
|
|
Parameters |
|
---------- |
|
G : graph |
|
A NetworkX graph |
|
|
|
weight : string or None, optional (default='weight') |
|
The edge data key used to compute each value in the matrix. |
|
If None, then each edge has weight 1. |
|
|
|
Returns |
|
------- |
|
evals : NumPy array |
|
Eigenvalues |
|
|
|
Notes |
|
----- |
|
For MultiGraph/MultiDiGraph, the edges weights are summed. |
|
See to_numpy_array for other options. |
|
|
|
See Also |
|
-------- |
|
adjacency_matrix |
|
""" |
|
import scipy as sp |
|
|
|
return sp.linalg.eigvals(nx.adjacency_matrix(G, weight=weight).todense()) |
|
|
|
|
|
@nx._dispatchable |
|
def modularity_spectrum(G): |
|
"""Returns eigenvalues of the modularity matrix of G. |
|
|
|
Parameters |
|
---------- |
|
G : Graph |
|
A NetworkX Graph or DiGraph |
|
|
|
Returns |
|
------- |
|
evals : NumPy array |
|
Eigenvalues |
|
|
|
See Also |
|
-------- |
|
modularity_matrix |
|
|
|
References |
|
---------- |
|
.. [1] M. E. J. Newman, "Modularity and community structure in networks", |
|
Proc. Natl. Acad. Sci. USA, vol. 103, pp. 8577-8582, 2006. |
|
""" |
|
import scipy as sp |
|
|
|
if G.is_directed(): |
|
return sp.linalg.eigvals(nx.directed_modularity_matrix(G)) |
|
else: |
|
return sp.linalg.eigvals(nx.modularity_matrix(G)) |
|
|
|
|
|
@nx._dispatchable |
|
def bethe_hessian_spectrum(G, r=None): |
|
"""Returns eigenvalues of the Bethe Hessian matrix of G. |
|
|
|
Parameters |
|
---------- |
|
G : Graph |
|
A NetworkX Graph or DiGraph |
|
|
|
r : float |
|
Regularizer parameter |
|
|
|
Returns |
|
------- |
|
evals : NumPy array |
|
Eigenvalues |
|
|
|
See Also |
|
-------- |
|
bethe_hessian_matrix |
|
|
|
References |
|
---------- |
|
.. [1] A. Saade, F. Krzakala and L. Zdeborová |
|
"Spectral clustering of graphs with the bethe hessian", |
|
Advances in Neural Information Processing Systems. 2014. |
|
""" |
|
import scipy as sp |
|
|
|
return sp.linalg.eigvalsh(nx.bethe_hessian_matrix(G, r).todense()) |
|
|
