Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / generators / geometric.py @ 5cef0f13

History | View | Annotate | Download (29.5 KB)

1
# -*- coding: utf-8 -*-
2
#    Copyright (C) 2004-2019 by
3
#    Aric Hagberg <hagberg@lanl.gov>
4
#    Dan Schult <dschult@colgate.edu>
5
#    Pieter Swart <swart@lanl.gov>
6
#    All rights reserved.
7
#    BSD license.
8
#
9
# Authors: Aric Hagberg (hagberg@lanl.gov)
10
#          Dan Schult (dschult@colgate.edu)
11
#          Ben Edwards (BJEdwards@gmail.com)
12
#          Arya McCarthy (admccarthy@smu.edu)
13
#          Cole MacLean (maclean.cole@gmail.com)
14

    
15
"""Generators for geometric graphs.
16
"""
17
from __future__ import division
18

    
19
from bisect import bisect_left
20
from itertools import combinations
21
from itertools import product
22
from math import sqrt
23
import math
24
try:
25
    from scipy.spatial import cKDTree as KDTree
26
except ImportError:
27
    _is_scipy_available = False
28
else:
29
    _is_scipy_available = True
30

    
31
import networkx as nx
32
from networkx.utils import nodes_or_number, py_random_state
33

    
34
__all__ = ['geographical_threshold_graph', 'waxman_graph',
35
           'navigable_small_world_graph', 'random_geometric_graph',
36
           'soft_random_geometric_graph', 'thresholded_random_geometric_graph']
37

    
38

    
39
def euclidean(x, y):
40
    """Returns the Euclidean distance between the vectors ``x`` and ``y``.
41

42
    Each of ``x`` and ``y`` can be any iterable of numbers. The
43
    iterables must be of the same length.
44

45
    """
46
    return sqrt(sum((a - b) ** 2 for a, b in zip(x, y)))
47

    
48

    
49
def _fast_edges(G, radius, p):
50
    """Returns edge list of node pairs within `radius` of each other
51
       using scipy KDTree and Minkowski distance metric `p`
52

53
    Requires scipy to be installed.
54
    """
55
    pos = nx.get_node_attributes(G, 'pos')
56
    nodes, coords = list(zip(*pos.items()))
57
    kdtree = KDTree(coords)  # Cannot provide generator.
58
    edge_indexes = kdtree.query_pairs(radius, p)
59
    edges = ((nodes[u], nodes[v]) for u, v in edge_indexes)
60
    return edges
61

    
62

    
63
def _slow_edges(G, radius, p):
64
    """Returns edge list of node pairs within `radius` of each other
65
       using Minkowski distance metric `p`
66

67
    Works without scipy, but in `O(n^2)` time.
68
    """
69
    # TODO This can be parallelized.
70
    edges = []
71
    for (u, pu), (v, pv) in combinations(G.nodes(data='pos'), 2):
72
        if sum(abs(a - b) ** p for a, b in zip(pu, pv)) <= radius ** p:
73
            edges.append((u, v))
74
    return edges
