Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# Source code for networkx.algorithms.bipartite.generators

# -*- coding: utf-8 -*-
#    Copyright (C) 2006-2011 by
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#
# Authors: Aric Hagberg <aric.hagberg@gmail.com>
#                        Pieter Swart <swart@lanl.gov>
#                        Dan Schult <dschult@colgate.edu>
"""
Generators and functions for bipartite graphs.
"""
import math
import numbers
import random
from functools import reduce
import networkx as nx
from networkx.utils import nodes_or_number, py_random_state

__all__ = ['configuration_model',
'havel_hakimi_graph',
'reverse_havel_hakimi_graph',
'alternating_havel_hakimi_graph',
'preferential_attachment_graph',
'random_graph',
'gnmk_random_graph',
'complete_bipartite_graph',
]

[docs]@nodes_or_number([0, 1])
def complete_bipartite_graph(n1, n2, create_using=None):
"""Returns the complete bipartite graph K_{n_1,n_2}.

Composed of two partitions with n_1 nodes in the first
and n_2 nodes in the second. Each node in the first is
connected to each node in the second.

Parameters
----------
n1 : integer
Number of nodes for node set A.
n2 : integer
Number of nodes for node set B.
create_using : NetworkX graph instance, optional
Return graph of this type.

Notes
-----
Node labels are the integers 0 to n_1 + n_2 - 1.

The nodes are assigned the attribute 'bipartite' with the value 0 or 1
to indicate which bipartite set the node belongs to.
"""
G = nx.empty_graph(0, create_using)
if G.is_directed():
raise nx.NetworkXError("Directed Graph not supported")

n1, top = n1
n2, bottom = n2
if isinstance(n2, numbers.Integral):
bottom = [n1 + i for i in bottom]
G.add_edges_from((u, v) for u in top for v in bottom)
G.graph['name'] = "complete_bipartite_graph(%s,%s)" % (n1, n2)
return G

[docs]@py_random_state(3)
def configuration_model(aseq, bseq, create_using=None, seed=None):
"""Returns a random bipartite graph from two given degree sequences.

Parameters
----------
aseq : list
Degree sequence for node set A.
bseq : list
Degree sequence for node set B.
create_using : NetworkX graph instance, optional
Return graph of this type.
seed : integer, random_state, or None (default)
Indicator of random number generation state.
See :ref:Randomness<randomness>.

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.

Notes
-----
The sum of the two sequences must be equal: sum(aseq)=sum(bseq)
If no graph type is specified use MultiGraph 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.

The nodes are assigned the attribute 'bipartite' with the value 0 or 1
to indicate which bipartite set the node belongs to.

This function is not imported in the main namespace.
To use it you have to explicitly import the bipartite package.
"""
G = nx.empty_graph(0, create_using, default=nx.MultiGraph)
if G.is_directed():
raise nx.NetworkXError("Directed Graph not supported")

# length and sum of each sequence
lena = len(aseq)
lenb = len(bseq)
suma = sum(aseq)
sumb = sum(bseq)

if not suma == sumb:
raise nx.NetworkXError(
'invalid degree sequences, sum(aseq)!=sum(bseq),%s,%s'
% (suma, sumb))

G = _add_nodes_with_bipartite_label(G, lena, lenb)

if len(aseq) == 0 or max(aseq) == 0:
return G  # done if no edges

# build lists of degree-repeated vertex numbers
stubs = []
stubs.extend([[v] * aseq[v] for v in range(0, lena)])
astubs = []
astubs = [x for subseq in stubs for x in subseq]

stubs = []
stubs.extend([[v] * bseq[v - lena] for v in range(lena, lena + lenb)])
bstubs = []
bstubs = [x for subseq in stubs for x in subseq]

# shuffle lists
seed.shuffle(astubs)
seed.shuffle(bstubs)

G.add_edges_from([[astubs[i], bstubs[i]] for i in range(suma)])

G.name = "bipartite_configuration_model"
return G

