NetworkX

Source code for networkx.generators.intersection

# -*- coding: utf-8 -*-
"""
Generators for random intersection graphs.
"""
#    Copyright (C) 2011 by 
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#    All rights reserved.
#    BSD license.
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). See Also -------- gnp_random_graph References ---------- .. [1] K.B. Singer-Cohen, Random Intersection Graphs, 1995, PhD thesis, Johns Hopkins University .. [2] 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). See Also -------- gnp_random_graph, uniform_random_intersection_graph References ---------- .. [1] 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) G.add_edges_from(zip([v]*len(targets), targets)) 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). See Also -------- gnp_random_graph, uniform_random_intersection_graph References ---------- .. [1] 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: G.add_edge(u,v) return nx.projected_graph(G, range(n))