75

    
76

    
77
@py_random_state(5)
78
@nodes_or_number(0)
79
def random_geometric_graph(n, radius, dim=2, pos=None, p=2, seed=None):
80
    """Returns a random geometric graph in the unit cube of dimensions `dim`.
81

82
    The random geometric graph model places `n` nodes uniformly at
83
    random in the unit cube. Two nodes are joined by an edge if the
84
    distance between the nodes is at most `radius`.
85

86
    Edges are determined using a KDTree when SciPy is available.
87
    This reduces the time complexity from $O(n^2)$ to $O(n)$.
88

89
    Parameters
90
    ----------
91
    n : int or iterable
92
        Number of nodes or iterable of nodes
93
    radius: float
94
        Distance threshold value
95
    dim : int, optional
96
        Dimension of graph
97
    pos : dict, optional
98
        A dictionary keyed by node with node positions as values.
99
    p : float, optional
100
        Which Minkowski distance metric to use.  `p` has to meet the condition
101
        ``1 <= p <= infinity``.
102

103
        If this argument is not specified, the :math:`L^2` metric
104
        (the Euclidean distance metric), p = 2 is used.
105
        This should not be confused with the `p` of an Erdős-Rényi random
106
        graph, which represents probability.
107
    seed : integer, random_state, or None (default)
108
        Indicator of random number generation state.
109
        See :ref:`Randomness<randomness>`.
110

111
    Returns
112
    -------
113
    Graph
114
        A random geometric graph, undirected and without self-loops.
115
        Each node has a node attribute ``'pos'`` that stores the
116
        position of that node in Euclidean space as provided by the
117
        ``pos`` keyword argument or, if ``pos`` was not provided, as
118
        generated by this function.
119

120
    Examples
121
    --------
122
    Create a random geometric graph on twenty nodes where nodes are joined by
123
    an edge if their distance is at most 0.1::
124

125
    >>> G = nx.random_geometric_graph(20, 0.1)
126

127
    Notes
128
    -----
129
    This uses a *k*-d tree to build the graph.
130

131
    The `pos` keyword argument can be used to specify node positions so you
132
    can create an arbitrary distribution and domain for positions.
133

134
    For example, to use a 2D Gaussian distribution of node positions with mean
135
    (0, 0) and standard deviation 2::
136

137
    >>> import random
138
    >>> n = 20
139
    >>> pos = {i: (random.gauss(0, 2), random.gauss(0, 2)) for i in range(n)}
140
    >>> G = nx.random_geometric_graph(n, 0.2, pos=pos)
141

142
    References
143
    ----------
144
    .. [1] Penrose, Mathew, *Random Geometric Graphs*,
145
           Oxford Studies in Probability, 5, 2003.
146

147
    """
148
    # TODO Is this function just a special case of the geographical
149
    # threshold graph?
150
    #
151
    #     n_name, nodes = n
152
    #     half_radius = {v: radius / 2 for v in nodes}
153
    #     return geographical_threshold_graph(nodes, theta=1, alpha=1,
154
    #                                         weight=half_radius)
155
    #
156
    n_name, nodes = n
157
    G = nx.Graph()
158
    G.add_nodes_from(nodes)
159
    # If no positions are provided, choose uniformly random vectors in
160
    # Euclidean space of the specified dimension.
161
    if pos is None:
162
        pos = {v: [seed.random() for i in range(dim)] for v in nodes}
163
    nx.set_node_attributes(G, pos, 'pos')
164

    
165
    if _is_scipy_available:
166
        edges = _fast_edges(G, radius, p)
167
    else:
168
        edges = _slow_edges(G, radius, p)
169
    G.add_edges_from(edges)
170

    
171
    return G
172

    
173

    
174
@py_random_state(6)
175
@nodes_or_number(0)
176
def soft_random_geometric_graph(n, radius, dim=2, pos=None, p=2, p_dist=None,
177
                                seed=None):
