### comparison env/lib/python3.9/site-packages/networkx/generators/geometric.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal 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
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.
49 edges = ((nodes[u], nodes[v]) for u, v in edge_indexes)
50 return edges
51
52
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
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,
145 #
146 n_name, nodes = n
147 G = nx.Graph()
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)
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
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})"
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
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)
300 else:
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()
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
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()
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
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:
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]))]
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
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})"
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