Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/linalg/modularitymatrix.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """Modularity matrix of graphs. | |
2 """ | |
3 import networkx as nx | |
4 from networkx.utils import not_implemented_for | |
5 | |
6 __all__ = ["modularity_matrix", "directed_modularity_matrix"] | |
7 | |
8 | |
9 @not_implemented_for("directed") | |
10 @not_implemented_for("multigraph") | |
11 def modularity_matrix(G, nodelist=None, weight=None): | |
12 r"""Returns the modularity matrix of G. | |
13 | |
14 The modularity matrix is the matrix B = A - <A>, where A is the adjacency | |
15 matrix and <A> is the average adjacency matrix, assuming that the graph | |
16 is described by the configuration model. | |
17 | |
18 More specifically, the element B_ij of B is defined as | |
19 | |
20 .. math:: | |
21 A_{ij} - {k_i k_j \over 2 m} | |
22 | |
23 where k_i is the degree of node i, and where m is the number of edges | |
24 in the graph. When weight is set to a name of an attribute edge, Aij, k_i, | |
25 k_j and m are computed using its value. | |
26 | |
27 Parameters | |
28 ---------- | |
29 G : Graph | |
30 A NetworkX graph | |
31 | |
32 nodelist : list, optional | |
33 The rows and columns are ordered according to the nodes in nodelist. | |
34 If nodelist is None, then the ordering is produced by G.nodes(). | |
35 | |
36 weight : string or None, optional (default=None) | |
37 The edge attribute that holds the numerical value used for | |
38 the edge weight. If None then all edge weights are 1. | |
39 | |
40 Returns | |
41 ------- | |
42 B : Numpy matrix | |
43 The modularity matrix of G. | |
44 | |
45 Examples | |
46 -------- | |
47 >>> k = [3, 2, 2, 1, 0] | |
48 >>> G = nx.havel_hakimi_graph(k) | |
49 >>> B = nx.modularity_matrix(G) | |
50 | |
51 | |
52 See Also | |
53 -------- | |
54 to_numpy_array | |
55 modularity_spectrum | |
56 adjacency_matrix | |
57 directed_modularity_matrix | |
58 | |
59 References | |
60 ---------- | |
61 .. [1] M. E. J. Newman, "Modularity and community structure in networks", | |
62 Proc. Natl. Acad. Sci. USA, vol. 103, pp. 8577-8582, 2006. | |
63 """ | |
64 if nodelist is None: | |
65 nodelist = list(G) | |
66 A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight, format="csr") | |
67 k = A.sum(axis=1) | |
68 m = k.sum() * 0.5 | |
69 # Expected adjacency matrix | |
70 X = k * k.transpose() / (2 * m) | |
71 return A - X | |
72 | |
73 | |
74 @not_implemented_for("undirected") | |
75 @not_implemented_for("multigraph") | |
76 def directed_modularity_matrix(G, nodelist=None, weight=None): | |
77 """Returns the directed modularity matrix of G. | |
78 | |
79 The modularity matrix is the matrix B = A - <A>, where A is the adjacency | |
80 matrix and <A> is the expected adjacency matrix, assuming that the graph | |
81 is described by the configuration model. | |
82 | |
83 More specifically, the element B_ij of B is defined as | |
84 | |
85 .. math:: | |
86 B_{ij} = A_{ij} - k_i^{out} k_j^{in} / m | |
87 | |
88 where :math:`k_i^{in}` is the in degree of node i, and :math:`k_j^{out}` is the out degree | |
89 of node j, with m the number of edges in the graph. When weight is set | |
90 to a name of an attribute edge, Aij, k_i, k_j and m are computed using | |
91 its value. | |
92 | |
93 Parameters | |
94 ---------- | |
95 G : DiGraph | |
96 A NetworkX DiGraph | |
97 | |
98 nodelist : list, optional | |
99 The rows and columns are ordered according to the nodes in nodelist. | |
100 If nodelist is None, then the ordering is produced by G.nodes(). | |
101 | |
102 weight : string or None, optional (default=None) | |
103 The edge attribute that holds the numerical value used for | |
104 the edge weight. If None then all edge weights are 1. | |
105 | |
106 Returns | |
107 ------- | |
108 B : Numpy matrix | |
109 The modularity matrix of G. | |
110 | |
111 Examples | |
112 -------- | |
113 >>> G = nx.DiGraph() | |
114 >>> G.add_edges_from( | |
115 ... ( | |
116 ... (1, 2), | |
117 ... (1, 3), | |
118 ... (3, 1), | |
119 ... (3, 2), | |
120 ... (3, 5), | |
121 ... (4, 5), | |
122 ... (4, 6), | |
123 ... (5, 4), | |
124 ... (5, 6), | |
125 ... (6, 4), | |
126 ... ) | |
127 ... ) | |
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_array | |
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, format="csr") | |
153 k_in = A.sum(axis=0) | |
154 k_out = A.sum(axis=1) | |
155 m = k_in.sum() | |
156 # Expected adjacency matrix | |
157 X = k_out * k_in / m | |
158 return A - X |