Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / linalg / tests / test_laplacian.py @ 5cef0f13

History | View | Annotate | Download (7.91 KB)

1
from nose import SkipTest
2

    
3
import networkx as nx
4
from networkx.generators.degree_seq import havel_hakimi_graph
5

    
6

    
7
class TestLaplacian(object):
8
    numpy = 1  # nosetests attribute, use nosetests -a 'not numpy' to skip test
9

    
10
    @classmethod
11
    def setupClass(cls):
12
        global numpy
13
        global scipy
14
        global assert_equal
15
        global assert_almost_equal
16
        try:
17
            import numpy
18
            import scipy
19
            from numpy.testing import assert_equal, assert_almost_equal
20
        except ImportError:
21
            raise SkipTest('SciPy not available.')
22

    
23
    def setUp(self):
24
        deg = [3, 2, 2, 1, 0]
25
        self.G = havel_hakimi_graph(deg)
26
        self.WG = nx.Graph((u, v, {'weight': 0.5, 'other': 0.3})
27
                           for (u, v) in self.G.edges())
28
        self.WG.add_node(4)
29
        self.MG = nx.MultiGraph(self.G)
30

    
31
        # Graph with selfloops
32
        self.Gsl = self.G.copy()
33
        for node in self.Gsl.nodes():
34
            self.Gsl.add_edge(node, node)
35

    
36
    def test_laplacian(self):
37
        "Graph Laplacian"
38
        NL = numpy.array([[3, -1, -1, -1, 0],
39
                          [-1,  2, -1,  0, 0],
40
                          [-1, -1,  2,  0, 0],
41
                          [-1,  0,  0,  1, 0],
42
                          [0,  0,  0,  0, 0]])
43
        WL = 0.5 * NL
44
        OL = 0.3 * NL
45
        assert_equal(nx.laplacian_matrix(self.G).todense(), NL)
46
        assert_equal(nx.laplacian_matrix(self.MG).todense(), NL)
47
        assert_equal(nx.laplacian_matrix(self.G, nodelist=[0, 1]).todense(),
48
                     numpy.array([[1, -1], [-1, 1]]))
49
        assert_equal(nx.laplacian_matrix(self.WG).todense(), WL)
50
        assert_equal(nx.laplacian_matrix(self.WG, weight=None).todense(), NL)
51
        assert_equal(nx.laplacian_matrix(self.WG, weight='other').todense(), OL)
52

    
53
    def test_normalized_laplacian(self):
54
        "Generalized Graph Laplacian"
55
        GL = numpy.array([[1.00, -0.408, -0.408, -0.577,  0.00],
56
                          [-0.408,  1.00, -0.50,  0.00, 0.00],
57
                          [-0.408, -0.50,  1.00,  0.00,  0.00],
58
                          [-0.577,  0.00,  0.00,  1.00,  0.00],
59
                          [0.00,  0.00,  0.00,  0.00,  0.00]])
60
        Lsl = numpy.array([[0.75, -0.2887, -0.2887, -0.3536,  0.],
61
                           [-0.2887,  0.6667, -0.3333,  0.,  0.],
62
                           [-0.2887, -0.3333,  0.6667,  0.,  0.],
63
                           [-0.3536,  0.,  0.,  0.5,  0.],
64
                           [0.,  0.,  0.,  0.,  0.]])
65

    
66
        assert_almost_equal(nx.normalized_laplacian_matrix(self.G).todense(),
67
                            GL, decimal=3)
68
        assert_almost_equal(nx.normalized_laplacian_matrix(self.MG).todense(),
69
                            GL, decimal=3)
70
        assert_almost_equal(nx.normalized_laplacian_matrix(self.WG).todense(),
71
                            GL, decimal=3)
72
        assert_almost_equal(nx.normalized_laplacian_matrix(self.WG, weight='other').todense(),
73
                            GL, decimal=3)
74
        assert_almost_equal(nx.normalized_laplacian_matrix(self.Gsl).todense(),
75
                            Lsl, decimal=3)
76

    
77
    def test_directed_laplacian(self):
78
        "Directed Laplacian"
79
        # Graph used as an example in Sec. 4.1 of Langville and Meyer,
80
        # "Google's PageRank and Beyond". The graph contains dangling nodes, so
81
        # the pagerank random walk is selected by directed_laplacian
82
        G = nx.DiGraph()
83
        G.add_edges_from(((1, 2), (1, 3), (3, 1), (3, 2), (3, 5), (4, 5), (4, 6),
84
                          (5, 4), (5, 6), (6, 4)))
85
        GL = numpy.array([[0.9833, -0.2941, -0.3882, -0.0291, -0.0231, -0.0261],
86
                          [-0.2941,  0.8333, -0.2339, -0.0536, -0.0589, -0.0554],
87
                          [-0.3882, -0.2339,  0.9833, -0.0278, -0.0896, -0.0251],
88
                          [-0.0291, -0.0536, -0.0278,  0.9833, -0.4878, -0.6675],
89
                          [-0.0231, -0.0589, -0.0896, -0.4878,  0.9833, -0.2078],
90
                          [-0.0261, -0.0554, -0.0251, -0.6675, -0.2078,  0.9833]])