178
    r"""Returns a soft random geometric graph in the unit cube.
179

180
    The soft random geometric graph [1] model places `n` nodes uniformly at
181
    random in the unit cube in dimension `dim`. Two nodes of distance, `dist`,
182
    computed by the `p`-Minkowski distance metric are joined by an edge with
183
    probability `p_dist` if the computed distance metric value of the nodes
184
    is at most `radius`, otherwise they are not joined.
185

186
    Edges within `radius` of each other are determined using a KDTree when
187
    SciPy is available. This reduces the time complexity from :math:`O(n^2)`
188
    to :math:`O(n)`.
189

190
    Parameters
191
    ----------
192
    n : int or iterable
193
        Number of nodes or iterable of nodes
194
    radius: float
195
        Distance threshold value
196
    dim : int, optional
197
        Dimension of graph
198
    pos : dict, optional
199
        A dictionary keyed by node with node positions as values.
200
    p : float, optional
201
        Which Minkowski distance metric to use.
202
        `p` has to meet the condition ``1 <= p <= infinity``.
203

204
        If this argument is not specified, the :math:`L^2` metric
205
        (the Euclidean distance metric), p = 2 is used.
206

207
        This should not be confused with the `p` of an Erdős-Rényi random
208
        graph, which represents probability.
209
    p_dist : function, optional
210
        A probability density function computing the probability of
211
        connecting two nodes that are of distance, dist, computed by the
212
        Minkowski distance metric. The probability density function, `p_dist`,
213
        must be any function that takes the metric value as input
214
        and outputs a single probability value between 0-1. The scipy.stats
215
        package has many probability distribution functions implemented and
216
        tools for custom probability distribution definitions [2], and passing
217
        the .pdf method of scipy.stats distributions can be used here.  If the
218
        probability function, `p_dist`, is not supplied, the default function
219
        is an exponential distribution with rate parameter :math:`\lambda=1`.
220
    seed : integer, random_state, or None (default)
221
        Indicator of random number generation state.
222
        See :ref:`Randomness<randomness>`.
223

224
    Returns
225
    -------
226
    Graph
227
        A soft random geometric graph, undirected and without self-loops.
228
        Each node has a node attribute ``'pos'`` that stores the
229
        position of that node in Euclidean space as provided by the
230
        ``pos`` keyword argument or, if ``pos`` was not provided, as
231
        generated by this function.
232

233
    Examples
234
    --------
235
    Default Graph:
236

237
    G = nx.soft_random_geometric_graph(50, 0.2)
238

239
    Custom Graph:
240

241
    Create a soft random geometric graph on 100 uniformly distributed nodes
242
    where nodes are joined by an edge with probability computed from an
243
    exponential distribution with rate parameter :math:`\lambda=1` if their
244
    Euclidean distance is at most 0.2.
245

246
    Notes
247
    -----
248
    This uses a *k*-d tree to build the graph.
249

250
    The `pos` keyword argument can be used to specify node positions so you
251
    can create an arbitrary distribution and domain for positions.
252

253
    For example, to use a 2D Gaussian distribution of node positions with mean
254
    (0, 0) and standard deviation 2
255

256
    The scipy.stats package can be used to define the probability distribution
257
    with the .pdf method used as `p_dist`.
258

259
    ::
260

261
    >>> import random
262
    >>> import math
263
    >>> n = 100
264
    >>> pos = {i: (random.gauss(0, 2), random.gauss(0, 2)) for i in range(n)}
265
    >>> p_dist = lambda dist : math.exp(-dist)
266
    >>> G = nx.soft_random_geometric_graph(n, 0.2, pos=pos, p_dist=p_dist)
267

268
    References
269
    ----------
270
    .. [1] Penrose, Mathew D. "Connectivity of soft random geometric graphs."
271
           The Annals of Applied Probability 26.2 (2016): 986-1028.
272
       [2] scipy.stats -
273
           https://docs.scipy.org/doc/scipy/reference/tutorial/stats.html
274

275
    """
276
    n_name, nodes = n
277
    G = nx.Graph()
278
    G.name = 'soft_random_geometric_graph({}, {}, {})'.format(n, radius, dim)
279
    G.add_nodes_from(nodes)
280
    # If no positions are provided, choose uniformly random vectors in
281
    # Euclidean space of the specified dimension.
282
    if pos is None:
283
        pos = {v: [seed.random() for i in range(dim)] for v in nodes}
284
    nx.set_node_attributes(G, pos, 'pos')
285

    
286
    # if p_dist function not supplied the default function is an exponential
287
    # distribution with rate parameter :math:`\lambda=1`.
288
    if p_dist is None:
289

    
290
        def p_dist(dist):
291
            return math.exp(-dist)
292

    
293
    def should_join(pair):
294
        u, v = pair
295
        u_pos, v_pos = pos[u], pos[v]
296
        dist = (sum(abs(a - b) ** p for a, b in zip(u_pos, v_pos)))**(1 / p)
297
        # Check if dist <= radius parameter. This check is redundant if scipy
298
        # is available and _fast_edges routine is used, but provides the
299
        # check in case scipy is not available and all edge combinations
300
        # need to be checked
301
        if dist <= radius:
302
            return seed.random() < p_dist(dist)
303
        else:
304
            return False
305

    
306
    if _is_scipy_available:
307
        edges = _fast_edges(G, radius, p)
308
        G.add_edges_from(filter(should_join, edges))
309
    else:
310
        G.add_edges_from(filter(should_join, combinations(G, 2)))
311

    
312
    return G
