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


2 
# Copyright (C) 20062019 by

3 
# Aric Hagberg <hagberg@lanl.gov>

4 
# Dan Schult <dschult@colgate.edu>

5 
# Pieter Swart <swart@lanl.gov>

6 
# Copyright (C) 2009 by Willem Ligtenberg <W.P.A.Ligtenberg@tue.nl>

7 
# All rights reserved.

8 
# BSD license.

9 
#

10 
# Authors: Aric Hagberg (hagberg@lanl.gov)

11 
# Willem Ligtenberg (W.P.A.Ligtenberg@tue.nl)

12 
"""

13 
Generators for some directed graphs, including growing network (GN) graphs and

14 
scalefree graphs.

15 

16 
"""

17 
from __future__ import division 
18  
19 
from collections import Counter 
20  
21 
import networkx as nx 
22 
from networkx.generators.classic import empty_graph 
23 
from networkx.utils import discrete_sequence 
24 
from networkx.utils import weighted_choice 
25 
from networkx.utils import py_random_state 
26  
27 
__all__ = ['gn_graph', 'gnc_graph', 'gnr_graph', 'random_k_out_graph', 
28 
'scale_free_graph']

29  
30  
31 
@py_random_state(3) 
32 
def gn_graph(n, kernel=None, create_using=None, seed=None): 
33 
"""Returns the growing network (GN) digraph with `n` nodes.

34 

35 
The GN graph is built by adding nodes one at a time with a link to one

36 
previously added node. The target node for the link is chosen with

37 
probability based on degree. The default attachment kernel is a linear

38 
function of the degree of a node.

39 

40 
The graph is always a (directed) tree.

41 

42 
Parameters

43 


44 
n : int

45 
The number of nodes for the generated graph.

46 
kernel : function

47 
The attachment kernel.

48 
create_using : NetworkX graph constructor, optional (default DiGraph)

49 
Graph type to create. If graph instance, then cleared before populated.

50 
seed : integer, random_state, or None (default)

51 
Indicator of random number generation state.

52 
See :ref:`Randomness<randomness>`.

53 

54 
Examples

55 


56 
To create the undirected GN graph, use the :meth:`~DiGraph.to_directed`

57 
method::

58 

59 
>>> D = nx.gn_graph(10) # the GN graph

60 
>>> G = D.to_undirected() # the undirected version

61 

62 
To specify an attachment kernel, use the `kernel` keyword argument::

63 

64 
>>> D = nx.gn_graph(10, kernel=lambda x: x ** 1.5) # A_k = k^1.5

65 

66 
References

67 


68 
.. [1] P. L. Krapivsky and S. Redner,

69 
Organization of Growing Random Networks,

70 
Phys. Rev. E, 63, 066123, 2001.

71 
"""

72 
G = empty_graph(1, create_using, default=nx.DiGraph)

73 
if not G.is_directed(): 
74 
raise nx.NetworkXError("create_using must indicate a Directed Graph") 
75  
76 
if kernel is None: 
77 
def kernel(x): return x 
78  
79 
if n == 1: 
80 
return G

81  
82 
G.add_edge(1, 0) # get started 
83 
ds = [1, 1] # degree sequence 
84  
85 
for source in range(2, n): 
86 
# compute distribution from kernel and degree

87 
dist = [kernel(d) for d in ds] 
88 
# choose target from discrete distribution

89 
target = discrete_sequence(1, distribution=dist, seed=seed)[0] 
90 
G.add_edge(source, target) 
91 
ds.append(1) # the source has only one link (degree one) 
92 
ds[target] += 1 # add one to the target link degree 
93 
return G

