Spaces:
Sleeping
Sleeping
File size: 4,194 Bytes
b200bda |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 |
"""
Eigenvalue spectrum of graphs.
"""
import networkx as nx
__all__ = [
"laplacian_spectrum",
"adjacency_spectrum",
"modularity_spectrum",
"normalized_laplacian_spectrum",
"bethe_hessian_spectrum",
]
@nx._dispatch(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._dispatch(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._dispatch(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._dispatch
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._dispatch
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())
|