[docs]def havel_hakimi_graph(aseq, bseq, create_using=None):
"""Returns 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.

Parameters
----------
aseq : list
Degree sequence for node set A.
bseq : list
Degree sequence for node set B.
create_using : NetworkX graph instance, optional
Return graph of this type.

Notes
-----
This function is not imported in the main namespace.
To use it you have to explicitly import the bipartite package.

The sum of the two sequences must be equal: sum(aseq)=sum(bseq)
If no graph type is specified use MultiGraph 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.

The nodes are assigned the attribute 'bipartite' with the value 0 or 1
to indicate which bipartite set the node belongs to.
"""
G = nx.empty_graph(0, create_using, default=nx.MultiGraph)
if G.is_directed():
raise nx.NetworkXError("Directed Graph not supported")

# length of the each sequence
naseq = len(aseq)
nbseq = len(bseq)

suma = sum(aseq)
sumb = sum(bseq)

if not suma == sumb:
raise nx.NetworkXError(
'invalid degree sequences, sum(aseq)!=sum(bseq),%s,%s'
% (suma, sumb))

G = _add_nodes_with_bipartite_label(G, naseq, nbseq)

if len(aseq) == 0 or max(aseq) == 0:
return G  # done if no edges

# build list of degree-repeated vertex numbers
astubs = [[aseq[v], v] for v in range(0, naseq)]
bstubs = [[bseq[v - naseq], v] for v in range(naseq, naseq + nbseq)]
astubs.sort()
while astubs:
(degree, u) = astubs.pop()  # take of largest degree node in the a set
if degree == 0:
break  # done, all are zero
# connect the source to largest degree nodes in the b set
bstubs.sort()
for target in bstubs[-degree:]:
v = target[1]
target[0] -= 1  # note this updates bstubs too.
if target[0] == 0:
bstubs.remove(target)

G.name = "bipartite_havel_hakimi_graph"
return G

[docs]def reverse_havel_hakimi_graph(aseq, bseq, create_using=None):
"""Returns a bipartite graph from two given degree sequences using a
Havel-Hakimi style construction.

Nodes from 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.

Parameters
----------
aseq : list
Degree sequence for node set A.
bseq : list
Degree sequence for node set B.
create_using : NetworkX graph instance, optional
Return graph of this type.

Notes
-----
This function is not imported in the main namespace.
To use it you have to explicitly import the bipartite package.

The sum of the two sequences must be equal: sum(aseq)=sum(bseq)
If no graph type is specified use MultiGraph 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.

The nodes are assigned the attribute 'bipartite' with the value 0 or 1
to indicate which bipartite set the node belongs to.
"""
G = nx.empty_graph(0, create_using, default=nx.MultiGraph)
if G.is_directed():
raise nx.NetworkXError("Directed Graph not supported")

# length of the each sequence
lena = len(aseq)
lenb = len(bseq)
suma = sum(aseq)
sumb = sum(bseq)

if not suma == sumb:
raise nx.NetworkXError(
'invalid degree sequences, sum(aseq)!=sum(bseq),%s,%s'
% (suma, sumb))

G = _add_nodes_with_bipartite_label(G, lena, lenb)

if len(aseq) == 0 or max(aseq) == 0:
return G  # done if no edges

# build list of degree-repeated vertex numbers
astubs = [[aseq[v], v] for v in range(0, lena)]
bstubs = [[bseq[v - lena], v] for v in range(lena, lena + lenb)]
astubs.sort()
bstubs.sort()
while astubs:
(degree, u) = astubs.pop()  # take of largest degree node in the a set
if degree == 0:
break  # done, all are zero
# connect the source to the smallest degree nodes in the b set
for target in bstubs[0:degree]:
v = target[1]
target[0] -= 1  # note this updates bstubs too.
if target[0] == 0:
bstubs.remove(target)

G.name = "bipartite_reverse_havel_hakimi_graph"
return G