94  
95  
96 
@py_random_state(3) 
97 
def gnr_graph(n, p, create_using=None, seed=None): 
98 
"""Returns the growing network with redirection (GNR) digraph with `n`

99 
nodes and redirection probability `p`.

100 

101 
The GNR graph is built by adding nodes one at a time with a link to one

102 
previously added node. The previous target node is chosen uniformly at

103 
random. With probabiliy `p` the link is instead "redirected" to the

104 
successor node of the target.

105 

106 
The graph is always a (directed) tree.

107 

108 
Parameters

109 


110 
n : int

111 
The number of nodes for the generated graph.

112 
p : float

113 
The redirection probability.

114 
create_using : NetworkX graph constructor, optional (default DiGraph)

115 
Graph type to create. If graph instance, then cleared before populated.

116 
seed : integer, random_state, or None (default)

117 
Indicator of random number generation state.

118 
See :ref:`Randomness<randomness>`.

119 

120 
Examples

121 


122 
To create the undirected GNR graph, use the :meth:`~DiGraph.to_directed`

123 
method::

124 

125 
>>> D = nx.gnr_graph(10, 0.5) # the GNR graph

126 
>>> G = D.to_undirected() # the undirected version

127 

128 
References

129 


130 
.. [1] P. L. Krapivsky and S. Redner,

131 
Organization of Growing Random Networks,

132 
Phys. Rev. E, 63, 066123, 2001.

133 
"""

134 
G = empty_graph(1, create_using, default=nx.DiGraph)

135 
if not G.is_directed(): 
136 
raise nx.NetworkXError("create_using must indicate a Directed Graph") 
137  
138 
if n == 1: 
139 
return G

140  
141 
for source in range(1, n): 
142 
target = seed.randrange(0, source)

143 
if seed.random() < p and target != 0: 
144 
target = next(G.successors(target))

145 
G.add_edge(source, target) 
146 
return G

147  
148  
149 
@py_random_state(2) 
150 
def gnc_graph(n, create_using=None, seed=None): 
151 
"""Returns the growing network with copying (GNC) digraph with `n` nodes.

152 

153 
The GNC graph is built by adding nodes one at a time with a link to one

154 
previously added node (chosen uniformly at random) and to all of that

155 
node's successors.

156 

157 
Parameters

158 


159 
n : int

160 
The number of nodes for the generated graph.

161 
create_using : NetworkX graph constructor, optional (default DiGraph)

162 
Graph type to create. If graph instance, then cleared before populated.

163 
seed : integer, random_state, or None (default)

164 
Indicator of random number generation state.

165 
See :ref:`Randomness<randomness>`.

166 

167 
References

168 


169 
.. [1] P. L. Krapivsky and S. Redner,

170 
Network Growth by Copying,

171 
Phys. Rev. E, 71, 036118, 2005k.},

172 
"""

173 
G = empty_graph(1, create_using, default=nx.DiGraph)

174 
if not G.is_directed(): 
175 
raise nx.NetworkXError("create_using must indicate a Directed Graph") 
176  
177 
if n == 1: 
178 
return G

179  
180 
for source in range(1, n): 
181 
target = seed.randrange(0, source)

182 
for succ in G.successors(target): 
183 
G.add_edge(source, succ) 
184 
G.add_edge(source, target) 
185 
return G

186  
187  
188 
@py_random_state(7) 
189 
def scale_free_graph(n, alpha=0.41, beta=0.54, gamma=0.05, delta_in=0.2, 
190 
delta_out=0, create_using=None, seed=None): 
191 
"""Returns a scalefree directed graph.

192 

193 
Parameters

194 


195 
n : integer

196 
Number of nodes in graph

197 
alpha : float

198 
Probability for adding a new node connected to an existing node

199 
chosen randomly according to the indegree distribution.

200 
beta : float

201 
Probability for adding an edge between two existing nodes.

202 
One existing node is chosen randomly according the indegree

203 
distribution and the other chosen randomly according to the outdegree

204 
distribution.

205 
gamma : float

206 
Probability for adding a new node connected to an existing node

207 
chosen randomly according to the outdegree distribution.

208 
delta_in : float

209 
Bias for choosing nodes from indegree distribution.

210 
delta_out : float

211 
Bias for choosing nodes from outdegree distribution.

212 
create_using : NetworkX graph constructor, optional

213 
The default is a MultiDiGraph 3cycle.

214 
If a graph instance, use it without clearing first.

215 
If a graph constructor, call it to construct an empty graph.

216 
seed : integer, random_state, or None (default)

217 
Indicator of random number generation state.

218 
See :ref:`Randomness<randomness>`.

219 

220 
Examples

221 


222 
Create a scalefree graph on one hundred nodes::

223 

224 
>>> G = nx.scale_free_graph(100)

225 

226 
Notes

227 


228 
The sum of `alpha`, `beta`, and `gamma` must be 1.

229 

230 
References

231 


232 
.. [1] B. Bollobás, C. Borgs, J. Chayes, and O. Riordan,

233 
Directed scalefree graphs,

234 
Proceedings of the fourteenth annual ACMSIAM Symposium on

235 
Discrete Algorithms, 132139, 2003.

236 
"""

