#
source:
networkx/networkx/generators/geometric.py
@
1711:e48e5bb50cf0

Revision 1711:e48e5bb50cf0, 11.2 KB checked in by Aric Hagberg <aric.hagberg@…>, 3 years ago (diff) |
---|

Line | |
---|---|

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 |

**Note:**See TracBrowser for help on using the repository browser.