Module bipartite

Return a random bipartite graph from two given degree sequences.

Nodes from the set A are connected to nodes in the set B by choosing randomly from the possible free stubs, one in A and one in B.

The sum of the two sequences must be equal: sum(aseq)=sum(bseq)

If no graph type is specified use XGraph with parallel edges.

If you want a graph with no parallel edges use create_using=Graph() but then the resulting degree sequences might not be exact.

Parameters:

• aseq - degree sequence for node set A
• bseq - degree sequence for node set B

Return a bipartite graph from two given degree sequences using a Havel-Hakimi style construction.

Nodes from the set A are connected to nodes in the set B by connecting the highest degree nodes in set A to the highest degree nodes in set B until all stubs are connected.

The sum of the two sequences must be equal: sum(aseq)=sum(bseq)

Parameters:

• aseq - degree sequence for node set A
• bseq - degree sequence for node set B

Return a bipartite graph from two given degree sequences using a "reverse" Havel-Hakimi style construction.

Nodes from the set A are connected to nodes in the set B by connecting the highest degree nodes in set A to the lowest degree nodes in set B until all stubs are connected.

The sum of the two sequences must be equal: sum(aseq)=sum(bseq)

Parameters:

• aseq - degree sequence for node set A
• bseq - degree sequence for node set B

Return a bipartite graph from two given degree sequences using a alternating Havel-Hakimi style construction.

Nodes from the set A are connected to nodes in the set B by connecting the highest degree nodes in set A to alternatively the highest and the lowest degree nodes in set B until all stubs are connected.

The sum of the two sequences must be equal: sum(aseq)=sum(bseq)

Parameters:

• aseq - degree sequence for node set A
• bseq - degree sequence for node set B

Create a bipartite graph with a preferential attachment model from a given single "top" degree sequence.

Reference:

@article{guillaume-2004-bipartite,
  author = {Jean-Loup Guillaume and Matthieu Latapy},
  title = {Bipartite structure of all complex networks},
  journal = {Inf. Process. Lett.},
  volume = {90},
  number = {5},
  year = {2004},
  issn = {0020-0190},
  pages = {215--221},
  doi = {http://dx.doi.org/10.1016/j.ipl.2004.03.007},
  publisher = {Elsevier North-Holland, Inc.},
  address = {Amsterdam, The Netherlands, The Netherlands},
  }

Parameters:

• aseq - degree sequence for node set A (top)
• p - probability that a new bottom node is added

UNTESTED:Generate a random bipartite graph of n nodes each with degree d.

Restrictions on n and d:

• n must be even
• n>=2*d

Nodes are numbered 0...n-1.

Algorithm inspired by random_regular_graph()

Returns a graph that is the projection of the bipartite graph B onto the set of nodes given in list nodes.

The nodes retain their names and are connected if they share a common node in the node set of {B not nodes }.

No attempt is made to verify that the input graph B is bipartite.

Returns True if graph G is bipartite, False if not.

Traverse the graph G with depth-first-search and color nodes.