313

    
314

    
315
@py_random_state(7)
316
@nodes_or_number(0)
317
def geographical_threshold_graph(n, theta, dim=2, pos=None, weight=None,
318
                                 metric=None, p_dist=None, seed=None):
319
    r"""Returns a geographical threshold graph.
320

321
    The geographical threshold graph model places $n$ nodes uniformly at
322
    random in a rectangular domain.  Each node $u$ is assigned a weight
323
    $w_u$. Two nodes $u$ and $v$ are joined by an edge if
324

325
    .. math::
326

327
       (w_u + w_v)h(r) \ge \theta
328

329
    where `r` is the distance between `u` and `v`, h(r) is a probability of
330
    connection as a function of `r`, and :math:`\theta` as the threshold
331
    parameter. h(r) corresponds to the p_dist parameter.
332

333
    Parameters
334
    ----------
335
    n : int or iterable
336
        Number of nodes or iterable of nodes
337
    theta: float
338
        Threshold value
339
    dim : int, optional
340
        Dimension of graph
341
    pos : dict
342
        Node positions as a dictionary of tuples keyed by node.
343
    weight : dict
344
        Node weights as a dictionary of numbers keyed by node.
345
    metric : function
346
        A metric on vectors of numbers (represented as lists or
347
        tuples). This must be a function that accepts two lists (or
348
        tuples) as input and yields a number as output. The function
349
        must also satisfy the four requirements of a `metric`_.
350
        Specifically, if $d$ is the function and $x$, $y$,
351
        and $z$ are vectors in the graph, then $d$ must satisfy
352

353
        1. $d(x, y) \ge 0$,
354
        2. $d(x, y) = 0$ if and only if $x = y$,
355
        3. $d(x, y) = d(y, x)$,
356
        4. $d(x, z) \le d(x, y) + d(y, z)$.
357

358
        If this argument is not specified, the Euclidean distance metric is
359
        used.
360

361
        .. _metric: https://en.wikipedia.org/wiki/Metric_%28mathematics%29
362
    p_dist : function, optional
363
        A probability density function computing the probability of
364
        connecting two nodes that are of distance, r, computed by metric.
365
        The probability density function, `p_dist`, must
366
        be any function that takes the metric value as input
367
        and outputs a single probability value between 0-1.
368
        The scipy.stats package has many probability distribution functions
369
        implemented and tools for custom probability distribution
370
        definitions [2], and passing the .pdf method of scipy.stats
371
        distributions can be used here. If the probability
372
        function, `p_dist`, is not supplied, the default exponential function
373
        :math: `r^{-2}` is used.
374
    seed : integer, random_state, or None (default)
375
        Indicator of random number generation state.
376
        See :ref:`Randomness<randomness>`.
377

378
    Returns
379
    -------
380
    Graph
381
        A random geographic threshold graph, undirected and without
382
        self-loops.
383

384
        Each node has a node attribute ``pos`` that stores the
385
        position of that node in Euclidean space as provided by the
386
        ``pos`` keyword argument or, if ``pos`` was not provided, as
387
        generated by this function. Similarly, each node has a node
388
        attribute ``weight`` that stores the weight of that node as
389
        provided or as generated.
390

391
    Examples
392
    --------
393
    Specify an alternate distance metric using the ``metric`` keyword
394
    argument. For example, to use the `taxicab metric`_ instead of the
395
    default `Euclidean metric`_::
396

397
        >>> dist = lambda x, y: sum(abs(a - b) for a, b in zip(x, y))
398
        >>> G = nx.geographical_threshold_graph(10, 0.1, metric=dist)
399

400
    .. _taxicab metric: https://en.wikipedia.org/wiki/Taxicab_geometry
401
    .. _Euclidean metric: https://en.wikipedia.org/wiki/Euclidean_distance
402

403
    Notes
404
    -----
405
    If weights are not specified they are assigned to nodes by drawing randomly
406
    from the exponential distribution with rate parameter $\lambda=1$.
407
    To specify weights from a different distribution, use the `weight` keyword
408
    argument::
409

410
    >>> import random
411
    >>> n = 20
412
    >>> w = {i: random.expovariate(5.0) for i in range(n)}
413
    >>> G = nx.geographical_threshold_graph(20, 50, weight=w)
414

415
    If node positions are not specified they are randomly assigned from the
416
    uniform distribution.
417

418
    Starting in NetworkX 2.1 the parameter ``alpha`` is deprecated and replaced
419
    with the customizable ``p_dist`` function parameter, which defaults to r^-2
420
    if ``p_dist`` is not supplied. To reproduce networks of earlier NetworkX
421
    versions, a custom function needs to be defined and passed as the
422
    ``p_dist`` parameter. For example, if the parameter ``alpha`` = 2 was used
423
    in NetworkX 2.0, the custom function def custom_dist(r): r**-2 can be
424
    passed in versions >=2.1 as the parameter p_dist = custom_dist to
425
    produce an equivalent network. Note the change in sign from +2 to -2 in
426
    this parameter change.
427

428
    References
429
    ----------
430
    .. [1] Masuda, N., Miwa, H., Konno, N.:
431
       Geographical threshold graphs with small-world and scale-free
432
       properties.
433
       Physical Review E 71, 036108 (2005)
434
    .. [2]  Milan Bradonjić, Aric Hagberg and Allon G. Percus,
435
       Giant component and connectivity in geographical threshold graphs,
436
       in Algorithms and Models for the Web-Graph (WAW 2007),
437
       Antony Bonato and Fan Chung (Eds), pp. 209--216, 2007
438
    """