237  
238 
def _choose_node(G, distribution, delta, psum): 
239 
cumsum = 0.0

240 
# normalization

241 
r = seed.random() 
242 
for n, d in distribution: 
243 
cumsum += (d + delta) / psum 
244 
if r < cumsum:

245 
break

246 
return n

247  
248 
if create_using is None or not hasattr(create_using, '_adj'): 
249 
# start with 3cycle

250 
G = nx.empty_graph(3, create_using, default=nx.MultiDiGraph)

251 
G.add_edges_from([(0, 1), (1, 2), (2, 0)]) 
252 
else:

253 
G = create_using 
254 
if not (G.is_directed() and G.is_multigraph()): 
255 
raise nx.NetworkXError("MultiDiGraph required in create_using") 
256  
257 
if alpha <= 0: 
258 
raise ValueError('alpha must be > 0.') 
259 
if beta <= 0: 
260 
raise ValueError('beta must be > 0.') 
261 
if gamma <= 0: 
262 
raise ValueError('gamma must be > 0.') 
263  
264 
if abs(alpha + beta + gamma  1.0) >= 1e9: 
265 
raise ValueError('alpha+beta+gamma must equal 1.') 
266  
267 
number_of_edges = G.number_of_edges() 
268 
while len(G) < n: 
269 
psum_in = number_of_edges + delta_in * len(G)

270 
psum_out = number_of_edges + delta_out * len(G)

271 
r = seed.random() 
272 
# random choice in alpha,beta,gamma ranges

273 
if r < alpha:

274 
# alpha

275 
# add new node v

276 
v = len(G)

277 
# choose w according to indegree and delta_in

278 
w = _choose_node(G, G.in_degree(), delta_in, psum_in) 
279 
elif r < alpha + beta:

280 
# beta

281 
# choose v according to outdegree and delta_out

282 
v = _choose_node(G, G.out_degree(), delta_out, psum_out) 
283 
# choose w according to indegree and delta_in

284 
w = _choose_node(G, G.in_degree(), delta_in, psum_in) 
285 
else:

286 
# gamma

287 
# choose v according to outdegree and delta_out

288 
v = _choose_node(G, G.out_degree(), delta_out, psum_out) 
289 
# add new node w

290 
w = len(G)

291 
G.add_edge(v, w) 
292 
number_of_edges += 1

293 
return G

294  
295  
296 
@py_random_state(4) 
297 
def random_uniform_k_out_graph(n, k, self_loops=True, with_replacement=True, 
298 
seed=None):

299 
"""Returns a random `k`out graph with uniform attachment.

300 

301 
A random `k`out graph with uniform attachment is a multidigraph

302 
generated by the following algorithm. For each node *u*, choose

303 
`k` nodes *v* uniformly at random (with replacement). Add a

304 
directed edge joining *u* to *v*.

305 

306 
Parameters

307 


308 
n : int

309 
The number of nodes in the returned graph.

310 

311 
k : int

312 
The outdegree of each node in the returned graph.

313 

314 
self_loops : bool

315 
If True, selfloops are allowed when generating the graph.

316 

317 
with_replacement : bool

318 
If True, neighbors are chosen with replacement and the

319 
returned graph will be a directed multigraph. Otherwise,

320 
neighbors are chosen without replacement and the returned graph

321 
will be a directed graph.

322 

323 
seed : integer, random_state, or None (default)

324 
Indicator of random number generation state.

325 
See :ref:`Randomness<randomness>`.

326 

327 
Returns

328 


329 
NetworkX graph

330 
A `k`outregular directed graph generated according to the

331 
above algorithm. It will be a multigraph if and only if

332 
`with_replacement` is True.

333 

334 
Raises

335 


336 
ValueError

337 
If `with_replacement` is False and `k` is greater than

338 
`n`.

339 

340 
See also

341 


342 
random_k_out_graph

343 

344 
Notes

345 


346 
The return digraph or multidigraph may not be strongly connected, or

347 
even weakly connected.

348 

349 
If `with_replacement` is True, this function is similar to

350 
:func:`random_k_out_graph`, if that function had parameter `alpha`

351 
set to positive infinity.

352 

353 
"""