91
        L = nx.directed_laplacian_matrix(G, alpha=0.9, nodelist=sorted(G))
92
        assert_almost_equal(L, GL, decimal=3)
93

    
94
        # Make the graph strongly connected, so we can use a random and lazy walk
95
        G.add_edges_from((((2, 5), (6, 1))))
96
        GL = numpy.array([[1., -0.3062, -0.4714,  0.,  0., -0.3227],
97
                          [-0.3062,  1., -0.1443,  0., -0.3162,  0.],
98
                          [-0.4714, -0.1443,  1.,  0., -0.0913,  0.],
99
                          [0.,  0.,  0.,  1., -0.5, -0.5],
100
                          [0., -0.3162, -0.0913, -0.5,  1., -0.25],
101
                          [-0.3227,  0.,  0., -0.5, -0.25,  1.]])
102
        L = nx.directed_laplacian_matrix(G, alpha=0.9, nodelist=sorted(G), walk_type='random')
103
        assert_almost_equal(L, GL, decimal=3)
104

    
105
        GL = numpy.array([[0.5, -0.1531, -0.2357,  0.,  0., -0.1614],
106
                          [-0.1531,  0.5, -0.0722,  0., -0.1581,  0.],
107
                          [-0.2357, -0.0722,  0.5,  0., -0.0456,  0.],
108
                          [0.,  0.,  0.,  0.5, -0.25, -0.25],
109
                          [0., -0.1581, -0.0456, -0.25,  0.5, -0.125],
110
                          [-0.1614,  0.,  0., -0.25, -0.125,  0.5]])
111
        L = nx.directed_laplacian_matrix(G, alpha=0.9, nodelist=sorted(G), walk_type='lazy')
112
        assert_almost_equal(L, GL, decimal=3)
113

    
114
    def test_directed_combinatorial_laplacian(self):
115
        "Directed combinatorial Laplacian"
116
        # Graph used as an example in Sec. 4.1 of Langville and Meyer,
117
        # "Google's PageRank and Beyond". The graph contains dangling nodes, so
118
        # the pagerank random walk is selected by directed_laplacian
119
        G = nx.DiGraph()
120
        G.add_edges_from(((1, 2), (1, 3), (3, 1), (3, 2), (3, 5), (4, 5), (4, 6),
121
                          (5, 4), (5, 6), (6, 4)))
122

    
123
        GL = numpy.array([[0.0366, -0.0132, -0.0153, -0.0034, -0.0020, -0.0027],
124
                          [-0.0132, 0.0450, -0.0111, -0.0076, -0.0062, -0.0069],
125
                          [-0.0153, -0.0111, 0.0408, -0.0035, -0.0083, -0.0027],
126
                          [-0.0034, -0.0076, -0.0035, 0.3688, -0.1356, -0.2187],
127
                          [-0.0020, -0.0062, -0.0083, -0.1356, 0.2026, -0.0505],
128
                          [-0.0027, -0.0069, -0.0027, -0.2187, -0.0505, 0.2815]])
129

    
130
        L = nx.directed_combinatorial_laplacian_matrix(G, alpha=0.9,
131
                                                       nodelist=sorted(G))
132
        assert_almost_equal(L, GL, decimal=3)
133

    
134
        # Make the graph strongly connected, so we can use a random and lazy walk
135
        G.add_edges_from((((2, 5), (6, 1))))
136

    
137
        GL = numpy.array([[0.1395, -0.0349, -0.0465, 0, 0, -0.0581],
138
                          [-0.0349, 0.0930, -0.0116, 0, -0.0465, 0],
139
                          [-0.0465, -0.0116, 0.0698, 0, -0.0116, 0],
140
                          [0, 0, 0, 0.2326, -0.1163, -0.1163],
141
                          [0, -0.0465, -0.0116, -0.1163, 0.2326, -0.0581],
142
                          [-0.0581, 0, 0, -0.1163, -0.0581, 0.2326]])
143

    
144
        L = nx.directed_combinatorial_laplacian_matrix(G, alpha=0.9,
145
                                                       nodelist=sorted(G),
146
                                                       walk_type='random')
147
        assert_almost_equal(L, GL, decimal=3)
148

    
149
        GL = numpy.array([[0.0698, -0.0174, -0.0233, 0, 0, -0.0291],
150
                          [-0.0174, 0.0465, -0.0058, 0, -0.0233, 0],
151
                          [-0.0233, -0.0058, 0.0349, 0, -0.0058, 0],
152
                          [0, 0, 0, 0.1163, -0.0581, -0.0581],
153
                          [0, -0.0233, -0.0058, -0.0581, 0.1163, -0.0291],
154
                          [-0.0291, 0, 0, -0.0581, -0.0291, 0.1163]])
155

    
156
        L = nx.directed_combinatorial_laplacian_matrix(G, alpha=0.9,
157
                                                       nodelist=sorted(G),
158
                                                       walk_type='lazy')
159
        assert_almost_equal(L, GL, decimal=3)