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