Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/bipartite/projection.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 """One-mode (unipartite) projections of bipartite graphs.""" | |
2 import networkx as nx | |
3 from networkx.utils import not_implemented_for | |
4 | |
5 __all__ = [ | |
6 "project", | |
7 "projected_graph", | |
8 "weighted_projected_graph", | |
9 "collaboration_weighted_projected_graph", | |
10 "overlap_weighted_projected_graph", | |
11 "generic_weighted_projected_graph", | |
12 ] | |
13 | |
14 | |
15 def projected_graph(B, nodes, multigraph=False): | |
16 r"""Returns the projection of B onto one of its node sets. | |
17 | |
18 Returns the graph G that is the projection of the bipartite graph B | |
19 onto the specified nodes. They retain their attributes and are connected | |
20 in G if they have a common neighbor in B. | |
21 | |
22 Parameters | |
23 ---------- | |
24 B : NetworkX graph | |
25 The input graph should be bipartite. | |
26 | |
27 nodes : list or iterable | |
28 Nodes to project onto (the "bottom" nodes). | |
29 | |
30 multigraph: bool (default=False) | |
31 If True return a multigraph where the multiple edges represent multiple | |
32 shared neighbors. They edge key in the multigraph is assigned to the | |
33 label of the neighbor. | |
34 | |
35 Returns | |
36 ------- | |
37 Graph : NetworkX graph or multigraph | |
38 A graph that is the projection onto the given nodes. | |
39 | |
40 Examples | |
41 -------- | |
42 >>> from networkx.algorithms import bipartite | |
43 >>> B = nx.path_graph(4) | |
44 >>> G = bipartite.projected_graph(B, [1, 3]) | |
45 >>> list(G) | |
46 [1, 3] | |
47 >>> list(G.edges()) | |
48 [(1, 3)] | |
49 | |
50 If nodes `a`, and `b` are connected through both nodes 1 and 2 then | |
51 building a multigraph results in two edges in the projection onto | |
52 [`a`, `b`]: | |
53 | |
54 >>> B = nx.Graph() | |
55 >>> B.add_edges_from([("a", 1), ("b", 1), ("a", 2), ("b", 2)]) | |
56 >>> G = bipartite.projected_graph(B, ["a", "b"], multigraph=True) | |
57 >>> print([sorted((u, v)) for u, v in G.edges()]) | |
58 [['a', 'b'], ['a', 'b']] | |
59 | |
60 Notes | |
61 ----- | |
62 No attempt is made to verify that the input graph B is bipartite. | |
63 Returns a simple graph that is the projection of the bipartite graph B | |
64 onto the set of nodes given in list nodes. If multigraph=True then | |
65 a multigraph is returned with an edge for every shared neighbor. | |
66 | |
67 Directed graphs are allowed as input. The output will also then | |
68 be a directed graph with edges if there is a directed path between | |
69 the nodes. | |
70 | |
71 The graph and node properties are (shallow) copied to the projected graph. | |
72 | |
73 See :mod:`bipartite documentation <networkx.algorithms.bipartite>` | |
74 for further details on how bipartite graphs are handled in NetworkX. | |
75 | |
76 See Also | |
77 -------- | |
78 is_bipartite, | |
79 is_bipartite_node_set, | |
80 sets, | |
81 weighted_projected_graph, | |
82 collaboration_weighted_projected_graph, | |
83 overlap_weighted_projected_graph, | |
84 generic_weighted_projected_graph | |
85 """ | |
86 if B.is_multigraph(): | |
87 raise nx.NetworkXError("not defined for multigraphs") | |
88 if B.is_directed(): | |
89 directed = True | |
90 if multigraph: | |
91 G = nx.MultiDiGraph() | |
92 else: | |
93 G = nx.DiGraph() | |
94 else: | |
95 directed = False | |
96 if multigraph: | |
97 G = nx.MultiGraph() | |
98 else: | |
99 G = nx.Graph() | |
100 G.graph.update(B.graph) | |
101 G.add_nodes_from((n, B.nodes[n]) for n in nodes) | |
102 for u in nodes: | |
103 nbrs2 = {v for nbr in B[u] for v in B[nbr] if v != u} | |
104 if multigraph: | |
105 for n in nbrs2: | |
106 if directed: | |
107 links = set(B[u]) & set(B.pred[n]) | |
108 else: | |
109 links = set(B[u]) & set(B[n]) | |
110 for l in links: | |
111 if not G.has_edge(u, n, l): | |
112 G.add_edge(u, n, key=l) | |
113 else: | |
114 G.add_edges_from((u, n) for n in nbrs2) | |
115 return G | |
116 | |
117 | |
118 @not_implemented_for("multigraph") | |
119 def weighted_projected_graph(B, nodes, ratio=False): | |
120 r"""Returns a weighted projection of B onto one of its node sets. | |
121 | |
122 The weighted projected graph is the projection of the bipartite | |
123 network B onto the specified nodes with weights representing the | |
124 number of shared neighbors or the ratio between actual shared | |
125 neighbors and possible shared neighbors if ``ratio is True`` [1]_. | |
126 The nodes retain their attributes and are connected in the resulting | |
127 graph if they have an edge to a common node in the original graph. | |
128 | |
129 Parameters | |
130 ---------- | |
131 B : NetworkX graph | |
132 The input graph should be bipartite. | |
133 | |
134 nodes : list or iterable | |
135 Nodes to project onto (the "bottom" nodes). | |
136 | |
137 ratio: Bool (default=False) | |
138 If True, edge weight is the ratio between actual shared neighbors | |
139 and maximum possible shared neighbors (i.e., the size of the other | |
140 node set). If False, edges weight is the number of shared neighbors. | |
141 | |
142 Returns | |
143 ------- | |
144 Graph : NetworkX graph | |
145 A graph that is the projection onto the given nodes. | |
146 | |
147 Examples | |
148 -------- | |
149 >>> from networkx.algorithms import bipartite | |
150 >>> B = nx.path_graph(4) | |
151 >>> G = bipartite.weighted_projected_graph(B, [1, 3]) | |
152 >>> list(G) | |
153 [1, 3] | |
154 >>> list(G.edges(data=True)) | |
155 [(1, 3, {'weight': 1})] | |
156 >>> G = bipartite.weighted_projected_graph(B, [1, 3], ratio=True) | |
157 >>> list(G.edges(data=True)) | |
158 [(1, 3, {'weight': 0.5})] | |
159 | |
160 Notes | |
161 ----- | |
162 No attempt is made to verify that the input graph B is bipartite. | |
163 The graph and node properties are (shallow) copied to the projected graph. | |
164 | |
165 See :mod:`bipartite documentation <networkx.algorithms.bipartite>` | |
166 for further details on how bipartite graphs are handled in NetworkX. | |
167 | |
168 See Also | |
169 -------- | |
170 is_bipartite, | |
171 is_bipartite_node_set, | |
172 sets, | |
173 collaboration_weighted_projected_graph, | |
174 overlap_weighted_projected_graph, | |
175 generic_weighted_projected_graph | |
176 projected_graph | |
177 | |
178 References | |
179 ---------- | |
180 .. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation | |
181 Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook | |
182 of Social Network Analysis. Sage Publications. | |
183 """ | |
184 if B.is_directed(): | |
185 pred = B.pred | |
186 G = nx.DiGraph() | |
187 else: | |
188 pred = B.adj | |
189 G = nx.Graph() | |
190 G.graph.update(B.graph) | |
191 G.add_nodes_from((n, B.nodes[n]) for n in nodes) | |
192 n_top = float(len(B) - len(nodes)) | |
193 for u in nodes: | |
194 unbrs = set(B[u]) | |
195 nbrs2 = {n for nbr in unbrs for n in B[nbr]} - {u} | |
196 for v in nbrs2: | |
197 vnbrs = set(pred[v]) | |
198 common = unbrs & vnbrs | |
199 if not ratio: | |
200 weight = len(common) | |
201 else: | |
202 weight = len(common) / n_top | |
203 G.add_edge(u, v, weight=weight) | |
204 return G | |
205 | |
206 | |
207 @not_implemented_for("multigraph") | |
208 def collaboration_weighted_projected_graph(B, nodes): | |
209 r"""Newman's weighted projection of B onto one of its node sets. | |
210 | |
211 The collaboration weighted projection is the projection of the | |
212 bipartite network B onto the specified nodes with weights assigned | |
213 using Newman's collaboration model [1]_: | |
214 | |
215 .. math:: | |
216 | |
217 w_{u, v} = \sum_k \frac{\delta_{u}^{k} \delta_{v}^{k}}{d_k - 1} | |
218 | |
219 where `u` and `v` are nodes from the bottom bipartite node set, | |
220 and `k` is a node of the top node set. | |
221 The value `d_k` is the degree of node `k` in the bipartite | |
222 network and `\delta_{u}^{k}` is 1 if node `u` is | |
223 linked to node `k` in the original bipartite graph or 0 otherwise. | |
224 | |
225 The nodes retain their attributes and are connected in the resulting | |
226 graph if have an edge to a common node in the original bipartite | |
227 graph. | |
228 | |
229 Parameters | |
230 ---------- | |
231 B : NetworkX graph | |
232 The input graph should be bipartite. | |
233 | |
234 nodes : list or iterable | |
235 Nodes to project onto (the "bottom" nodes). | |
236 | |
237 Returns | |
238 ------- | |
239 Graph : NetworkX graph | |
240 A graph that is the projection onto the given nodes. | |
241 | |
242 Examples | |
243 -------- | |
244 >>> from networkx.algorithms import bipartite | |
245 >>> B = nx.path_graph(5) | |
246 >>> B.add_edge(1, 5) | |
247 >>> G = bipartite.collaboration_weighted_projected_graph(B, [0, 2, 4, 5]) | |
248 >>> list(G) | |
249 [0, 2, 4, 5] | |
250 >>> for edge in sorted(G.edges(data=True)): | |
251 ... print(edge) | |
252 ... | |
253 (0, 2, {'weight': 0.5}) | |
254 (0, 5, {'weight': 0.5}) | |
255 (2, 4, {'weight': 1.0}) | |
256 (2, 5, {'weight': 0.5}) | |
257 | |
258 Notes | |
259 ----- | |
260 No attempt is made to verify that the input graph B is bipartite. | |
261 The graph and node properties are (shallow) copied to the projected graph. | |
262 | |
263 See :mod:`bipartite documentation <networkx.algorithms.bipartite>` | |
264 for further details on how bipartite graphs are handled in NetworkX. | |
265 | |
266 See Also | |
267 -------- | |
268 is_bipartite, | |
269 is_bipartite_node_set, | |
270 sets, | |
271 weighted_projected_graph, | |
272 overlap_weighted_projected_graph, | |
273 generic_weighted_projected_graph, | |
274 projected_graph | |
275 | |
276 References | |
277 ---------- | |
278 .. [1] Scientific collaboration networks: II. | |
279 Shortest paths, weighted networks, and centrality, | |
280 M. E. J. Newman, Phys. Rev. E 64, 016132 (2001). | |
281 """ | |
282 if B.is_directed(): | |
283 pred = B.pred | |
284 G = nx.DiGraph() | |
285 else: | |
286 pred = B.adj | |
287 G = nx.Graph() | |
288 G.graph.update(B.graph) | |
289 G.add_nodes_from((n, B.nodes[n]) for n in nodes) | |
290 for u in nodes: | |
291 unbrs = set(B[u]) | |
292 nbrs2 = {n for nbr in unbrs for n in B[nbr] if n != u} | |
293 for v in nbrs2: | |
294 vnbrs = set(pred[v]) | |
295 common_degree = (len(B[n]) for n in unbrs & vnbrs) | |
296 weight = sum(1.0 / (deg - 1) for deg in common_degree if deg > 1) | |
297 G.add_edge(u, v, weight=weight) | |
298 return G | |
299 | |
300 | |
301 @not_implemented_for("multigraph") | |
302 def overlap_weighted_projected_graph(B, nodes, jaccard=True): | |
303 r"""Overlap weighted projection of B onto one of its node sets. | |
304 | |
305 The overlap weighted projection is the projection of the bipartite | |
306 network B onto the specified nodes with weights representing | |
307 the Jaccard index between the neighborhoods of the two nodes in the | |
308 original bipartite network [1]_: | |
309 | |
310 .. math:: | |
311 | |
312 w_{v, u} = \frac{|N(u) \cap N(v)|}{|N(u) \cup N(v)|} | |
313 | |
314 or if the parameter 'jaccard' is False, the fraction of common | |
315 neighbors by minimum of both nodes degree in the original | |
316 bipartite graph [1]_: | |
317 | |
318 .. math:: | |
319 | |
320 w_{v, u} = \frac{|N(u) \cap N(v)|}{min(|N(u)|, |N(v)|)} | |
321 | |
322 The nodes retain their attributes and are connected in the resulting | |
323 graph if have an edge to a common node in the original bipartite graph. | |
324 | |
325 Parameters | |
326 ---------- | |
327 B : NetworkX graph | |
328 The input graph should be bipartite. | |
329 | |
330 nodes : list or iterable | |
331 Nodes to project onto (the "bottom" nodes). | |
332 | |
333 jaccard: Bool (default=True) | |
334 | |
335 Returns | |
336 ------- | |
337 Graph : NetworkX graph | |
338 A graph that is the projection onto the given nodes. | |
339 | |
340 Examples | |
341 -------- | |
342 >>> from networkx.algorithms import bipartite | |
343 >>> B = nx.path_graph(5) | |
344 >>> nodes = [0, 2, 4] | |
345 >>> G = bipartite.overlap_weighted_projected_graph(B, nodes) | |
346 >>> list(G) | |
347 [0, 2, 4] | |
348 >>> list(G.edges(data=True)) | |
349 [(0, 2, {'weight': 0.5}), (2, 4, {'weight': 0.5})] | |
350 >>> G = bipartite.overlap_weighted_projected_graph(B, nodes, jaccard=False) | |
351 >>> list(G.edges(data=True)) | |
352 [(0, 2, {'weight': 1.0}), (2, 4, {'weight': 1.0})] | |
353 | |
354 Notes | |
355 ----- | |
356 No attempt is made to verify that the input graph B is bipartite. | |
357 The graph and node properties are (shallow) copied to the projected graph. | |
358 | |
359 See :mod:`bipartite documentation <networkx.algorithms.bipartite>` | |
360 for further details on how bipartite graphs are handled in NetworkX. | |
361 | |
362 See Also | |
363 -------- | |
364 is_bipartite, | |
365 is_bipartite_node_set, | |
366 sets, | |
367 weighted_projected_graph, | |
368 collaboration_weighted_projected_graph, | |
369 generic_weighted_projected_graph, | |
370 projected_graph | |
371 | |
372 References | |
373 ---------- | |
374 .. [1] Borgatti, S.P. and Halgin, D. In press. Analyzing Affiliation | |
375 Networks. In Carrington, P. and Scott, J. (eds) The Sage Handbook | |
376 of Social Network Analysis. Sage Publications. | |
377 | |
378 """ | |
379 if B.is_directed(): | |
380 pred = B.pred | |
381 G = nx.DiGraph() | |
382 else: | |
383 pred = B.adj | |
384 G = nx.Graph() | |
385 G.graph.update(B.graph) | |
386 G.add_nodes_from((n, B.nodes[n]) for n in nodes) | |
387 for u in nodes: | |
388 unbrs = set(B[u]) | |
389 nbrs2 = {n for nbr in unbrs for n in B[nbr]} - {u} | |
390 for v in nbrs2: | |
391 vnbrs = set(pred[v]) | |
392 if jaccard: | |
393 wt = float(len(unbrs & vnbrs)) / len(unbrs | vnbrs) | |
394 else: | |
395 wt = float(len(unbrs & vnbrs)) / min(len(unbrs), len(vnbrs)) | |
396 G.add_edge(u, v, weight=wt) | |
397 return G | |
398 | |
399 | |
400 @not_implemented_for("multigraph") | |
401 def generic_weighted_projected_graph(B, nodes, weight_function=None): | |
402 r"""Weighted projection of B with a user-specified weight function. | |
403 | |
404 The bipartite network B is projected on to the specified nodes | |
405 with weights computed by a user-specified function. This function | |
406 must accept as a parameter the neighborhood sets of two nodes and | |
407 return an integer or a float. | |
408 | |
409 The nodes retain their attributes and are connected in the resulting graph | |
410 if they have an edge to a common node in the original graph. | |
411 | |
412 Parameters | |
413 ---------- | |
414 B : NetworkX graph | |
415 The input graph should be bipartite. | |
416 | |
417 nodes : list or iterable | |
418 Nodes to project onto (the "bottom" nodes). | |
419 | |
420 weight_function : function | |
421 This function must accept as parameters the same input graph | |
422 that this function, and two nodes; and return an integer or a float. | |
423 The default function computes the number of shared neighbors. | |
424 | |
425 Returns | |
426 ------- | |
427 Graph : NetworkX graph | |
428 A graph that is the projection onto the given nodes. | |
429 | |
430 Examples | |
431 -------- | |
432 >>> from networkx.algorithms import bipartite | |
433 >>> # Define some custom weight functions | |
434 >>> def jaccard(G, u, v): | |
435 ... unbrs = set(G[u]) | |
436 ... vnbrs = set(G[v]) | |
437 ... return float(len(unbrs & vnbrs)) / len(unbrs | vnbrs) | |
438 ... | |
439 >>> def my_weight(G, u, v, weight="weight"): | |
440 ... w = 0 | |
441 ... for nbr in set(G[u]) & set(G[v]): | |
442 ... w += G[u][nbr].get(weight, 1) + G[v][nbr].get(weight, 1) | |
443 ... return w | |
444 ... | |
445 >>> # A complete bipartite graph with 4 nodes and 4 edges | |
446 >>> B = nx.complete_bipartite_graph(2, 2) | |
447 >>> # Add some arbitrary weight to the edges | |
448 >>> for i, (u, v) in enumerate(B.edges()): | |
449 ... B.edges[u, v]["weight"] = i + 1 | |
450 ... | |
451 >>> for edge in B.edges(data=True): | |
452 ... print(edge) | |
453 ... | |
454 (0, 2, {'weight': 1}) | |
455 (0, 3, {'weight': 2}) | |
456 (1, 2, {'weight': 3}) | |
457 (1, 3, {'weight': 4}) | |
458 >>> # By default, the weight is the number of shared neighbors | |
459 >>> G = bipartite.generic_weighted_projected_graph(B, [0, 1]) | |
460 >>> print(list(G.edges(data=True))) | |
461 [(0, 1, {'weight': 2})] | |
462 >>> # To specify a custom weight function use the weight_function parameter | |
463 >>> G = bipartite.generic_weighted_projected_graph( | |
464 ... B, [0, 1], weight_function=jaccard | |
465 ... ) | |
466 >>> print(list(G.edges(data=True))) | |
467 [(0, 1, {'weight': 1.0})] | |
468 >>> G = bipartite.generic_weighted_projected_graph( | |
469 ... B, [0, 1], weight_function=my_weight | |
470 ... ) | |
471 >>> print(list(G.edges(data=True))) | |
472 [(0, 1, {'weight': 10})] | |
473 | |
474 Notes | |
475 ----- | |
476 No attempt is made to verify that the input graph B is bipartite. | |
477 The graph and node properties are (shallow) copied to the projected graph. | |
478 | |
479 See :mod:`bipartite documentation <networkx.algorithms.bipartite>` | |
480 for further details on how bipartite graphs are handled in NetworkX. | |
481 | |
482 See Also | |
483 -------- | |
484 is_bipartite, | |
485 is_bipartite_node_set, | |
486 sets, | |
487 weighted_projected_graph, | |
488 collaboration_weighted_projected_graph, | |
489 overlap_weighted_projected_graph, | |
490 projected_graph | |
491 | |
492 """ | |
493 if B.is_directed(): | |
494 pred = B.pred | |
495 G = nx.DiGraph() | |
496 else: | |
497 pred = B.adj | |
498 G = nx.Graph() | |
499 if weight_function is None: | |
500 | |
501 def weight_function(G, u, v): | |
502 # Notice that we use set(pred[v]) for handling the directed case. | |
503 return len(set(G[u]) & set(pred[v])) | |
504 | |
505 G.graph.update(B.graph) | |
506 G.add_nodes_from((n, B.nodes[n]) for n in nodes) | |
507 for u in nodes: | |
508 nbrs2 = {n for nbr in set(B[u]) for n in B[nbr]} - {u} | |
509 for v in nbrs2: | |
510 weight = weight_function(B, u, v) | |
511 G.add_edge(u, v, weight=weight) | |
512 return G | |
513 | |
514 | |
515 def project(B, nodes, create_using=None): | |
516 return projected_graph(B, nodes) |