Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/link_analysis/tests/test_pagerank.py @ 0:4f3585e2f14b draft default tip
"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 random | |
2 | |
3 import networkx | |
4 import pytest | |
5 | |
6 numpy = pytest.importorskip("numpy") | |
7 scipy = pytest.importorskip("scipy") | |
8 | |
9 from networkx.testing import almost_equal | |
10 | |
11 # Example from | |
12 # A. Langville and C. Meyer, "A survey of eigenvector methods of web | |
13 # information retrieval." http://citeseer.ist.psu.edu/713792.html | |
14 | |
15 | |
16 class TestPageRank: | |
17 @classmethod | |
18 def setup_class(cls): | |
19 G = networkx.DiGraph() | |
20 edges = [ | |
21 (1, 2), | |
22 (1, 3), | |
23 # 2 is a dangling node | |
24 (3, 1), | |
25 (3, 2), | |
26 (3, 5), | |
27 (4, 5), | |
28 (4, 6), | |
29 (5, 4), | |
30 (5, 6), | |
31 (6, 4), | |
32 ] | |
33 G.add_edges_from(edges) | |
34 cls.G = G | |
35 cls.G.pagerank = dict( | |
36 zip( | |
37 sorted(G), | |
38 [ | |
39 0.03721197, | |
40 0.05395735, | |
41 0.04150565, | |
42 0.37508082, | |
43 0.20599833, | |
44 0.28624589, | |
45 ], | |
46 ) | |
47 ) | |
48 cls.dangling_node_index = 1 | |
49 cls.dangling_edges = {1: 2, 2: 3, 3: 0, 4: 0, 5: 0, 6: 0} | |
50 cls.G.dangling_pagerank = dict( | |
51 zip( | |
52 sorted(G), | |
53 [0.10844518, 0.18618601, 0.0710892, 0.2683668, 0.15919783, 0.20671497], | |
54 ) | |
55 ) | |
56 | |
57 def test_pagerank(self): | |
58 G = self.G | |
59 p = networkx.pagerank(G, alpha=0.9, tol=1.0e-08) | |
60 for n in G: | |
61 assert almost_equal(p[n], G.pagerank[n], places=4) | |
62 | |
63 nstart = {n: random.random() for n in G} | |
64 p = networkx.pagerank(G, alpha=0.9, tol=1.0e-08, nstart=nstart) | |
65 for n in G: | |
66 assert almost_equal(p[n], G.pagerank[n], places=4) | |
67 | |
68 def test_pagerank_max_iter(self): | |
69 with pytest.raises(networkx.PowerIterationFailedConvergence): | |
70 networkx.pagerank(self.G, max_iter=0) | |
71 | |
72 def test_numpy_pagerank(self): | |
73 G = self.G | |
74 p = networkx.pagerank_numpy(G, alpha=0.9) | |
75 for n in G: | |
76 assert almost_equal(p[n], G.pagerank[n], places=4) | |
77 personalize = {n: random.random() for n in G} | |
78 p = networkx.pagerank_numpy(G, alpha=0.9, personalization=personalize) | |
79 | |
80 def test_google_matrix(self): | |
81 G = self.G | |
82 M = networkx.google_matrix(G, alpha=0.9, nodelist=sorted(G)) | |
83 e, ev = numpy.linalg.eig(M.T) | |
84 p = numpy.array(ev[:, 0] / ev[:, 0].sum())[:, 0] | |
85 for (a, b) in zip(p, self.G.pagerank.values()): | |
86 assert almost_equal(a, b) | |
87 | |
88 def test_personalization(self): | |
89 G = networkx.complete_graph(4) | |
90 personalize = {0: 1, 1: 1, 2: 4, 3: 4} | |
91 answer = { | |
92 0: 0.23246732615667579, | |
93 1: 0.23246732615667579, | |
94 2: 0.267532673843324, | |
95 3: 0.2675326738433241, | |
96 } | |
97 p = networkx.pagerank(G, alpha=0.85, personalization=personalize) | |
98 for n in G: | |
99 assert almost_equal(p[n], answer[n], places=4) | |
100 | |
101 def test_zero_personalization_vector(self): | |
102 G = networkx.complete_graph(4) | |
103 personalize = {0: 0, 1: 0, 2: 0, 3: 0} | |
104 pytest.raises( | |
105 ZeroDivisionError, networkx.pagerank, G, personalization=personalize | |
106 ) | |
107 | |
108 def test_one_nonzero_personalization_value(self): | |
109 G = networkx.complete_graph(4) | |
110 personalize = {0: 0, 1: 0, 2: 0, 3: 1} | |
111 answer = { | |
112 0: 0.22077931820379187, | |
113 1: 0.22077931820379187, | |
114 2: 0.22077931820379187, | |
115 3: 0.3376620453886241, | |
116 } | |
117 p = networkx.pagerank(G, alpha=0.85, personalization=personalize) | |
118 for n in G: | |
119 assert almost_equal(p[n], answer[n], places=4) | |
120 | |
121 def test_incomplete_personalization(self): | |
122 G = networkx.complete_graph(4) | |
123 personalize = {3: 1} | |
124 answer = { | |
125 0: 0.22077931820379187, | |
126 1: 0.22077931820379187, | |
127 2: 0.22077931820379187, | |
128 3: 0.3376620453886241, | |
129 } | |
130 p = networkx.pagerank(G, alpha=0.85, personalization=personalize) | |
131 for n in G: | |
132 assert almost_equal(p[n], answer[n], places=4) | |
133 | |
134 def test_dangling_matrix(self): | |
135 """ | |
136 Tests that the google_matrix doesn't change except for the dangling | |
137 nodes. | |
138 """ | |
139 G = self.G | |
140 dangling = self.dangling_edges | |
141 dangling_sum = float(sum(dangling.values())) | |
142 M1 = networkx.google_matrix(G, personalization=dangling) | |
143 M2 = networkx.google_matrix(G, personalization=dangling, dangling=dangling) | |
144 for i in range(len(G)): | |
145 for j in range(len(G)): | |
146 if i == self.dangling_node_index and (j + 1) in dangling: | |
147 assert almost_equal( | |
148 M2[i, j], dangling[j + 1] / dangling_sum, places=4 | |
149 ) | |
150 else: | |
151 assert almost_equal(M2[i, j], M1[i, j], places=4) | |
152 | |
153 def test_dangling_pagerank(self): | |
154 pr = networkx.pagerank(self.G, dangling=self.dangling_edges) | |
155 for n in self.G: | |
156 assert almost_equal(pr[n], self.G.dangling_pagerank[n], places=4) | |
157 | |
158 def test_dangling_numpy_pagerank(self): | |
159 pr = networkx.pagerank_numpy(self.G, dangling=self.dangling_edges) | |
160 for n in self.G: | |
161 assert almost_equal(pr[n], self.G.dangling_pagerank[n], places=4) | |
162 | |
163 def test_empty(self): | |
164 G = networkx.Graph() | |
165 assert networkx.pagerank(G) == {} | |
166 assert networkx.pagerank_numpy(G) == {} | |
167 assert networkx.google_matrix(G).shape == (0, 0) | |
168 | |
169 | |
170 class TestPageRankScipy(TestPageRank): | |
171 def test_scipy_pagerank(self): | |
172 G = self.G | |
173 p = networkx.pagerank_scipy(G, alpha=0.9, tol=1.0e-08) | |
174 for n in G: | |
175 assert almost_equal(p[n], G.pagerank[n], places=4) | |
176 personalize = {n: random.random() for n in G} | |
177 p = networkx.pagerank_scipy( | |
178 G, alpha=0.9, tol=1.0e-08, personalization=personalize | |
179 ) | |
180 | |
181 nstart = {n: random.random() for n in G} | |
182 p = networkx.pagerank_scipy(G, alpha=0.9, tol=1.0e-08, nstart=nstart) | |
183 for n in G: | |
184 assert almost_equal(p[n], G.pagerank[n], places=4) | |
185 | |
186 def test_scipy_pagerank_max_iter(self): | |
187 with pytest.raises(networkx.PowerIterationFailedConvergence): | |
188 networkx.pagerank_scipy(self.G, max_iter=0) | |
189 | |
190 def test_dangling_scipy_pagerank(self): | |
191 pr = networkx.pagerank_scipy(self.G, dangling=self.dangling_edges) | |
192 for n in self.G: | |
193 assert almost_equal(pr[n], self.G.dangling_pagerank[n], places=4) | |
194 | |
195 def test_empty_scipy(self): | |
196 G = networkx.Graph() | |
197 assert networkx.pagerank_scipy(G) == {} |