Mercurial > repos > shellac > guppy_basecaller
comparison env/lib/python3.7/site-packages/networkx/linalg/modularitymatrix.py @ 2:6af9afd405e9 draft
"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') |