Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (5.07 KB)

1
"""Modularity 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
from __future__ import division
10
import networkx as nx
11
from networkx.utils import not_implemented_for
12
__author__ = "\n".join(['Aric Hagberg <aric.hagberg@gmail.com>',
13
                        'Pieter Swart (swart@lanl.gov)',
14
                        'Dan Schult (dschult@colgate.edu)',
15
                        'Jean-Gabriel Young (Jean.gabriel.young@gmail.com)'])
16
__all__ = ['modularity_matrix', 'directed_modularity_matrix']
17

    
18

    
19
@not_implemented_for('directed')
20
@not_implemented_for('multigraph')
21
def modularity_matrix(G, nodelist=None, weight=None):
22
    r"""Returns the modularity matrix of G.
23

24
    The modularity matrix is the matrix B = A - <A>, where A is the adjacency
25
    matrix and <A> is the average adjacency matrix, assuming that the graph
26
    is described by the configuration model.
27

28
    More specifically, the element B_ij of B is defined as
29

30
    .. math::
31
        A_{ij} - {k_i k_j \over 2 m}
32

33
    where k_i is the degree of node i, and where m is the number of edges
34
    in the graph. When weight is set to a name of an attribute edge, Aij, k_i,
35
    k_j and m are computed using its value.
36

37
    Parameters
38
    ----------
39
    G : Graph
40
       A NetworkX graph
41

42
    nodelist : list, optional
43
       The rows and columns are ordered according to the nodes in nodelist.
44
       If nodelist is None, then the ordering is produced by G.nodes().
45

46
    weight : string or None, optional (default=None)
47
       The edge attribute that holds the numerical value used for
48
       the edge weight.  If None then all edge weights are 1.
49

50
    Returns
51
    -------
52
    B : Numpy matrix
53
      The modularity matrix of G.
54

55
    Examples
56
    --------
57
    >>> import networkx as nx
58
    >>> k =[3, 2, 2, 1, 0]
59
    >>> G = nx.havel_hakimi_graph(k)
60
    >>> B = nx.modularity_matrix(G)
61

62

63
    See Also
64
    --------
65
    to_numpy_matrix
66
    modularity_spectrum
67
    adjacency_matrix
68
    directed_modularity_matrix
69

70
    References
71
    ----------
72
    .. [1] M. E. J. Newman, "Modularity and community structure in networks",
73
           Proc. Natl. Acad. Sci. USA, vol. 103, pp. 8577-8582, 2006.
74
    """
75
    if nodelist is None:
76
        nodelist = list(G)
77
    A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight,
78
                                  format='csr')
79
    k = A.sum(axis=1)
80
    m = k.sum() * 0.5
81
    # Expected adjacency matrix
82
    X = k * k.transpose() / (2 * m)
83
    return A - X
84

    
85

    
86
@not_implemented_for('undirected')
87
@not_implemented_for('multigraph')
88
def directed_modularity_matrix(G, nodelist=None, weight=None):
89
    """Returns the directed modularity matrix of G.
90

91
    The modularity matrix is the matrix B = A - <A>, where A is the adjacency
92
    matrix and <A> is the expected adjacency matrix, assuming that the graph
93
    is described by the configuration model.
94

95
    More specifically, the element B_ij of B is defined as
96

97
    .. math::
98
        B_{ij} = A_{ij} - k_i^{out} k_j^{in} / m
99

100
    where :math:`k_i^{in}` is the in degree of node i, and :math:`k_j^{out}` is the out degree
101
    of node j, with m the number of edges in the graph. When weight is set
102
    to a name of an attribute edge, Aij, k_i, k_j and m are computed using
103
    its value.
104

105
    Parameters
106
    ----------
107
    G : DiGraph
108
       A NetworkX DiGraph
109

110
    nodelist : list, optional
111
       The rows and columns are ordered according to the nodes in nodelist.
112
       If nodelist is None, then the ordering is produced by G.nodes().
113

114
    weight : string or None, optional (default=None)
115
       The edge attribute that holds the numerical value used for
116
       the edge weight.  If None then all edge weights are 1.
117

118
    Returns
119
    -------
120
    B : Numpy matrix
121
      The modularity matrix of G.
122

123
    Examples
124
    --------
125
    >>> import networkx as nx
126
    >>> G = nx.DiGraph()
127
    >>> G.add_edges_from(((1,2), (1,3), (3,1), (3,2), (3,5), (4,5), (4,6),
128
    ...                   (5,4), (5,6), (6,4)))
129
    >>> B = nx.directed_modularity_matrix(G)
130

131

132
    Notes
133
    -----
134
    NetworkX defines the element A_ij of the adjacency matrix as 1 if there
135
    is a link going from node i to node j. Leicht and Newman use the opposite
136
    definition. This explains the different expression for B_ij.
137

138
    See Also
139
    --------
140
    to_numpy_matrix
141
    modularity_spectrum
142
    adjacency_matrix
143
    modularity_matrix
144

145
    References
146
    ----------
147
    .. [1] E. A. Leicht, M. E. J. Newman,
148
        "Community structure in directed networks",
149
        Phys. Rev Lett., vol. 100, no. 11, p. 118703, 2008.
150
    """
151
    if nodelist is None:
152
        nodelist = list(G)
153
    A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight,
154
                                  format='csr')
155
    k_in = A.sum(axis=0)
156
    k_out = A.sum(axis=1)
157
    m = k_in.sum()
158
    # Expected adjacency matrix
159
    X = k_out * k_in / m
160
    return A - X
161

    
162

    
163
# fixture for nose tests
164
def setup_module(module):
165
    from nose import SkipTest
166
    try:
167
        import numpy
168
        import scipy
169
    except:
170
        raise SkipTest("NumPy not available")