Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (11.2 KB)

1
"""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")