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 for random intersection graphs.
3"""
5import networkx as nx
6from networkx.utils import py_random_state
8__all__ = [
9 "uniform_random_intersection_graph",
10 "k_random_intersection_graph",
11 "general_random_intersection_graph",
12]
15@py_random_state(3)
16@nx._dispatchable(graphs=None, returns_graph=True)
17def uniform_random_intersection_graph(n, m, p, seed=None):
18 """Returns a uniform random intersection graph.
20 Parameters
21 ----------
22 n : int
23 The number of nodes in the first bipartite set (nodes)
24 m : int
25 The number of nodes in the second bipartite set (attributes)
26 p : float
27 Probability of connecting nodes between bipartite sets
28 seed : integer, random_state, or None (default)
29 Indicator of random number generation state.
30 See :ref:`Randomness<randomness>`.
32 See Also
33 --------
34 gnp_random_graph
36 References
37 ----------
38 .. [1] K.B. Singer-Cohen, Random Intersection Graphs, 1995,
39 PhD thesis, Johns Hopkins University
40 .. [2] Fill, J. A., Scheinerman, E. R., and Singer-Cohen, K. B.,
41 Random intersection graphs when m = !(n):
42 An equivalence theorem relating the evolution of the g(n, m, p)
43 and g(n, p) models. Random Struct. Algorithms 16, 2 (2000), 156–176.
44 """
45 from networkx.algorithms import bipartite
47 G = bipartite.random_graph(n, m, p, seed)
48 return nx.projected_graph(G, range(n))
51@py_random_state(3)
52@nx._dispatchable(graphs=None, returns_graph=True)
53def k_random_intersection_graph(n, m, k, seed=None):
54 """Returns a intersection graph with randomly chosen attribute sets for
55 each node that are of equal size (k).
57 Parameters
58 ----------
59 n : int
60 The number of nodes in the first bipartite set (nodes)
61 m : int
62 The number of nodes in the second bipartite set (attributes)
63 k : float
64 Size of attribute set to assign to each node.
65 seed : integer, random_state, or None (default)
66 Indicator of random number generation state.
67 See :ref:`Randomness<randomness>`.
69 See Also
70 --------
71 gnp_random_graph, uniform_random_intersection_graph
73 References
74 ----------
75 .. [1] Godehardt, E., and Jaworski, J.
76 Two models of random intersection graphs and their applications.
77 Electronic Notes in Discrete Mathematics 10 (2001), 129--132.
78 """
79 G = nx.empty_graph(n + m)
80 mset = range(n, n + m)
81 for v in range(n):
82 targets = seed.sample(mset, k)
83 G.add_edges_from(zip([v] * len(targets), targets))
84 return nx.projected_graph(G, range(n))
87@py_random_state(3)
88@nx._dispatchable(graphs=None, returns_graph=True)
89def general_random_intersection_graph(n, m, p, seed=None):
90 """Returns a random intersection graph with independent probabilities
91 for connections between node and attribute sets.
93 Parameters
94 ----------
95 n : int
96 The number of nodes in the first bipartite set (nodes)
97 m : int
98 The number of nodes in the second bipartite set (attributes)
99 p : list of floats of length m
100 Probabilities for connecting nodes to each attribute
101 seed : integer, random_state, or None (default)
102 Indicator of random number generation state.
103 See :ref:`Randomness<randomness>`.
105 See Also
106 --------
107 gnp_random_graph, uniform_random_intersection_graph
109 References
110 ----------
111 .. [1] Nikoletseas, S. E., Raptopoulos, C., and Spirakis, P. G.
112 The existence and efficient construction of large independent sets
113 in general random intersection graphs. In ICALP (2004), J. D´ıaz,
114 J. Karhum¨aki, A. Lepist¨o, and D. Sannella, Eds., vol. 3142
115 of Lecture Notes in Computer Science, Springer, pp. 1029–1040.
116 """
117 if len(p) != m:
118 raise ValueError("Probability list p must have m elements.")
119 G = nx.empty_graph(n + m)
120 mset = range(n, n + m)
121 for u in range(n):
122 for v, q in zip(mset, p):
123 if seed.random() < q:
124 G.add_edge(u, v)
125 return nx.projected_graph(G, range(n))