Mercurial > repos > shellac > guppy_basecaller

comparison env/lib/python3.7/site-packages/networkx/linalg/modularitymatrix.py @ 2:6af9afd405e9 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 0a63dd5f4d38a1f6944587f52a8cd79874177fc1"
author shellac
date Thu, 14 May 2020 14:56:58 -0400
parents 26e78fe6e8c4
children
comparison
equal deleted inserted replaced
1:75ca89e9b81c 2:6af9afd405e9
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 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 'Jean-Gabriel Young (Jean.gabriel.young@gmail.com)'])
15 __all__ = ['modularity_matrix', 'directed_modularity_matrix']
16
17
18 @not_implemented_for('directed')
19 @not_implemented_for('multigraph')
20 def modularity_matrix(G, nodelist=None, weight=None):
21 r"""Returns the modularity matrix of G.
22
23 The modularity matrix is the matrix B = A - <A>, where A is the adjacency
24 matrix and <A> is the average adjacency matrix, assuming that the graph
25 is described by the configuration model.
26
27 More specifically, the element B_ij of B is defined as
28
29 .. math::
30 A_{ij} - {k_i k_j \over 2 m}
31
32 where k_i is the degree of node i, and where m is the number of edges
33 in the graph. When weight is set to a name of an attribute edge, Aij, k_i,
34 k_j and m are computed using its value.
35
36 Parameters
37 ----------
38 G : Graph
39 A NetworkX graph
40
41 nodelist : list, optional
42 The rows and columns are ordered according to the nodes in nodelist.
43 If nodelist is None, then the ordering is produced by G.nodes().
44
45 weight : string or None, optional (default=None)
46 The edge attribute that holds the numerical value used for
47 the edge weight. If None then all edge weights are 1.
48
49 Returns
50 -------
51 B : Numpy matrix
52 The modularity matrix of G.
53
54 Examples
55 --------
56 >>> import networkx as nx
57 >>> k =[3, 2, 2, 1, 0]
58 >>> G = nx.havel_hakimi_graph(k)
59 >>> B = nx.modularity_matrix(G)
60
61
62 See Also
63 --------
64 to_numpy_matrix
65 modularity_spectrum
66 adjacency_matrix
67 directed_modularity_matrix
68
69 References
70 ----------
71 .. [1] M. E. J. Newman, "Modularity and community structure in networks",
72 Proc. Natl. Acad. Sci. USA, vol. 103, pp. 8577-8582, 2006.
73 """
74 if nodelist is None:
75 nodelist = list(G)
76 A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight,
77 format='csr')
78 k = A.sum(axis=1)
79 m = k.sum() * 0.5
80 # Expected adjacency matrix
81 X = k * k.transpose() / (2 * m)
82 return A - X
83
84
85 @not_implemented_for('undirected')
86 @not_implemented_for('multigraph')
87 def directed_modularity_matrix(G, nodelist=None, weight=None):
88 """Returns the directed modularity matrix of G.
89
90 The modularity matrix is the matrix B = A - <A>, where A is the adjacency
91 matrix and <A> is the expected adjacency matrix, assuming that the graph
92 is described by the configuration model.
93
94 More specifically, the element B_ij of B is defined as
95
96 .. math::
97 B_{ij} = A_{ij} - k_i^{out} k_j^{in} / m
98
99 where :math:`k_i^{in}` is the in degree of node i, and :math:`k_j^{out}` is the out degree
100 of node j, with m the number of edges in the graph. When weight is set
101 to a name of an attribute edge, Aij, k_i, k_j and m are computed using
102 its value.
103
104 Parameters
105 ----------
106 G : DiGraph
107 A NetworkX DiGraph
108
109 nodelist : list, optional
110 The rows and columns are ordered according to the nodes in nodelist.
111 If nodelist is None, then the ordering is produced by G.nodes().
112
113 weight : string or None, optional (default=None)
114 The edge attribute that holds the numerical value used for
115 the edge weight. If None then all edge weights are 1.
116
117 Returns
118 -------
119 B : Numpy matrix
120 The modularity matrix of G.
121
122 Examples
123 --------
124 >>> import networkx as nx
125 >>> G = nx.DiGraph()
126 >>> G.add_edges_from(((1,2), (1,3), (3,1), (3,2), (3,5), (4,5), (4,6),
127 ... (5,4), (5,6), (6,4)))
128 >>> B = nx.directed_modularity_matrix(G)
129
130
131 Notes
132 -----
133 NetworkX defines the element A_ij of the adjacency matrix as 1 if there
134 is a link going from node i to node j. Leicht and Newman use the opposite
135 definition. This explains the different expression for B_ij.
136
137 See Also
138 --------
139 to_numpy_matrix
140 modularity_spectrum
141 adjacency_matrix
142 modularity_matrix
143
144 References
145 ----------
146 .. [1] E. A. Leicht, M. E. J. Newman,
147 "Community structure in directed networks",
148 Phys. Rev Lett., vol. 100, no. 11, p. 118703, 2008.
149 """
150 if nodelist is None:
151 nodelist = list(G)
152 A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight,
153 format='csr')
154 k_in = A.sum(axis=0)
155 k_out = A.sum(axis=1)
156 m = k_in.sum()
157 # Expected adjacency matrix
158 X = k_out * k_in / m
159 return A - X
160
161
162 # fixture for pytest
163 def setup_module(module):
164 import pytest
165 numpy = pytest.importorskip('numpy')
166 scipy = pytest.importorskip('scipy')