439
    n_name, nodes = n
440
    G = nx.Graph()
441
    G.add_nodes_from(nodes)
442
    # If no weights are provided, choose them from an exponential
443
    # distribution.
444
    if weight is None:
445
        weight = {v: seed.expovariate(1) for v in G}
446
    # If no positions are provided, choose uniformly random vectors in
447
    # Euclidean space of the specified dimension.
448
    if pos is None:
449
        pos = {v: [seed.random() for i in range(dim)] for v in nodes}
450
    # If no distance metric is provided, use Euclidean distance.
451
    if metric is None:
452
        metric = euclidean
453
    nx.set_node_attributes(G, weight, 'weight')
454
    nx.set_node_attributes(G, pos, 'pos')
455

    
456
    # if p_dist is not supplied, use default r^-2
457
    if p_dist is None:
458
        def p_dist(r):
459
            return r**-2
460

    
461
    # Returns ``True`` if and only if the nodes whose attributes are
462
    # ``du`` and ``dv`` should be joined, according to the threshold
463
    # condition.
464
    def should_join(pair):
465
        u, v = pair
466
        u_pos, v_pos = pos[u], pos[v]
467
        u_weight, v_weight = weight[u], weight[v]
468
        return (u_weight + v_weight) * p_dist(metric(u_pos, v_pos)) >= theta
469

    
470
    G.add_edges_from(filter(should_join, combinations(G, 2)))
471
    return G
472

    
473

    
474
@py_random_state(6)
475
@nodes_or_number(0)
476
def waxman_graph(n, beta=0.4, alpha=0.1, L=None, domain=(0, 0, 1, 1),
477
                 metric=None, seed=None):