354 
if with_replacement:

355 
create_using = nx.MultiDiGraph() 
356  
357 
def sample(v, nodes): 
358 
if not self_loops: 
359 
nodes = nodes  {v} 
360 
return (seed.choice(list(nodes)) for i in range(k)) 
361  
362 
else:

363 
create_using = nx.DiGraph() 
364  
365 
def sample(v, nodes): 
366 
if not self_loops: 
367 
nodes = nodes  {v} 
368 
return seed.sample(nodes, k)

369  
370 
G = nx.empty_graph(n, create_using) 
371 
nodes = set(G)

372 
for u in G: 
373 
G.add_edges_from((u, v) for v in sample(u, nodes)) 
374 
return G

375  
376  
377 
@py_random_state(4) 
378 
def random_k_out_graph(n, k, alpha, self_loops=True, seed=None): 
379 
"""Returns a random `k`out graph with preferential attachment.

380 

381 
A random `k`out graph with preferential attachment is a

382 
multidigraph generated by the following algorithm.

383 

384 
1. Begin with an empty digraph, and initially set each node to have

385 
weight `alpha`.

386 
2. Choose a node `u` with outdegree less than `k` uniformly at

387 
random.

388 
3. Choose a node `v` from with probability proportional to its

389 
weight.

390 
4. Add a directed edge from `u` to `v`, and increase the weight

391 
of `v` by one.

392 
5. If each node has outdegree `k`, halt, otherwise repeat from

393 
step 2.

394 

395 
For more information on this model of random graph, see [1].

396 

397 
Parameters

398 


399 
n : int

400 
The number of nodes in the returned graph.

401 

402 
k : int

403 
The outdegree of each node in the returned graph.

404 

405 
alpha : float

406 
A positive :class:`float` representing the initial weight of

407 
each vertex. A higher number means that in step 3 above, nodes

408 
will be chosen more like a true uniformly random sample, and a

409 
lower number means that nodes are more likely to be chosen as

410 
their indegree increases. If this parameter is not positive, a

411 
:exc:`ValueError` is raised.

412 

413 
self_loops : bool

414 
If True, selfloops are allowed when generating the graph.

415 

416 
seed : integer, random_state, or None (default)

417 
Indicator of random number generation state.

418 
See :ref:`Randomness<randomness>`.

419 

420 
Returns

421 


422 
:class:`~networkx.classes.MultiDiGraph`

423 
A `k`outregular multidigraph generated according to the above

424 
algorithm.

425 

426 
Raises

427 


428 
ValueError

429 
If `alpha` is not positive.

430 

431 
Notes

432 


433 
The returned multidigraph may not be strongly connected, or even

434 
weakly connected.

435 

436 
References

437 


438 
[1]: Peterson, Nicholas R., and Boris Pittel.

439 
"Distance between two random `k`out digraphs, with and without

440 
preferential attachment."

441 
arXiv preprint arXiv:1311.5961 (2013).

442 
<https://arxiv.org/abs/1311.5961>

443 

444 
"""

445 
if alpha < 0: 
446 
raise ValueError('alpha must be positive') 
447 
G = nx.empty_graph(n, create_using=nx.MultiDiGraph) 
448 
weights = Counter({v: alpha for v in G}) 
449 
for i in range(k * n): 
450 
u = seed.choice([v for v, d in G.out_degree() if d < k]) 
451 
# If selfloops are not allowed, make the source node `u` have

452 
# weight zero.

453 
if not self_loops: 
454 
adjustment = Counter({u: weights[u]}) 
455 
else:

456 
adjustment = Counter() 
457 
v = weighted_choice(weights  adjustment, seed=seed) 
458 
G.add_edge(u, v) 
459 
weights[v] += 1

460 
return G
