Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (4.16 KB)

1
"""
2
Eigenvalue spectrum of graphs.
3
"""
4
#    Copyright (C) 2004-2019 by
5
#    Aric Hagberg <hagberg@lanl.gov>
6
#    Dan Schult <dschult@colgate.edu>
7
#    Pieter Swart <swart@lanl.gov>
8
#    All rights reserved.
9
#    BSD license.
10
import networkx as nx
11
__author__ = "\n".join(['Aric Hagberg <aric.hagberg@gmail.com>',
12
                        'Pieter Swart (swart@lanl.gov)',
13
                        'Dan Schult(dschult@colgate.edu)',
14
                        'Jean-Gabriel Young (jean.gabriel.young@gmail.com)'])
15

    
16
__all__ = ['laplacian_spectrum', 'adjacency_spectrum', 'modularity_spectrum', 
17
   'normalized_laplacian_spectrum', 'bethe_hessian_spectrum']
18

    
19

    
20
def laplacian_spectrum(G, weight='weight'):
21
    """Returns eigenvalues of the Laplacian of G
22

23
    Parameters
24
    ----------
25
    G : graph
26
       A NetworkX graph
27

28
    weight : string or None, optional (default='weight')
29
       The edge data key used to compute each value in the matrix.
30
       If None, then each edge has weight 1.
31

32
    Returns
33
    -------
34
    evals : NumPy array
35
      Eigenvalues
36

37
    Notes
38
    -----
39
    For MultiGraph/MultiDiGraph, the edges weights are summed.
40
    See to_numpy_matrix for other options.
41

42
    See Also
43
    --------
44
    laplacian_matrix
45
    """
46
    from scipy.linalg import eigvalsh
47
    return eigvalsh(nx.laplacian_matrix(G, weight=weight).todense())
48

    
49

    
50
def normalized_laplacian_spectrum(G, weight='weight'):
51
    """Return eigenvalues of the normalized Laplacian of G
52

53
    Parameters
54
    ----------
55
    G : graph
56
       A NetworkX graph
57

58
    weight : string or None, optional (default='weight')
59
       The edge data key used to compute each value in the matrix.
60
       If None, then each edge has weight 1.
61

62
    Returns
63
    -------
64
    evals : NumPy array
65
      Eigenvalues
66

67
    Notes
68
    -----
69
    For MultiGraph/MultiDiGraph, the edges weights are summed.
70
    See to_numpy_matrix for other options.
71

72
    See Also
73
    --------
74
    normalized_laplacian_matrix
75
    """
76
    from scipy.linalg import eigvalsh
77
    return eigvalsh(nx.normalized_laplacian_matrix(G, weight=weight).todense())
78

    
79

    
80
def adjacency_spectrum(G, weight='weight'):
81
    """Returns eigenvalues of the adjacency matrix of G.
82

83
    Parameters
84
    ----------
85
    G : graph
86
       A NetworkX graph
87

88
    weight : string or None, optional (default='weight')
89
       The edge data key used to compute each value in the matrix.
90
       If None, then each edge has weight 1.
91

92
    Returns
93
    -------
94
    evals : NumPy array
95
      Eigenvalues
96

97
    Notes
98
    -----
99
    For MultiGraph/MultiDiGraph, the edges weights are summed.
100
    See to_numpy_matrix for other options.
101

102
    See Also
103
    --------
104
    adjacency_matrix
105
    """
106
    from scipy.linalg import eigvals
107
    return eigvals(nx.adjacency_matrix(G, weight=weight).todense())
108

    
109

    
110
def modularity_spectrum(G):
111
    """Returns eigenvalues of the modularity matrix of G.
112

113
    Parameters
114
    ----------
115
    G : Graph
116
       A NetworkX Graph or DiGraph
117

118
    Returns
119
    -------
120
    evals : NumPy array
121
      Eigenvalues
122

123
    See Also
124
    --------
125
    modularity_matrix
126

127
    References
128
    ----------
129
    .. [1] M. E. J. Newman, "Modularity and community structure in networks",
130
       Proc. Natl. Acad. Sci. USA, vol. 103, pp. 8577-8582, 2006.
131
    """
132
    from scipy.linalg import eigvals
133
    if G.is_directed():
134
        return eigvals(nx.directed_modularity_matrix(G))
135
    else:
136
        return eigvals(nx.modularity_matrix(G))
137

    
138

    
139
def bethe_hessian_spectrum(G, r=None):
140
    """Returns eigenvalues of the Bethe Hessian matrix of G.
141

142
    Parameters
143
    ----------
144
    G : Graph
145
       A NetworkX Graph or DiGraph
146

147
    r : float
148
       Regularizer parameter
149

150
    Returns
151
    -------
152
    evals : NumPy array
153
      Eigenvalues
154

155
    See Also
156
    --------
157
    bethe_hessian_matrix
158

159
    References
160
    ----------
161
    .. [1] A. Saade, F. Krzakala and L. Zdeborov√°
162
      "Spectral clustering of graphs with the bethe hessian",
163
       Advances in Neural Information Processing Systems. 2014.
164
    """
165
    from scipy.linalg import eigvalsh
166
    return eigvalsh(nx.bethe_hessian_matrix(G, r).todense())
167
 
168
# fixture for nose tests
169

    
170

    
171
def setup_module(module):
172
    from nose import SkipTest
173
    try:
174
        import scipy.linalg
175
    except:
176
        raise SkipTest("scipy.linalg not available")