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"""Generators for geometric graphs."""
3import math
4from bisect import bisect_left
5from itertools import accumulate, combinations, product
7import networkx as nx
8from networkx.utils import py_random_state
10__all__ = [
11 "geometric_edges",
12 "geographical_threshold_graph",
13 "navigable_small_world_graph",
14 "random_geometric_graph",
15 "soft_random_geometric_graph",
16 "thresholded_random_geometric_graph",
17 "waxman_graph",
18 "geometric_soft_configuration_graph",
19]
22@nx._dispatchable(node_attrs="pos_name")
23def geometric_edges(G, radius, p=2, *, pos_name="pos"):
24 """Returns edge list of node pairs within `radius` of each other.
26 Parameters
27 ----------
28 G : networkx graph
29 The graph from which to generate the edge list. The nodes in `G` should
30 have an attribute ``pos`` corresponding to the node position, which is
31 used to compute the distance to other nodes.
32 radius : scalar
33 The distance threshold. Edges are included in the edge list if the
34 distance between the two nodes is less than `radius`.
35 pos_name : string, default="pos"
36 The name of the node attribute which represents the position of each
37 node in 2D coordinates. Every node in the Graph must have this attribute.
38 p : scalar, default=2
39 The `Minkowski distance metric
40 <https://en.wikipedia.org/wiki/Minkowski_distance>`_ used to compute
41 distances. The default value is 2, i.e. Euclidean distance.
43 Returns
44 -------
45 edges : list
46 List of edges whose distances are less than `radius`
48 Notes
49 -----
50 Radius uses Minkowski distance metric `p`.
51 If scipy is available, `scipy.spatial.cKDTree` is used to speed computation.
53 Examples
54 --------
55 Create a graph with nodes that have a "pos" attribute representing 2D
56 coordinates.
58 >>> G = nx.Graph()
59 >>> G.add_nodes_from(
60 ... [
61 ... (0, {"pos": (0, 0)}),
62 ... (1, {"pos": (3, 0)}),
63 ... (2, {"pos": (8, 0)}),
64 ... ]
65 ... )
66 >>> nx.geometric_edges(G, radius=1)
67 []
68 >>> nx.geometric_edges(G, radius=4)
69 [(0, 1)]
70 >>> nx.geometric_edges(G, radius=6)
71 [(0, 1), (1, 2)]
72 >>> nx.geometric_edges(G, radius=9)
73 [(0, 1), (0, 2), (1, 2)]
74 """
75 # Input validation - every node must have a "pos" attribute
76 for n, pos in G.nodes(data=pos_name):
77 if pos is None:
78 raise nx.NetworkXError(
79 f"Node {n} (and all nodes) must have a '{pos_name}' attribute."
80 )
82 # NOTE: See _geometric_edges for the actual implementation. The reason this
83 # is split into two functions is to avoid the overhead of input validation
84 # every time the function is called internally in one of the other
85 # geometric generators
86 return _geometric_edges(G, radius, p, pos_name)
89def _geometric_edges(G, radius, p, pos_name):
90 """
91 Implements `geometric_edges` without input validation. See `geometric_edges`
92 for complete docstring.
93 """
94 nodes_pos = G.nodes(data=pos_name)
95 try:
96 import scipy as sp
97 except ImportError:
98 # no scipy KDTree so compute by for-loop
99 radius_p = radius**p
100 edges = [
101 (u, v)
102 for (u, pu), (v, pv) in combinations(nodes_pos, 2)
103 if sum(abs(a - b) ** p for a, b in zip(pu, pv)) <= radius_p
104 ]
105 return edges
106 # scipy KDTree is available
107 nodes, coords = list(zip(*nodes_pos))
108 kdtree = sp.spatial.cKDTree(coords) # Cannot provide generator.
109 edge_indexes = kdtree.query_pairs(radius, p)
110 edges = [(nodes[u], nodes[v]) for u, v in sorted(edge_indexes)]
111 return edges
114@py_random_state(5)
115@nx._dispatchable(graphs=None, returns_graph=True)
116def random_geometric_graph(
117 n, radius, dim=2, pos=None, p=2, seed=None, *, pos_name="pos"
118):
119 """Returns a random geometric graph in the unit cube of dimensions `dim`.
121 The random geometric graph model places `n` nodes uniformly at
122 random in the unit cube. Two nodes are joined by an edge if the
123 distance between the nodes is at most `radius`.
125 Edges are determined using a KDTree when SciPy is available.
126 This reduces the time complexity from $O(n^2)$ to $O(n)$.
128 Parameters
129 ----------
130 n : int or iterable
131 Number of nodes or iterable of nodes
132 radius: float
133 Distance threshold value
134 dim : int, optional
135 Dimension of graph
136 pos : dict, optional
137 A dictionary keyed by node with node positions as values.
138 p : float, optional
139 Which Minkowski distance metric to use. `p` has to meet the condition
140 ``1 <= p <= infinity``.
142 If this argument is not specified, the :math:`L^2` metric
143 (the Euclidean distance metric), p = 2 is used.
144 This should not be confused with the `p` of an Erdős-Rényi random
145 graph, which represents probability.
146 seed : integer, random_state, or None (default)
147 Indicator of random number generation state.
148 See :ref:`Randomness<randomness>`.
149 pos_name : string, default="pos"
150 The name of the node attribute which represents the position
151 in 2D coordinates of the node in the returned graph.
153 Returns
154 -------
155 Graph
156 A random geometric graph, undirected and without self-loops.
157 Each node has a node attribute ``'pos'`` that stores the
158 position of that node in Euclidean space as provided by the
159 ``pos`` keyword argument or, if ``pos`` was not provided, as
160 generated by this function.
162 Examples
163 --------
164 Create a random geometric graph on twenty nodes where nodes are joined by
165 an edge if their distance is at most 0.1::
167 >>> G = nx.random_geometric_graph(20, 0.1)
169 Notes
170 -----
171 This uses a *k*-d tree to build the graph.
173 The `pos` keyword argument can be used to specify node positions so you
174 can create an arbitrary distribution and domain for positions.
176 For example, to use a 2D Gaussian distribution of node positions with mean
177 (0, 0) and standard deviation 2::
179 >>> import random
180 >>> n = 20
181 >>> pos = {i: (random.gauss(0, 2), random.gauss(0, 2)) for i in range(n)}
182 >>> G = nx.random_geometric_graph(n, 0.2, pos=pos)
184 References
185 ----------
186 .. [1] Penrose, Mathew, *Random Geometric Graphs*,
187 Oxford Studies in Probability, 5, 2003.
189 """
190 # TODO Is this function just a special case of the geographical
191 # threshold graph?
192 #
193 # half_radius = {v: radius / 2 for v in n}
194 # return geographical_threshold_graph(nodes, theta=1, alpha=1,
195 # weight=half_radius)
196 #
197 G = nx.empty_graph(n)
198 # If no positions are provided, choose uniformly random vectors in
199 # Euclidean space of the specified dimension.
200 if pos is None:
201 pos = {v: [seed.random() for i in range(dim)] for v in G}
202 nx.set_node_attributes(G, pos, pos_name)
204 G.add_edges_from(_geometric_edges(G, radius, p, pos_name))
205 return G
208@py_random_state(6)
209@nx._dispatchable(graphs=None, returns_graph=True)
210def soft_random_geometric_graph(
211 n, radius, dim=2, pos=None, p=2, p_dist=None, seed=None, *, pos_name="pos"
212):
213 r"""Returns a soft random geometric graph in the unit cube.
215 The soft random geometric graph [1] model places `n` nodes uniformly at
216 random in the unit cube in dimension `dim`. Two nodes of distance, `dist`,
217 computed by the `p`-Minkowski distance metric are joined by an edge with
218 probability `p_dist` if the computed distance metric value of the nodes
219 is at most `radius`, otherwise they are not joined.
221 Edges within `radius` of each other are determined using a KDTree when
222 SciPy is available. This reduces the time complexity from :math:`O(n^2)`
223 to :math:`O(n)`.
225 Parameters
226 ----------
227 n : int or iterable
228 Number of nodes or iterable of nodes
229 radius: float
230 Distance threshold value
231 dim : int, optional
232 Dimension of graph
233 pos : dict, optional
234 A dictionary keyed by node with node positions as values.
235 p : float, optional
236 Which Minkowski distance metric to use.
237 `p` has to meet the condition ``1 <= p <= infinity``.
239 If this argument is not specified, the :math:`L^2` metric
240 (the Euclidean distance metric), p = 2 is used.
242 This should not be confused with the `p` of an Erdős-Rényi random
243 graph, which represents probability.
244 p_dist : function, optional
245 A probability density function computing the probability of
246 connecting two nodes that are of distance, dist, computed by the
247 Minkowski distance metric. The probability density function, `p_dist`,
248 must be any function that takes the metric value as input
249 and outputs a single probability value between 0-1. The `scipy.stats`
250 package has many probability distribution functions implemented and
251 tools for custom probability distribution definitions [2], and passing
252 the .pdf method of `scipy.stats` distributions can be used here. If the
253 probability function, `p_dist`, is not supplied, the default function
254 is an exponential distribution with rate parameter :math:`\lambda=1`.
255 seed : integer, random_state, or None (default)
256 Indicator of random number generation state.
257 See :ref:`Randomness<randomness>`.
258 pos_name : string, default="pos"
259 The name of the node attribute which represents the position
260 in 2D coordinates of the node in the returned graph.
262 Returns
263 -------
264 Graph
265 A soft random geometric graph, undirected and without self-loops.
266 Each node has a node attribute ``'pos'`` that stores the
267 position of that node in Euclidean space as provided by the
268 ``pos`` keyword argument or, if ``pos`` was not provided, as
269 generated by this function.
271 Notes
272 -----
273 This uses a *k*-d tree to build the graph.
275 References
276 ----------
277 .. [1] Penrose, Mathew D. "Connectivity of soft random geometric graphs."
278 The Annals of Applied Probability 26.2 (2016): 986-1028.
280 Examples
281 --------
282 Default Graph:
284 >>> G = nx.soft_random_geometric_graph(50, 0.2)
286 Custom Graph:
288 The `pos` keyword argument can be used to specify node positions so you
289 can create an arbitrary distribution and domain for positions.
291 The `scipy.stats` package can be used to define the probability distribution
292 with the ``.pdf`` method used as `p_dist`.
294 For example, create a soft random geometric graph on 100 nodes using a 2D
295 Gaussian distribution of node positions with mean (0, 0) and standard deviation 2,
296 where nodes are joined by an edge with probability computed from an
297 exponential distribution with rate parameter :math:`\lambda=1` if their
298 Euclidean distance is at most 0.2.
300 >>> import random
301 >>> from scipy.stats import expon
302 >>> n = 100
303 >>> pos = {i: (random.gauss(0, 2), random.gauss(0, 2)) for i in range(n)}
304 >>> p_dist = lambda x: expon.pdf(x, scale=1)
305 >>> G = nx.soft_random_geometric_graph(n, 0.2, pos=pos, p_dist=p_dist)
307 """
308 G = nx.empty_graph(n)
309 G.name = f"soft_random_geometric_graph({n}, {radius}, {dim})"
310 # If no positions are provided, choose uniformly random vectors in
311 # Euclidean space of the specified dimension.
312 if pos is None:
313 pos = {v: [seed.random() for i in range(dim)] for v in G}
314 nx.set_node_attributes(G, pos, pos_name)
316 # if p_dist function not supplied the default function is an exponential
317 # distribution with rate parameter :math:`\lambda=1`.
318 if p_dist is None:
320 def p_dist(dist):
321 return math.exp(-dist)
323 def should_join(edge):
324 u, v = edge
325 dist = (sum(abs(a - b) ** p for a, b in zip(pos[u], pos[v]))) ** (1 / p)
326 return seed.random() < p_dist(dist)
328 G.add_edges_from(filter(should_join, _geometric_edges(G, radius, p, pos_name)))
329 return G
332@py_random_state(7)
333@nx._dispatchable(graphs=None, returns_graph=True)
334def geographical_threshold_graph(
335 n,
336 theta,
337 dim=2,
338 pos=None,
339 weight=None,
340 metric=None,
341 p_dist=None,
342 seed=None,
343 *,
344 pos_name="pos",
345 weight_name="weight",
346):
347 r"""Returns a geographical threshold graph.
349 The geographical threshold graph model places $n$ nodes uniformly at
350 random in a rectangular domain. Each node $u$ is assigned a weight
351 $w_u$. Two nodes $u$ and $v$ are joined by an edge if
353 .. math::
355 (w_u + w_v)p_{dist}(r) \ge \theta
357 where `r` is the distance between `u` and `v`, `p_dist` is any function of
358 `r`, and :math:`\theta` as the threshold parameter. `p_dist` is used to
359 give weight to the distance between nodes when deciding whether or not
360 they should be connected. The larger `p_dist` is, the more prone nodes
361 separated by `r` are to be connected, and vice versa.
363 Parameters
364 ----------
365 n : int or iterable
366 Number of nodes or iterable of nodes
367 theta: float
368 Threshold value
369 dim : int, optional
370 Dimension of graph
371 pos : dict
372 Node positions as a dictionary of tuples keyed by node.
373 weight : dict
374 Node weights as a dictionary of numbers keyed by node.
375 metric : function
376 A metric on vectors of numbers (represented as lists or
377 tuples). This must be a function that accepts two lists (or
378 tuples) as input and yields a number as output. The function
379 must also satisfy the four requirements of a `metric`_.
380 Specifically, if $d$ is the function and $x$, $y$,
381 and $z$ are vectors in the graph, then $d$ must satisfy
383 1. $d(x, y) \ge 0$,
384 2. $d(x, y) = 0$ if and only if $x = y$,
385 3. $d(x, y) = d(y, x)$,
386 4. $d(x, z) \le d(x, y) + d(y, z)$.
388 If this argument is not specified, the Euclidean distance metric is
389 used.
391 .. _metric: https://en.wikipedia.org/wiki/Metric_%28mathematics%29
392 p_dist : function, optional
393 Any function used to give weight to the distance between nodes when
394 deciding whether or not they should be connected. `p_dist` was
395 originally conceived as a probability density function giving the
396 probability of connecting two nodes that are of metric distance `r`
397 apart. The implementation here allows for more arbitrary definitions
398 of `p_dist` that do not need to correspond to valid probability
399 density functions. The :mod:`scipy.stats` package has many
400 probability density functions implemented and tools for custom
401 probability density definitions, and passing the ``.pdf`` method of
402 `scipy.stats` distributions can be used here. If ``p_dist=None``
403 (the default), the exponential function :math:`r^{-2}` is used.
404 seed : integer, random_state, or None (default)
405 Indicator of random number generation state.
406 See :ref:`Randomness<randomness>`.
407 pos_name : string, default="pos"
408 The name of the node attribute which represents the position
409 in 2D coordinates of the node in the returned graph.
410 weight_name : string, default="weight"
411 The name of the node attribute which represents the weight
412 of the node in the returned graph.
414 Returns
415 -------
416 Graph
417 A random geographic threshold graph, undirected and without
418 self-loops.
420 Each node has a node attribute ``pos`` that stores the
421 position of that node in Euclidean space as provided by the
422 ``pos`` keyword argument or, if ``pos`` was not provided, as
423 generated by this function. Similarly, each node has a node
424 attribute ``weight`` that stores the weight of that node as
425 provided or as generated.
427 Examples
428 --------
429 Specify an alternate distance metric using the ``metric`` keyword
430 argument. For example, to use the `taxicab metric`_ instead of the
431 default `Euclidean metric`_::
433 >>> dist = lambda x, y: sum(abs(a - b) for a, b in zip(x, y))
434 >>> G = nx.geographical_threshold_graph(10, 0.1, metric=dist)
436 .. _taxicab metric: https://en.wikipedia.org/wiki/Taxicab_geometry
437 .. _Euclidean metric: https://en.wikipedia.org/wiki/Euclidean_distance
439 Notes
440 -----
441 If weights are not specified they are assigned to nodes by drawing randomly
442 from the exponential distribution with rate parameter $\lambda=1$.
443 To specify weights from a different distribution, use the `weight` keyword
444 argument::
446 >>> import random
447 >>> n = 20
448 >>> w = {i: random.expovariate(5.0) for i in range(n)}
449 >>> G = nx.geographical_threshold_graph(20, 50, weight=w)
451 If node positions are not specified they are randomly assigned from the
452 uniform distribution.
454 References
455 ----------
456 .. [1] Masuda, N., Miwa, H., Konno, N.:
457 Geographical threshold graphs with small-world and scale-free
458 properties.
459 Physical Review E 71, 036108 (2005)
460 .. [2] Milan Bradonjić, Aric Hagberg and Allon G. Percus,
461 Giant component and connectivity in geographical threshold graphs,
462 in Algorithms and Models for the Web-Graph (WAW 2007),
463 Antony Bonato and Fan Chung (Eds), pp. 209--216, 2007
464 """
465 G = nx.empty_graph(n)
466 # If no weights are provided, choose them from an exponential
467 # distribution.
468 if weight is None:
469 weight = {v: seed.expovariate(1) for v in G}
470 # If no positions are provided, choose uniformly random vectors in
471 # Euclidean space of the specified dimension.
472 if pos is None:
473 pos = {v: [seed.random() for i in range(dim)] for v in G}
474 # If no distance metric is provided, use Euclidean distance.
475 if metric is None:
476 metric = math.dist
477 nx.set_node_attributes(G, weight, weight_name)
478 nx.set_node_attributes(G, pos, pos_name)
480 # if p_dist is not supplied, use default r^-2
481 if p_dist is None:
483 def p_dist(r):
484 return r**-2
486 # Returns ``True`` if and only if the nodes whose attributes are
487 # ``du`` and ``dv`` should be joined, according to the threshold
488 # condition.
489 def should_join(pair):
490 u, v = pair
491 u_pos, v_pos = pos[u], pos[v]
492 u_weight, v_weight = weight[u], weight[v]
493 return (u_weight + v_weight) * p_dist(metric(u_pos, v_pos)) >= theta
495 G.add_edges_from(filter(should_join, combinations(G, 2)))
496 return G
499@py_random_state(6)
500@nx._dispatchable(graphs=None, returns_graph=True)
501def waxman_graph(
502 n,
503 beta=0.4,
504 alpha=0.1,
505 L=None,
506 domain=(0, 0, 1, 1),
507 metric=None,
508 seed=None,
509 *,
510 pos_name="pos",
511):
512 r"""Returns a Waxman random graph.
514 The Waxman random graph model places `n` nodes uniformly at random
515 in a rectangular domain. Each pair of nodes at distance `d` is
516 joined by an edge with probability
518 .. math::
519 p = \beta \exp(-d / \alpha L).
521 This function implements both Waxman models, using the `L` keyword
522 argument.
524 * Waxman-1: if `L` is not specified, it is set to be the maximum distance
525 between any pair of nodes.
526 * Waxman-2: if `L` is specified, the distance between a pair of nodes is
527 chosen uniformly at random from the interval `[0, L]`.
529 Parameters
530 ----------
531 n : int or iterable
532 Number of nodes or iterable of nodes
533 beta: float
534 Model parameter
535 alpha: float
536 Model parameter
537 L : float, optional
538 Maximum distance between nodes. If not specified, the actual distance
539 is calculated.
540 domain : four-tuple of numbers, optional
541 Domain size, given as a tuple of the form `(x_min, y_min, x_max,
542 y_max)`.
543 metric : function
544 A metric on vectors of numbers (represented as lists or
545 tuples). This must be a function that accepts two lists (or
546 tuples) as input and yields a number as output. The function
547 must also satisfy the four requirements of a `metric`_.
548 Specifically, if $d$ is the function and $x$, $y$,
549 and $z$ are vectors in the graph, then $d$ must satisfy
551 1. $d(x, y) \ge 0$,
552 2. $d(x, y) = 0$ if and only if $x = y$,
553 3. $d(x, y) = d(y, x)$,
554 4. $d(x, z) \le d(x, y) + d(y, z)$.
556 If this argument is not specified, the Euclidean distance metric is
557 used.
559 .. _metric: https://en.wikipedia.org/wiki/Metric_%28mathematics%29
561 seed : integer, random_state, or None (default)
562 Indicator of random number generation state.
563 See :ref:`Randomness<randomness>`.
564 pos_name : string, default="pos"
565 The name of the node attribute which represents the position
566 in 2D coordinates of the node in the returned graph.
568 Returns
569 -------
570 Graph
571 A random Waxman graph, undirected and without self-loops. Each
572 node has a node attribute ``'pos'`` that stores the position of
573 that node in Euclidean space as generated by this function.
575 Examples
576 --------
577 Specify an alternate distance metric using the ``metric`` keyword
578 argument. For example, to use the "`taxicab metric`_" instead of the
579 default `Euclidean metric`_::
581 >>> dist = lambda x, y: sum(abs(a - b) for a, b in zip(x, y))
582 >>> G = nx.waxman_graph(10, 0.5, 0.1, metric=dist)
584 .. _taxicab metric: https://en.wikipedia.org/wiki/Taxicab_geometry
585 .. _Euclidean metric: https://en.wikipedia.org/wiki/Euclidean_distance
587 Notes
588 -----
589 Starting in NetworkX 2.0 the parameters alpha and beta align with their
590 usual roles in the probability distribution. In earlier versions their
591 positions in the expression were reversed. Their position in the calling
592 sequence reversed as well to minimize backward incompatibility.
594 References
595 ----------
596 .. [1] B. M. Waxman, *Routing of multipoint connections*.
597 IEEE J. Select. Areas Commun. 6(9),(1988) 1617--1622.
598 """
599 G = nx.empty_graph(n)
600 (xmin, ymin, xmax, ymax) = domain
601 # Each node gets a uniformly random position in the given rectangle.
602 pos = {v: (seed.uniform(xmin, xmax), seed.uniform(ymin, ymax)) for v in G}
603 nx.set_node_attributes(G, pos, pos_name)
604 # If no distance metric is provided, use Euclidean distance.
605 if metric is None:
606 metric = math.dist
607 # If the maximum distance L is not specified (that is, we are in the
608 # Waxman-1 model), then find the maximum distance between any pair
609 # of nodes.
610 #
611 # In the Waxman-1 model, join nodes randomly based on distance. In
612 # the Waxman-2 model, join randomly based on random l.
613 if L is None:
614 L = max(metric(x, y) for x, y in combinations(pos.values(), 2))
616 def dist(u, v):
617 return metric(pos[u], pos[v])
619 else:
621 def dist(u, v):
622 return seed.random() * L
624 # `pair` is the pair of nodes to decide whether to join.
625 def should_join(pair):
626 return seed.random() < beta * math.exp(-dist(*pair) / (alpha * L))
628 G.add_edges_from(filter(should_join, combinations(G, 2)))
629 return G
632@py_random_state(5)
633@nx._dispatchable(graphs=None, returns_graph=True)
634def navigable_small_world_graph(n, p=1, q=1, r=2, dim=2, seed=None):
635 r"""Returns a navigable small-world graph.
637 A navigable small-world graph is a directed grid with additional long-range
638 connections that are chosen randomly.
640 [...] we begin with a set of nodes [...] that are identified with the set
641 of lattice points in an $n \times n$ square,
642 $\{(i, j): i \in \{1, 2, \ldots, n\}, j \in \{1, 2, \ldots, n\}\}$,
643 and we define the *lattice distance* between two nodes $(i, j)$ and
644 $(k, l)$ to be the number of "lattice steps" separating them:
645 $d((i, j), (k, l)) = |k - i| + |l - j|$.
647 For a universal constant $p >= 1$, the node $u$ has a directed edge to
648 every other node within lattice distance $p$---these are its *local
649 contacts*. For universal constants $q >= 0$ and $r >= 0$ we also
650 construct directed edges from $u$ to $q$ other nodes (the *long-range
651 contacts*) using independent random trials; the $i$th directed edge from
652 $u$ has endpoint $v$ with probability proportional to $[d(u,v)]^{-r}$.
654 -- [1]_
656 Parameters
657 ----------
658 n : int
659 The length of one side of the lattice; the number of nodes in
660 the graph is therefore $n^2$.
661 p : int
662 The diameter of short range connections. Each node is joined with every
663 other node within this lattice distance.
664 q : int
665 The number of long-range connections for each node.
666 r : float
667 Exponent for decaying probability of connections. The probability of
668 connecting to a node at lattice distance $d$ is $1/d^r$.
669 dim : int
670 Dimension of grid
671 seed : integer, random_state, or None (default)
672 Indicator of random number generation state.
673 See :ref:`Randomness<randomness>`.
675 References
676 ----------
677 .. [1] J. Kleinberg. The small-world phenomenon: An algorithmic
678 perspective. Proc. 32nd ACM Symposium on Theory of Computing, 2000.
679 """
680 if p < 1:
681 raise nx.NetworkXException("p must be >= 1")
682 if q < 0:
683 raise nx.NetworkXException("q must be >= 0")
684 if r < 0:
685 raise nx.NetworkXException("r must be >= 0")
687 G = nx.DiGraph()
688 nodes = list(product(range(n), repeat=dim))
689 for p1 in nodes:
690 probs = [0]
691 for p2 in nodes:
692 if p1 == p2:
693 continue
694 d = sum((abs(b - a) for a, b in zip(p1, p2)))
695 if d <= p:
696 G.add_edge(p1, p2)
697 probs.append(d**-r)
698 cdf = list(accumulate(probs))
699 for _ in range(q):
700 target = nodes[bisect_left(cdf, seed.uniform(0, cdf[-1]))]
701 G.add_edge(p1, target)
702 return G
705@py_random_state(7)
706@nx._dispatchable(graphs=None, returns_graph=True)
707def thresholded_random_geometric_graph(
708 n,
709 radius,
710 theta,
711 dim=2,
712 pos=None,
713 weight=None,
714 p=2,
715 seed=None,
716 *,
717 pos_name="pos",
718 weight_name="weight",
719):
720 r"""Returns a thresholded random geometric graph in the unit cube.
722 The thresholded random geometric graph [1] model places `n` nodes
723 uniformly at random in the unit cube of dimensions `dim`. Each node
724 `u` is assigned a weight :math:`w_u`. Two nodes `u` and `v` are
725 joined by an edge if they are within the maximum connection distance,
726 `radius` computed by the `p`-Minkowski distance and the summation of
727 weights :math:`w_u` + :math:`w_v` is greater than or equal
728 to the threshold parameter `theta`.
730 Edges within `radius` of each other are determined using a KDTree when
731 SciPy is available. This reduces the time complexity from :math:`O(n^2)`
732 to :math:`O(n)`.
734 Parameters
735 ----------
736 n : int or iterable
737 Number of nodes or iterable of nodes
738 radius: float
739 Distance threshold value
740 theta: float
741 Threshold value
742 dim : int, optional
743 Dimension of graph
744 pos : dict, optional
745 A dictionary keyed by node with node positions as values.
746 weight : dict, optional
747 Node weights as a dictionary of numbers keyed by node.
748 p : float, optional (default 2)
749 Which Minkowski distance metric to use. `p` has to meet the condition
750 ``1 <= p <= infinity``.
752 If this argument is not specified, the :math:`L^2` metric
753 (the Euclidean distance metric), p = 2 is used.
755 This should not be confused with the `p` of an Erdős-Rényi random
756 graph, which represents probability.
757 seed : integer, random_state, or None (default)
758 Indicator of random number generation state.
759 See :ref:`Randomness<randomness>`.
760 pos_name : string, default="pos"
761 The name of the node attribute which represents the position
762 in 2D coordinates of the node in the returned graph.
763 weight_name : string, default="weight"
764 The name of the node attribute which represents the weight
765 of the node in the returned graph.
767 Returns
768 -------
769 Graph
770 A thresholded random geographic graph, undirected and without
771 self-loops.
773 Each node has a node attribute ``'pos'`` that stores the
774 position of that node in Euclidean space as provided by the
775 ``pos`` keyword argument or, if ``pos`` was not provided, as
776 generated by this function. Similarly, each node has a nodethre
777 attribute ``'weight'`` that stores the weight of that node as
778 provided or as generated.
780 Notes
781 -----
782 This uses a *k*-d tree to build the graph.
784 References
785 ----------
786 .. [1] http://cole-maclean.github.io/blog/files/thesis.pdf
788 Examples
789 --------
790 Default Graph:
792 >>> G = nx.thresholded_random_geometric_graph(50, 0.2, 0.1)
794 Custom Graph:
796 The `pos` keyword argument can be used to specify node positions so you
797 can create an arbitrary distribution and domain for positions.
799 If weights are not specified they are assigned to nodes by drawing randomly
800 from the exponential distribution with rate parameter :math:`\lambda=1`.
801 To specify weights from a different distribution, use the `weight` keyword
802 argument.
804 For example, create a thresholded random geometric graph on 50 nodes using a 2D
805 Gaussian distribution of node positions with mean (0, 0) and standard deviation 2,
806 where nodes are joined by an edge if their sum weights drawn from
807 a exponential distribution with rate = 5 are >= theta = 0.1 and their
808 Euclidean distance is at most 0.2.
810 >>> import random
811 >>> n = 50
812 >>> pos = {i: (random.gauss(0, 2), random.gauss(0, 2)) for i in range(n)}
813 >>> w = {i: random.expovariate(5.0) for i in range(n)}
814 >>> G = nx.thresholded_random_geometric_graph(n, 0.2, 0.1, 2, pos, w)
816 """
817 G = nx.empty_graph(n)
818 G.name = f"thresholded_random_geometric_graph({n}, {radius}, {theta}, {dim})"
819 # If no weights are provided, choose them from an exponential
820 # distribution.
821 if weight is None:
822 weight = {v: seed.expovariate(1) for v in G}
823 # If no positions are provided, choose uniformly random vectors in
824 # Euclidean space of the specified dimension.
825 if pos is None:
826 pos = {v: [seed.random() for i in range(dim)] for v in G}
827 # If no distance metric is provided, use Euclidean distance.
828 nx.set_node_attributes(G, weight, weight_name)
829 nx.set_node_attributes(G, pos, pos_name)
831 edges = (
832 (u, v)
833 for u, v in _geometric_edges(G, radius, p, pos_name)
834 if weight[u] + weight[v] >= theta
835 )
836 G.add_edges_from(edges)
837 return G
840@py_random_state(5)
841@nx._dispatchable(graphs=None, returns_graph=True)
842def geometric_soft_configuration_graph(
843 *, beta, n=None, gamma=None, mean_degree=None, kappas=None, seed=None
844):
845 r"""Returns a random graph from the geometric soft configuration model.
847 The $\mathbb{S}^1$ model [1]_ is the geometric soft configuration model
848 which is able to explain many fundamental features of real networks such as
849 small-world property, heteregenous degree distributions, high level of
850 clustering, and self-similarity.
852 In the geometric soft configuration model, a node $i$ is assigned two hidden
853 variables: a hidden degree $\kappa_i$, quantifying its popularity, influence,
854 or importance, and an angular position $\theta_i$ in a circle abstracting the
855 similarity space, where angular distances between nodes are a proxy for their
856 similarity. Focusing on the angular position, this model is often called
857 the $\mathbb{S}^1$ model (a one-dimensional sphere). The circle's radius is
858 adjusted to $R = N/2\pi$, where $N$ is the number of nodes, so that the density
859 is set to 1 without loss of generality.
861 The connection probability between any pair of nodes increases with
862 the product of their hidden degrees (i.e., their combined popularities),
863 and decreases with the angular distance between the two nodes.
864 Specifically, nodes $i$ and $j$ are connected with the probability
866 $p_{ij} = \frac{1}{1 + \frac{d_{ij}^\beta}{\left(\mu \kappa_i \kappa_j\right)^{\max(1, \beta)}}}$
868 where $d_{ij} = R\Delta\theta_{ij}$ is the arc length of the circle between
869 nodes $i$ and $j$ separated by an angular distance $\Delta\theta_{ij}$.
870 Parameters $\mu$ and $\beta$ (also called inverse temperature) control the
871 average degree and the clustering coefficient, respectively.
873 It can be shown [2]_ that the model undergoes a structural phase transition
874 at $\beta=1$ so that for $\beta<1$ networks are unclustered in the thermodynamic
875 limit (when $N\to \infty$) whereas for $\beta>1$ the ensemble generates
876 networks with finite clustering coefficient.
878 The $\mathbb{S}^1$ model can be expressed as a purely geometric model
879 $\mathbb{H}^2$ in the hyperbolic plane [3]_ by mapping the hidden degree of
880 each node into a radial coordinate as
882 $r_i = \hat{R} - \frac{2 \max(1, \beta)}{\beta \zeta} \ln \left(\frac{\kappa_i}{\kappa_0}\right)$
884 where $\hat{R}$ is the radius of the hyperbolic disk and $\zeta$ is the curvature,
886 $\hat{R} = \frac{2}{\zeta} \ln \left(\frac{N}{\pi}\right)
887 - \frac{2\max(1, \beta)}{\beta \zeta} \ln (\mu \kappa_0^2)$
889 The connection probability then reads
891 $p_{ij} = \frac{1}{1 + \exp\left({\frac{\beta\zeta}{2} (x_{ij} - \hat{R})}\right)}$
893 where
895 $x_{ij} = r_i + r_j + \frac{2}{\zeta} \ln \frac{\Delta\theta_{ij}}{2}$
897 is a good approximation of the hyperbolic distance between two nodes separated
898 by an angular distance $\Delta\theta_{ij}$ with radial coordinates $r_i$ and $r_j$.
899 For $\beta > 1$, the curvature $\zeta = 1$, for $\beta < 1$, $\zeta = \beta^{-1}$.
902 Parameters
903 ----------
904 Either `n`, `gamma`, `mean_degree` are provided or `kappas`. The values of
905 `n`, `gamma`, `mean_degree` (if provided) are used to construct a random
906 kappa-dict keyed by node with values sampled from a power-law distribution.
908 beta : positive number
909 Inverse temperature, controlling the clustering coefficient.
910 n : int (default: None)
911 Size of the network (number of nodes).
912 If not provided, `kappas` must be provided and holds the nodes.
913 gamma : float (default: None)
914 Exponent of the power-law distribution for hidden degrees `kappas`.
915 If not provided, `kappas` must be provided directly.
916 mean_degree : float (default: None)
917 The mean degree in the network.
918 If not provided, `kappas` must be provided directly.
919 kappas : dict (default: None)
920 A dict keyed by node to its hidden degree value.
921 If not provided, random values are computed based on a power-law
922 distribution using `n`, `gamma` and `mean_degree`.
923 seed : int, random_state, or None (default)
924 Indicator of random number generation state.
925 See :ref:`Randomness<randomness>`.
927 Returns
928 -------
929 Graph
930 A random geometric soft configuration graph (undirected with no self-loops).
931 Each node has three node-attributes:
933 - ``kappa`` that represents the hidden degree.
935 - ``theta`` the position in the similarity space ($\mathbb{S}^1$) which is
936 also the angular position in the hyperbolic plane.
938 - ``radius`` the radial position in the hyperbolic plane
939 (based on the hidden degree).
942 Examples
943 --------
944 Generate a network with specified parameters:
946 >>> G = nx.geometric_soft_configuration_graph(
947 ... beta=1.5, n=100, gamma=2.7, mean_degree=5
948 ... )
950 Create a geometric soft configuration graph with 100 nodes. The $\beta$ parameter
951 is set to 1.5 and the exponent of the powerlaw distribution of the hidden
952 degrees is 2.7 with mean value of 5.
954 Generate a network with predefined hidden degrees:
956 >>> kappas = {i: 10 for i in range(100)}
957 >>> G = nx.geometric_soft_configuration_graph(beta=2.5, kappas=kappas)
959 Create a geometric soft configuration graph with 100 nodes. The $\beta$ parameter
960 is set to 2.5 and all nodes with hidden degree $\kappa=10$.
963 References
964 ----------
965 .. [1] Serrano, M. Á., Krioukov, D., & Boguñá, M. (2008). Self-similarity
966 of complex networks and hidden metric spaces. Physical review letters, 100(7), 078701.
968 .. [2] van der Kolk, J., Serrano, M. Á., & Boguñá, M. (2022). An anomalous
969 topological phase transition in spatial random graphs. Communications Physics, 5(1), 245.
971 .. [3] Krioukov, D., Papadopoulos, F., Kitsak, M., Vahdat, A., & Boguná, M. (2010).
972 Hyperbolic geometry of complex networks. Physical Review E, 82(3), 036106.
974 """
975 if beta <= 0:
976 raise nx.NetworkXError("The parameter beta cannot be smaller or equal to 0.")
978 if kappas is not None:
979 if not all((n is None, gamma is None, mean_degree is None)):
980 raise nx.NetworkXError(
981 "When kappas is input, n, gamma and mean_degree must not be."
982 )
984 n = len(kappas)
985 mean_degree = sum(kappas) / len(kappas)
986 else:
987 if any((n is None, gamma is None, mean_degree is None)):
988 raise nx.NetworkXError(
989 "Please provide either kappas, or all 3 of: n, gamma and mean_degree."
990 )
992 # Generate `n` hidden degrees from a powerlaw distribution
993 # with given exponent `gamma` and mean value `mean_degree`
994 gam_ratio = (gamma - 2) / (gamma - 1)
995 kappa_0 = mean_degree * gam_ratio * (1 - 1 / n) / (1 - 1 / n**gam_ratio)
996 base = 1 - 1 / n
997 power = 1 / (1 - gamma)
998 kappas = {i: kappa_0 * (1 - seed.random() * base) ** power for i in range(n)}
1000 G = nx.Graph()
1001 R = n / (2 * math.pi)
1003 # Approximate values for mu in the thermodynamic limit (when n -> infinity)
1004 if beta > 1:
1005 mu = beta * math.sin(math.pi / beta) / (2 * math.pi * mean_degree)
1006 elif beta == 1:
1007 mu = 1 / (2 * mean_degree * math.log(n))
1008 else:
1009 mu = (1 - beta) / (2**beta * mean_degree * n ** (1 - beta))
1011 # Generate random positions on a circle
1012 thetas = {k: seed.uniform(0, 2 * math.pi) for k in kappas}
1014 for u in kappas:
1015 for v in list(G):
1016 angle = math.pi - math.fabs(math.pi - math.fabs(thetas[u] - thetas[v]))
1017 dij = math.pow(R * angle, beta)
1018 mu_kappas = math.pow(mu * kappas[u] * kappas[v], max(1, beta))
1019 p_ij = 1 / (1 + dij / mu_kappas)
1021 # Create an edge with a certain connection probability
1022 if seed.random() < p_ij:
1023 G.add_edge(u, v)
1024 G.add_node(u)
1026 nx.set_node_attributes(G, thetas, "theta")
1027 nx.set_node_attributes(G, kappas, "kappa")
1029 # Map hidden degrees into the radial coordinates
1030 zeta = 1 if beta > 1 else 1 / beta
1031 kappa_min = min(kappas.values())
1032 R_c = 2 * max(1, beta) / (beta * zeta)
1033 R_hat = (2 / zeta) * math.log(n / math.pi) - R_c * math.log(mu * kappa_min)
1034 radii = {node: R_hat - R_c * math.log(kappa) for node, kappa in kappas.items()}
1035 nx.set_node_attributes(G, radii, "radius")
1037 return G