Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/generators/geometric.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """Generators for geometric graphs. | |
2 """ | |
3 | |
4 from bisect import bisect_left | |
5 from itertools import accumulate, combinations, product | |
6 from math import sqrt | |
7 import math | |
8 | |
9 try: | |
10 from scipy.spatial import cKDTree as KDTree | |
11 except ImportError: | |
12 _is_scipy_available = False | |
13 else: | |
14 _is_scipy_available = True | |
15 | |
16 import networkx as nx | |
17 from networkx.utils import nodes_or_number, py_random_state | |
18 | |
19 __all__ = [ | |
20 "geographical_threshold_graph", | |
21 "waxman_graph", | |
22 "navigable_small_world_graph", | |
23 "random_geometric_graph", | |
24 "soft_random_geometric_graph", | |
25 "thresholded_random_geometric_graph", | |
26 ] | |
27 | |
28 | |
29 def euclidean(x, y): | |
30 """Returns the Euclidean distance between the vectors ``x`` and ``y``. | |
31 | |
32 Each of ``x`` and ``y`` can be any iterable of numbers. The | |
33 iterables must be of the same length. | |
34 | |
35 """ | |
36 return sqrt(sum((a - b) ** 2 for a, b in zip(x, y))) | |
37 | |
38 | |
39 def _fast_edges(G, radius, p): | |
40 """Returns edge list of node pairs within `radius` of each other | |
41 using scipy KDTree and Minkowski distance metric `p` | |
42 | |
43 Requires scipy to be installed. | |
44 """ | |
45 pos = nx.get_node_attributes(G, "pos") | |
46 nodes, coords = list(zip(*pos.items())) | |
47 kdtree = KDTree(coords) # Cannot provide generator. | |
48 edge_indexes = kdtree.query_pairs(radius, p) | |
49 edges = ((nodes[u], nodes[v]) for u, v in edge_indexes) | |
50 return edges | |
51 | |
52 | |
53 def _slow_edges(G, radius, p): | |
54 """Returns edge list of node pairs within `radius` of each other | |
55 using Minkowski distance metric `p` | |
56 | |
57 Works without scipy, but in `O(n^2)` time. | |
58 """ | |
59 # TODO This can be parallelized. | |
60 edges = [] | |
61 for (u, pu), (v, pv) in combinations(G.nodes(data="pos"), 2): | |
62 if sum(abs(a - b) ** p for a, b in zip(pu, pv)) <= radius ** p: | |
63 edges.append((u, v)) | |
64 return edges | |
65 | |
66 | |
67 @py_random_state(5) | |
68 @nodes_or_number(0) | |
69 def random_geometric_graph(n, radius, dim=2, pos=None, p=2, seed=None): | |
70 """Returns a random geometric graph in the unit cube of dimensions `dim`. | |
71 | |
72 The random geometric graph model places `n` nodes uniformly at | |
73 random in the unit cube. Two nodes are joined by an edge if the | |
74 distance between the nodes is at most `radius`. | |
75 | |
76 Edges are determined using a KDTree when SciPy is available. | |
77 This reduces the time complexity from $O(n^2)$ to $O(n)$. | |
78 | |
79 Parameters | |
80 ---------- | |
81 n : int or iterable | |
82 Number of nodes or iterable of nodes | |
83 radius: float | |
84 Distance threshold value | |
85 dim : int, optional | |
86 Dimension of graph | |
87 pos : dict, optional | |
88 A dictionary keyed by node with node positions as values. | |
89 p : float, optional | |
90 Which Minkowski distance metric to use. `p` has to meet the condition | |
91 ``1 <= p <= infinity``. | |
92 | |
93 If this argument is not specified, the :math:`L^2` metric | |
94 (the Euclidean distance metric), p = 2 is used. | |
95 This should not be confused with the `p` of an Erdős-Rényi random | |
96 graph, which represents probability. | |
97 seed : integer, random_state, or None (default) | |
98 Indicator of random number generation state. | |
99 See :ref:`Randomness<randomness>`. | |
100 | |
101 Returns | |
102 ------- | |
103 Graph | |
104 A random geometric graph, undirected and without self-loops. | |
105 Each node has a node attribute ``'pos'`` that stores the | |
106 position of that node in Euclidean space as provided by the | |
107 ``pos`` keyword argument or, if ``pos`` was not provided, as | |
108 generated by this function. | |
109 | |
110 Examples | |
111 -------- | |
112 Create a random geometric graph on twenty nodes where nodes are joined by | |
113 an edge if their distance is at most 0.1:: | |
114 | |
115 >>> G = nx.random_geometric_graph(20, 0.1) | |
116 | |
117 Notes | |
118 ----- | |
119 This uses a *k*-d tree to build the graph. | |
120 | |
121 The `pos` keyword argument can be used to specify node positions so you | |
122 can create an arbitrary distribution and domain for positions. | |
123 | |
124 For example, to use a 2D Gaussian distribution of node positions with mean | |
125 (0, 0) and standard deviation 2:: | |
126 | |
127 >>> import random | |
128 >>> n = 20 | |
129 >>> pos = {i: (random.gauss(0, 2), random.gauss(0, 2)) for i in range(n)} | |
130 >>> G = nx.random_geometric_graph(n, 0.2, pos=pos) | |
131 | |
132 References | |
133 ---------- | |
134 .. [1] Penrose, Mathew, *Random Geometric Graphs*, | |
135 Oxford Studies in Probability, 5, 2003. | |
136 | |
137 """ | |
138 # TODO Is this function just a special case of the geographical | |
139 # threshold graph? | |
140 # | |
141 # n_name, nodes = n | |
142 # half_radius = {v: radius / 2 for v in nodes} | |
143 # return geographical_threshold_graph(nodes, theta=1, alpha=1, | |
144 # weight=half_radius) | |
145 # | |
146 n_name, nodes = n | |
147 G = nx.Graph() | |
148 G.add_nodes_from(nodes) | |
149 # If no positions are provided, choose uniformly random vectors in | |
150 # Euclidean space of the specified dimension. | |
151 if pos is None: | |
152 pos = {v: [seed.random() for i in range(dim)] for v in nodes} | |
153 nx.set_node_attributes(G, pos, "pos") | |
154 | |
155 if _is_scipy_available: | |
156 edges = _fast_edges(G, radius, p) | |
157 else: | |
158 edges = _slow_edges(G, radius, p) | |
159 G.add_edges_from(edges) | |
160 | |
161 return G | |
162 | |
163 | |
164 @py_random_state(6) | |
165 @nodes_or_number(0) | |
166 def soft_random_geometric_graph( | |
167 n, radius, dim=2, pos=None, p=2, p_dist=None, seed=None | |
168 ): | |
169 r"""Returns a soft random geometric graph in the unit cube. | |
170 | |
171 The soft random geometric graph [1] model places `n` nodes uniformly at | |
172 random in the unit cube in dimension `dim`. Two nodes of distance, `dist`, | |
173 computed by the `p`-Minkowski distance metric are joined by an edge with | |
174 probability `p_dist` if the computed distance metric value of the nodes | |
175 is at most `radius`, otherwise they are not joined. | |
176 | |
177 Edges within `radius` of each other are determined using a KDTree when | |
178 SciPy is available. This reduces the time complexity from :math:`O(n^2)` | |
179 to :math:`O(n)`. | |
180 | |
181 Parameters | |
182 ---------- | |
183 n : int or iterable | |
184 Number of nodes or iterable of nodes | |
185 radius: float | |
186 Distance threshold value | |
187 dim : int, optional | |
188 Dimension of graph | |
189 pos : dict, optional | |
190 A dictionary keyed by node with node positions as values. | |
191 p : float, optional | |
192 Which Minkowski distance metric to use. | |
193 `p` has to meet the condition ``1 <= p <= infinity``. | |
194 | |
195 If this argument is not specified, the :math:`L^2` metric | |
196 (the Euclidean distance metric), p = 2 is used. | |
197 | |
198 This should not be confused with the `p` of an Erdős-Rényi random | |
199 graph, which represents probability. | |
200 p_dist : function, optional | |
201 A probability density function computing the probability of | |
202 connecting two nodes that are of distance, dist, computed by the | |
203 Minkowski distance metric. The probability density function, `p_dist`, | |
204 must be any function that takes the metric value as input | |
205 and outputs a single probability value between 0-1. The scipy.stats | |
206 package has many probability distribution functions implemented and | |
207 tools for custom probability distribution definitions [2], and passing | |
208 the .pdf method of scipy.stats distributions can be used here. If the | |
209 probability function, `p_dist`, is not supplied, the default function | |
210 is an exponential distribution with rate parameter :math:`\lambda=1`. | |
211 seed : integer, random_state, or None (default) | |
212 Indicator of random number generation state. | |
213 See :ref:`Randomness<randomness>`. | |
214 | |
215 Returns | |
216 ------- | |
217 Graph | |
218 A soft random geometric graph, undirected and without self-loops. | |
219 Each node has a node attribute ``'pos'`` that stores the | |
220 position of that node in Euclidean space as provided by the | |
221 ``pos`` keyword argument or, if ``pos`` was not provided, as | |
222 generated by this function. | |
223 | |
224 Examples | |
225 -------- | |
226 Default Graph: | |
227 | |
228 G = nx.soft_random_geometric_graph(50, 0.2) | |
229 | |
230 Custom Graph: | |
231 | |
232 Create a soft random geometric graph on 100 uniformly distributed nodes | |
233 where nodes are joined by an edge with probability computed from an | |
234 exponential distribution with rate parameter :math:`\lambda=1` if their | |
235 Euclidean distance is at most 0.2. | |
236 | |
237 Notes | |
238 ----- | |
239 This uses a *k*-d tree to build the graph. | |
240 | |
241 The `pos` keyword argument can be used to specify node positions so you | |
242 can create an arbitrary distribution and domain for positions. | |
243 | |
244 For example, to use a 2D Gaussian distribution of node positions with mean | |
245 (0, 0) and standard deviation 2 | |
246 | |
247 The scipy.stats package can be used to define the probability distribution | |
248 with the .pdf method used as `p_dist`. | |
249 | |
250 :: | |
251 | |
252 >>> import random | |
253 >>> import math | |
254 >>> n = 100 | |
255 >>> pos = {i: (random.gauss(0, 2), random.gauss(0, 2)) for i in range(n)} | |
256 >>> p_dist = lambda dist: math.exp(-dist) | |
257 >>> G = nx.soft_random_geometric_graph(n, 0.2, pos=pos, p_dist=p_dist) | |
258 | |
259 References | |
260 ---------- | |
261 .. [1] Penrose, Mathew D. "Connectivity of soft random geometric graphs." | |
262 The Annals of Applied Probability 26.2 (2016): 986-1028. | |
263 [2] scipy.stats - | |
264 https://docs.scipy.org/doc/scipy/reference/tutorial/stats.html | |
265 | |
266 """ | |
267 n_name, nodes = n | |
268 G = nx.Graph() | |
269 G.name = f"soft_random_geometric_graph({n}, {radius}, {dim})" | |
270 G.add_nodes_from(nodes) | |
271 # If no positions are provided, choose uniformly random vectors in | |
272 # Euclidean space of the specified dimension. | |
273 if pos is None: | |
274 pos = {v: [seed.random() for i in range(dim)] for v in nodes} | |
275 nx.set_node_attributes(G, pos, "pos") | |
276 | |
277 # if p_dist function not supplied the default function is an exponential | |
278 # distribution with rate parameter :math:`\lambda=1`. | |
279 if p_dist is None: | |
280 | |
281 def p_dist(dist): | |
282 return math.exp(-dist) | |
283 | |
284 def should_join(pair): | |
285 u, v = pair | |
286 u_pos, v_pos = pos[u], pos[v] | |
287 dist = (sum(abs(a - b) ** p for a, b in zip(u_pos, v_pos))) ** (1 / p) | |
288 # Check if dist <= radius parameter. This check is redundant if scipy | |
289 # is available and _fast_edges routine is used, but provides the | |
290 # check in case scipy is not available and all edge combinations | |
291 # need to be checked | |
292 if dist <= radius: | |
293 return seed.random() < p_dist(dist) | |
294 else: | |
295 return False | |
296 | |
297 if _is_scipy_available: | |
298 edges = _fast_edges(G, radius, p) | |
299 G.add_edges_from(filter(should_join, edges)) | |
300 else: | |
301 G.add_edges_from(filter(should_join, combinations(G, 2))) | |
302 | |
303 return G | |
304 | |
305 | |
306 @py_random_state(7) | |
307 @nodes_or_number(0) | |
308 def geographical_threshold_graph( | |
309 n, theta, dim=2, pos=None, weight=None, metric=None, p_dist=None, seed=None | |
310 ): | |
311 r"""Returns a geographical threshold graph. | |
312 | |
313 The geographical threshold graph model places $n$ nodes uniformly at | |
314 random in a rectangular domain. Each node $u$ is assigned a weight | |
315 $w_u$. Two nodes $u$ and $v$ are joined by an edge if | |
316 | |
317 .. math:: | |
318 | |
319 (w_u + w_v)h(r) \ge \theta | |
320 | |
321 where `r` is the distance between `u` and `v`, h(r) is a probability of | |
322 connection as a function of `r`, and :math:`\theta` as the threshold | |
323 parameter. h(r) corresponds to the p_dist parameter. | |
324 | |
325 Parameters | |
326 ---------- | |
327 n : int or iterable | |
328 Number of nodes or iterable of nodes | |
329 theta: float | |
330 Threshold value | |
331 dim : int, optional | |
332 Dimension of graph | |
333 pos : dict | |
334 Node positions as a dictionary of tuples keyed by node. | |
335 weight : dict | |
336 Node weights as a dictionary of numbers keyed by node. | |
337 metric : function | |
338 A metric on vectors of numbers (represented as lists or | |
339 tuples). This must be a function that accepts two lists (or | |
340 tuples) as input and yields a number as output. The function | |
341 must also satisfy the four requirements of a `metric`_. | |
342 Specifically, if $d$ is the function and $x$, $y$, | |
343 and $z$ are vectors in the graph, then $d$ must satisfy | |
344 | |
345 1. $d(x, y) \ge 0$, | |
346 2. $d(x, y) = 0$ if and only if $x = y$, | |
347 3. $d(x, y) = d(y, x)$, | |
348 4. $d(x, z) \le d(x, y) + d(y, z)$. | |
349 | |
350 If this argument is not specified, the Euclidean distance metric is | |
351 used. | |
352 | |
353 .. _metric: https://en.wikipedia.org/wiki/Metric_%28mathematics%29 | |
354 p_dist : function, optional | |
355 A probability density function computing the probability of | |
356 connecting two nodes that are of distance, r, computed by metric. | |
357 The probability density function, `p_dist`, must | |
358 be any function that takes the metric value as input | |
359 and outputs a single probability value between 0-1. | |
360 The scipy.stats package has many probability distribution functions | |
361 implemented and tools for custom probability distribution | |
362 definitions [2], and passing the .pdf method of scipy.stats | |
363 distributions can be used here. If the probability | |
364 function, `p_dist`, is not supplied, the default exponential function | |
365 :math: `r^{-2}` is used. | |
366 seed : integer, random_state, or None (default) | |
367 Indicator of random number generation state. | |
368 See :ref:`Randomness<randomness>`. | |
369 | |
370 Returns | |
371 ------- | |
372 Graph | |
373 A random geographic threshold graph, undirected and without | |
374 self-loops. | |
375 | |
376 Each node has a node attribute ``pos`` that stores the | |
377 position of that node in Euclidean space as provided by the | |
378 ``pos`` keyword argument or, if ``pos`` was not provided, as | |
379 generated by this function. Similarly, each node has a node | |
380 attribute ``weight`` that stores the weight of that node as | |
381 provided or as generated. | |
382 | |
383 Examples | |
384 -------- | |
385 Specify an alternate distance metric using the ``metric`` keyword | |
386 argument. For example, to use the `taxicab metric`_ instead of the | |
387 default `Euclidean metric`_:: | |
388 | |
389 >>> dist = lambda x, y: sum(abs(a - b) for a, b in zip(x, y)) | |
390 >>> G = nx.geographical_threshold_graph(10, 0.1, metric=dist) | |
391 | |
392 .. _taxicab metric: https://en.wikipedia.org/wiki/Taxicab_geometry | |
393 .. _Euclidean metric: https://en.wikipedia.org/wiki/Euclidean_distance | |
394 | |
395 Notes | |
396 ----- | |
397 If weights are not specified they are assigned to nodes by drawing randomly | |
398 from the exponential distribution with rate parameter $\lambda=1$. | |
399 To specify weights from a different distribution, use the `weight` keyword | |
400 argument:: | |
401 | |
402 >>> import random | |
403 >>> n = 20 | |
404 >>> w = {i: random.expovariate(5.0) for i in range(n)} | |
405 >>> G = nx.geographical_threshold_graph(20, 50, weight=w) | |
406 | |
407 If node positions are not specified they are randomly assigned from the | |
408 uniform distribution. | |
409 | |
410 References | |
411 ---------- | |
412 .. [1] Masuda, N., Miwa, H., Konno, N.: | |
413 Geographical threshold graphs with small-world and scale-free | |
414 properties. | |
415 Physical Review E 71, 036108 (2005) | |
416 .. [2] Milan Bradonjić, Aric Hagberg and Allon G. Percus, | |
417 Giant component and connectivity in geographical threshold graphs, | |
418 in Algorithms and Models for the Web-Graph (WAW 2007), | |
419 Antony Bonato and Fan Chung (Eds), pp. 209--216, 2007 | |
420 """ | |
421 n_name, nodes = n | |
422 G = nx.Graph() | |
423 G.add_nodes_from(nodes) | |
424 # If no weights are provided, choose them from an exponential | |
425 # distribution. | |
426 if weight is None: | |
427 weight = {v: seed.expovariate(1) for v in G} | |
428 # If no positions are provided, choose uniformly random vectors in | |
429 # Euclidean space of the specified dimension. | |
430 if pos is None: | |
431 pos = {v: [seed.random() for i in range(dim)] for v in nodes} | |
432 # If no distance metric is provided, use Euclidean distance. | |
433 if metric is None: | |
434 metric = euclidean | |
435 nx.set_node_attributes(G, weight, "weight") | |
436 nx.set_node_attributes(G, pos, "pos") | |
437 | |
438 # if p_dist is not supplied, use default r^-2 | |
439 if p_dist is None: | |
440 | |
441 def p_dist(r): | |
442 return r ** -2 | |
443 | |
444 # Returns ``True`` if and only if the nodes whose attributes are | |
445 # ``du`` and ``dv`` should be joined, according to the threshold | |
446 # condition. | |
447 def should_join(pair): | |
448 u, v = pair | |
449 u_pos, v_pos = pos[u], pos[v] | |
450 u_weight, v_weight = weight[u], weight[v] | |
451 return (u_weight + v_weight) * p_dist(metric(u_pos, v_pos)) >= theta | |
452 | |
453 G.add_edges_from(filter(should_join, combinations(G, 2))) | |
454 return G | |
455 | |
456 | |
457 @py_random_state(6) | |
458 @nodes_or_number(0) | |
459 def waxman_graph( | |
460 n, beta=0.4, alpha=0.1, L=None, domain=(0, 0, 1, 1), metric=None, seed=None | |
461 ): | |
462 r"""Returns a Waxman random graph. | |
463 | |
464 The Waxman random graph model places `n` nodes uniformly at random | |
465 in a rectangular domain. Each pair of nodes at distance `d` is | |
466 joined by an edge with probability | |
467 | |
468 .. math:: | |
469 p = \beta \exp(-d / \alpha L). | |
470 | |
471 This function implements both Waxman models, using the `L` keyword | |
472 argument. | |
473 | |
474 * Waxman-1: if `L` is not specified, it is set to be the maximum distance | |
475 between any pair of nodes. | |
476 * Waxman-2: if `L` is specified, the distance between a pair of nodes is | |
477 chosen uniformly at random from the interval `[0, L]`. | |
478 | |
479 Parameters | |
480 ---------- | |
481 n : int or iterable | |
482 Number of nodes or iterable of nodes | |
483 beta: float | |
484 Model parameter | |
485 alpha: float | |
486 Model parameter | |
487 L : float, optional | |
488 Maximum distance between nodes. If not specified, the actual distance | |
489 is calculated. | |
490 domain : four-tuple of numbers, optional | |
491 Domain size, given as a tuple of the form `(x_min, y_min, x_max, | |
492 y_max)`. | |
493 metric : function | |
494 A metric on vectors of numbers (represented as lists or | |
495 tuples). This must be a function that accepts two lists (or | |
496 tuples) as input and yields a number as output. The function | |
497 must also satisfy the four requirements of a `metric`_. | |
498 Specifically, if $d$ is the function and $x$, $y$, | |
499 and $z$ are vectors in the graph, then $d$ must satisfy | |
500 | |
501 1. $d(x, y) \ge 0$, | |
502 2. $d(x, y) = 0$ if and only if $x = y$, | |
503 3. $d(x, y) = d(y, x)$, | |
504 4. $d(x, z) \le d(x, y) + d(y, z)$. | |
505 | |
506 If this argument is not specified, the Euclidean distance metric is | |
507 used. | |
508 | |
509 .. _metric: https://en.wikipedia.org/wiki/Metric_%28mathematics%29 | |
510 | |
511 seed : integer, random_state, or None (default) | |
512 Indicator of random number generation state. | |
513 See :ref:`Randomness<randomness>`. | |
514 | |
515 Returns | |
516 ------- | |
517 Graph | |
518 A random Waxman graph, undirected and without self-loops. Each | |
519 node has a node attribute ``'pos'`` that stores the position of | |
520 that node in Euclidean space as generated by this function. | |
521 | |
522 Examples | |
523 -------- | |
524 Specify an alternate distance metric using the ``metric`` keyword | |
525 argument. For example, to use the "`taxicab metric`_" instead of the | |
526 default `Euclidean metric`_:: | |
527 | |
528 >>> dist = lambda x, y: sum(abs(a - b) for a, b in zip(x, y)) | |
529 >>> G = nx.waxman_graph(10, 0.5, 0.1, metric=dist) | |
530 | |
531 .. _taxicab metric: https://en.wikipedia.org/wiki/Taxicab_geometry | |
532 .. _Euclidean metric: https://en.wikipedia.org/wiki/Euclidean_distance | |
533 | |
534 Notes | |
535 ----- | |
536 Starting in NetworkX 2.0 the parameters alpha and beta align with their | |
537 usual roles in the probability distribution. In earlier versions their | |
538 positions in the expression were reversed. Their position in the calling | |
539 sequence reversed as well to minimize backward incompatibility. | |
540 | |
541 References | |
542 ---------- | |
543 .. [1] B. M. Waxman, *Routing of multipoint connections*. | |
544 IEEE J. Select. Areas Commun. 6(9),(1988) 1617--1622. | |
545 """ | |
546 n_name, nodes = n | |
547 G = nx.Graph() | |
548 G.add_nodes_from(nodes) | |
549 (xmin, ymin, xmax, ymax) = domain | |
550 # Each node gets a uniformly random position in the given rectangle. | |
551 pos = {v: (seed.uniform(xmin, xmax), seed.uniform(ymin, ymax)) for v in G} | |
552 nx.set_node_attributes(G, pos, "pos") | |
553 # If no distance metric is provided, use Euclidean distance. | |
554 if metric is None: | |
555 metric = euclidean | |
556 # If the maximum distance L is not specified (that is, we are in the | |
557 # Waxman-1 model), then find the maximum distance between any pair | |
558 # of nodes. | |
559 # | |
560 # In the Waxman-1 model, join nodes randomly based on distance. In | |
561 # the Waxman-2 model, join randomly based on random l. | |
562 if L is None: | |
563 L = max(metric(x, y) for x, y in combinations(pos.values(), 2)) | |
564 | |
565 def dist(u, v): | |
566 return metric(pos[u], pos[v]) | |
567 | |
568 else: | |
569 | |
570 def dist(u, v): | |
571 return seed.random() * L | |
572 | |
573 # `pair` is the pair of nodes to decide whether to join. | |
574 def should_join(pair): | |
575 return seed.random() < beta * math.exp(-dist(*pair) / (alpha * L)) | |
576 | |
577 G.add_edges_from(filter(should_join, combinations(G, 2))) | |
578 return G | |
579 | |
580 | |
581 @py_random_state(5) | |
582 def navigable_small_world_graph(n, p=1, q=1, r=2, dim=2, seed=None): | |
583 r"""Returns a navigable small-world graph. | |
584 | |
585 A navigable small-world graph is a directed grid with additional long-range | |
586 connections that are chosen randomly. | |
587 | |
588 [...] we begin with a set of nodes [...] that are identified with the set | |
589 of lattice points in an $n \times n$ square, | |
590 $\{(i, j): i \in \{1, 2, \ldots, n\}, j \in \{1, 2, \ldots, n\}\}$, | |
591 and we define the *lattice distance* between two nodes $(i, j)$ and | |
592 $(k, l)$ to be the number of "lattice steps" separating them: | |
593 $d((i, j), (k, l)) = |k - i| + |l - j|$. | |
594 | |
595 For a universal constant $p >= 1$, the node $u$ has a directed edge to | |
596 every other node within lattice distance $p$---these are its *local | |
597 contacts*. For universal constants $q >= 0$ and $r >= 0$ we also | |
598 construct directed edges from $u$ to $q$ other nodes (the *long-range | |
599 contacts*) using independent random trials; the $i$th directed edge from | |
600 $u$ has endpoint $v$ with probability proportional to $[d(u,v)]^{-r}$. | |
601 | |
602 -- [1]_ | |
603 | |
604 Parameters | |
605 ---------- | |
606 n : int | |
607 The length of one side of the lattice; the number of nodes in | |
608 the graph is therefore $n^2$. | |
609 p : int | |
610 The diameter of short range connections. Each node is joined with every | |
611 other node within this lattice distance. | |
612 q : int | |
613 The number of long-range connections for each node. | |
614 r : float | |
615 Exponent for decaying probability of connections. The probability of | |
616 connecting to a node at lattice distance $d$ is $1/d^r$. | |
617 dim : int | |
618 Dimension of grid | |
619 seed : integer, random_state, or None (default) | |
620 Indicator of random number generation state. | |
621 See :ref:`Randomness<randomness>`. | |
622 | |
623 References | |
624 ---------- | |
625 .. [1] J. Kleinberg. The small-world phenomenon: An algorithmic | |
626 perspective. Proc. 32nd ACM Symposium on Theory of Computing, 2000. | |
627 """ | |
628 if p < 1: | |
629 raise nx.NetworkXException("p must be >= 1") | |
630 if q < 0: | |
631 raise nx.NetworkXException("q must be >= 0") | |
632 if r < 0: | |
633 raise nx.NetworkXException("r must be >= 1") | |
634 | |
635 G = nx.DiGraph() | |
636 nodes = list(product(range(n), repeat=dim)) | |
637 for p1 in nodes: | |
638 probs = [0] | |
639 for p2 in nodes: | |
640 if p1 == p2: | |
641 continue | |
642 d = sum((abs(b - a) for a, b in zip(p1, p2))) | |
643 if d <= p: | |
644 G.add_edge(p1, p2) | |
645 probs.append(d ** -r) | |
646 cdf = list(accumulate(probs)) | |
647 for _ in range(q): | |
648 target = nodes[bisect_left(cdf, seed.uniform(0, cdf[-1]))] | |
649 G.add_edge(p1, target) | |
650 return G | |
651 | |
652 | |
653 @py_random_state(7) | |
654 @nodes_or_number(0) | |
655 def thresholded_random_geometric_graph( | |
656 n, radius, theta, dim=2, pos=None, weight=None, p=2, seed=None | |
657 ): | |
658 r"""Returns a thresholded random geometric graph in the unit cube. | |
659 | |
660 The thresholded random geometric graph [1] model places `n` nodes | |
661 uniformly at random in the unit cube of dimensions `dim`. Each node | |
662 `u` is assigned a weight :math:`w_u`. Two nodes `u` and `v` are | |
663 joined by an edge if they are within the maximum connection distance, | |
664 `radius` computed by the `p`-Minkowski distance and the summation of | |
665 weights :math:`w_u` + :math:`w_v` is greater than or equal | |
666 to the threshold parameter `theta`. | |
667 | |
668 Edges within `radius` of each other are determined using a KDTree when | |
669 SciPy is available. This reduces the time complexity from :math:`O(n^2)` | |
670 to :math:`O(n)`. | |
671 | |
672 Parameters | |
673 ---------- | |
674 n : int or iterable | |
675 Number of nodes or iterable of nodes | |
676 radius: float | |
677 Distance threshold value | |
678 theta: float | |
679 Threshold value | |
680 dim : int, optional | |
681 Dimension of graph | |
682 pos : dict, optional | |
683 A dictionary keyed by node with node positions as values. | |
684 weight : dict, optional | |
685 Node weights as a dictionary of numbers keyed by node. | |
686 p : float, optional | |
687 Which Minkowski distance metric to use. `p` has to meet the condition | |
688 ``1 <= p <= infinity``. | |
689 | |
690 If this argument is not specified, the :math:`L^2` metric | |
691 (the Euclidean distance metric), p = 2 is used. | |
692 | |
693 This should not be confused with the `p` of an Erdős-Rényi random | |
694 graph, which represents probability. | |
695 seed : integer, random_state, or None (default) | |
696 Indicator of random number generation state. | |
697 See :ref:`Randomness<randomness>`. | |
698 | |
699 Returns | |
700 ------- | |
701 Graph | |
702 A thresholded random geographic graph, undirected and without | |
703 self-loops. | |
704 | |
705 Each node has a node attribute ``'pos'`` that stores the | |
706 position of that node in Euclidean space as provided by the | |
707 ``pos`` keyword argument or, if ``pos`` was not provided, as | |
708 generated by this function. Similarly, each node has a nodethre | |
709 attribute ``'weight'`` that stores the weight of that node as | |
710 provided or as generated. | |
711 | |
712 Examples | |
713 -------- | |
714 Default Graph: | |
715 | |
716 G = nx.thresholded_random_geometric_graph(50, 0.2, 0.1) | |
717 | |
718 Custom Graph: | |
719 | |
720 Create a thresholded random geometric graph on 50 uniformly distributed | |
721 nodes where nodes are joined by an edge if their sum weights drawn from | |
722 a exponential distribution with rate = 5 are >= theta = 0.1 and their | |
723 Euclidean distance is at most 0.2. | |
724 | |
725 Notes | |
726 ----- | |
727 This uses a *k*-d tree to build the graph. | |
728 | |
729 The `pos` keyword argument can be used to specify node positions so you | |
730 can create an arbitrary distribution and domain for positions. | |
731 | |
732 For example, to use a 2D Gaussian distribution of node positions with mean | |
733 (0, 0) and standard deviation 2 | |
734 | |
735 If weights are not specified they are assigned to nodes by drawing randomly | |
736 from the exponential distribution with rate parameter :math:`\lambda=1`. | |
737 To specify weights from a different distribution, use the `weight` keyword | |
738 argument:: | |
739 | |
740 :: | |
741 | |
742 >>> import random | |
743 >>> import math | |
744 >>> n = 50 | |
745 >>> pos = {i: (random.gauss(0, 2), random.gauss(0, 2)) for i in range(n)} | |
746 >>> w = {i: random.expovariate(5.0) for i in range(n)} | |
747 >>> G = nx.thresholded_random_geometric_graph(n, 0.2, 0.1, 2, pos, w) | |
748 | |
749 References | |
750 ---------- | |
751 .. [1] http://cole-maclean.github.io/blog/files/thesis.pdf | |
752 | |
753 """ | |
754 | |
755 n_name, nodes = n | |
756 G = nx.Graph() | |
757 G.name = f"thresholded_random_geometric_graph({n}, {radius}, {theta}, {dim})" | |
758 G.add_nodes_from(nodes) | |
759 # If no weights are provided, choose them from an exponential | |
760 # distribution. | |
761 if weight is None: | |
762 weight = {v: seed.expovariate(1) for v in G} | |
763 # If no positions are provided, choose uniformly random vectors in | |
764 # Euclidean space of the specified dimension. | |
765 if pos is None: | |
766 pos = {v: [seed.random() for i in range(dim)] for v in nodes} | |
767 # If no distance metric is provided, use Euclidean distance. | |
768 | |
769 nx.set_node_attributes(G, weight, "weight") | |
770 nx.set_node_attributes(G, pos, "pos") | |
771 | |
772 # Returns ``True`` if and only if the nodes whose attributes are | |
773 # ``du`` and ``dv`` should be joined, according to the threshold | |
774 # condition and node pairs are within the maximum connection | |
775 # distance, ``radius``. | |
776 def should_join(pair): | |
777 u, v = pair | |
778 u_weight, v_weight = weight[u], weight[v] | |
779 u_pos, v_pos = pos[u], pos[v] | |
780 dist = (sum(abs(a - b) ** p for a, b in zip(u_pos, v_pos))) ** (1 / p) | |
781 # Check if dist is <= radius parameter. This check is redundant if | |
782 # scipy is available and _fast_edges routine is used, but provides | |
783 # the check in case scipy is not available and all edge combinations | |
784 # need to be checked | |
785 if dist <= radius: | |
786 return theta <= u_weight + v_weight | |
787 else: | |
788 return False | |
789 | |
790 if _is_scipy_available: | |
791 edges = _fast_edges(G, radius, p) | |
792 G.add_edges_from(filter(should_join, edges)) | |
793 else: | |
794 G.add_edges_from(filter(should_join, combinations(G, 2))) | |
795 | |
796 return G |