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"""
2Generators and functions for bipartite graphs.
3"""
5import math
6import numbers
7from functools import reduce
9import networkx as nx
10from networkx.utils import nodes_or_number, py_random_state
12__all__ = [
13 "configuration_model",
14 "havel_hakimi_graph",
15 "reverse_havel_hakimi_graph",
16 "alternating_havel_hakimi_graph",
17 "preferential_attachment_graph",
18 "random_graph",
19 "gnmk_random_graph",
20 "complete_bipartite_graph",
21]
24@nx._dispatchable(graphs=None, returns_graph=True)
25@nodes_or_number([0, 1])
26def complete_bipartite_graph(n1, n2, create_using=None):
27 """Returns the complete bipartite graph `K_{n_1,n_2}`.
29 The graph is composed of two partitions with nodes 0 to (n1 - 1)
30 in the first and nodes n1 to (n1 + n2 - 1) in the second.
31 Each node in the first is connected to each node in the second.
33 Parameters
34 ----------
35 n1, n2 : integer or iterable container of nodes
36 If integers, nodes are from `range(n1)` and `range(n1, n1 + n2)`.
37 If a container, the elements are the nodes.
38 create_using : NetworkX graph instance, (default: nx.Graph)
39 Return graph of this type.
41 Notes
42 -----
43 Nodes are the integers 0 to `n1 + n2 - 1` unless either n1 or n2 are
44 containers of nodes. If only one of n1 or n2 are integers, that
45 integer is replaced by `range` of that integer.
47 The nodes are assigned the attribute 'bipartite' with the value 0 or 1
48 to indicate which bipartite set the node belongs to.
50 This function is not imported in the main namespace.
51 To use it use nx.bipartite.complete_bipartite_graph
52 """
53 G = nx.empty_graph(0, create_using)
54 if G.is_directed():
55 raise nx.NetworkXError("Directed Graph not supported")
57 n1, top = n1
58 n2, bottom = n2
59 if isinstance(n1, numbers.Integral) and isinstance(n2, numbers.Integral):
60 bottom = [n1 + i for i in bottom]
61 G.add_nodes_from(top, bipartite=0)
62 G.add_nodes_from(bottom, bipartite=1)
63 if len(G) != len(top) + len(bottom):
64 raise nx.NetworkXError("Inputs n1 and n2 must contain distinct nodes")
65 G.add_edges_from((u, v) for u in top for v in bottom)
66 G.graph["name"] = f"complete_bipartite_graph({len(top)}, {len(bottom)})"
67 return G
70@py_random_state(3)
71@nx._dispatchable(name="bipartite_configuration_model", graphs=None, returns_graph=True)
72def configuration_model(aseq, bseq, create_using=None, seed=None):
73 """Returns a random bipartite graph from two given degree sequences.
75 Parameters
76 ----------
77 aseq : list
78 Degree sequence for node set A.
79 bseq : list
80 Degree sequence for node set B.
81 create_using : NetworkX graph instance, optional
82 Return graph of this type.
83 seed : integer, random_state, or None (default)
84 Indicator of random number generation state.
85 See :ref:`Randomness<randomness>`.
87 The graph is composed of two partitions. Set A has nodes 0 to
88 (len(aseq) - 1) and set B has nodes len(aseq) to (len(bseq) - 1).
89 Nodes from set A are connected to nodes in set B by choosing
90 randomly from the possible free stubs, one in A and one in B.
92 Notes
93 -----
94 The sum of the two sequences must be equal: sum(aseq)=sum(bseq)
95 If no graph type is specified use MultiGraph with parallel edges.
96 If you want a graph with no parallel edges use create_using=Graph()
97 but then the resulting degree sequences might not be exact.
99 The nodes are assigned the attribute 'bipartite' with the value 0 or 1
100 to indicate which bipartite set the node belongs to.
102 This function is not imported in the main namespace.
103 To use it use nx.bipartite.configuration_model
104 """
105 G = nx.empty_graph(0, create_using, default=nx.MultiGraph)
106 if G.is_directed():
107 raise nx.NetworkXError("Directed Graph not supported")
109 # length and sum of each sequence
110 lena = len(aseq)
111 lenb = len(bseq)
112 suma = sum(aseq)
113 sumb = sum(bseq)
115 if not suma == sumb:
116 raise nx.NetworkXError(
117 f"invalid degree sequences, sum(aseq)!=sum(bseq),{suma},{sumb}"
118 )
120 G = _add_nodes_with_bipartite_label(G, lena, lenb)
122 if len(aseq) == 0 or max(aseq) == 0:
123 return G # done if no edges
125 # build lists of degree-repeated vertex numbers
126 stubs = [[v] * aseq[v] for v in range(lena)]
127 astubs = [x for subseq in stubs for x in subseq]
129 stubs = [[v] * bseq[v - lena] for v in range(lena, lena + lenb)]
130 bstubs = [x for subseq in stubs for x in subseq]
132 # shuffle lists
133 seed.shuffle(astubs)
134 seed.shuffle(bstubs)
136 G.add_edges_from([astubs[i], bstubs[i]] for i in range(suma))
138 G.name = "bipartite_configuration_model"
139 return G
142@nx._dispatchable(name="bipartite_havel_hakimi_graph", graphs=None, returns_graph=True)
143def havel_hakimi_graph(aseq, bseq, create_using=None):
144 """Returns a bipartite graph from two given degree sequences using a
145 Havel-Hakimi style construction.
147 The graph is composed of two partitions. Set A has nodes 0 to
148 (len(aseq) - 1) and set B has nodes len(aseq) to (len(bseq) - 1).
149 Nodes from the set A are connected to nodes in the set B by
150 connecting the highest degree nodes in set A to the highest degree
151 nodes in set B until all stubs are connected.
153 Parameters
154 ----------
155 aseq : list
156 Degree sequence for node set A.
157 bseq : list
158 Degree sequence for node set B.
159 create_using : NetworkX graph instance, optional
160 Return graph of this type.
162 Notes
163 -----
164 The sum of the two sequences must be equal: sum(aseq)=sum(bseq)
165 If no graph type is specified use MultiGraph with parallel edges.
166 If you want a graph with no parallel edges use create_using=Graph()
167 but then the resulting degree sequences might not be exact.
169 The nodes are assigned the attribute 'bipartite' with the value 0 or 1
170 to indicate which bipartite set the node belongs to.
172 This function is not imported in the main namespace.
173 To use it use nx.bipartite.havel_hakimi_graph
174 """
175 G = nx.empty_graph(0, create_using, default=nx.MultiGraph)
176 if G.is_directed():
177 raise nx.NetworkXError("Directed Graph not supported")
179 # length of the each sequence
180 naseq = len(aseq)
181 nbseq = len(bseq)
183 suma = sum(aseq)
184 sumb = sum(bseq)
186 if not suma == sumb:
187 raise nx.NetworkXError(
188 f"invalid degree sequences, sum(aseq)!=sum(bseq),{suma},{sumb}"
189 )
191 G = _add_nodes_with_bipartite_label(G, naseq, nbseq)
193 if len(aseq) == 0 or max(aseq) == 0:
194 return G # done if no edges
196 # build list of degree-repeated vertex numbers
197 astubs = [[aseq[v], v] for v in range(naseq)]
198 bstubs = [[bseq[v - naseq], v] for v in range(naseq, naseq + nbseq)]
199 astubs.sort()
200 while astubs:
201 (degree, u) = astubs.pop() # take of largest degree node in the a set
202 if degree == 0:
203 break # done, all are zero
204 # connect the source to largest degree nodes in the b set
205 bstubs.sort()
206 for target in bstubs[-degree:]:
207 v = target[1]
208 G.add_edge(u, v)
209 target[0] -= 1 # note this updates bstubs too.
210 if target[0] == 0:
211 bstubs.remove(target)
213 G.name = "bipartite_havel_hakimi_graph"
214 return G
217@nx._dispatchable(graphs=None, returns_graph=True)
218def reverse_havel_hakimi_graph(aseq, bseq, create_using=None):
219 """Returns a bipartite graph from two given degree sequences using a
220 Havel-Hakimi style construction.
222 The graph is composed of two partitions. Set A has nodes 0 to
223 (len(aseq) - 1) and set B has nodes len(aseq) to (len(bseq) - 1).
224 Nodes from set A are connected to nodes in the set B by connecting
225 the highest degree nodes in set A to the lowest degree nodes in
226 set B until all stubs are connected.
228 Parameters
229 ----------
230 aseq : list
231 Degree sequence for node set A.
232 bseq : list
233 Degree sequence for node set B.
234 create_using : NetworkX graph instance, optional
235 Return graph of this type.
237 Notes
238 -----
239 The sum of the two sequences must be equal: sum(aseq)=sum(bseq)
240 If no graph type is specified use MultiGraph with parallel edges.
241 If you want a graph with no parallel edges use create_using=Graph()
242 but then the resulting degree sequences might not be exact.
244 The nodes are assigned the attribute 'bipartite' with the value 0 or 1
245 to indicate which bipartite set the node belongs to.
247 This function is not imported in the main namespace.
248 To use it use nx.bipartite.reverse_havel_hakimi_graph
249 """
250 G = nx.empty_graph(0, create_using, default=nx.MultiGraph)
251 if G.is_directed():
252 raise nx.NetworkXError("Directed Graph not supported")
254 # length of the each sequence
255 lena = len(aseq)
256 lenb = len(bseq)
257 suma = sum(aseq)
258 sumb = sum(bseq)
260 if not suma == sumb:
261 raise nx.NetworkXError(
262 f"invalid degree sequences, sum(aseq)!=sum(bseq),{suma},{sumb}"
263 )
265 G = _add_nodes_with_bipartite_label(G, lena, lenb)
267 if len(aseq) == 0 or max(aseq) == 0:
268 return G # done if no edges
270 # build list of degree-repeated vertex numbers
271 astubs = [[aseq[v], v] for v in range(lena)]
272 bstubs = [[bseq[v - lena], v] for v in range(lena, lena + lenb)]
273 astubs.sort()
274 bstubs.sort()
275 while astubs:
276 (degree, u) = astubs.pop() # take of largest degree node in the a set
277 if degree == 0:
278 break # done, all are zero
279 # connect the source to the smallest degree nodes in the b set
280 for target in bstubs[0:degree]:
281 v = target[1]
282 G.add_edge(u, v)
283 target[0] -= 1 # note this updates bstubs too.
284 if target[0] == 0:
285 bstubs.remove(target)
287 G.name = "bipartite_reverse_havel_hakimi_graph"
288 return G
291@nx._dispatchable(graphs=None, returns_graph=True)
292def alternating_havel_hakimi_graph(aseq, bseq, create_using=None):
293 """Returns a bipartite graph from two given degree sequences using
294 an alternating Havel-Hakimi style construction.
296 The graph is composed of two partitions. Set A has nodes 0 to
297 (len(aseq) - 1) and set B has nodes len(aseq) to (len(bseq) - 1).
298 Nodes from the set A are connected to nodes in the set B by
299 connecting the highest degree nodes in set A to alternatively the
300 highest and the lowest degree nodes in set B until all stubs are
301 connected.
303 Parameters
304 ----------
305 aseq : list
306 Degree sequence for node set A.
307 bseq : list
308 Degree sequence for node set B.
309 create_using : NetworkX graph instance, optional
310 Return graph of this type.
312 Notes
313 -----
314 The sum of the two sequences must be equal: sum(aseq)=sum(bseq)
315 If no graph type is specified use MultiGraph with parallel edges.
316 If you want a graph with no parallel edges use create_using=Graph()
317 but then the resulting degree sequences might not be exact.
319 The nodes are assigned the attribute 'bipartite' with the value 0 or 1
320 to indicate which bipartite set the node belongs to.
322 This function is not imported in the main namespace.
323 To use it use nx.bipartite.alternating_havel_hakimi_graph
324 """
325 G = nx.empty_graph(0, create_using, default=nx.MultiGraph)
326 if G.is_directed():
327 raise nx.NetworkXError("Directed Graph not supported")
329 # length of the each sequence
330 naseq = len(aseq)
331 nbseq = len(bseq)
332 suma = sum(aseq)
333 sumb = sum(bseq)
335 if not suma == sumb:
336 raise nx.NetworkXError(
337 f"invalid degree sequences, sum(aseq)!=sum(bseq),{suma},{sumb}"
338 )
340 G = _add_nodes_with_bipartite_label(G, naseq, nbseq)
342 if len(aseq) == 0 or max(aseq) == 0:
343 return G # done if no edges
344 # build list of degree-repeated vertex numbers
345 astubs = [[aseq[v], v] for v in range(naseq)]
346 bstubs = [[bseq[v - naseq], v] for v in range(naseq, naseq + nbseq)]
347 while astubs:
348 astubs.sort()
349 (degree, u) = astubs.pop() # take of largest degree node in the a set
350 if degree == 0:
351 break # done, all are zero
352 bstubs.sort()
353 small = bstubs[0 : degree // 2] # add these low degree targets
354 large = bstubs[(-degree + degree // 2) :] # now high degree targets
355 stubs = [x for z in zip(large, small) for x in z] # combine, sorry
356 if len(stubs) < len(small) + len(large): # check for zip truncation
357 stubs.append(large.pop())
358 for target in stubs:
359 v = target[1]
360 G.add_edge(u, v)
361 target[0] -= 1 # note this updates bstubs too.
362 if target[0] == 0:
363 bstubs.remove(target)
365 G.name = "bipartite_alternating_havel_hakimi_graph"
366 return G
369@py_random_state(3)
370@nx._dispatchable(graphs=None, returns_graph=True)
371def preferential_attachment_graph(aseq, p, create_using=None, seed=None):
372 """Create a bipartite graph with a preferential attachment model from
373 a given single degree sequence.
375 The graph is composed of two partitions. Set A has nodes 0 to
376 (len(aseq) - 1) and set B has nodes starting with node len(aseq).
377 The number of nodes in set B is random.
379 Parameters
380 ----------
381 aseq : list
382 Degree sequence for node set A.
383 p : float
384 Probability that a new bottom node is added.
385 create_using : NetworkX graph instance, optional
386 Return graph of this type.
387 seed : integer, random_state, or None (default)
388 Indicator of random number generation state.
389 See :ref:`Randomness<randomness>`.
391 References
392 ----------
393 .. [1] Guillaume, J.L. and Latapy, M.,
394 Bipartite graphs as models of complex networks.
395 Physica A: Statistical Mechanics and its Applications,
396 2006, 371(2), pp.795-813.
397 .. [2] Jean-Loup Guillaume and Matthieu Latapy,
398 Bipartite structure of all complex networks,
399 Inf. Process. Lett. 90, 2004, pg. 215-221
400 https://doi.org/10.1016/j.ipl.2004.03.007
402 Notes
403 -----
404 The nodes are assigned the attribute 'bipartite' with the value 0 or 1
405 to indicate which bipartite set the node belongs to.
407 This function is not imported in the main namespace.
408 To use it use nx.bipartite.preferential_attachment_graph
409 """
410 G = nx.empty_graph(0, create_using, default=nx.MultiGraph)
411 if G.is_directed():
412 raise nx.NetworkXError("Directed Graph not supported")
414 if p > 1:
415 raise nx.NetworkXError(f"probability {p} > 1")
417 naseq = len(aseq)
418 G = _add_nodes_with_bipartite_label(G, naseq, 0)
419 vv = [[v] * aseq[v] for v in range(naseq)]
420 while vv:
421 while vv[0]:
422 source = vv[0][0]
423 vv[0].remove(source)
424 if seed.random() < p or len(G) == naseq:
425 target = len(G)
426 G.add_node(target, bipartite=1)
427 G.add_edge(source, target)
428 else:
429 bb = [[b] * G.degree(b) for b in range(naseq, len(G))]
430 # flatten the list of lists into a list.
431 bbstubs = reduce(lambda x, y: x + y, bb)
432 # choose preferentially a bottom node.
433 target = seed.choice(bbstubs)
434 G.add_node(target, bipartite=1)
435 G.add_edge(source, target)
436 vv.remove(vv[0])
437 G.name = "bipartite_preferential_attachment_model"
438 return G
441@py_random_state(3)
442@nx._dispatchable(graphs=None, returns_graph=True)
443def random_graph(n, m, p, seed=None, directed=False):
444 """Returns a bipartite random graph.
446 This is a bipartite version of the binomial (Erdős-Rényi) graph.
447 The graph is composed of two partitions. Set A has nodes 0 to
448 (n - 1) and set B has nodes n to (n + m - 1).
450 Parameters
451 ----------
452 n : int
453 The number of nodes in the first bipartite set.
454 m : int
455 The number of nodes in the second bipartite set.
456 p : float
457 Probability for edge creation.
458 seed : integer, random_state, or None (default)
459 Indicator of random number generation state.
460 See :ref:`Randomness<randomness>`.
461 directed : bool, optional (default=False)
462 If True return a directed graph
464 Notes
465 -----
466 The bipartite random graph algorithm chooses each of the n*m (undirected)
467 or 2*nm (directed) possible edges with probability p.
469 This algorithm is $O(n+m)$ where $m$ is the expected number of edges.
471 The nodes are assigned the attribute 'bipartite' with the value 0 or 1
472 to indicate which bipartite set the node belongs to.
474 This function is not imported in the main namespace.
475 To use it use nx.bipartite.random_graph
477 See Also
478 --------
479 gnp_random_graph, configuration_model
481 References
482 ----------
483 .. [1] Vladimir Batagelj and Ulrik Brandes,
484 "Efficient generation of large random networks",
485 Phys. Rev. E, 71, 036113, 2005.
486 """
487 G = nx.Graph()
488 G = _add_nodes_with_bipartite_label(G, n, m)
489 if directed:
490 G = nx.DiGraph(G)
491 G.name = f"fast_gnp_random_graph({n},{m},{p})"
493 if p <= 0:
494 return G
495 if p >= 1:
496 return nx.complete_bipartite_graph(n, m)
498 lp = math.log(1.0 - p)
500 v = 0
501 w = -1
502 while v < n:
503 lr = math.log(1.0 - seed.random())
504 w = w + 1 + int(lr / lp)
505 while w >= m and v < n:
506 w = w - m
507 v = v + 1
508 if v < n:
509 G.add_edge(v, n + w)
511 if directed:
512 # use the same algorithm to
513 # add edges from the "m" to "n" set
514 v = 0
515 w = -1
516 while v < n:
517 lr = math.log(1.0 - seed.random())
518 w = w + 1 + int(lr / lp)
519 while w >= m and v < n:
520 w = w - m
521 v = v + 1
522 if v < n:
523 G.add_edge(n + w, v)
525 return G
528@py_random_state(3)
529@nx._dispatchable(graphs=None, returns_graph=True)
530def gnmk_random_graph(n, m, k, seed=None, directed=False):
531 """Returns a random bipartite graph G_{n,m,k}.
533 Produces a bipartite graph chosen randomly out of the set of all graphs
534 with n top nodes, m bottom nodes, and k edges.
535 The graph is composed of two sets of nodes.
536 Set A has nodes 0 to (n - 1) and set B has nodes n to (n + m - 1).
538 Parameters
539 ----------
540 n : int
541 The number of nodes in the first bipartite set.
542 m : int
543 The number of nodes in the second bipartite set.
544 k : int
545 The number of edges
546 seed : integer, random_state, or None (default)
547 Indicator of random number generation state.
548 See :ref:`Randomness<randomness>`.
549 directed : bool, optional (default=False)
550 If True return a directed graph
552 Examples
553 --------
554 >>> G = nx.bipartite.gnmk_random_graph(10, 20, 50)
556 See Also
557 --------
558 gnm_random_graph
560 Notes
561 -----
562 If k > m * n then a complete bipartite graph is returned.
564 This graph is a bipartite version of the `G_{nm}` random graph model.
566 The nodes are assigned the attribute 'bipartite' with the value 0 or 1
567 to indicate which bipartite set the node belongs to.
569 This function is not imported in the main namespace.
570 To use it use nx.bipartite.gnmk_random_graph
571 """
572 G = nx.Graph()
573 G = _add_nodes_with_bipartite_label(G, n, m)
574 if directed:
575 G = nx.DiGraph(G)
576 G.name = f"bipartite_gnm_random_graph({n},{m},{k})"
577 if n == 1 or m == 1:
578 return G
579 max_edges = n * m # max_edges for bipartite networks
580 if k >= max_edges: # Maybe we should raise an exception here
581 return nx.complete_bipartite_graph(n, m, create_using=G)
583 top = [n for n, d in G.nodes(data=True) if d["bipartite"] == 0]
584 bottom = list(set(G) - set(top))
585 edge_count = 0
586 while edge_count < k:
587 # generate random edge,u,v
588 u = seed.choice(top)
589 v = seed.choice(bottom)
590 if v in G[u]:
591 continue
592 else:
593 G.add_edge(u, v)
594 edge_count += 1
595 return G
598def _add_nodes_with_bipartite_label(G, lena, lenb):
599 G.add_nodes_from(range(lena + lenb))
600 b = dict(zip(range(lena), [0] * lena))
601 b.update(dict(zip(range(lena, lena + lenb), [1] * lenb)))
602 nx.set_node_attributes(G, b, "bipartite")
603 return G