Mercurial > repos > shellac > sam_consensus_v3

comparison env/lib/python3.9/site-packages/networkx/algorithms/tests/test_link_prediction.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 import math
2
3 from functools import partial
4 import pytest
5
6 import networkx as nx
7
8
9 def _test_func(G, ebunch, expected, predict_func, **kwargs):
10 result = predict_func(G, ebunch, **kwargs)
11 exp_dict = {tuple(sorted([u, v])): score for u, v, score in expected}
12 res_dict = {tuple(sorted([u, v])): score for u, v, score in result}
13
14 assert len(exp_dict) == len(res_dict)
15 for p in exp_dict:
16 assert nx.testing.almost_equal(exp_dict[p], res_dict[p])
17
18
19 class TestResourceAllocationIndex:
20 @classmethod
21 def setup_class(cls):
22 cls.func = staticmethod(nx.resource_allocation_index)
23 cls.test = partial(_test_func, predict_func=cls.func)
24
25 def test_K5(self):
26 G = nx.complete_graph(5)
27 self.test(G, [(0, 1)], [(0, 1, 0.75)])
28
29 def test_P3(self):
30 G = nx.path_graph(3)
31 self.test(G, [(0, 2)], [(0, 2, 0.5)])
32
33 def test_S4(self):
34 G = nx.star_graph(4)
35 self.test(G, [(1, 2)], [(1, 2, 0.25)])
36
37 def test_notimplemented(self):
38 assert pytest.raises(
39 nx.NetworkXNotImplemented, self.func, nx.DiGraph([(0, 1), (1, 2)]), [(0, 2)]
40 )
41 assert pytest.raises(
42 nx.NetworkXNotImplemented,
43 self.func,
44 nx.MultiGraph([(0, 1), (1, 2)]),
45 [(0, 2)],
46 )
47 assert pytest.raises(
48 nx.NetworkXNotImplemented,
49 self.func,
50 nx.MultiDiGraph([(0, 1), (1, 2)]),
51 [(0, 2)],
52 )
53
54 def test_no_common_neighbor(self):
55 G = nx.Graph()
56 G.add_nodes_from([0, 1])
57 self.test(G, [(0, 1)], [(0, 1, 0)])
58
59 def test_equal_nodes(self):
60 G = nx.complete_graph(4)
61 self.test(G, [(0, 0)], [(0, 0, 1)])
62
63 def test_all_nonexistent_edges(self):
64 G = nx.Graph()
65 G.add_edges_from([(0, 1), (0, 2), (2, 3)])
66 self.test(G, None, [(0, 3, 0.5), (1, 2, 0.5), (1, 3, 0)])
67
68
69 class TestJaccardCoefficient:
70 @classmethod
71 def setup_class(cls):
72 cls.func = staticmethod(nx.jaccard_coefficient)
73 cls.test = partial(_test_func, predict_func=cls.func)
74
75 def test_K5(self):
76 G = nx.complete_graph(5)
77 self.test(G, [(0, 1)], [(0, 1, 0.6)])
78
79 def test_P4(self):
80 G = nx.path_graph(4)
81 self.test(G, [(0, 2)], [(0, 2, 0.5)])
82
83 def test_notimplemented(self):
84 assert pytest.raises(
85 nx.NetworkXNotImplemented, self.func, nx.DiGraph([(0, 1), (1, 2)]), [(0, 2)]
86 )
87 assert pytest.raises(
88 nx.NetworkXNotImplemented,
89 self.func,
90 nx.MultiGraph([(0, 1), (1, 2)]),
91 [(0, 2)],
92 )
93 assert pytest.raises(
94 nx.NetworkXNotImplemented,
95 self.func,
96 nx.MultiDiGraph([(0, 1), (1, 2)]),
97 [(0, 2)],
98 )
99
100 def test_no_common_neighbor(self):
101 G = nx.Graph()
102 G.add_edges_from([(0, 1), (2, 3)])
103 self.test(G, [(0, 2)], [(0, 2, 0)])
104
105 def test_isolated_nodes(self):
106 G = nx.Graph()
107 G.add_nodes_from([0, 1])
108 self.test(G, [(0, 1)], [(0, 1, 0)])
109
110 def test_all_nonexistent_edges(self):
111 G = nx.Graph()
112 G.add_edges_from([(0, 1), (0, 2), (2, 3)])
113 self.test(G, None, [(0, 3, 0.5), (1, 2, 0.5), (1, 3, 0)])
114
115
116 class TestAdamicAdarIndex:
117 @classmethod
118 def setup_class(cls):
119 cls.func = staticmethod(nx.adamic_adar_index)
120 cls.test = partial(_test_func, predict_func=cls.func)
121
122 def test_K5(self):
123 G = nx.complete_graph(5)
124 self.test(G, [(0, 1)], [(0, 1, 3 / math.log(4))])
125
126 def test_P3(self):
127 G = nx.path_graph(3)
128 self.test(G, [(0, 2)], [(0, 2, 1 / math.log(2))])
129
130 def test_S4(self):
131 G = nx.star_graph(4)
132 self.test(G, [(1, 2)], [(1, 2, 1 / math.log(4))])
133
134 def test_notimplemented(self):
135 assert pytest.raises(
136 nx.NetworkXNotImplemented, self.func, nx.DiGraph([(0, 1), (1, 2)]), [(0, 2)]
137 )
138 assert pytest.raises(
139 nx.NetworkXNotImplemented,
140 self.func,
141 nx.MultiGraph([(0, 1), (1, 2)]),
142 [(0, 2)],
143 )
144 assert pytest.raises(
145 nx.NetworkXNotImplemented,
146 self.func,
147 nx.MultiDiGraph([(0, 1), (1, 2)]),
148 [(0, 2)],
149 )
150
151 def test_no_common_neighbor(self):
152 G = nx.Graph()
153 G.add_nodes_from([0, 1])
154 self.test(G, [(0, 1)], [(0, 1, 0)])
155
156 def test_equal_nodes(self):
157 G = nx.complete_graph(4)
158 self.test(G, [(0, 0)], [(0, 0, 3 / math.log(3))])
159
160 def test_all_nonexistent_edges(self):
161 G = nx.Graph()
162 G.add_edges_from([(0, 1), (0, 2), (2, 3)])
163 self.test(
164 G, None, [(0, 3, 1 / math.log(2)), (1, 2, 1 / math.log(2)), (1, 3, 0)]
165 )
166
167
168 class TestPreferentialAttachment:
169 @classmethod
170 def setup_class(cls):
171 cls.func = staticmethod(nx.preferential_attachment)
172 cls.test = partial(_test_func, predict_func=cls.func)
173
174 def test_K5(self):
175 G = nx.complete_graph(5)
176 self.test(G, [(0, 1)], [(0, 1, 16)])
177
178 def test_P3(self):
179 G = nx.path_graph(3)
180 self.test(G, [(0, 1)], [(0, 1, 2)])
181
182 def test_S4(self):
183 G = nx.star_graph(4)
184 self.test(G, [(0, 2)], [(0, 2, 4)])
185
186 def test_notimplemented(self):
187 assert pytest.raises(
188 nx.NetworkXNotImplemented, self.func, nx.DiGraph([(0, 1), (1, 2)]), [(0, 2)]
189 )
190 assert pytest.raises(
191 nx.NetworkXNotImplemented,
192 self.func,
193 nx.MultiGraph([(0, 1), (1, 2)]),
194 [(0, 2)],
195 )
196 assert pytest.raises(
197 nx.NetworkXNotImplemented,
198 self.func,
199 nx.MultiDiGraph([(0, 1), (1, 2)]),
200 [(0, 2)],
201 )
202
203 def test_zero_degrees(self):
204 G = nx.Graph()
205 G.add_nodes_from([0, 1])
206 self.test(G, [(0, 1)], [(0, 1, 0)])
207
208 def test_all_nonexistent_edges(self):
209 G = nx.Graph()
210 G.add_edges_from([(0, 1), (0, 2), (2, 3)])
211 self.test(G, None, [(0, 3, 2), (1, 2, 2), (1, 3, 1)])
212
213
214 class TestCNSoundarajanHopcroft:
215 @classmethod
216 def setup_class(cls):
217 cls.func = staticmethod(nx.cn_soundarajan_hopcroft)
218 cls.test = partial(_test_func, predict_func=cls.func, community="community")
219
220 def test_K5(self):
221 G = nx.complete_graph(5)
222 G.nodes[0]["community"] = 0
223 G.nodes[1]["community"] = 0
224 G.nodes[2]["community"] = 0
225 G.nodes[3]["community"] = 0
226 G.nodes[4]["community"] = 1
227 self.test(G, [(0, 1)], [(0, 1, 5)])
228
229 def test_P3(self):
230 G = nx.path_graph(3)
231 G.nodes[0]["community"] = 0
232 G.nodes[1]["community"] = 1
233 G.nodes[2]["community"] = 0
234 self.test(G, [(0, 2)], [(0, 2, 1)])
235
236 def test_S4(self):
237 G = nx.star_graph(4)
238 G.nodes[0]["community"] = 1
239 G.nodes[1]["community"] = 1
240 G.nodes[2]["community"] = 1
241 G.nodes[3]["community"] = 0
242 G.nodes[4]["community"] = 0
243 self.test(G, [(1, 2)], [(1, 2, 2)])
244
245 def test_notimplemented(self):
246 G = nx.DiGraph([(0, 1), (1, 2)])
247 G.add_nodes_from([0, 1, 2], community=0)
248 assert pytest.raises(nx.NetworkXNotImplemented, self.func, G, [(0, 2)])
249 G = nx.MultiGraph([(0, 1), (1, 2)])
250 G.add_nodes_from([0, 1, 2], community=0)
251 assert pytest.raises(nx.NetworkXNotImplemented, self.func, G, [(0, 2)])
252 G = nx.MultiDiGraph([(0, 1), (1, 2)])
253 G.add_nodes_from([0, 1, 2], community=0)
254 assert pytest.raises(nx.NetworkXNotImplemented, self.func, G, [(0, 2)])
255
256 def test_no_common_neighbor(self):
257 G = nx.Graph()
258 G.add_nodes_from([0, 1])
259 G.nodes[0]["community"] = 0
260 G.nodes[1]["community"] = 0
261 self.test(G, [(0, 1)], [(0, 1, 0)])
262
263 def test_equal_nodes(self):
264 G = nx.complete_graph(3)
265 G.nodes[0]["community"] = 0
266 G.nodes[1]["community"] = 0
267 G.nodes[2]["community"] = 0
268 self.test(G, [(0, 0)], [(0, 0, 4)])
269
270 def test_different_community(self):
271 G = nx.Graph()
272 G.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 3)])
273 G.nodes[0]["community"] = 0
274 G.nodes[1]["community"] = 0
275 G.nodes[2]["community"] = 0
276 G.nodes[3]["community"] = 1
277 self.test(G, [(0, 3)], [(0, 3, 2)])
278
279 def test_no_community_information(self):
280 G = nx.complete_graph(5)
281 assert pytest.raises(nx.NetworkXAlgorithmError, list, self.func(G, [(0, 1)]))
282
283 def test_insufficient_community_information(self):
284 G = nx.Graph()
285 G.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 3)])
286 G.nodes[0]["community"] = 0
287 G.nodes[1]["community"] = 0
288 G.nodes[3]["community"] = 0
289 assert pytest.raises(nx.NetworkXAlgorithmError, list, self.func(G, [(0, 3)]))
290
291 def test_sufficient_community_information(self):
292 G = nx.Graph()
293 G.add_edges_from([(0, 1), (1, 2), (1, 3), (2, 4), (3, 4), (4, 5)])
294 G.nodes[1]["community"] = 0
295 G.nodes[2]["community"] = 0
296 G.nodes[3]["community"] = 0
297 G.nodes[4]["community"] = 0
298 self.test(G, [(1, 4)], [(1, 4, 4)])
299
300 def test_custom_community_attribute_name(self):
301 G = nx.Graph()
302 G.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 3)])
303 G.nodes[0]["cmty"] = 0
304 G.nodes[1]["cmty"] = 0
305 G.nodes[2]["cmty"] = 0
306 G.nodes[3]["cmty"] = 1
307 self.test(G, [(0, 3)], [(0, 3, 2)], community="cmty")
308
309 def test_all_nonexistent_edges(self):
310 G = nx.Graph()
311 G.add_edges_from([(0, 1), (0, 2), (2, 3)])
312 G.nodes[0]["community"] = 0
313 G.nodes[1]["community"] = 1
314 G.nodes[2]["community"] = 0
315 G.nodes[3]["community"] = 0
316 self.test(G, None, [(0, 3, 2), (1, 2, 1), (1, 3, 0)])
317
318
319 class TestRAIndexSoundarajanHopcroft:
320 @classmethod
321 def setup_class(cls):
322 cls.func = staticmethod(nx.ra_index_soundarajan_hopcroft)
323 cls.test = partial(_test_func, predict_func=cls.func, community="community")
324
325 def test_K5(self):
326 G = nx.complete_graph(5)
327 G.nodes[0]["community"] = 0
328 G.nodes[1]["community"] = 0
329 G.nodes[2]["community"] = 0
330 G.nodes[3]["community"] = 0
331 G.nodes[4]["community"] = 1
332 self.test(G, [(0, 1)], [(0, 1, 0.5)])
333
334 def test_P3(self):
335 G = nx.path_graph(3)
336 G.nodes[0]["community"] = 0
337 G.nodes[1]["community"] = 1
338 G.nodes[2]["community"] = 0
339 self.test(G, [(0, 2)], [(0, 2, 0)])
340
341 def test_S4(self):
342 G = nx.star_graph(4)
343 G.nodes[0]["community"] = 1
344 G.nodes[1]["community"] = 1
345 G.nodes[2]["community"] = 1
346 G.nodes[3]["community"] = 0
347 G.nodes[4]["community"] = 0
348 self.test(G, [(1, 2)], [(1, 2, 0.25)])
349
350 def test_notimplemented(self):
351 G = nx.DiGraph([(0, 1), (1, 2)])
352 G.add_nodes_from([0, 1, 2], community=0)
353 assert pytest.raises(nx.NetworkXNotImplemented, self.func, G, [(0, 2)])
354 G = nx.MultiGraph([(0, 1), (1, 2)])
355 G.add_nodes_from([0, 1, 2], community=0)
356 assert pytest.raises(nx.NetworkXNotImplemented, self.func, G, [(0, 2)])
357 G = nx.MultiDiGraph([(0, 1), (1, 2)])
358 G.add_nodes_from([0, 1, 2], community=0)
359 assert pytest.raises(nx.NetworkXNotImplemented, self.func, G, [(0, 2)])
360
361 def test_no_common_neighbor(self):
362 G = nx.Graph()
363 G.add_nodes_from([0, 1])
364 G.nodes[0]["community"] = 0
365 G.nodes[1]["community"] = 0
366 self.test(G, [(0, 1)], [(0, 1, 0)])
367
368 def test_equal_nodes(self):
369 G = nx.complete_graph(3)
370 G.nodes[0]["community"] = 0
371 G.nodes[1]["community"] = 0
372 G.nodes[2]["community"] = 0
373 self.test(G, [(0, 0)], [(0, 0, 1)])
374
375 def test_different_community(self):
376 G = nx.Graph()
377 G.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 3)])
378 G.nodes[0]["community"] = 0
379 G.nodes[1]["community"] = 0
380 G.nodes[2]["community"] = 0
381 G.nodes[3]["community"] = 1
382 self.test(G, [(0, 3)], [(0, 3, 0)])
383
384 def test_no_community_information(self):
385 G = nx.complete_graph(5)
386 assert pytest.raises(nx.NetworkXAlgorithmError, list, self.func(G, [(0, 1)]))
387
388 def test_insufficient_community_information(self):
389 G = nx.Graph()
390 G.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 3)])
391 G.nodes[0]["community"] = 0
392 G.nodes[1]["community"] = 0
393 G.nodes[3]["community"] = 0
394 assert pytest.raises(nx.NetworkXAlgorithmError, list, self.func(G, [(0, 3)]))
395
396 def test_sufficient_community_information(self):
397 G = nx.Graph()
398 G.add_edges_from([(0, 1), (1, 2), (1, 3), (2, 4), (3, 4), (4, 5)])
399 G.nodes[1]["community"] = 0
400 G.nodes[2]["community"] = 0
401 G.nodes[3]["community"] = 0
402 G.nodes[4]["community"] = 0
403 self.test(G, [(1, 4)], [(1, 4, 1)])
404
405 def test_custom_community_attribute_name(self):
406 G = nx.Graph()
407 G.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 3)])
408 G.nodes[0]["cmty"] = 0
409 G.nodes[1]["cmty"] = 0
410 G.nodes[2]["cmty"] = 0
411 G.nodes[3]["cmty"] = 1
412 self.test(G, [(0, 3)], [(0, 3, 0)], community="cmty")
413
414 def test_all_nonexistent_edges(self):
415 G = nx.Graph()
416 G.add_edges_from([(0, 1), (0, 2), (2, 3)])
417 G.nodes[0]["community"] = 0
418 G.nodes[1]["community"] = 1
419 G.nodes[2]["community"] = 0
420 G.nodes[3]["community"] = 0
421 self.test(G, None, [(0, 3, 0.5), (1, 2, 0), (1, 3, 0)])
422
423
424 class TestWithinInterCluster:
425 @classmethod
426 def setup_class(cls):
427 cls.delta = 0.001
428 cls.func = staticmethod(nx.within_inter_cluster)
429 cls.test = partial(
430 _test_func, predict_func=cls.func, delta=cls.delta, community="community"
431 )
432
433 def test_K5(self):
434 G = nx.complete_graph(5)
435 G.nodes[0]["community"] = 0
436 G.nodes[1]["community"] = 0
437 G.nodes[2]["community"] = 0
438 G.nodes[3]["community"] = 0
439 G.nodes[4]["community"] = 1
440 self.test(G, [(0, 1)], [(0, 1, 2 / (1 + self.delta))])
441
442 def test_P3(self):
443 G = nx.path_graph(3)
444 G.nodes[0]["community"] = 0
445 G.nodes[1]["community"] = 1
446 G.nodes[2]["community"] = 0
447 self.test(G, [(0, 2)], [(0, 2, 0)])
448
449 def test_S4(self):
450 G = nx.star_graph(4)
451 G.nodes[0]["community"] = 1
452 G.nodes[1]["community"] = 1
453 G.nodes[2]["community"] = 1
454 G.nodes[3]["community"] = 0
455 G.nodes[4]["community"] = 0
456 self.test(G, [(1, 2)], [(1, 2, 1 / self.delta)])
457
458 def test_notimplemented(self):
459 G = nx.DiGraph([(0, 1), (1, 2)])
460 G.add_nodes_from([0, 1, 2], community=0)
461 assert pytest.raises(nx.NetworkXNotImplemented, self.func, G, [(0, 2)])
462 G = nx.MultiGraph([(0, 1), (1, 2)])
463 G.add_nodes_from([0, 1, 2], community=0)
464 assert pytest.raises(nx.NetworkXNotImplemented, self.func, G, [(0, 2)])
465 G = nx.MultiDiGraph([(0, 1), (1, 2)])
466 G.add_nodes_from([0, 1, 2], community=0)
467 assert pytest.raises(nx.NetworkXNotImplemented, self.func, G, [(0, 2)])
468
469 def test_no_common_neighbor(self):
470 G = nx.Graph()
471 G.add_nodes_from([0, 1])
472 G.nodes[0]["community"] = 0
473 G.nodes[1]["community"] = 0
474 self.test(G, [(0, 1)], [(0, 1, 0)])
475
476 def test_equal_nodes(self):
477 G = nx.complete_graph(3)
478 G.nodes[0]["community"] = 0
479 G.nodes[1]["community"] = 0
480 G.nodes[2]["community"] = 0
481 self.test(G, [(0, 0)], [(0, 0, 2 / self.delta)])
482
483 def test_different_community(self):
484 G = nx.Graph()
485 G.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 3)])
486 G.nodes[0]["community"] = 0
487 G.nodes[1]["community"] = 0
488 G.nodes[2]["community"] = 0
489 G.nodes[3]["community"] = 1
490 self.test(G, [(0, 3)], [(0, 3, 0)])
491
492 def test_no_inter_cluster_common_neighbor(self):
493 G = nx.complete_graph(4)
494 G.nodes[0]["community"] = 0
495 G.nodes[1]["community"] = 0
496 G.nodes[2]["community"] = 0
497 G.nodes[3]["community"] = 0
498 self.test(G, [(0, 3)], [(0, 3, 2 / self.delta)])
499
500 def test_no_community_information(self):
501 G = nx.complete_graph(5)
502 assert pytest.raises(nx.NetworkXAlgorithmError, list, self.func(G, [(0, 1)]))
503
504 def test_insufficient_community_information(self):
505 G = nx.Graph()
506 G.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 3)])
507 G.nodes[0]["community"] = 0
508 G.nodes[1]["community"] = 0
509 G.nodes[3]["community"] = 0
510 assert pytest.raises(nx.NetworkXAlgorithmError, list, self.func(G, [(0, 3)]))
511
512 def test_sufficient_community_information(self):
513 G = nx.Graph()
514 G.add_edges_from([(0, 1), (1, 2), (1, 3), (2, 4), (3, 4), (4, 5)])
515 G.nodes[1]["community"] = 0
516 G.nodes[2]["community"] = 0
517 G.nodes[3]["community"] = 0
518 G.nodes[4]["community"] = 0
519 self.test(G, [(1, 4)], [(1, 4, 2 / self.delta)])
520
521 def test_invalid_delta(self):
522 G = nx.complete_graph(3)
523 G.add_nodes_from([0, 1, 2], community=0)
524 assert pytest.raises(nx.NetworkXAlgorithmError, self.func, G, [(0, 1)], 0)
525 assert pytest.raises(nx.NetworkXAlgorithmError, self.func, G, [(0, 1)], -0.5)
526
527 def test_custom_community_attribute_name(self):
528 G = nx.complete_graph(4)
529 G.nodes[0]["cmty"] = 0
530 G.nodes[1]["cmty"] = 0
531 G.nodes[2]["cmty"] = 0
532 G.nodes[3]["cmty"] = 0
533 self.test(G, [(0, 3)], [(0, 3, 2 / self.delta)], community="cmty")
534
535 def test_all_nonexistent_edges(self):
536 G = nx.Graph()
537 G.add_edges_from([(0, 1), (0, 2), (2, 3)])
538 G.nodes[0]["community"] = 0
539 G.nodes[1]["community"] = 1
540 G.nodes[2]["community"] = 0
541 G.nodes[3]["community"] = 0
542 self.test(G, None, [(0, 3, 1 / self.delta), (1, 2, 0), (1, 3, 0)])