ioftools / networkxMiCe / networkxmaster / networkx / generators / geometric.py @ 5cef0f13
History  View  Annotate  Download (29.5 KB)
1 
# * coding: utf8 *


2 
# Copyright (C) 20042019 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ősRé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 selfloops.

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ősRé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 01. 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 selfloops.

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): 9861028.

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 01.

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 
selfloops.

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 smallworld and scalefree

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 WebGraph (WAW 2007),

437 
Antony Bonato and Fan Chung (Eds), pp. 209216, 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 
* Waxman1: if `L` is not specified, it is set to be the maximum distance

491 
between any pair of nodes.

492 
* Waxman2: 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 : fourtuple 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 selfloops. 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) 16171622.

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 
# Waxman1 model), then find the maximum distance between any pair

574 
# of nodes.

575 
#

576 
# In the Waxman1 model, join nodes randomly based on distance. In

577 
# the Waxman2 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 smallworld graph.

596 

597 
A navigable smallworld graph is a directed grid with additional longrange

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 *longrange

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 longrange 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 smallworld 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ősRé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 
selfloops.

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://colemaclean.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
