### comparison env/lib/python3.9/site-packages/networkx/linalg/laplacianmatrix.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal inserted replaced
-1:000000000000 0:4f3585e2f14b
1 """Laplacian matrix of graphs.
2 """
3 import networkx as nx
4 from networkx.utils import not_implemented_for
5
6 __all__ = [
7 "laplacian_matrix",
8 "normalized_laplacian_matrix",
9 "directed_laplacian_matrix",
10 "directed_combinatorial_laplacian_matrix",
11 ]
12
13
14 @not_implemented_for("directed")
15 def laplacian_matrix(G, nodelist=None, weight="weight"):
16 """Returns the Laplacian matrix of G.
17
18 The graph Laplacian is the matrix L = D - A, where
19 A is the adjacency matrix and D is the diagonal matrix of node degrees.
20
21 Parameters
22 ----------
23 G : graph
24 A NetworkX graph
25
26 nodelist : list, optional
27 The rows and columns are ordered according to the nodes in nodelist.
28 If nodelist is None, then the ordering is produced by G.nodes().
29
30 weight : string or None, optional (default='weight')
31 The edge data key used to compute each value in the matrix.
32 If None, then each edge has weight 1.
33
34 Returns
35 -------
36 L : SciPy sparse matrix
37 The Laplacian matrix of G.
38
39 Notes
40 -----
41 For MultiGraph/MultiDiGraph, the edges weights are summed.
42
44 --------
45 to_numpy_array
46 normalized_laplacian_matrix
47 laplacian_spectrum
48 """
49 import scipy.sparse
50
51 if nodelist is None:
52 nodelist = list(G)
53 A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight, format="csr")
54 n, m = A.shape
55 diags = A.sum(axis=1)
56 D = scipy.sparse.spdiags(diags.flatten(), , m, n, format="csr")
57 return D - A
58
59
60 @not_implemented_for("directed")
61 def normalized_laplacian_matrix(G, nodelist=None, weight="weight"):
62 r"""Returns the normalized Laplacian matrix of G.
63
64 The normalized graph Laplacian is the matrix
65
66 .. math::
67
68 N = D^{-1/2} L D^{-1/2}
69
70 where `L` is the graph Laplacian and `D` is the diagonal matrix of
71 node degrees.
72
73 Parameters
74 ----------
75 G : graph
76 A NetworkX graph
77
78 nodelist : list, optional
79 The rows and columns are ordered according to the nodes in nodelist.
80 If nodelist is None, then the ordering is produced by G.nodes().
81
82 weight : string or None, optional (default='weight')
83 The edge data key used to compute each value in the matrix.
84 If None, then each edge has weight 1.
85
86 Returns
87 -------
88 N : Scipy sparse matrix
89 The normalized Laplacian matrix of G.
90
91 Notes
92 -----
93 For MultiGraph/MultiDiGraph, the edges weights are summed.
94 See to_numpy_array for other options.
95
96 If the Graph contains selfloops, D is defined as diag(sum(A,1)), where A is
98
100 --------
101 laplacian_matrix
102 normalized_laplacian_spectrum
103
104 References
105 ----------
106 ..  Fan Chung-Graham, Spectral Graph Theory,
107 CBMS Regional Conference Series in Mathematics, Number 92, 1997.
108 ..  Steve Butler, Interlacing For Weighted Graphs Using The Normalized
109 Laplacian, Electronic Journal of Linear Algebra, Volume 16, pp. 90-98,
110 March 2007.
111 """
112 import numpy as np
113 import scipy
114 import scipy.sparse
115
116 if nodelist is None:
117 nodelist = list(G)
118 A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight, format="csr")
119 n, m = A.shape
120 diags = A.sum(axis=1).flatten()
121 D = scipy.sparse.spdiags(diags, , m, n, format="csr")
122 L = D - A
123 with scipy.errstate(divide="ignore"):
124 diags_sqrt = 1.0 / np.sqrt(diags)
125 diags_sqrt[np.isinf(diags_sqrt)] = 0
126 DH = scipy.sparse.spdiags(diags_sqrt, , m, n, format="csr")
127 return DH.dot(L.dot(DH))
128
129
130 ###############################################################################
131 # Code based on
132 # https://bitbucket.org/bedwards/networkx-community/src/370bd69fc02f/networkx/algorithms/community/
133
134
135 @not_implemented_for("undirected")
136 @not_implemented_for("multigraph")
137 def directed_laplacian_matrix(
138 G, nodelist=None, weight="weight", walk_type=None, alpha=0.95
139 ):
140 r"""Returns the directed Laplacian matrix of G.
141
142 The graph directed Laplacian is the matrix
143
144 .. math::
145
146 L = I - (\Phi^{1/2} P \Phi^{-1/2} + \Phi^{-1/2} P^T \Phi^{1/2} ) / 2
147
148 where `I` is the identity matrix, `P` is the transition matrix of the
149 graph, and `\Phi` a matrix with the Perron vector of `P` in the diagonal and
150 zeros elsewhere.
151
152 Depending on the value of walk_type, `P` can be the transition matrix
153 induced by a random walk, a lazy random walk, or a random walk with
154 teleportation (PageRank).
155
156 Parameters
157 ----------
158 G : DiGraph
159 A NetworkX graph
160
161 nodelist : list, optional
162 The rows and columns are ordered according to the nodes in nodelist.
163 If nodelist is None, then the ordering is produced by G.nodes().
164
165 weight : string or None, optional (default='weight')
166 The edge data key used to compute each value in the matrix.
167 If None, then each edge has weight 1.
168
169 walk_type : string or None, optional (default=None)
170 If None, `P` is selected depending on the properties of the
171 graph. Otherwise is one of 'random', 'lazy', or 'pagerank'
172
173 alpha : real
174 (1 - alpha) is the teleportation probability used with pagerank
175
176 Returns
177 -------
178 L : NumPy matrix
179 Normalized Laplacian of G.
180
181 Notes
182 -----
183 Only implemented for DiGraphs
184
186 --------
187 laplacian_matrix
188
189 References
190 ----------
191 ..  Fan Chung (2005).
192 Laplacians and the Cheeger inequality for directed graphs.
193 Annals of Combinatorics, 9(1), 2005
194 """
195 import numpy as np
196 from scipy.sparse import spdiags, linalg
197
198 P = _transition_matrix(
199 G, nodelist=nodelist, weight=weight, walk_type=walk_type, alpha=alpha
200 )
201
202 n, m = P.shape
203
204 evals, evecs = linalg.eigs(P.T, k=1)
205 v = evecs.flatten().real
206 p = v / v.sum()
207 sqrtp = np.sqrt(p)
208 Q = spdiags(sqrtp, , n, n) * P * spdiags(1.0 / sqrtp, , n, n)
209 I = np.identity(len(G))
210
211 return I - (Q + Q.T) / 2.0
212
213
214 @not_implemented_for("undirected")
215 @not_implemented_for("multigraph")
216 def directed_combinatorial_laplacian_matrix(
217 G, nodelist=None, weight="weight", walk_type=None, alpha=0.95
218 ):
219 r"""Return the directed combinatorial Laplacian matrix of G.
220
221 The graph directed combinatorial Laplacian is the matrix
222
223 .. math::
224
225 L = \Phi - (\Phi P + P^T \Phi) / 2
226
227 where `P` is the transition matrix of the graph and and `\Phi` a matrix
228 with the Perron vector of `P` in the diagonal and zeros elsewhere.
229
230 Depending on the value of walk_type, `P` can be the transition matrix
231 induced by a random walk, a lazy random walk, or a random walk with
232 teleportation (PageRank).
233
234 Parameters
235 ----------
236 G : DiGraph
237 A NetworkX graph
238
239 nodelist : list, optional
240 The rows and columns are ordered according to the nodes in nodelist.
241 If nodelist is None, then the ordering is produced by G.nodes().
242
243 weight : string or None, optional (default='weight')
244 The edge data key used to compute each value in the matrix.
245 If None, then each edge has weight 1.
246
247 walk_type : string or None, optional (default=None)
248 If None, `P` is selected depending on the properties of the
249 graph. Otherwise is one of 'random', 'lazy', or 'pagerank'
250
251 alpha : real
252 (1 - alpha) is the teleportation probability used with pagerank
253
254 Returns
255 -------
256 L : NumPy matrix
257 Combinatorial Laplacian of G.
258
259 Notes
260 -----
261 Only implemented for DiGraphs
262
264 --------
265 laplacian_matrix
266
267 References
268 ----------
269 ..  Fan Chung (2005).
270 Laplacians and the Cheeger inequality for directed graphs.
271 Annals of Combinatorics, 9(1), 2005
272 """
273 from scipy.sparse import spdiags, linalg
274
275 P = _transition_matrix(
276 G, nodelist=nodelist, weight=weight, walk_type=walk_type, alpha=alpha
277 )
278
279 n, m = P.shape
280
281 evals, evecs = linalg.eigs(P.T, k=1)
282 v = evecs.flatten().real
283 p = v / v.sum()
284 Phi = spdiags(p, , n, n)
285
286 Phi = Phi.todense()
287
288 return Phi - (Phi * P + P.T * Phi) / 2.0
289
290
291 def _transition_matrix(G, nodelist=None, weight="weight", walk_type=None, alpha=0.95):
292 """Returns the transition matrix of G.
293
294 This is a row stochastic giving the transition probabilities while
295 performing a random walk on the graph. Depending on the value of walk_type,
296 P can be the transition matrix induced by a random walk, a lazy random walk,
297 or a random walk with teleportation (PageRank).
298
299 Parameters
300 ----------
301 G : DiGraph
302 A NetworkX graph
303
304 nodelist : list, optional
305 The rows and columns are ordered according to the nodes in nodelist.
306 If nodelist is None, then the ordering is produced by G.nodes().
307
308 weight : string or None, optional (default='weight')
309 The edge data key used to compute each value in the matrix.
310 If None, then each edge has weight 1.
311
312 walk_type : string or None, optional (default=None)
313 If None, `P` is selected depending on the properties of the
314 graph. Otherwise is one of 'random', 'lazy', or 'pagerank'
315
316 alpha : real
317 (1 - alpha) is the teleportation probability used with pagerank
318
319 Returns
320 -------
321 P : NumPy matrix
322 transition matrix of G.
323
324 Raises
325 ------
326 NetworkXError
327 If walk_type not specified or alpha not in valid range
328 """
329 import numpy as np
330 from scipy.sparse import identity, spdiags
331
332 if walk_type is None:
333 if nx.is_strongly_connected(G):
334 if nx.is_aperiodic(G):
335 walk_type = "random"
336 else:
337 walk_type = "lazy"
338 else:
339 walk_type = "pagerank"
340
341 M = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight, dtype=float)
342 n, m = M.shape
343 if walk_type in ["random", "lazy"]:
344 DI = spdiags(1.0 / np.array(M.sum(axis=1).flat), , n, n)
345 if walk_type == "random":
346 P = DI * M
347 else:
348 I = identity(n)
349 P = (I + DI * M) / 2.0
350
351 elif walk_type == "pagerank":
352 if not (0 < alpha < 1):
353 raise nx.NetworkXError("alpha must be between 0 and 1")
354 # this is using a dense representation
355 M = M.todense()
356 # add constant to dangling nodes' row
357 dangling = np.where(M.sum(axis=1) == 0)
358 for d in dangling:
359 M[d] = 1.0 / n
360 # normalize
361 M = M / M.sum(axis=1)
362 P = alpha * M + (1 - alpha) / n
363 else:
364 raise nx.NetworkXError("walk_type must be random, lazy, or pagerank")
365
366 return P