478
    r"""Returns a Waxman random graph.
479

480
    The Waxman random graph model places `n` nodes uniformly at random
481
    in a rectangular domain. Each pair of nodes at distance `d` is
482
    joined by an edge with probability
483

484
    .. math::
485
            p = \beta \exp(-d / \alpha L).
486

487
    This function implements both Waxman models, using the `L` keyword
488
    argument.
489

490
    * Waxman-1: if `L` is not specified, it is set to be the maximum distance
491
      between any pair of nodes.
492
    * Waxman-2: if `L` is specified, the distance between a pair of nodes is
493
      chosen uniformly at random from the interval `[0, L]`.
494

495
    Parameters
496
    ----------
497
    n : int or iterable
498
        Number of nodes or iterable of nodes
499
    beta: float
500
        Model parameter
501
    alpha: float
502
        Model parameter
503
    L : float, optional
504
        Maximum distance between nodes.  If not specified, the actual distance
505
        is calculated.
506
    domain : four-tuple of numbers, optional
507
        Domain size, given as a tuple of the form `(x_min, y_min, x_max,
508
        y_max)`.
509
    metric : function
510
        A metric on vectors of numbers (represented as lists or
511
        tuples). This must be a function that accepts two lists (or
512
        tuples) as input and yields a number as output. The function
513
        must also satisfy the four requirements of a `metric`_.
514
        Specifically, if $d$ is the function and $x$, $y$,
515
        and $z$ are vectors in the graph, then $d$ must satisfy
516

517
        1. $d(x, y) \ge 0$,
518
        2. $d(x, y) = 0$ if and only if $x = y$,
519
        3. $d(x, y) = d(y, x)$,
520
        4. $d(x, z) \le d(x, y) + d(y, z)$.
521

522
        If this argument is not specified, the Euclidean distance metric is
523
        used.
524

525
        .. _metric: https://en.wikipedia.org/wiki/Metric_%28mathematics%29
526

527
    seed : integer, random_state, or None (default)
528
        Indicator of random number generation state.
529
        See :ref:`Randomness<randomness>`.
530

531
    Returns
532
    -------
533
    Graph
534
        A random Waxman graph, undirected and without self-loops. Each
535
        node has a node attribute ``'pos'`` that stores the position of
536
        that node in Euclidean space as generated by this function.
537

538
    Examples
539
    --------
540
    Specify an alternate distance metric using the ``metric`` keyword
541
    argument. For example, to use the "`taxicab metric`_" instead of the
542
    default `Euclidean metric`_::
543

544
        >>> dist = lambda x, y: sum(abs(a - b) for a, b in zip(x, y))
545
        >>> G = nx.waxman_graph(10, 0.5, 0.1, metric=dist)
546

547
    .. _taxicab metric: https://en.wikipedia.org/wiki/Taxicab_geometry
548
    .. _Euclidean metric: https://en.wikipedia.org/wiki/Euclidean_distance
549

550
    Notes
551
    -----
552
    Starting in NetworkX 2.0 the parameters alpha and beta align with their
553
    usual roles in the probability distribution. In earlier versions their
554
    positions in the expression were reversed. Their position in the calling
555
    sequence reversed as well to minimize backward incompatibility.
556

557
    References
558
    ----------
559
    .. [1]  B. M. Waxman, *Routing of multipoint connections*.
560
       IEEE J. Select. Areas Commun. 6(9),(1988) 1617--1622.
561
    """
562
    n_name, nodes = n
563
    G = nx.Graph()
564
    G.add_nodes_from(nodes)
565
    (xmin, ymin, xmax, ymax) = domain
566
    # Each node gets a uniformly random position in the given rectangle.
567
    pos = {v: (seed.uniform(xmin, xmax), seed.uniform(ymin, ymax)) for v in G}
568
    nx.set_node_attributes(G, pos, 'pos')
569
    # If no distance metric is provided, use Euclidean distance.
570
    if metric is None:
571
        metric = euclidean
572
    # If the maximum distance L is not specified (that is, we are in the
573
    # Waxman-1 model), then find the maximum distance between any pair
574
    # of nodes.
575
    #
576
    # In the Waxman-1 model, join nodes randomly based on distance. In
577
    # the Waxman-2 model, join randomly based on random l.
578
    if L is None:
579
        L = max(metric(x, y) for x, y in combinations(pos.values(), 2))
580

    
581
        def dist(u, v): return metric(pos[u], pos[v])
582
    else:
583
        def dist(u, v): return seed.random() * L
584

    
585
    # `pair` is the pair of nodes to decide whether to join.
586
    def should_join(pair):
587
        return seed.random() < beta * math.exp(-dist(*pair) / (alpha * L))
588

    
589
    G.add_edges_from(filter(should_join, combinations(G, 2)))
590
    return G
