Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / assortativity / correlation.py @ 5cef0f13

History | View | Annotate | Download (8.55 KB)

1
#-*- coding: utf-8 -*-
2
"""Node assortativity coefficients and correlation measures.
3
"""
4
import networkx as nx
5
from networkx.algorithms.assortativity.mixing import degree_mixing_matrix, \
6
    attribute_mixing_matrix, numeric_mixing_matrix
7
from networkx.algorithms.assortativity.pairs import node_degree_xy, \
8
    node_attribute_xy
9
__author__ = ' '.join(['Aric Hagberg <aric.hagberg@gmail.com>',
10
                       'Oleguer Sagarra <oleguer.sagarra@gmail.com>'])
11
__all__ = ['degree_pearson_correlation_coefficient',
12
           'degree_assortativity_coefficient',
13
           'attribute_assortativity_coefficient',
14
           'numeric_assortativity_coefficient']
15

    
16

    
17
def degree_assortativity_coefficient(G, x='out', y='in', weight=None,
18
                                     nodes=None):
19
    """Compute degree assortativity of graph.
20

21
    Assortativity measures the similarity of connections
22
    in the graph with respect to the node degree.
23

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

28
    x: string ('in','out')
29
       The degree type for source node (directed graphs only).
30

31
    y: string ('in','out')
32
       The degree type for target node (directed graphs only).
33

34
    weight: string or None, optional (default=None)
35
       The edge attribute that holds the numerical value used 
36
       as a weight.  If None, then each edge has weight 1.
37
       The degree is the sum of the edge weights adjacent to the node.
38

39
    nodes: list or iterable (optional)
40
        Compute degree assortativity only for nodes in container. 
41
        The default is all nodes.
42

43
    Returns
44
    -------
45
    r : float
46
       Assortativity of graph by degree.
47

48
    Examples
49
    --------
50
    >>> G=nx.path_graph(4)
51
    >>> r=nx.degree_assortativity_coefficient(G)
52
    >>> print("%3.1f"%r)
53
    -0.5
54

55
    See Also
56
    --------
57
    attribute_assortativity_coefficient
58
    numeric_assortativity_coefficient
59
    neighbor_connectivity
60
    degree_mixing_dict
61
    degree_mixing_matrix
62

63
    Notes
64
    -----
65
    This computes Eq. (21) in Ref. [1]_ , where e is the joint
66
    probability distribution (mixing matrix) of the degrees.  If G is
67
    directed than the matrix e is the joint probability of the 
68
    user-specified degree type for the source and target.
69

70
    References
71
    ----------
72
    .. [1] M. E. J. Newman, Mixing patterns in networks,
73
       Physical Review E, 67 026126, 2003
74
    .. [2] Foster, J.G., Foster, D.V., Grassberger, P. & Paczuski, M. 
75
       Edge direction and the structure of networks, PNAS 107, 10815-20 (2010).
76
    """
77
    M = degree_mixing_matrix(G, x=x, y=y, nodes=nodes, weight=weight)
78
    return numeric_ac(M)
79

    
80

    
81
def degree_pearson_correlation_coefficient(G, x='out', y='in',
82
                                           weight=None, nodes=None):
83
    """Compute degree assortativity of graph. 
84

85
    Assortativity measures the similarity of connections
86
    in the graph with respect to the node degree.
87

88
    This is the same as degree_assortativity_coefficient but uses the 
89
    potentially faster scipy.stats.pearsonr function.
90

91
    Parameters
92
    ----------
93
    G : NetworkX graph
94

95
    x: string ('in','out')
96
       The degree type for source node (directed graphs only).
97

98
    y: string ('in','out')
99
       The degree type for target node (directed graphs only).
100

101
    weight: string or None, optional (default=None)
102
       The edge attribute that holds the numerical value used 
103
       as a weight.  If None, then each edge has weight 1.
104
       The degree is the sum of the edge weights adjacent to the node.
105

106
    nodes: list or iterable (optional)
107
        Compute pearson correlation of degrees only for specified nodes.
108
        The default is all nodes.
109

110
    Returns
111
    -------
112
    r : float
113
       Assortativity of graph by degree.
114

115
    Examples
116
    --------
117
    >>> G=nx.path_graph(4)
118
    >>> r=nx.degree_pearson_correlation_coefficient(G) 
119
    >>> print("%3.1f"%r)
120
    -0.5
121

122
    Notes
123
    -----
124
    This calls scipy.stats.pearsonr.
125

126
    References
127
    ----------
128
    .. [1] M. E. J. Newman, Mixing patterns in networks
129
           Physical Review E, 67 026126, 2003
130
    .. [2] Foster, J.G., Foster, D.V., Grassberger, P. & Paczuski, M. 
131
       Edge direction and the structure of networks, PNAS 107, 10815-20 (2010).
132
    """
133
    try:
134
        import scipy.stats as stats
135
    except ImportError:
136
        raise ImportError(
137
            "Assortativity requires SciPy: http://scipy.org/ ")
138
    xy = node_degree_xy(G, x=x, y=y, nodes=nodes, weight=weight)
139
    x, y = zip(*xy)
140
    return stats.pearsonr(x, y)[0]
