Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/bipartite/centrality.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 import networkx as nx | |
2 | |
3 __all__ = ["degree_centrality", "betweenness_centrality", "closeness_centrality"] | |
4 | |
5 | |
6 def degree_centrality(G, nodes): | |
7 r"""Compute the degree centrality for nodes in a bipartite network. | |
8 | |
9 The degree centrality for a node `v` is the fraction of nodes | |
10 connected to it. | |
11 | |
12 Parameters | |
13 ---------- | |
14 G : graph | |
15 A bipartite network | |
16 | |
17 nodes : list or container | |
18 Container with all nodes in one bipartite node set. | |
19 | |
20 Returns | |
21 ------- | |
22 centrality : dictionary | |
23 Dictionary keyed by node with bipartite degree centrality as the value. | |
24 | |
25 See Also | |
26 -------- | |
27 betweenness_centrality, | |
28 closeness_centrality, | |
29 sets, | |
30 is_bipartite | |
31 | |
32 Notes | |
33 ----- | |
34 The nodes input parameter must contain all nodes in one bipartite node set, | |
35 but the dictionary returned contains all nodes from both bipartite node | |
36 sets. See :mod:`bipartite documentation <networkx.algorithms.bipartite>` | |
37 for further details on how bipartite graphs are handled in NetworkX. | |
38 | |
39 For unipartite networks, the degree centrality values are | |
40 normalized by dividing by the maximum possible degree (which is | |
41 `n-1` where `n` is the number of nodes in G). | |
42 | |
43 In the bipartite case, the maximum possible degree of a node in a | |
44 bipartite node set is the number of nodes in the opposite node set | |
45 [1]_. The degree centrality for a node `v` in the bipartite | |
46 sets `U` with `n` nodes and `V` with `m` nodes is | |
47 | |
48 .. math:: | |
49 | |
50 d_{v} = \frac{deg(v)}{m}, \mbox{for} v \in U , | |
51 | |
52 d_{v} = \frac{deg(v)}{n}, \mbox{for} v \in V , | |
53 | |
54 | |
55 where `deg(v)` is the degree of node `v`. | |
56 | |
57 References | |
58 ---------- | |
59 .. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation | |
60 Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook | |
61 of Social Network Analysis. Sage Publications. | |
62 http://www.steveborgatti.com/research/publications/bhaffiliations.pdf | |
63 """ | |
64 top = set(nodes) | |
65 bottom = set(G) - top | |
66 s = 1.0 / len(bottom) | |
67 centrality = {n: d * s for n, d in G.degree(top)} | |
68 s = 1.0 / len(top) | |
69 centrality.update({n: d * s for n, d in G.degree(bottom)}) | |
70 return centrality | |
71 | |
72 | |
73 def betweenness_centrality(G, nodes): | |
74 r"""Compute betweenness centrality for nodes in a bipartite network. | |
75 | |
76 Betweenness centrality of a node `v` is the sum of the | |
77 fraction of all-pairs shortest paths that pass through `v`. | |
78 | |
79 Values of betweenness are normalized by the maximum possible | |
80 value which for bipartite graphs is limited by the relative size | |
81 of the two node sets [1]_. | |
82 | |
83 Let `n` be the number of nodes in the node set `U` and | |
84 `m` be the number of nodes in the node set `V`, then | |
85 nodes in `U` are normalized by dividing by | |
86 | |
87 .. math:: | |
88 | |
89 \frac{1}{2} [m^2 (s + 1)^2 + m (s + 1)(2t - s - 1) - t (2s - t + 3)] , | |
90 | |
91 where | |
92 | |
93 .. math:: | |
94 | |
95 s = (n - 1) \div m , t = (n - 1) \mod m , | |
96 | |
97 and nodes in `V` are normalized by dividing by | |
98 | |
99 .. math:: | |
100 | |
101 \frac{1}{2} [n^2 (p + 1)^2 + n (p + 1)(2r - p - 1) - r (2p - r + 3)] , | |
102 | |
103 where, | |
104 | |
105 .. math:: | |
106 | |
107 p = (m - 1) \div n , r = (m - 1) \mod n . | |
108 | |
109 Parameters | |
110 ---------- | |
111 G : graph | |
112 A bipartite graph | |
113 | |
114 nodes : list or container | |
115 Container with all nodes in one bipartite node set. | |
116 | |
117 Returns | |
118 ------- | |
119 betweenness : dictionary | |
120 Dictionary keyed by node with bipartite betweenness centrality | |
121 as the value. | |
122 | |
123 See Also | |
124 -------- | |
125 degree_centrality, | |
126 closeness_centrality, | |
127 sets, | |
128 is_bipartite | |
129 | |
130 Notes | |
131 ----- | |
132 The nodes input parameter must contain all nodes in one bipartite node set, | |
133 but the dictionary returned contains all nodes from both node sets. | |
134 See :mod:`bipartite documentation <networkx.algorithms.bipartite>` | |
135 for further details on how bipartite graphs are handled in NetworkX. | |
136 | |
137 | |
138 References | |
139 ---------- | |
140 .. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation | |
141 Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook | |
142 of Social Network Analysis. Sage Publications. | |
143 http://www.steveborgatti.com/research/publications/bhaffiliations.pdf | |
144 """ | |
145 top = set(nodes) | |
146 bottom = set(G) - top | |
147 n = float(len(top)) | |
148 m = float(len(bottom)) | |
149 s = (n - 1) // m | |
150 t = (n - 1) % m | |
151 bet_max_top = ( | |
152 ((m ** 2) * ((s + 1) ** 2)) | |
153 + (m * (s + 1) * (2 * t - s - 1)) | |
154 - (t * ((2 * s) - t + 3)) | |
155 ) / 2.0 | |
156 p = (m - 1) // n | |
157 r = (m - 1) % n | |
158 bet_max_bot = ( | |
159 ((n ** 2) * ((p + 1) ** 2)) | |
160 + (n * (p + 1) * (2 * r - p - 1)) | |
161 - (r * ((2 * p) - r + 3)) | |
162 ) / 2.0 | |
163 betweenness = nx.betweenness_centrality(G, normalized=False, weight=None) | |
164 for node in top: | |
165 betweenness[node] /= bet_max_top | |
166 for node in bottom: | |
167 betweenness[node] /= bet_max_bot | |
168 return betweenness | |
169 | |
170 | |
171 def closeness_centrality(G, nodes, normalized=True): | |
172 r"""Compute the closeness centrality for nodes in a bipartite network. | |
173 | |
174 The closeness of a node is the distance to all other nodes in the | |
175 graph or in the case that the graph is not connected to all other nodes | |
176 in the connected component containing that node. | |
177 | |
178 Parameters | |
179 ---------- | |
180 G : graph | |
181 A bipartite network | |
182 | |
183 nodes : list or container | |
184 Container with all nodes in one bipartite node set. | |
185 | |
186 normalized : bool, optional | |
187 If True (default) normalize by connected component size. | |
188 | |
189 Returns | |
190 ------- | |
191 closeness : dictionary | |
192 Dictionary keyed by node with bipartite closeness centrality | |
193 as the value. | |
194 | |
195 See Also | |
196 -------- | |
197 betweenness_centrality, | |
198 degree_centrality | |
199 sets, | |
200 is_bipartite | |
201 | |
202 Notes | |
203 ----- | |
204 The nodes input parameter must contain all nodes in one bipartite node set, | |
205 but the dictionary returned contains all nodes from both node sets. | |
206 See :mod:`bipartite documentation <networkx.algorithms.bipartite>` | |
207 for further details on how bipartite graphs are handled in NetworkX. | |
208 | |
209 | |
210 Closeness centrality is normalized by the minimum distance possible. | |
211 In the bipartite case the minimum distance for a node in one bipartite | |
212 node set is 1 from all nodes in the other node set and 2 from all | |
213 other nodes in its own set [1]_. Thus the closeness centrality | |
214 for node `v` in the two bipartite sets `U` with | |
215 `n` nodes and `V` with `m` nodes is | |
216 | |
217 .. math:: | |
218 | |
219 c_{v} = \frac{m + 2(n - 1)}{d}, \mbox{for} v \in U, | |
220 | |
221 c_{v} = \frac{n + 2(m - 1)}{d}, \mbox{for} v \in V, | |
222 | |
223 where `d` is the sum of the distances from `v` to all | |
224 other nodes. | |
225 | |
226 Higher values of closeness indicate higher centrality. | |
227 | |
228 As in the unipartite case, setting normalized=True causes the | |
229 values to normalized further to n-1 / size(G)-1 where n is the | |
230 number of nodes in the connected part of graph containing the | |
231 node. If the graph is not completely connected, this algorithm | |
232 computes the closeness centrality for each connected part | |
233 separately. | |
234 | |
235 References | |
236 ---------- | |
237 .. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation | |
238 Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook | |
239 of Social Network Analysis. Sage Publications. | |
240 http://www.steveborgatti.com/research/publications/bhaffiliations.pdf | |
241 """ | |
242 closeness = {} | |
243 path_length = nx.single_source_shortest_path_length | |
244 top = set(nodes) | |
245 bottom = set(G) - top | |
246 n = float(len(top)) | |
247 m = float(len(bottom)) | |
248 for node in top: | |
249 sp = dict(path_length(G, node)) | |
250 totsp = sum(sp.values()) | |
251 if totsp > 0.0 and len(G) > 1: | |
252 closeness[node] = (m + 2 * (n - 1)) / totsp | |
253 if normalized: | |
254 s = (len(sp) - 1.0) / (len(G) - 1) | |
255 closeness[node] *= s | |
256 else: | |
257 closeness[n] = 0.0 | |
258 for node in bottom: | |
259 sp = dict(path_length(G, node)) | |
260 totsp = sum(sp.values()) | |
261 if totsp > 0.0 and len(G) > 1: | |
262 closeness[node] = (n + 2 * (m - 1)) / totsp | |
263 if normalized: | |
264 s = (len(sp) - 1.0) / (len(G) - 1) | |
265 closeness[node] *= s | |
266 else: | |
267 closeness[n] = 0.0 | |
268 return closeness |