Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / link_analysis / tests / test_pagerank.py @ 5cef0f13

History | View | Annotate | Download (6.37 KB)

1
#!/usr/bin/env python
2
import random
3

    
4
import networkx
5
from nose.tools import *
6
from nose import SkipTest
7

    
8
# Example from
9
# A. Langville and C. Meyer, "A survey of eigenvector methods of web
10
# information retrieval."  http://citeseer.ist.psu.edu/713792.html
11

    
12

    
13
class TestPageRank(object):
14

    
15
    @classmethod
16
    def setupClass(cls):
17
        global numpy
18
        try:
19
            import numpy
20
        except ImportError:
21
            raise SkipTest('NumPy not available.')
22

    
23
    def setUp(self):
24
        G = networkx.DiGraph()
25
        edges = [(1, 2), (1, 3),
26
                 # 2 is a dangling node
27
                 (3, 1), (3, 2), (3, 5),
28
                 (4, 5), (4, 6),
29
                 (5, 4), (5, 6),
30
                 (6, 4)]
31
        G.add_edges_from(edges)
32
        self.G = G
33
        self.G.pagerank = dict(zip(sorted(G),
34
                                   [0.03721197, 0.05395735, 0.04150565,
35
                                    0.37508082, 0.20599833, 0.28624589]))
36
        self.dangling_node_index = 1
37
        self.dangling_edges = {1: 2, 2: 3,
38
                               3: 0, 4: 0, 5: 0, 6: 0}
39
        self.G.dangling_pagerank = dict(zip(sorted(G),
40
                                            [0.10844518, 0.18618601, 0.0710892,
41
                                             0.2683668, 0.15919783, 0.20671497]))
42

    
43
    def test_pagerank(self):
44
        G = self.G
45
        p = networkx.pagerank(G, alpha=0.9, tol=1.e-08)
46
        for n in G:
47
            assert_almost_equal(p[n], G.pagerank[n], places=4)
48

    
49
        nstart = dict((n, random.random()) for n in G)
50
        p = networkx.pagerank(G, alpha=0.9, tol=1.e-08, nstart=nstart)
51
        for n in G:
52
            assert_almost_equal(p[n], G.pagerank[n], places=4)
53

    
54
    @raises(networkx.PowerIterationFailedConvergence)
55
    def test_pagerank_max_iter(self):
56
        networkx.pagerank(self.G, max_iter=0)
57

    
58
    def test_numpy_pagerank(self):
59
        G = self.G
60
        p = networkx.pagerank_numpy(G, alpha=0.9)
61
        for n in G:
62
            assert_almost_equal(p[n], G.pagerank[n], places=4)
63
        personalize = dict((n, random.random()) for n in G)
64
        p = networkx.pagerank_numpy(G, alpha=0.9, personalization=personalize)
65

    
66
    def test_google_matrix(self):
67
        G = self.G
68
        M = networkx.google_matrix(G, alpha=0.9, nodelist=sorted(G))
69
        e, ev = numpy.linalg.eig(M.T)
70
        p = numpy.array(ev[:, 0] / ev[:, 0].sum())[:, 0]
71
        for (a, b) in zip(p, self.G.pagerank.values()):
72
            assert_almost_equal(a, b)
73

    
74
    def test_personalization(self):
75
        G = networkx.complete_graph(4)
76
        personalize = {0: 1, 1: 1, 2: 4, 3: 4}
77
        answer = {0: 0.23246732615667579, 1: 0.23246732615667579, 2: 0.267532673843324, 3: 0.2675326738433241}
78
        p = networkx.pagerank(G, alpha=0.85, personalization=personalize)
79
        for n in G:
80
            assert_almost_equal(p[n], answer[n], places=4)
81

    
82
    def test_zero_personalization_vector(self):
83
        G = networkx.complete_graph(4)
84
        personalize = {0: 0, 1: 0, 2: 0, 3: 0}
85
        assert_raises(ZeroDivisionError, networkx.pagerank, G,
86
                      personalization=personalize)