141

    
142

    
143
def attribute_assortativity_coefficient(G, attribute, nodes=None):
144
    """Compute assortativity for node attributes.
145

146
    Assortativity measures the similarity of connections
147
    in the graph with respect to the given attribute.
148

149
    Parameters
150
    ----------
151
    G : NetworkX graph
152

153
    attribute : string 
154
        Node attribute key
155

156
    nodes: list or iterable (optional)
157
        Compute attribute assortativity for nodes in container. 
158
        The default is all nodes. 
159

160
    Returns
161
    -------
162
    r: float
163
       Assortativity of graph for given attribute
164

165
    Examples
166
    --------
167
    >>> G=nx.Graph()
168
    >>> G.add_nodes_from([0,1],color='red')
169
    >>> G.add_nodes_from([2,3],color='blue')
170
    >>> G.add_edges_from([(0,1),(2,3)])
171
    >>> print(nx.attribute_assortativity_coefficient(G,'color'))
172
    1.0
173

174
    Notes
175
    -----
176
    This computes Eq. (2) in Ref. [1]_ , trace(M)-sum(M))/(1-sum(M),
177
    where M is the joint probability distribution (mixing matrix)
178
    of the specified attribute.
179

180
    References
181
    ----------
182
    .. [1] M. E. J. Newman, Mixing patterns in networks,
183
       Physical Review E, 67 026126, 2003
184
    """
185
    M = attribute_mixing_matrix(G, attribute, nodes)
186
    return attribute_ac(M)
187

    
188

    
189
def numeric_assortativity_coefficient(G, attribute, nodes=None):
190
    """Compute assortativity for numerical node attributes.
191

192
    Assortativity measures the similarity of connections
193
    in the graph with respect to the given numeric attribute.
194
    The numeric attribute must be an integer.
195

196
    Parameters
197
    ----------
198
    G : NetworkX graph
199

200
    attribute : string 
201
        Node attribute key.  The corresponding attribute value must be an
202
        integer.
203

204
    nodes: list or iterable (optional)
205
        Compute numeric assortativity only for attributes of nodes in 
206
        container. The default is all nodes.
207

208
    Returns
209
    -------
210
    r: float
211
       Assortativity of graph for given attribute
212

213
    Examples
214
    --------
215
    >>> G=nx.Graph()
216
    >>> G.add_nodes_from([0,1],size=2)
217
    >>> G.add_nodes_from([2,3],size=3)
218
    >>> G.add_edges_from([(0,1),(2,3)])
219
    >>> print(nx.numeric_assortativity_coefficient(G,'size'))
220
    1.0
221

222
    Notes
223
    -----
224
    This computes Eq. (21) in Ref. [1]_ , for the mixing matrix of 
225
    of the specified attribute.
226

227
    References
228
    ----------
229
    .. [1] M. E. J. Newman, Mixing patterns in networks
230
           Physical Review E, 67 026126, 2003
231
    """
232
    a = numeric_mixing_matrix(G, attribute, nodes)
233
    return numeric_ac(a)
234

    
235

    
236
def attribute_ac(M):
237
    """Compute assortativity for attribute matrix M.
238

239
    Parameters
240
    ----------
241
    M : numpy array or matrix
242
        Attribute mixing matrix.
243

244
    Notes
245
    -----
246
    This computes Eq. (2) in Ref. [1]_ , (trace(e)-sum(e))/(1-sum(e)),
247
    where e is the joint probability distribution (mixing matrix)
248
    of the specified attribute.
249

250
    References
251
    ----------
252
    .. [1] M. E. J. Newman, Mixing patterns in networks,
253
       Physical Review E, 67 026126, 2003
254
    """
255
    try:
256
        import numpy
257
    except ImportError:
258
        raise ImportError(
259
            "attribute_assortativity requires NumPy: http://scipy.org/ ")
260
    if M.sum() != 1.0:
261
        M = M / float(M.sum())
262
    M = numpy.asmatrix(M)
263
    s = (M * M).sum()
264
    t = M.trace()
265
    r = (t - s) / (1 - s)
266
    return float(r)
267

    
268

    
269
def numeric_ac(M):
270
    # M is a numpy matrix or array
271
    # numeric assortativity coefficient, pearsonr
272
    try:
273
        import numpy
274
    except ImportError:
275
        raise ImportError('numeric_assortativity requires ',
276
                          'NumPy: http://scipy.org/')
277
    if M.sum() != 1.0:
278
        M = M / float(M.sum())
279
    nx, ny = M.shape  # nx=ny
280
    x = numpy.arange(nx)
281
    y = numpy.arange(ny)
282
    a = M.sum(axis=0)
283
    b = M.sum(axis=1)
284
    vara = (a * x**2).sum() - ((a * x).sum())**2
285
    varb = (b * x**2).sum() - ((b * x).sum())**2
286
    xy = numpy.outer(x, y)
287
    ab = numpy.outer(a, b)
288
    return (xy * (M - ab)).sum() / numpy.sqrt(vara * varb)
289

    
290

    
291
# fixture for nose tests
292
def setup_module(module):
293
    from nose import SkipTest
294
    try:
295
        import numpy
296
    except:
297
        raise SkipTest("NumPy not available")
298
    try:
299
        import scipy
300
    except:
301
        raise SkipTest("SciPy not available")