Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/generators/intersection.py @ 1:56ad4e20f292 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
author guerler
date Fri, 31 Jul 2020 00:32:28 -0400
parents
children
comparison
equal deleted inserted replaced
0:d30785e31577 1:56ad4e20f292
1 # -*- coding: utf-8 -*-
2 """
3 Generators for random intersection graphs.
4 """
5 # Copyright (C) 2011 by
6 # Aric Hagberg <hagberg@lanl.gov>
7 # Dan Schult <dschult@colgate.edu>
8 # Pieter Swart <swart@lanl.gov>
9 # All rights reserved.
10 # BSD license.
11 import random
12 import networkx as nx
13 from networkx.algorithms import bipartite
14 from networkx.utils import py_random_state
15
16 __author__ = "\n".join(['Aric Hagberg (hagberg@lanl.gov)'])
17
18 __all__ = ['uniform_random_intersection_graph',
19 'k_random_intersection_graph',
20 'general_random_intersection_graph',
21 ]
22
23
24 @py_random_state(3)
25 def uniform_random_intersection_graph(n, m, p, seed=None):
26 """Returns a uniform random intersection graph.
27
28 Parameters
29 ----------
30 n : int
31 The number of nodes in the first bipartite set (nodes)
32 m : int
33 The number of nodes in the second bipartite set (attributes)
34 p : float
35 Probability of connecting nodes between bipartite sets
36 seed : integer, random_state, or None (default)
37 Indicator of random number generation state.
38 See :ref:`Randomness<randomness>`.
39
40 See Also
41 --------
42 gnp_random_graph
43
44 References
45 ----------
46 .. [1] K.B. Singer-Cohen, Random Intersection Graphs, 1995,
47 PhD thesis, Johns Hopkins University
48 .. [2] Fill, J. A., Scheinerman, E. R., and Singer-Cohen, K. B.,
49 Random intersection graphs when m = !(n):
50 An equivalence theorem relating the evolution of the g(n, m, p)
51 and g(n, p) models. Random Struct. Algorithms 16, 2 (2000), 156–176.
52 """
53 G = bipartite.random_graph(n, m, p, seed)
54 return nx.projected_graph(G, range(n))
55
56
57 @py_random_state(3)
58 def k_random_intersection_graph(n, m, k, seed=None):
59 """Returns a intersection graph with randomly chosen attribute sets for
60 each node that are of equal size (k).
61
62 Parameters
63 ----------
64 n : int
65 The number of nodes in the first bipartite set (nodes)
66 m : int
67 The number of nodes in the second bipartite set (attributes)
68 k : float
69 Size of attribute set to assign to each node.
70 seed : integer, random_state, or None (default)
71 Indicator of random number generation state.
72 See :ref:`Randomness<randomness>`.
73
74 See Also
75 --------
76 gnp_random_graph, uniform_random_intersection_graph
77
78 References
79 ----------
80 .. [1] Godehardt, E., and Jaworski, J.
81 Two models of random intersection graphs and their applications.
82 Electronic Notes in Discrete Mathematics 10 (2001), 129--132.
83 """
84 G = nx.empty_graph(n + m)
85 mset = range(n, n + m)
86 for v in range(n):
87 targets = seed.sample(mset, k)
88 G.add_edges_from(zip([v] * len(targets), targets))
89 return nx.projected_graph(G, range(n))
90
91
92 @py_random_state(3)
93 def general_random_intersection_graph(n, m, p, seed=None):
94 """Returns a random intersection graph with independent probabilities
95 for connections between node and attribute sets.
96
97 Parameters
98 ----------
99 n : int
100 The number of nodes in the first bipartite set (nodes)
101 m : int
102 The number of nodes in the second bipartite set (attributes)
103 p : list of floats of length m
104 Probabilities for connecting nodes to each attribute
105 seed : integer, random_state, or None (default)
106 Indicator of random number generation state.
107 See :ref:`Randomness<randomness>`.
108
109 See Also
110 --------
111 gnp_random_graph, uniform_random_intersection_graph
112
113 References
114 ----------
115 .. [1] Nikoletseas, S. E., Raptopoulos, C., and Spirakis, P. G.
116 The existence and efficient construction of large independent sets
117 in general random intersection graphs. In ICALP (2004), J. D´ıaz,
118 J. Karhum¨aki, A. Lepist¨o, and D. Sannella, Eds., vol. 3142
119 of Lecture Notes in Computer Science, Springer, pp. 1029–1040.
120 """
121 if len(p) != m:
122 raise ValueError("Probability list p must have m elements.")
123 G = nx.empty_graph(n + m)
124 mset = range(n, n + m)
125 for u in range(n):
126 for v, q in zip(mset, p):
127 if seed.random() < q:
128 G.add_edge(u, v)
129 return nx.projected_graph(G, range(n))