[docs]def alternating_havel_hakimi_graph(aseq, bseq, create_using=None):
"""Returns a bipartite graph from two given degree sequences using
an 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.

Parameters
----------
aseq : list
Degree sequence for node set A.
bseq : list
Degree sequence for node set B.
create_using : NetworkX graph instance, optional
Return graph of this type.

Notes
-----
This function is not imported in the main namespace.
To use it you have to explicitly import the bipartite package.

The sum of the two sequences must be equal: sum(aseq)=sum(bseq)
If no graph type is specified use MultiGraph 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.

The nodes are assigned the attribute 'bipartite' with the value 0 or 1
to indicate which bipartite set the node belongs to.
"""
G = nx.empty_graph(0, create_using, default=nx.MultiGraph)
if G.is_directed():
raise nx.NetworkXError("Directed Graph not supported")

# length of the each sequence
naseq = len(aseq)
nbseq = len(bseq)
suma = sum(aseq)
sumb = sum(bseq)

if not suma == sumb:
raise nx.NetworkXError(
'invalid degree sequences, sum(aseq)!=sum(bseq),%s,%s'
% (suma, sumb))

G = _add_nodes_with_bipartite_label(G, naseq, nbseq)

if len(aseq) == 0 or max(aseq) == 0:
return G  # done if no edges
# build list of degree-repeated vertex numbers
astubs = [[aseq[v], v] for v in range(0, naseq)]
bstubs = [[bseq[v - naseq], v] for v in range(naseq, naseq + nbseq)]
while astubs:
astubs.sort()
(degree, u) = astubs.pop()  # take of largest degree node in the a set
if degree == 0:
break  # done, all are zero
bstubs.sort()
small = bstubs[0:degree // 2]  # add these low degree targets
large = bstubs[(-degree + degree // 2):]  # and these high degree targets
stubs = [x for z in zip(large, small) for x in z]  # combine, sorry
if len(stubs) < len(small) + len(large):  # check for zip truncation
stubs.append(large.pop())
for target in stubs:
v = target[1]
target[0] -= 1  # note this updates bstubs too.
if target[0] == 0:
bstubs.remove(target)

G.name = "bipartite_alternating_havel_hakimi_graph"
return G

[docs]@py_random_state(3)
def preferential_attachment_graph(aseq, p, create_using=None, seed=None):
"""Create a bipartite graph with a preferential attachment model from
a given single degree sequence.

Parameters
----------
aseq : list
Degree sequence for node set A.
p :  float
Probability that a new bottom node is added.
create_using : NetworkX graph instance, optional
Return graph of this type.
seed : integer, random_state, or None (default)
Indicator of random number generation state.
See :ref:Randomness<randomness>.

References
----------
.. [1] Guillaume, J.L. and Latapy, M.,
Bipartite graphs as models of complex networks.
Physica A: Statistical Mechanics and its Applications,
2006, 371(2), pp.795-813.
.. [2] Jean-Loup Guillaume and Matthieu Latapy,
Bipartite structure of all complex networks,
Inf. Process. Lett. 90, 2004, pg. 215-221
https://doi.org/10.1016/j.ipl.2004.03.007

Notes
-----

This function is not imported in the main namespace.
To use it you have to explicitly import the bipartite package.
"""
G = nx.empty_graph(0, create_using, default=nx.MultiGraph)
if G.is_directed():
raise nx.NetworkXError("Directed Graph not supported")

if p > 1:
raise nx.NetworkXError("probability %s > 1" % (p))

naseq = len(aseq)
G = _add_nodes_with_bipartite_label(G, naseq, 0)
vv = [[v] * aseq[v] for v in range(0, naseq)]
while vv:
while vv[0]:
source = vv[0][0]
vv[0].remove(source)
if seed.random() < p or G.number_of_nodes() == naseq:
target = G.number_of_nodes()
else:
bb = [[b] * G.degree(b) for b in range(naseq, G.number_of_nodes())]
# flatten the list of lists into a list.
bbstubs = reduce(lambda x, y: x + y, bb)
# choose preferentially a bottom node.
target = seed.choice(bbstubs)
vv.remove(vv[0])
G.name = "bipartite_preferential_attachment_model"
return G

[docs]@py_random_state(3)
def random_graph(n, m, p, seed=None, directed=False):
"""Returns a bipartite random graph.

This is a bipartite version of the binomial (Erdős-Rényi) graph.

Parameters
----------
n : int
The number of nodes in the first bipartite set.
m : int
The number of nodes in the second bipartite set.
p : float
Probability for edge creation.
seed : integer, random_state, or None (default)
Indicator of random number generation state.
See :ref:Randomness<randomness>.
directed : bool, optional (default=False)
If True return a directed graph

Notes
-----
This function is not imported in the main namespace.
To use it you have to explicitly import the bipartite package.

The bipartite random graph algorithm chooses each of the n*m (undirected)
or 2*nm (directed) possible edges with probability p.

This algorithm is $O(n+m)$ where $m$ is the expected number of edges.

The nodes are assigned the attribute 'bipartite' with the value 0 or 1
to indicate which bipartite set the node belongs to.

--------
gnp_random_graph, configuration_model

References
----------
.. [1] Vladimir Batagelj and Ulrik Brandes,
"Efficient generation of large random networks",
Phys. Rev. E, 71, 036113, 2005.
"""
G = nx.Graph()
G = _add_nodes_with_bipartite_label(G, n, m)
if directed:
G = nx.DiGraph(G)
G.name = "fast_gnp_random_graph(%s,%s,%s)" % (n, m, p)

if p <= 0:
return G
if p >= 1:
return nx.complete_bipartite_graph(n, m)

lp = math.log(1.0 - p)

v = 0
w = -1
while v < n:
lr = math.log(1.0 - seed.random())
w = w + 1 + int(lr / lp)
while w >= m and v < n:
w = w - m
v = v + 1
if v < n:
G.add_edge(v, n + w)

if directed:
# use the same algorithm to
# add edges from the "m" to "n" set
v = 0
w = -1
while v < n:
lr = math.log(1.0 - seed.random())
w = w + 1 + int(lr / lp)
while w >= m and v < n:
w = w - m
v = v + 1
if v < n:
G.add_edge(n + w, v)

return G

[docs]@py_random_state(3)
def gnmk_random_graph(n, m, k, seed=None, directed=False):
"""Returns a random bipartite graph G_{n,m,k}.

Produces a bipartite graph chosen randomly out of the set of all graphs
with n top nodes, m bottom nodes, and k edges.

Parameters
----------
n : int
The number of nodes in the first bipartite set.
m : int
The number of nodes in the second bipartite set.
k : int
The number of edges
seed : integer, random_state, or None (default)
Indicator of random number generation state.
See :ref:Randomness<randomness>.
directed : bool, optional (default=False)
If True return a directed graph

Examples
--------
from nx.algorithms import bipartite
G = bipartite.gnmk_random_graph(10,20,50)

--------
gnm_random_graph

Notes
-----
This function is not imported in the main namespace.
To use it you have to explicitly import the bipartite package.

If k > m * n then a complete bipartite graph is returned.

This graph is a bipartite version of the G_{nm} random graph model.
"""
G = nx.Graph()
G = _add_nodes_with_bipartite_label(G, n, m)
if directed:
G = nx.DiGraph(G)
G.name = "bipartite_gnm_random_graph(%s,%s,%s)" % (n, m, k)
if n == 1 or m == 1:
return G
max_edges = n * m  # max_edges for bipartite networks
if k >= max_edges:  # Maybe we should raise an exception here
return nx.complete_bipartite_graph(n, m, create_using=G)

top = [n for n, d in G.nodes(data=True) if d['bipartite'] == 0]
bottom = list(set(G) - set(top))
edge_count = 0
while edge_count < k:
# generate random edge,u,v
u = seed.choice(top)
v = seed.choice(bottom)
if v in G[u]:
continue
else: