Mercurial > repos > shellac > sam_consensus_v3

comparison env/lib/python3.9/site-packages/networkx/generators/internet_as_graphs.py @ 0:4f3585e2f14b draft default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author shellac
date Mon, 22 Mar 2021 18:12:50 +0000
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:4f3585e2f14b
1 """Generates graphs resembling the Internet Autonomous System network"""
2
3 import networkx as nx
4 from networkx.utils import py_random_state
5
6 __all__ = ["random_internet_as_graph"]
7
8
9 def uniform_int_from_avg(a, m, seed):
10 """ Pick a random integer with uniform probability.
11
12 Returns a random integer uniformly taken from a distribution with
13 minimum value 'a' and average value 'm', X~U(a,b), E[X]=m, X in N where
14 b = 2*m - a.
15
16 Notes
17 -----
18 p = (b-floor(b))/2
19 X = X1 + X2; X1~U(a,floor(b)), X2~B(p)
20 E[X] = E[X1] + E[X2] = (floor(b)+a)/2 + (b-floor(b))/2 = (b+a)/2 = m
21 """
22
23 from math import floor
24
25 assert m >= a
26 b = 2 * m - a
27 p = (b - floor(b)) / 2
28 X1 = int(round(seed.random() * (floor(b) - a) + a))
29 if seed.random() < p:
30 X2 = 1
31 else:
32 X2 = 0
33 return X1 + X2
34
35
36 def choose_pref_attach(degs, seed):
37 """ Pick a random value, with a probability given by its weight.
38
39 Returns a random choice among degs keys, each of which has a
40 probability proportional to the corresponding dictionary value.
41
42 Parameters
43 ----------
44 degs: dictionary
45 It contains the possible values (keys) and the corresponding
46 probabilities (values)
47 seed: random state
48
49 Returns
50 -------
51 v: object
52 A key of degs or None if degs is empty
53 """
54
55 if len(degs) == 0:
56 return None
57 s = sum(degs.values())
58 if s == 0:
59 return seed.choice(list(degs.keys()))
60 v = seed.random() * s
61
62 nodes = list(degs.keys())
63 i = 0
64 acc = degs[nodes[i]]
65 while v > acc:
66 i += 1
67 acc += degs[nodes[i]]
68 return nodes[i]
69
70
71 class AS_graph_generator:
72 """ Generates random internet AS graphs.
73 """
74
75 def __init__(self, n, seed):
76 """ Initializes variables. Immediate numbers are taken from [1].
77
78 Parameters
79 ----------
80 n: integer
81 Number of graph nodes
82 seed: random state
83 Indicator of random number generation state.
84 See :ref:`Randomness<randomness>`.
85
86 Returns
87 -------
88 GG: AS_graph_generator object
89
90 References
91 ----------
92 [1] A. Elmokashfi, A. Kvalbein and C. Dovrolis, "On the Scalability of
93 BGP: The Role of Topology Growth," in IEEE Journal on Selected Areas
94 in Communications, vol. 28, no. 8, pp. 1250-1261, October 2010.
95 """
96
97 self.seed = seed
98 self.n_t = min(n, int(round(self.seed.random() * 2 + 4))) # num of T nodes
99 self.n_m = int(round(0.15 * n)) # number of M nodes
100 self.n_cp = int(round(0.05 * n)) # number of CP nodes
101 self.n_c = max(0, n - self.n_t - self.n_m - self.n_cp) # number of C nodes
102
103 self.d_m = 2 + (2.5 * n) / 10000 # average multihoming degree for M nodes
104 self.d_cp = 2 + (1.5 * n) / 10000 # avg multihoming degree for CP nodes
105 self.d_c = 1 + (5 * n) / 100000 # average multihoming degree for C nodes
106
107 self.p_m_m = 1 + (2 * n) / 10000 # avg num of peer edges between M and M
108 self.p_cp_m = 0.2 + (2 * n) / 10000 # avg num of peer edges between CP, M
109 self.p_cp_cp = 0.05 + (2 * n) / 100000 # avg num of peer edges btwn CP, CP
110
111 self.t_m = 0.375 # probability M's provider is T
112 self.t_cp = 0.375 # probability CP's provider is T
113 self.t_c = 0.125 # probability C's provider is T
114
115 def t_graph(self):
116 """ Generates the core mesh network of tier one nodes of a AS graph.
117
118 Returns
119 -------
120 G: Networkx Graph
121 Core network
122 """
123
124 self.G = nx.Graph()
125 for i in range(self.n_t):
126 self.G.add_node(i, type="T")
127 for r in self.regions:
128 self.regions[r].add(i)
129 for j in self.G.nodes():
130 if i != j:
131 self.add_edge(i, j, "peer")
132 self.customers[i] = set()
133 self.providers[i] = set()
134 return self.G
135
136 def add_edge(self, i, j, kind):
137 if kind == "transit":
138 customer = str(i)
139 else:
140 customer = "none"
141 self.G.add_edge(i, j, type=kind, customer=customer)
142
143 def choose_peer_pref_attach(self, node_list):
144 """ Pick a node with a probability weighted by its peer degree.
145
146 Pick a node from node_list with preferential attachment
147 computed only on their peer degree
148 """
149
150 d = {}
151 for n in node_list:
152 d[n] = self.G.nodes[n]["peers"]
153 return choose_pref_attach(d, self.seed)
154
155 def choose_node_pref_attach(self, node_list):
156 """ Pick a node with a probability weighted by its degree.
157
158 Pick a node from node_list with preferential attachment
159 computed on their degree
160 """
161
162 degs = dict(self.G.degree(node_list))
163 return choose_pref_attach(degs, self.seed)
164
165 def add_customer(self, i, j):
166 """ Keep the dictionaries 'customers' and 'providers' consistent.
167 """
168
169 self.customers[j].add(i)
170 self.providers[i].add(j)
171 for z in self.providers[j]:
172 self.customers[z].add(i)
173 self.providers[i].add(z)
174
175 def add_node(self, i, kind, reg2prob, avg_deg, t_edge_prob):
176 """ Add a node and its customer transit edges to the graph.
177
178 Parameters
179 ----------
180 i: object
181 Identifier of the new node
182 kind: string
183 Type of the new node. Options are: 'M' for middle node, 'CP' for
184 content provider and 'C' for customer.
185 reg2prob: float
186 Probability the new node can be in two different regions.
187 avg_deg: float
188 Average number of transit nodes of which node i is customer.
189 t_edge_prob: float
190 Probability node i establish a customer transit edge with a tier
191 one (T) node
192
193 Returns
194 -------
195 i: object
196 Identifier of the new node
197 """
198
199 regs = 1 # regions in which node resides
200 if self.seed.random() < reg2prob: # node is in two regions
201 regs = 2
202 node_options = set()
203
204 self.G.add_node(i, type=kind, peers=0)
205 self.customers[i] = set()
206 self.providers[i] = set()
207 self.nodes[kind].add(i)
208 for r in self.seed.sample(list(self.regions), regs):
209 node_options = node_options.union(self.regions[r])
210 self.regions[r].add(i)
211
212 edge_num = uniform_int_from_avg(1, avg_deg, self.seed)
213
214 t_options = node_options.intersection(self.nodes["T"])
215 m_options = node_options.intersection(self.nodes["M"])
216 if i in m_options:
217 m_options.remove(i)
218 d = 0
219 while d < edge_num and (len(t_options) > 0 or len(m_options) > 0):
220 if len(m_options) == 0 or (
221 len(t_options) > 0 and self.seed.random() < t_edge_prob
222 ): # add edge to a T node
223 j = self.choose_node_pref_attach(t_options)
224 t_options.remove(j)
225 else:
226 j = self.choose_node_pref_attach(m_options)
227 m_options.remove(j)
228 self.add_edge(i, j, "transit")
229 self.add_customer(i, j)
230 d += 1
231
232 return i
233
234 def add_m_peering_link(self, m, to_kind):
235 """ Add a peering link between two middle tier (M) nodes.
236
237 Target node j is drawn considering a preferential attachment based on
238 other M node peering degree.
239
240 Parameters
241 ----------
242 m: object
243 Node identifier
244 to_kind: string
245 type for target node j (must be always M)
246
247 Returns
248 -------
249 success: boolean
250 """
251
252 # candidates are of type 'M' and are not customers of m
253 node_options = self.nodes["M"].difference(self.customers[m])
254 # candidates are not providers of m
255 node_options = node_options.difference(self.providers[m])
256 # remove self
257 if m in node_options:
258 node_options.remove(m)
259
260 # remove candidates we are already connected to
261 for j in self.G.neighbors(m):
262 if j in node_options:
263 node_options.remove(j)
264
265 if len(node_options) > 0:
266 j = self.choose_peer_pref_attach(node_options)
267 self.add_edge(m, j, "peer")
268 self.G.nodes[m]["peers"] += 1
269 self.G.nodes[j]["peers"] += 1
270 return True
271 else:
272 return False
273
274 def add_cp_peering_link(self, cp, to_kind):
275 """ Add a peering link to a content provider (CP) node.
276
277 Target node j can be CP or M and it is drawn uniformely among the nodes
278 belonging to the same region as cp.
279
280 Parameters
281 ----------
282 cp: object
283 Node identifier
284 to_kind: string
285 type for target node j (must be M or CP)
286
287 Returns
288 -------
289 success: boolean
290 """
291
292 node_options = set()
293 for r in self.regions: # options include nodes in the same region(s)
294 if cp in self.regions[r]:
295 node_options = node_options.union(self.regions[r])
296
297 # options are restricted to the indicated kind ('M' or 'CP')
298 node_options = self.nodes[to_kind].intersection(node_options)
299
300 # remove self
301 if cp in node_options:
302 node_options.remove(cp)
303
304 # remove nodes that are cp's providers
305 node_options = node_options.difference(self.providers[cp])
306
307 # remove nodes we are already connected to
308 for j in self.G.neighbors(cp):
309 if j in node_options:
310 node_options.remove(j)
311
312 if len(node_options) > 0:
313 j = self.seed.sample(node_options, 1)[0]
314 self.add_edge(cp, j, "peer")
315 self.G.nodes[cp]["peers"] += 1
316 self.G.nodes[j]["peers"] += 1
317 return True
318 else:
319 return False
320
321 def graph_regions(self, rn):
322 """ Initializes AS network regions.
323
324 Parameters
325 ----------
326 rn: integer
327 Number of regions
328 """
329
330 self.regions = {}
331 for i in range(rn):
332 self.regions["REG" + str(i)] = set()
333
334 def add_peering_links(self, from_kind, to_kind):
335 """ Utility function to add peering links among node groups.
336 """
337 peer_link_method = None
338 if from_kind == "M":
339 peer_link_method = self.add_m_peering_link
340 m = self.p_m_m
341 if from_kind == "CP":
342 peer_link_method = self.add_cp_peering_link
343 if to_kind == "M":
344 m = self.p_cp_m
345 else:
346 m = self.p_cp_cp
347
348 for i in self.nodes[from_kind]:
349 num = uniform_int_from_avg(0, m, self.seed)
350 for _ in range(num):
351 peer_link_method(i, to_kind)
352
353 def generate(self):
354 """ Generates a random AS network graph as described in [1].
355
356 Returns
357 -------
358 G: Graph object
359
360 Notes
361 -----
362 The process steps are the following: first we create the core network
363 of tier one nodes, then we add the middle tier (M), the content
364 provider (CP) and the customer (C) nodes along with their transit edges
365 (link i,j means i is customer of j). Finally we add peering links
366 between M nodes, between M and CP nodes and between CP node couples.
367 For a detailed description of the algorithm, please refer to [1].
368
369 References
370 ----------
371 [1] A. Elmokashfi, A. Kvalbein and C. Dovrolis, "On the Scalability of
372 BGP: The Role of Topology Growth," in IEEE Journal on Selected Areas
373 in Communications, vol. 28, no. 8, pp. 1250-1261, October 2010.
374 """
375
376 self.graph_regions(5)
377 self.customers = {}
378 self.providers = {}
379 self.nodes = {"T": set(), "M": set(), "CP": set(), "C": set()}
380
381 self.t_graph()
382 self.nodes["T"] = set(list(self.G.nodes()))
383
384 i = len(self.nodes["T"])
385 for _ in range(self.n_m):
386 self.nodes["M"].add(self.add_node(i, "M", 0.2, self.d_m, self.t_m))
387 i += 1
388 for _ in range(self.n_cp):
389 self.nodes["CP"].add(self.add_node(i, "CP", 0.05, self.d_cp, self.t_cp))
390 i += 1
391 for _ in range(self.n_c):
392 self.nodes["C"].add(self.add_node(i, "C", 0, self.d_c, self.t_c))
393 i += 1
394
395 self.add_peering_links("M", "M")
396 self.add_peering_links("CP", "M")
397 self.add_peering_links("CP", "CP")
398
399 return self.G
400
401
402 @py_random_state(1)
403 def random_internet_as_graph(n, seed=None):
404 """ Generates a random undirected graph resembling the Internet AS network
405
406 Parameters
407 ----------
408 n: integer in [1000, 10000]
409 Number of graph nodes
410 seed : integer, random_state, or None (default)
411 Indicator of random number generation state.
412 See :ref:`Randomness<randomness>`.
413
414 Returns
415 -------
416 G: Networkx Graph object
417 A randomly generated undirected graph
418
419 Notes
420 -----
421 This algorithm returns an undirected graph resembling the Internet
422 Autonomous System (AS) network, it uses the approach by Elmokashfi et al.
423 [1] and it grants the properties described in the related paper [1].
424
425 Each node models an autonomous system, with an attribute 'type' specifying
426 its kind; tier-1 (T), mid-level (M), customer (C) or content-provider (CP).
427 Each edge models an ADV communication link (hence, bidirectional) with
428 attributes:
429 - type: transit|peer, the kind of commercial agreement between nodes;
430 - customer: <node id>, the identifier of the node acting as customer
431 ('none' if type is peer).
432
433 References
434 ----------
435 [1] A. Elmokashfi, A. Kvalbein and C. Dovrolis, "On the Scalability of
436 BGP: The Role of Topology Growth," in IEEE Journal on Selected Areas
437 in Communications, vol. 28, no. 8, pp. 1250-1261, October 2010.
438 """
439
440 GG = AS_graph_generator(n, seed)
441 G = GG.generate()
442 return G