591

    
592

    
593
@py_random_state(5)
594
def navigable_small_world_graph(n, p=1, q=1, r=2, dim=2, seed=None):
595
    r"""Returns a navigable small-world graph.
596

597
    A navigable small-world graph is a directed grid with additional long-range
598
    connections that are chosen randomly.
599

600
      [...] we begin with a set of nodes [...] that are identified with the set
601
      of lattice points in an $n \times n$ square,
602
      $\{(i, j): i \in \{1, 2, \ldots, n\}, j \in \{1, 2, \ldots, n\}\}$,
603
      and we define the *lattice distance* between two nodes $(i, j)$ and
604
      $(k, l)$ to be the number of "lattice steps" separating them:
605
      $d((i, j), (k, l)) = |k - i| + |l - j|$.
606

607
      For a universal constant $p >= 1$, the node $u$ has a directed edge to
608
      every other node within lattice distance $p$---these are its *local
609
      contacts*. For universal constants $q >= 0$ and $r >= 0$ we also
610
      construct directed edges from $u$ to $q$ other nodes (the *long-range
611
      contacts*) using independent random trials; the $i$th directed edge from
612
      $u$ has endpoint $v$ with probability proportional to $[d(u,v)]^{-r}$.
613

614
      -- [1]_
615

616
    Parameters
617
    ----------
618
    n : int
619
        The length of one side of the lattice; the number of nodes in
620
        the graph is therefore $n^2$.
621
    p : int
622
        The diameter of short range connections. Each node is joined with every
623
        other node within this lattice distance.
624
    q : int
625
        The number of long-range connections for each node.
626
    r : float
627
        Exponent for decaying probability of connections.  The probability of
628
        connecting to a node at lattice distance $d$ is $1/d^r$.
629
    dim : int
630
        Dimension of grid
631
    seed : integer, random_state, or None (default)
632
        Indicator of random number generation state.
633
        See :ref:`Randomness<randomness>`.
634

635
    References
636
    ----------
637
    .. [1] J. Kleinberg. The small-world phenomenon: An algorithmic
638
       perspective. Proc. 32nd ACM Symposium on Theory of Computing, 2000.
639
    """
640
    if (p < 1):
641
        raise nx.NetworkXException("p must be >= 1")
642
    if (q < 0):
643
        raise nx.NetworkXException("q must be >= 0")
644
    if (r < 0):
645
        raise nx.NetworkXException("r must be >= 1")
646

    
647
    G = nx.DiGraph()
648
    nodes = list(product(range(n), repeat=dim))
649
    for p1 in nodes:
650
        probs = [0]
651
        for p2 in nodes:
652
            if p1 == p2:
653
                continue
654
            d = sum((abs(b - a) for a, b in zip(p1, p2)))
655
            if d <= p:
656
                G.add_edge(p1, p2)
657
            probs.append(d**-r)
658
        cdf = list(nx.utils.accumulate(probs))
659
        for _ in range(q):
660
            target = nodes[bisect_left(cdf, seed.uniform(0, cdf[-1]))]
661
            G.add_edge(p1, target)
662
    return G
663

    
664

    
665
@py_random_state(7)
666
@nodes_or_number(0)
667
def thresholded_random_geometric_graph(n, radius, theta, dim=2,
668
                                       pos=None, weight=None, p=2, seed=None):