87

    
88
    def test_one_nonzero_personalization_value(self):
89
        G = networkx.complete_graph(4)
90
        personalize = {0: 0, 1: 0, 2: 0, 3: 1}
91
        answer = {0: 0.22077931820379187, 1: 0.22077931820379187, 2: 0.22077931820379187, 3: 0.3376620453886241}
92
        p = networkx.pagerank(G, alpha=0.85, personalization=personalize)
93
        for n in G:
94
            assert_almost_equal(p[n], answer[n], places=4)
95

    
96
    def test_incomplete_personalization(self):
97
        G = networkx.complete_graph(4)
98
        personalize = {3: 1}
99
        answer = {0: 0.22077931820379187, 1: 0.22077931820379187, 2: 0.22077931820379187, 3: 0.3376620453886241}
100
        p = networkx.pagerank(G, alpha=0.85, personalization=personalize)
101
        for n in G:
102
            assert_almost_equal(p[n], answer[n], places=4)
103

    
104
    def test_dangling_matrix(self):
105
        """
106
        Tests that the google_matrix doesn't change except for the dangling
107
        nodes.
108
        """
109
        G = self.G
110
        dangling = self.dangling_edges
111
        dangling_sum = float(sum(dangling.values()))
112
        M1 = networkx.google_matrix(G, personalization=dangling)
113
        M2 = networkx.google_matrix(G, personalization=dangling,
114
                                    dangling=dangling)
115
        for i in range(len(G)):
116
            for j in range(len(G)):
117
                if i == self.dangling_node_index and (j + 1) in dangling:
118
                    assert_almost_equal(M2[i, j],
119
                                        dangling[j + 1] / dangling_sum,
120
                                        places=4)
121
                else:
122
                    assert_almost_equal(M2[i, j], M1[i, j], places=4)
123

    
124
    def test_dangling_pagerank(self):
125
        pr = networkx.pagerank(self.G, dangling=self.dangling_edges)
126
        for n in self.G:
127
            assert_almost_equal(pr[n], self.G.dangling_pagerank[n], places=4)
128

    
129
    def test_dangling_numpy_pagerank(self):
130
        pr = networkx.pagerank_numpy(self.G, dangling=self.dangling_edges)
131
        for n in self.G:
132
            assert_almost_equal(pr[n], self.G.dangling_pagerank[n], places=4)
133

    
134
    def test_empty(self):
135
        G = networkx.Graph()
136
        assert_equal(networkx.pagerank(G), {})
137
        assert_equal(networkx.pagerank_numpy(G), {})
138
        assert_equal(networkx.google_matrix(G).shape, (0, 0))
139

    
140

    
141
class TestPageRankScipy(TestPageRank):
142

    
143
    @classmethod
144
    def setupClass(cls):
145
        global scipy
146
        try:
147
            import scipy
148
        except ImportError:
149
            raise SkipTest('SciPy not available.')
150

    
151
    def test_scipy_pagerank(self):
152
        G = self.G
153
        p = networkx.pagerank_scipy(G, alpha=0.9, tol=1.e-08)
154
        for n in G:
155
            assert_almost_equal(p[n], G.pagerank[n], places=4)
156
        personalize = dict((n, random.random()) for n in G)
157
        p = networkx.pagerank_scipy(G, alpha=0.9, tol=1.e-08,
158
                                    personalization=personalize)
159

    
160
    @raises(networkx.PowerIterationFailedConvergence)
161
    def test_scipy_pagerank_max_iter(self):
162
        networkx.pagerank_scipy(self.G, max_iter=0)
163

    
164
    def test_dangling_scipy_pagerank(self):
165
        pr = networkx.pagerank_scipy(self.G, dangling=self.dangling_edges)
166
        for n in self.G:
167
            assert_almost_equal(pr[n], self.G.dangling_pagerank[n], places=4)
168

    
169
    def test_empty_scipy(self):
170
        G = networkx.Graph()
171
        assert_equal(networkx.pagerank_scipy(G), {})