## iof-tools / networkxMiCe / networkx-master / networkx / linalg / laplacianmatrix.py @ 5cef0f13

History | View | Annotate | Download (11.2 KB)

1 | 5cef0f13 | tiamilani | ```
"""Laplacian matrix of graphs.
``` |
---|---|---|---|

2 | ```
"""
``` |
||

3 | ```
# Copyright (C) 2004-2019 by
``` |
||

4 | ```
# Aric Hagberg <hagberg@lanl.gov>
``` |
||

5 | ```
# Dan Schult <dschult@colgate.edu>
``` |
||

6 | ```
# Pieter Swart <swart@lanl.gov>
``` |
||

7 | ```
# All rights reserved.
``` |
||

8 | ```
# BSD license.
``` |
||

9 | import networkx as nx |
||

10 | from networkx.utils import not_implemented_for |
||

11 | __author__ = "\n".join(['Aric Hagberg <aric.hagberg@gmail.com>', |
||

12 | ```
'Pieter Swart (swart@lanl.gov)',
``` |
||

13 | ```
'Dan Schult (dschult@colgate.edu)',
``` |
||

14 | ```
'Alejandro Weinstein <alejandro.weinstein@gmail.com>'])
``` |
||

15 | ```
__all__ = ['laplacian_matrix',
``` |
||

16 | ```
'normalized_laplacian_matrix',
``` |
||

17 | ```
'directed_laplacian_matrix',
``` |
||

18 | ```
'directed_combinatorial_laplacian_matrix']
``` |
||

19 | |||

20 | |||

21 | @not_implemented_for('directed') |
||

22 | def laplacian_matrix(G, nodelist=None, weight='weight'): |
||

23 | ```
"""Returns the Laplacian matrix of G.
``` |
||

24 | ```
``` |
||

25 | ```
The graph Laplacian is the matrix L = D - A, where
``` |
||

26 | ```
A is the adjacency matrix and D is the diagonal matrix of node degrees.
``` |
||

27 | ```
``` |
||

28 | ```
Parameters
``` |
||

29 | ```
----------
``` |
||

30 | ```
G : graph
``` |
||

31 | ```
A NetworkX graph
``` |
||

32 | ```
``` |
||

33 | ```
nodelist : list, optional
``` |
||

34 | ```
The rows and columns are ordered according to the nodes in nodelist.
``` |
||

35 | ```
If nodelist is None, then the ordering is produced by G.nodes().
``` |
||

36 | ```
``` |
||

37 | ```
weight : string or None, optional (default='weight')
``` |
||

38 | ```
The edge data key used to compute each value in the matrix.
``` |
||

39 | ```
If None, then each edge has weight 1.
``` |
||

40 | ```
``` |
||

41 | ```
Returns
``` |
||

42 | ```
-------
``` |
||

43 | ```
L : SciPy sparse matrix
``` |
||

44 | ```
The Laplacian matrix of G.
``` |
||

45 | ```
``` |
||

46 | ```
Notes
``` |
||

47 | ```
-----
``` |
||

48 | ```
For MultiGraph/MultiDiGraph, the edges weights are summed.
``` |
||

49 | ```
``` |
||

50 | ```
See Also
``` |
||

51 | ```
--------
``` |
||

52 | ```
to_numpy_matrix
``` |
||

53 | ```
normalized_laplacian_matrix
``` |
||

54 | ```
laplacian_spectrum
``` |
||

55 | ```
"""
``` |
||

56 | import scipy.sparse |
||

57 | if nodelist is None: |
||

58 | ```
nodelist = list(G)
``` |
||

59 | A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight, |
||

60 | ```
format='csr')
``` |
||

61 | n, m = A.shape |
||

62 | ```
diags = A.sum(axis=1)
``` |
||

63 | D = scipy.sparse.spdiags(diags.flatten(), [0], m, n, format='csr') |
||

64 | ```
return D - A
``` |
||

65 | |||

66 | |||

67 | @not_implemented_for('directed') |
||

68 | def normalized_laplacian_matrix(G, nodelist=None, weight='weight'): |
||

69 | ```
r"""Returns the normalized Laplacian matrix of G.
``` |
||

70 | ```
``` |
||

71 | ```
The normalized graph Laplacian is the matrix
``` |
||

72 | ```
``` |
||

73 | ```
.. math::
``` |
||

74 | ```
``` |
||

75 | ```
N = D^{-1/2} L D^{-1/2}
``` |
||

76 | ```
``` |
||

77 | ```
where `L` is the graph Laplacian and `D` is the diagonal matrix of
``` |
||

78 | ```
node degrees.
``` |
||

79 | ```
``` |
||

80 | ```
Parameters
``` |
||

81 | ```
----------
``` |
||

82 | ```
G : graph
``` |
||

83 | ```
A NetworkX graph
``` |
||

84 | ```
``` |
||

85 | ```
nodelist : list, optional
``` |
||

86 | ```
The rows and columns are ordered according to the nodes in nodelist.
``` |
||

87 | ```
If nodelist is None, then the ordering is produced by G.nodes().
``` |
||

88 | ```
``` |
||

89 | ```
weight : string or None, optional (default='weight')
``` |
||

90 | ```
The edge data key used to compute each value in the matrix.
``` |
||

91 | ```
If None, then each edge has weight 1.
``` |
||

92 | ```
``` |
||

93 | ```
Returns
``` |
||

94 | ```
-------
``` |
||

95 | ```
N : NumPy matrix
``` |
||

96 | ```
The normalized Laplacian matrix of G.
``` |
||

97 | ```
``` |
||

98 | ```
Notes
``` |
||

99 | ```
-----
``` |
||

100 | ```
For MultiGraph/MultiDiGraph, the edges weights are summed.
``` |
||

101 | ```
See to_numpy_matrix for other options.
``` |
||

102 | ```
``` |
||

103 | ```
If the Graph contains selfloops, D is defined as diag(sum(A,1)), where A is
``` |
||

104 | ```
the adjacency matrix [2]_.
``` |
||

105 | ```
``` |
||

106 | ```
See Also
``` |
||

107 | ```
--------
``` |
||

108 | ```
laplacian_matrix
``` |
||

109 | ```
normalized_laplacian_spectrum
``` |
||

110 | ```
``` |
||

111 | ```
References
``` |
||

112 | ```
----------
``` |
||

113 | ```
.. [1] Fan Chung-Graham, Spectral Graph Theory,
``` |
||

114 | ```
CBMS Regional Conference Series in Mathematics, Number 92, 1997.
``` |
||

115 | ```
.. [2] Steve Butler, Interlacing For Weighted Graphs Using The Normalized
``` |
||

116 | ```
Laplacian, Electronic Journal of Linear Algebra, Volume 16, pp. 90-98,
``` |
||

117 | ```
March 2007.
``` |
||

118 | ```
"""
``` |
||

119 | import scipy |
||

120 | import scipy.sparse |
||

121 | if nodelist is None: |
||

122 | ```
nodelist = list(G)
``` |
||

123 | A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight, |
||

124 | ```
format='csr')
``` |
||

125 | n, m = A.shape |
||

126 | ```
diags = A.sum(axis=1).flatten()
``` |
||

127 | D = scipy.sparse.spdiags(diags, [0], m, n, format='csr') |
||

128 | L = D - A |
||

129 | with scipy.errstate(divide='ignore'): |
||

130 | ```
diags_sqrt = 1.0 / scipy.sqrt(diags)
``` |
||

131 | ```
diags_sqrt[scipy.isinf(diags_sqrt)] = 0
``` |
||

132 | DH = scipy.sparse.spdiags(diags_sqrt, [0], m, n, format='csr') |
||

133 | ```
return DH.dot(L.dot(DH))
``` |
||

134 | |||

135 | ```
###############################################################################
``` |
||

136 | ```
# Code based on
``` |
||

137 | ```
# https://bitbucket.org/bedwards/networkx-community/src/370bd69fc02f/networkx/algorithms/community/
``` |
||

138 | |||

139 | |||

140 | @not_implemented_for('undirected') |
||

141 | @not_implemented_for('multigraph') |
||

142 | def directed_laplacian_matrix(G, nodelist=None, weight='weight', |
||

143 | walk_type=None, alpha=0.95): |
||

144 | ```
r"""Returns the directed Laplacian matrix of G.
``` |
||

145 | ```
``` |
||

146 | ```
The graph directed Laplacian is the matrix
``` |
||

147 | ```
``` |
||

148 | ```
.. math::
``` |
||

149 | ```
``` |
||

150 | ```
L = I - (\Phi^{1/2} P \Phi^{-1/2} + \Phi^{-1/2} P^T \Phi^{1/2} ) / 2
``` |
||

151 | ```
``` |
||

152 | ```
where `I` is the identity matrix, `P` is the transition matrix of the
``` |
||

153 | ```
graph, and `\Phi` a matrix with the Perron vector of `P` in the diagonal and
``` |
||

154 | ```
zeros elsewhere.
``` |
||

155 | ```
``` |
||

156 | ```
Depending on the value of walk_type, `P` can be the transition matrix
``` |
||

157 | ```
induced by a random walk, a lazy random walk, or a random walk with
``` |
||

158 | ```
teleportation (PageRank).
``` |
||

159 | ```
``` |
||

160 | ```
Parameters
``` |
||

161 | ```
----------
``` |
||

162 | ```
G : DiGraph
``` |
||

163 | ```
A NetworkX graph
``` |
||

164 | ```
``` |
||

165 | ```
nodelist : list, optional
``` |
||

166 | ```
The rows and columns are ordered according to the nodes in nodelist.
``` |
||

167 | ```
If nodelist is None, then the ordering is produced by G.nodes().
``` |
||

168 | ```
``` |
||

169 | ```
weight : string or None, optional (default='weight')
``` |
||

170 | ```
The edge data key used to compute each value in the matrix.
``` |
||

171 | ```
If None, then each edge has weight 1.
``` |
||

172 | ```
``` |
||

173 | ```
walk_type : string or None, optional (default=None)
``` |
||

174 | ```
If None, `P` is selected depending on the properties of the
``` |
||

175 | ```
graph. Otherwise is one of 'random', 'lazy', or 'pagerank'
``` |
||

176 | ```
``` |
||

177 | ```
alpha : real
``` |
||

178 | ```
(1 - alpha) is the teleportation probability used with pagerank
``` |
||

179 | ```
``` |
||

180 | ```
Returns
``` |
||

181 | ```
-------
``` |
||

182 | ```
L : NumPy array
``` |
||

183 | ```
Normalized Laplacian of G.
``` |
||

184 | ```
``` |
||

185 | ```
Notes
``` |
||

186 | ```
-----
``` |
||

187 | ```
Only implemented for DiGraphs
``` |
||

188 | ```
``` |
||

189 | ```
See Also
``` |
||

190 | ```
--------
``` |
||

191 | ```
laplacian_matrix
``` |
||

192 | ```
``` |
||

193 | ```
References
``` |
||

194 | ```
----------
``` |
||

195 | ```
.. [1] Fan Chung (2005).
``` |
||

196 | ```
Laplacians and the Cheeger inequality for directed graphs.
``` |
||

197 | ```
Annals of Combinatorics, 9(1), 2005
``` |
||

198 | ```
"""
``` |
||

199 | import scipy as sp |
||

200 | from scipy.sparse import spdiags, linalg |
||

201 | |||

202 | P = _transition_matrix(G, nodelist=nodelist, weight=weight, |
||

203 | walk_type=walk_type, alpha=alpha) |
||

204 | |||

205 | n, m = P.shape |
||

206 | |||

207 | ```
evals, evecs = linalg.eigs(P.T, k=1)
``` |
||

208 | v = evecs.flatten().real |
||

209 | p = v / v.sum() |
||

210 | sqrtp = sp.sqrt(p) |
||

211 | Q = spdiags(sqrtp, [0], n, n) * P * spdiags(1.0 / sqrtp, [0], n, n) |
||

212 | ```
I = sp.identity(len(G))
``` |
||

213 | |||

214 | return I - (Q + Q.T) / 2.0 |
||

215 | |||

216 | |||

217 | @not_implemented_for('undirected') |
||

218 | @not_implemented_for('multigraph') |
||

219 | def directed_combinatorial_laplacian_matrix(G, nodelist=None, weight='weight', |
||

220 | walk_type=None, alpha=0.95): |
||

221 | ```
r"""Return the directed combinatorial Laplacian matrix of G.
``` |
||

222 | ```
``` |
||

223 | ```
The graph directed combinatorial Laplacian is the matrix
``` |
||

224 | ```
``` |
||

225 | ```
.. math::
``` |
||

226 | ```
``` |
||

227 | ```
L = \Phi - (\Phi P + P^T \Phi) / 2
``` |
||

228 | ```
``` |
||

229 | ```
where `P` is the transition matrix of the graph and and `\Phi` a matrix
``` |
||

230 | ```
with the Perron vector of `P` in the diagonal and zeros elsewhere.
``` |
||

231 | ```
``` |
||

232 | ```
Depending on the value of walk_type, `P` can be the transition matrix
``` |
||

233 | ```
induced by a random walk, a lazy random walk, or a random walk with
``` |
||

234 | ```
teleportation (PageRank).
``` |
||

235 | ```
``` |
||

236 | ```
Parameters
``` |
||

237 | ```
----------
``` |
||

238 | ```
G : DiGraph
``` |
||

239 | ```
A NetworkX graph
``` |
||

240 | ```
``` |
||

241 | ```
nodelist : list, optional
``` |
||

242 | ```
The rows and columns are ordered according to the nodes in nodelist.
``` |
||

243 | ```
If nodelist is None, then the ordering is produced by G.nodes().
``` |
||

244 | ```
``` |
||

245 | ```
weight : string or None, optional (default='weight')
``` |
||

246 | ```
The edge data key used to compute each value in the matrix.
``` |
||

247 | ```
If None, then each edge has weight 1.
``` |
||

248 | ```
``` |
||

249 | ```
walk_type : string or None, optional (default=None)
``` |
||

250 | ```
If None, `P` is selected depending on the properties of the
``` |
||

251 | ```
graph. Otherwise is one of 'random', 'lazy', or 'pagerank'
``` |
||

252 | ```
``` |
||

253 | ```
alpha : real
``` |
||

254 | ```
(1 - alpha) is the teleportation probability used with pagerank
``` |
||

255 | ```
``` |
||

256 | ```
Returns
``` |
||

257 | ```
-------
``` |
||

258 | ```
L : NumPy array
``` |
||

259 | ```
Combinatorial Laplacian of G.
``` |
||

260 | ```
``` |
||

261 | ```
Notes
``` |
||

262 | ```
-----
``` |
||

263 | ```
Only implemented for DiGraphs
``` |
||

264 | ```
``` |
||

265 | ```
See Also
``` |
||

266 | ```
--------
``` |
||

267 | ```
laplacian_matrix
``` |
||

268 | ```
``` |
||

269 | ```
References
``` |
||

270 | ```
----------
``` |
||

271 | ```
.. [1] Fan Chung (2005).
``` |
||

272 | ```
Laplacians and the Cheeger inequality for directed graphs.
``` |
||

273 | ```
Annals of Combinatorics, 9(1), 2005
``` |
||

274 | ```
"""
``` |
||

275 | from scipy.sparse import spdiags, linalg |
||

276 | |||

277 | P = _transition_matrix(G, nodelist=nodelist, weight=weight, |
||

278 | walk_type=walk_type, alpha=alpha) |
||

279 | |||

280 | n, m = P.shape |
||

281 | |||

282 | ```
evals, evecs = linalg.eigs(P.T, k=1)
``` |
||

283 | v = evecs.flatten().real |
||

284 | p = v / v.sum() |
||

285 | ```
Phi = spdiags(p, [0], n, n)
``` |
||

286 | |||

287 | Phi = Phi.todense() |
||

288 | |||

289 | return Phi - (Phi*P + P.T*Phi) / 2.0 |
||

290 | |||

291 | |||

292 | def _transition_matrix(G, nodelist=None, weight='weight', |
||

293 | walk_type=None, alpha=0.95): |
||

294 | ```
"""Returns the transition matrix of G.
``` |
||

295 | ```
``` |
||

296 | ```
This is a row stochastic giving the transition probabilities while
``` |
||

297 | ```
performing a random walk on the graph. Depending on the value of walk_type,
``` |
||

298 | ```
P can be the transition matrix induced by a random walk, a lazy random walk,
``` |
||

299 | ```
or a random walk with teleportation (PageRank).
``` |
||

300 | ```
``` |
||

301 | ```
Parameters
``` |
||

302 | ```
----------
``` |
||

303 | ```
G : DiGraph
``` |
||

304 | ```
A NetworkX graph
``` |
||

305 | ```
``` |
||

306 | ```
nodelist : list, optional
``` |
||

307 | ```
The rows and columns are ordered according to the nodes in nodelist.
``` |
||

308 | ```
If nodelist is None, then the ordering is produced by G.nodes().
``` |
||

309 | ```
``` |
||

310 | ```
weight : string or None, optional (default='weight')
``` |
||

311 | ```
The edge data key used to compute each value in the matrix.
``` |
||

312 | ```
If None, then each edge has weight 1.
``` |
||

313 | ```
``` |
||

314 | ```
walk_type : string or None, optional (default=None)
``` |
||

315 | ```
If None, `P` is selected depending on the properties of the
``` |
||

316 | ```
graph. Otherwise is one of 'random', 'lazy', or 'pagerank'
``` |
||

317 | ```
``` |
||

318 | ```
alpha : real
``` |
||

319 | ```
(1 - alpha) is the teleportation probability used with pagerank
``` |
||

320 | ```
``` |
||

321 | ```
Returns
``` |
||

322 | ```
-------
``` |
||

323 | ```
P : NumPy array
``` |
||

324 | ```
transition matrix of G.
``` |
||

325 | ```
``` |
||

326 | ```
Raises
``` |
||

327 | ```
------
``` |
||

328 | ```
NetworkXError
``` |
||

329 | ```
If walk_type not specified or alpha not in valid range
``` |
||

330 | ```
"""
``` |
||

331 | |||

332 | import scipy as sp |
||

333 | from scipy.sparse import identity, spdiags |
||

334 | if walk_type is None: |
||

335 | ```
if nx.is_strongly_connected(G):
``` |
||

336 | ```
if nx.is_aperiodic(G):
``` |
||

337 | ```
walk_type = "random"
``` |
||

338 | ```
else:
``` |
||

339 | ```
walk_type = "lazy"
``` |
||

340 | ```
else:
``` |
||

341 | ```
walk_type = "pagerank"
``` |
||

342 | |||

343 | M = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight, |
||

344 | ```
dtype=float)
``` |
||

345 | n, m = M.shape |
||

346 | if walk_type in ["random", "lazy"]: |
||

347 | DI = spdiags(1.0 / sp.array(M.sum(axis=1).flat), [0], n, n) |
||

348 | if walk_type == "random": |
||

349 | P = DI * M |
||

350 | ```
else:
``` |
||

351 | I = identity(n) |
||

352 | ```
P = (I + DI * M) / 2.0
``` |
||

353 | |||

354 | elif walk_type == "pagerank": |
||

355 | if not (0 < alpha < 1): |
||

356 | raise nx.NetworkXError('alpha must be between 0 and 1') |
||

357 | ```
# this is using a dense representation
``` |
||

358 | M = M.todense() |
||

359 | ```
# add constant to dangling nodes' row
``` |
||

360 | dangling = sp.where(M.sum(axis=1) == 0) |
||

361 | for d in dangling[0]: |
||

362 | ```
M[d] = 1.0 / n
``` |
||

363 | ```
# normalize
``` |
||

364 | ```
M = M / M.sum(axis=1)
``` |
||

365 | ```
P = alpha * M + (1 - alpha) / n
``` |
||

366 | ```
else:
``` |
||

367 | raise nx.NetworkXError("walk_type must be random, lazy, or pagerank") |
||

368 | |||

369 | ```
return P
``` |
||

370 | |||

371 | ```
# fixture for nose tests
``` |
||

372 | |||

373 | |||

374 | def setup_module(module): |
||

375 | from nose import SkipTest |
||

376 | ```
try:
``` |
||

377 | import numpy |
||

378 | ```
except:
``` |
||

379 | raise SkipTest("NumPy not available") |