669
    r"""Returns a thresholded random geometric graph in the unit cube.
670

671
    The thresholded random geometric graph [1] model places `n` nodes
672
    uniformly at random in the unit cube of dimensions `dim`. Each node
673
    `u` is assigned a weight :math:`w_u`. Two nodes `u` and `v` are
674
    joined by an edge if they are within the maximum connection distance,
675
    `radius` computed by the `p`-Minkowski distance and the summation of
676
    weights :math:`w_u` + :math:`w_v` is greater than or equal
677
    to the threshold parameter `theta`.
678

679
    Edges within `radius` of each other are determined using a KDTree when
680
    SciPy is available. This reduces the time complexity from :math:`O(n^2)`
681
    to :math:`O(n)`.
682

683
    Parameters
684
    ----------
685
    n : int or iterable
686
        Number of nodes or iterable of nodes
687
    radius: float
688
        Distance threshold value
689
    theta: float
690
        Threshold value
691
    dim : int, optional
692
        Dimension of graph
693
    pos : dict, optional
694
        A dictionary keyed by node with node positions as values.
695
    weight : dict, optional
696
        Node weights as a dictionary of numbers keyed by node.
697
    p : float, optional
698
        Which Minkowski distance metric to use.  `p` has to meet the condition
699
        ``1 <= p <= infinity``.
700

701
        If this argument is not specified, the :math:`L^2` metric
702
        (the Euclidean distance metric), p = 2 is used.
703

704
        This should not be confused with the `p` of an Erdős-Rényi random
705
        graph, which represents probability.
706
    seed : integer, random_state, or None (default)
707
        Indicator of random number generation state.
708
        See :ref:`Randomness<randomness>`.
709

710
    Returns
711
    -------
712
    Graph
713
        A thresholded random geographic graph, undirected and without
714
        self-loops.
715

716
        Each node has a node attribute ``'pos'`` that stores the
717
        position of that node in Euclidean space as provided by the
718
        ``pos`` keyword argument or, if ``pos`` was not provided, as
719
        generated by this function. Similarly, each node has a nodethre
720
        attribute ``'weight'`` that stores the weight of that node as
721
        provided or as generated.
722

723
    Examples
724
    --------
725
    Default Graph:
726

727
    G = nx.thresholded_random_geometric_graph(50, 0.2, 0.1)
728

729
    Custom Graph:
730

731
    Create a thresholded random geometric graph on 50 uniformly distributed
732
    nodes where nodes are joined by an edge if their sum weights drawn from
733
    a exponential distribution with rate = 5 are >= theta = 0.1 and their
734
    Euclidean distance is at most 0.2.
735

736
    Notes
737
    -----
738
    This uses a *k*-d tree to build the graph.
739

740
    The `pos` keyword argument can be used to specify node positions so you
741
    can create an arbitrary distribution and domain for positions.
742

743
    For example, to use a 2D Gaussian distribution of node positions with mean
744
    (0, 0) and standard deviation 2
745

746
    If weights are not specified they are assigned to nodes by drawing randomly
747
    from the exponential distribution with rate parameter :math:`\lambda=1`.
748
    To specify weights from a different distribution, use the `weight` keyword
749
    argument::
750

751
    ::
752

753
    >>> import random
754
    >>> import math
755
    >>> n = 50
756
    >>> pos = {i: (random.gauss(0, 2), random.gauss(0, 2)) for i in range(n)}
757
    >>> w = {i: random.expovariate(5.0) for i in range(n)}
758
    >>> G = nx.thresholded_random_geometric_graph(n, 0.2, 0.1, 2, pos, w)
759

760
    References
761
    ----------
762
    .. [1] http://cole-maclean.github.io/blog/files/thesis.pdf
763

764
    """
765

    
766
    n_name, nodes = n
767
    G = nx.Graph()
768
    namestr = 'thresholded_random_geometric_graph({}, {}, {}, {})'
769
    G.name = namestr.format(n, radius, theta, dim)
770
    G.add_nodes_from(nodes)
771
    # If no weights are provided, choose them from an exponential
772
    # distribution.
773
    if weight is None:
774
        weight = {v: seed.expovariate(1) for v in G}
775
    # If no positions are provided, choose uniformly random vectors in
776
    # Euclidean space of the specified dimension.
777
    if pos is None:
778
        pos = {v: [seed.random() for i in range(dim)] for v in nodes}
779
    # If no distance metric is provided, use Euclidean distance.
780

    
781
    nx.set_node_attributes(G, weight, 'weight')
782
    nx.set_node_attributes(G, pos, 'pos')
783

    
784
    # Returns ``True`` if and only if the nodes whose attributes are
785
    # ``du`` and ``dv`` should be joined, according to the threshold
786
    # condition and node pairs are within the maximum connection
787
    # distance, ``radius``.
788
    def should_join(pair):
789
        u, v = pair
790
        u_weight, v_weight = weight[u], weight[v]
791
        u_pos, v_pos = pos[u], pos[v]
792
        dist = (sum(abs(a - b) ** p for a, b in zip(u_pos, v_pos)))**(1 / p)
793
        # Check if dist is <= radius parameter. This check is redundant if
794
        # scipy is available and _fast_edges routine is used, but provides
795
        # the check in case scipy is not available and all edge combinations
796
        # need to be checked
797
        if dist <= radius:
798
            return theta <= u_weight + v_weight
799
        else:
800
            return False
801

    
802
    if _is_scipy_available:
803
        edges = _fast_edges(G, radius, p)
804
        G.add_edges_from(filter(should_join, edges))
805
    else:
806
        G.add_edges_from(filter(should_join, combinations(G, 2)))
807

    
808
    return G