author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal 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 ]
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
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}
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:
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}
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:
120
121 def test_incomplete_personalization(self):
122 G = networkx.complete_graph(4)
123 personalize = {3: 1}
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:
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()))
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) == {}