1 | # -*- coding: utf-8 -*- |
---|
2 | """ |
---|
3 | Generators for geometric graphs. |
---|
4 | """ |
---|
5 | # Copyright (C) 2004-2011 by |
---|
6 | # Aric Hagberg <hagberg@lanl.gov> |
---|
7 | # Dan Schult <dschult@colgate.edu> |
---|
8 | # Pieter Swart <swart@lanl.gov> |
---|
9 | # All rights reserved. |
---|
10 | # BSD license. |
---|
11 | |
---|
12 | from __future__ import print_function |
---|
13 | |
---|
14 | __author__ = "\n".join(['Aric Hagberg (hagberg@lanl.gov)', |
---|
15 | 'Dan Schult (dschult@colgate.edu)', |
---|
16 | 'Ben Edwards (BJEdwards@gmail.com)']) |
---|
17 | |
---|
18 | __all__ = ['random_geometric_graph', |
---|
19 | 'waxman_graph', |
---|
20 | 'geographical_threshold_graph', |
---|
21 | 'navigable_small_world_graph'] |
---|
22 | |
---|
23 | from bisect import bisect_left |
---|
24 | from functools import reduce |
---|
25 | from itertools import product |
---|
26 | import math, random, sys |
---|
27 | import networkx as nx |
---|
28 | |
---|
29 | #--------------------------------------------------------------------------- |
---|
30 | # Random Geometric Graphs |
---|
31 | #--------------------------------------------------------------------------- |
---|
32 | |
---|
33 | def random_geometric_graph(n, radius, dim=2, pos=None): |
---|
34 | r"""Return the random geometric graph in the unit cube. |
---|
35 | |
---|
36 | The random geometric graph model places n nodes uniformly at random |
---|
37 | in the unit cube Two nodes `u,v` are connected with an edge if |
---|
38 | `d(u,v)<=r` where `d` is the Euclidean distance and `r` is a radius |
---|
39 | threshold. |
---|
40 | |
---|
41 | Parameters |
---|
42 | ---------- |
---|
43 | n : int |
---|
44 | Number of nodes |
---|
45 | radius: float |
---|
46 | Distance threshold value |
---|
47 | dim : int, optional |
---|
48 | Dimension of graph |
---|
49 | pos : dict, optional |
---|
50 | A dictionary keyed by node with node positions as values. |
---|
51 | |
---|
52 | Returns |
---|
53 | ------- |
---|
54 | Graph |
---|
55 | |
---|
56 | Examples |
---|
57 | -------- |
---|
58 | >>> G = nx.random_geometric_graph(20,0.1) |
---|
59 | |
---|
60 | Notes |
---|
61 | ----- |
---|
62 | This uses an `n^2` algorithm to build the graph. A faster algorithm |
---|
63 | is possible using k-d trees. |
---|
64 | |
---|
65 | The pos keyword can be used to specify node positions so you can create |
---|
66 | an arbitrary distribution and domain for positions. If you need a distance |
---|
67 | function other than Euclidean you'll have to hack the algorithm. |
---|
68 | |
---|
69 | E.g to use a 2d Gaussian distribution of node positions with mean (0,0) |
---|
70 | and std. dev. 2 |
---|
71 | |
---|
72 | >>> import random |
---|
73 | >>> n=20 |
---|
74 | >>> p=dict((i,(random.gauss(0,2),random.gauss(0,2))) for i in range(n)) |
---|
75 | >>> G = nx.random_geometric_graph(n,0.2,pos=p) |
---|
76 | |
---|
77 | References |
---|
78 | ---------- |
---|
79 | .. [1] Penrose, Mathew, Random Geometric Graphs, |
---|
80 | Oxford Studies in Probability, 5, 2003. |
---|
81 | """ |
---|
82 | G=nx.Graph() |
---|
83 | G.name="Random Geometric Graph" |
---|
84 | G.add_nodes_from(range(n)) |
---|
85 | if pos is None: |
---|
86 | # random positions |
---|
87 | for n in G: |
---|
88 | G.node[n]['pos']=[random.random() for i in range(0,dim)] |
---|
89 | else: |
---|
90 | nx.set_node_attributes(G,'pos',pos) |
---|
91 | # connect nodes within "radius" of each other |
---|
92 | # n^2 algorithm, could use a k-d tree implementation |
---|
93 | nodes = G.nodes(data=True) |
---|
94 | while nodes: |
---|
95 | u,du = nodes.pop() |
---|
96 | pu = du['pos'] |
---|
97 | for v,dv in nodes: |
---|
98 | pv = dv['pos'] |
---|
99 | d = sum(((a-b)**2 for a,b in zip(pu,pv))) |
---|
100 | if d <= radius**2: |
---|
101 | G.add_edge(u,v) |
---|
102 | return G |
---|
103 | |
---|
104 | def geographical_threshold_graph(n, theta, alpha=2, dim=2, |
---|
105 | pos=None, weight=None): |
---|
106 | r"""Return a geographical threshold graph. |
---|
107 | |
---|
108 | The geographical threshold graph model places n nodes uniformly at random |
---|
109 | in a rectangular domain. Each node `u` is assigned a weight `w_u`. |
---|
110 | Two nodes `u,v` are connected with an edge if |
---|
111 | |
---|
112 | .. math:: |
---|
113 | |
---|
114 | w_u + w_v \ge \theta r^{\alpha} |
---|
115 | |
---|
116 | where `r` is the Euclidean distance between `u` and `v`, |
---|
117 | and `\theta`, `\alpha` are parameters. |
---|
118 | |
---|
119 | Parameters |
---|
120 | ---------- |
---|
121 | n : int |
---|
122 | Number of nodes |
---|
123 | theta: float |
---|
124 | Threshold value |
---|
125 | alpha: float, optional |
---|
126 | Exponent of distance function |
---|
127 | dim : int, optional |
---|
128 | Dimension of graph |
---|
129 | pos : dict |
---|
130 | Node positions as a dictionary of tuples keyed by node. |
---|
131 | weight : dict |
---|
132 | Node weights as a dictionary of numbers keyed by node. |
---|
133 | |
---|
134 | Returns |
---|
135 | ------- |
---|
136 | Graph |
---|
137 | |
---|
138 | Examples |
---|
139 | -------- |
---|
140 | >>> G = nx.geographical_threshold_graph(20,50) |
---|
141 | |
---|
142 | Notes |
---|
143 | ----- |
---|
144 | If weights are not specified they are assigned to nodes by drawing randomly |
---|
145 | from an the exponential distribution with rate parameter `\lambda=1`. |
---|
146 | To specify a weights from a different distribution assign them to a |
---|
147 | dictionary and pass it as the weight= keyword |
---|
148 | |
---|
149 | >>> import random |
---|
150 | >>> n = 20 |
---|
151 | >>> w=dict((i,random.expovariate(5.0)) for i in range(n)) |
---|
152 | >>> G = nx.geographical_threshold_graph(20,50,weight=w) |
---|
153 | |
---|
154 | If node positions are not specified they are randomly assigned from the |
---|
155 | uniform distribution. |
---|
156 | |
---|
157 | References |
---|
158 | ---------- |
---|
159 | .. [1] Masuda, N., Miwa, H., Konno, N.: |
---|
160 | Geographical threshold graphs with small-world and scale-free properties. |
---|
161 | Physical Review E 71, 036108 (2005) |
---|
162 | .. [2] Milan Bradonjić, Aric Hagberg and Allon G. Percus, |
---|
163 | Giant component and connectivity in geographical threshold graphs, |
---|
164 | in Algorithms and Models for the Web-Graph (WAW 2007), |
---|
165 | Antony Bonato and Fan Chung (Eds), pp. 209--216, 2007 |
---|
166 | """ |
---|
167 | G=nx.Graph() |
---|
168 | # add n nodes |
---|
169 | G.add_nodes_from([v for v in range(n)]) |
---|
170 | if weight is None: |
---|
171 | # choose weights from exponential distribution |
---|
172 | for n in G: |
---|
173 | G.node[n]['weight'] = random.expovariate(1.0) |
---|
174 | else: |
---|
175 | nx.set_node_attributes(G,'weight',weight) |
---|
176 | if pos is None: |
---|
177 | # random positions |
---|
178 | for n in G: |
---|
179 | G.node[n]['pos']=[random.random() for i in range(0,dim)] |
---|
180 | else: |
---|
181 | nx.set_node_attributes(G,'pos',pos) |
---|
182 | G.add_edges_from(geographical_threshold_edges(G, theta, alpha)) |
---|
183 | return G |
---|
184 | |
---|
185 | def geographical_threshold_edges(G, theta, alpha=2): |
---|
186 | # generate edges for a geographical threshold graph given a graph |
---|
187 | # with positions and weights assigned as node attributes 'pos' and 'weight'. |
---|
188 | nodes = G.nodes(data=True) |
---|
189 | while nodes: |
---|
190 | u,du = nodes.pop() |
---|
191 | wu = du['weight'] |
---|
192 | pu = du['pos'] |
---|
193 | for v,dv in nodes: |
---|
194 | wv = dv['weight'] |
---|
195 | pv = dv['pos'] |
---|
196 | r = math.sqrt(sum(((a-b)**2 for a,b in zip(pu,pv)))) |
---|
197 | if wu+wv >= theta*r**alpha: |
---|
198 | yield(u,v) |
---|
199 | |
---|
200 | def waxman_graph(n, alpha=0.4, beta=0.1, L=None, domain=(0,0,1,1)): |
---|
201 | r"""Return a Waxman random graph. |
---|
202 | |
---|
203 | The Waxman random graph models place n nodes uniformly at random |
---|
204 | in a rectangular domain. Two nodes u,v are connected with an edge |
---|
205 | with probability |
---|
206 | |
---|
207 | .. math:: |
---|
208 | p = \alpha*exp(d/(\beta*L)). |
---|
209 | |
---|
210 | This function implements both Waxman models. |
---|
211 | |
---|
212 | Waxman-1: `L` not specified |
---|
213 | The distance `d` is the Euclidean distance between the nodes u and v. |
---|
214 | `L` is the maximum distance between all nodes in the graph. |
---|
215 | |
---|
216 | Waxman-2: `L` specified |
---|
217 | The distance `d` is chosen randomly in `[0,L]`. |
---|
218 | |
---|
219 | Parameters |
---|
220 | ---------- |
---|
221 | n : int |
---|
222 | Number of nodes |
---|
223 | alpha: float |
---|
224 | Model parameter |
---|
225 | beta: float |
---|
226 | Model parameter |
---|
227 | L : float, optional |
---|
228 | Maximum distance between nodes. If not specified the actual distance |
---|
229 | is calculated. |
---|
230 | domain : tuple of numbers, optional |
---|
231 | Domain size (xmin, ymin, xmax, ymax) |
---|
232 | |
---|
233 | Returns |
---|
234 | ------- |
---|
235 | G: Graph |
---|
236 | |
---|
237 | References |
---|
238 | ---------- |
---|
239 | .. [1] B. M. Waxman, Routing of multipoint connections. |
---|
240 | IEEE J. Select. Areas Commun. 6(9),(1988) 1617-1622. |
---|
241 | """ |
---|
242 | # build graph of n nodes with random positions in the unit square |
---|
243 | G = nx.Graph() |
---|
244 | G.add_nodes_from(range(n)) |
---|
245 | (xmin,ymin,xmax,ymax)=domain |
---|
246 | for n in G: |
---|
247 | G.node[n]['pos']=((xmin + (xmax-xmin))*random.random(), |
---|
248 | (ymin + (ymax-ymin))*random.random()) |
---|
249 | if L is None: |
---|
250 | # find maximum distance L between two nodes |
---|
251 | l = 0 |
---|
252 | pos = list(nx.get_node_attributes(G,'pos').values()) |
---|
253 | while pos: |
---|
254 | x1,y1 = pos.pop() |
---|
255 | for x2,y2 in pos: |
---|
256 | r2 = (x1-x2)**2 + (y1-y2)**2 |
---|
257 | if r2 > l: |
---|
258 | l = r2 |
---|
259 | l=math.sqrt(l) |
---|
260 | else: |
---|
261 | # user specified maximum distance |
---|
262 | l = L |
---|
263 | |
---|
264 | nodes=G.nodes() |
---|
265 | if L is None: |
---|
266 | # Waxman-1 model |
---|
267 | # try all pairs, connect randomly based on euclidean distance |
---|
268 | while nodes: |
---|
269 | u = nodes.pop() |
---|
270 | x1,y1 = G.node[u]['pos'] |
---|
271 | for v in nodes: |
---|
272 | x2,y2 = G.node[v]['pos'] |
---|
273 | r = math.sqrt((x1-x2)**2 + (y1-y2)**2) |
---|
274 | if random.random() < alpha*math.exp(-r/(beta*l)): |
---|
275 | G.add_edge(u,v) |
---|
276 | else: |
---|
277 | # Waxman-2 model |
---|
278 | # try all pairs, connect randomly based on randomly chosen l |
---|
279 | while nodes: |
---|
280 | u = nodes.pop() |
---|
281 | for v in nodes: |
---|
282 | r = random.random()*l |
---|
283 | if random.random() < alpha*math.exp(-r/(beta*l)): |
---|
284 | G.add_edge(u,v) |
---|
285 | return G |
---|
286 | |
---|
287 | |
---|
288 | def navigable_small_world_graph(n, p=1, q=1, r=2, dim=2, seed=None): |
---|
289 | r"""Return a navigable small-world graph. |
---|
290 | |
---|
291 | A navigable small-world graph is a directed grid with additional |
---|
292 | long-range connections that are chosen randomly. From [1]_: |
---|
293 | |
---|
294 | Begin with a set of nodes that are identified with the set of lattice |
---|
295 | points in an `n \times n` square, `{(i,j): i\in {1,2,\ldots,n}, j\in {1,2,\ldots,n}}` |
---|
296 | and define the lattice distance between two nodes `(i,j)` and `(k,l)` |
---|
297 | to be the number of "lattice steps" separating them: `d((i,j),(k,l)) = |k-i|+|l-j|`. |
---|
298 | |
---|
299 | For a universal constant `p`, the node `u` has a directed edge to every other |
---|
300 | node within lattice distance `p` (local contacts) . |
---|
301 | |
---|
302 | For universal constants `q\ge 0` and `r\ge 0` construct directed edges from `u` to `q` |
---|
303 | other nodes (long-range contacts) using independent random trials; the i'th |
---|
304 | directed edge from `u` has endpoint `v` with probability proportional to `d(u,v)^{-r}`. |
---|
305 | |
---|
306 | Parameters |
---|
307 | ---------- |
---|
308 | n : int |
---|
309 | The number of nodes. |
---|
310 | p : int |
---|
311 | The diameter of short range connections. Each node is connected |
---|
312 | to every other node within lattice distance p. |
---|
313 | q : int |
---|
314 | The number of long-range connections for each node. |
---|
315 | r : float |
---|
316 | Exponent for decaying probability of connections. The probability of |
---|
317 | connecting to a node at lattice distance d is 1/d^r. |
---|
318 | dim : int |
---|
319 | Dimension of grid |
---|
320 | seed : int, optional |
---|
321 | Seed for random number generator (default=None). |
---|
322 | |
---|
323 | References |
---|
324 | ---------- |
---|
325 | .. [1] J. Kleinberg. The small-world phenomenon: An algorithmic |
---|
326 | perspective. Proc. 32nd ACM Symposium on Theory of Computing, 2000. |
---|
327 | """ |
---|
328 | if (p < 1): |
---|
329 | raise nx.NetworkXException("p must be >= 1") |
---|
330 | if (q < 0): |
---|
331 | raise nx.NetworkXException("q must be >= 0") |
---|
332 | if (r < 0): |
---|
333 | raise nx.NetworkXException("r must be >= 1") |
---|
334 | if not seed is None: |
---|
335 | random.seed(seed) |
---|
336 | G = nx.DiGraph() |
---|
337 | nodes = list(product(range(n),repeat=dim)) |
---|
338 | for p1 in nodes: |
---|
339 | probs = [0] |
---|
340 | for p2 in nodes: |
---|
341 | if p1==p2: |
---|
342 | continue |
---|
343 | d = sum((abs(b-a) for a,b in zip(p1,p2))) |
---|
344 | if d <= p: |
---|
345 | G.add_edge(p1,p2) |
---|
346 | probs.append(d**-r) |
---|
347 | cdf = list(nx.utils.cumulative_sum(probs)) |
---|
348 | for _ in range(q): |
---|
349 | target = nodes[bisect_left(cdf,random.uniform(0, cdf[-1]))] |
---|
350 | G.add_edge(p1,target) |
---|
351 | return G |
---|
352 | |
---|