Warning

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

# Source code for networkx.generators.intersection

# -*- coding: utf-8 -*-
"""
Generators for random intersection graphs.
"""
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
import random
import networkx as nx
__author__ = "\n".join(['Aric Hagberg (hagberg@lanl.gov)'])

__all__ = ['uniform_random_intersection_graph',
'k_random_intersection_graph',
'general_random_intersection_graph',
]

[docs]def uniform_random_intersection_graph(n, m, p, seed=None):
"""Return a uniform random intersection graph.

Parameters
----------
n : int
The number of nodes in the first bipartite set (nodes)
m : int
The number of nodes in the second bipartite set (attributes)
p : float
Probability of connecting nodes between bipartite sets
seed : int, optional
Seed for random number generator (default=None).

--------
gnp_random_graph

References
----------
..  K.B. Singer-Cohen, Random Intersection Graphs, 1995,
PhD thesis, Johns Hopkins University
..  Fill, J. A., Scheinerman, E. R., and Singer-Cohen, K. B.,
Random intersection graphs when m = !(n):
An equivalence theorem relating the evolution of the g(n, m, p)
and g(n, p) models. Random Struct. Algorithms 16, 2 (2000), 156–176.
"""
G=nx.bipartite_random_graph(n, m, p, seed=seed)
return nx.projected_graph(G, range(n))

[docs]def k_random_intersection_graph(n,m,k):
"""Return a intersection graph with randomly chosen attribute sets for
each node that are of equal size (k).

Parameters
----------
n : int
The number of nodes in the first bipartite set (nodes)
m : int
The number of nodes in the second bipartite set (attributes)
k : float
Size of attribute set to assign to each node.
seed : int, optional
Seed for random number generator (default=None).

--------
gnp_random_graph, uniform_random_intersection_graph

References
----------
..  Godehardt, E., and Jaworski, J.
Two models of random intersection graphs and their applications.
Electronic Notes in Discrete Mathematics 10 (2001), 129--132.
"""
G = nx.empty_graph(n + m)
mset = range(n,n+m)
for v in range(n):
targets = random.sample(mset, k)
return nx.projected_graph(G, range(n))

[docs]def general_random_intersection_graph(n,m,p):
"""Return a random intersection graph with independent probabilities
for connections between node and attribute sets.

Parameters
----------
n : int
The number of nodes in the first bipartite set (nodes)
m : int
The number of nodes in the second bipartite set (attributes)
p : list of floats of length m
Probabilities for connecting nodes to each attribute
seed : int, optional
Seed for random number generator (default=None).

--------
gnp_random_graph, uniform_random_intersection_graph

References
----------
..  Nikoletseas, S. E., Raptopoulos, C., and Spirakis, P. G.
The existence and efficient construction of large independent sets
in general random intersection graphs. In ICALP (2004), J. D´ıaz,
J. Karhum¨aki, A. Lepist¨o, and D. Sannella, Eds., vol. 3142
of Lecture Notes in Computer Science, Springer, pp. 1029–1040.
"""
if len(p)!=m:
raise ValueError("Probability list p must have m elements.")
G = nx.empty_graph(n + m)
mset = range(n,n+m)
for u in range(n):
for v,q in zip(mset,p):
if random.random()<q: