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