1 from nose import SkipTest 2 3 import networkx as nx 4 from networkx.generators.degree_seq import havel_hakimi_graph 5 6 class TestLaplacian(object): 7 numpy=1 # nosetests attribute, use nosetests -a 'not numpy' to skip test 8 @classmethod 9 def setupClass(cls): 10 global numpy 11 global assert_equal 12 global assert_almost_equal 13 try: 14 import numpy 15 from numpy.testing import assert_equal,assert_almost_equal 16 except ImportError: 17 raise SkipTest('NumPy not available.') 18 19 def setUp(self): 20 deg=[3,2,2,1,0] 21 self.G=havel_hakimi_graph(deg) 22 self.WG=nx.Graph( (u,v,{'weight':0.5,'other':0.3}) 23 for (u,v) in self.G.edges_iter() ) 24 self.WG.add_node(4) 25 self.MG=nx.MultiGraph(self.G) 26 27 # Graph with selfloops 28 self.Gsl = self.G.copy() 29 for node in self.Gsl.nodes(): 30 self.Gsl.add_edge(node, node) 31 32 33 def test_laplacian(self): 34 "Graph Laplacian" 35 NL=numpy.array([[ 3, -1, -1, -1, 0], 36 [-1, 2, -1, 0, 0], 37 [-1, -1, 2, 0, 0], 38 [-1, 0, 0, 1, 0], 39 [ 0, 0, 0, 0, 0]]) 40 WL=0.5*NL 41 OL=0.3*NL 42 assert_equal(nx.laplacian_matrix(self.G),NL) 43 assert_equal(nx.laplacian_matrix(self.MG),NL) 44 assert_equal(nx.laplacian_matrix(self.G,nodelist=[0,1]), 45 numpy.array([[ 1, -1],[-1, 1]])) 46 assert_equal(nx.laplacian_matrix(self.WG),WL) 47 assert_equal(nx.laplacian_matrix(self.WG,weight=None),NL) 48 assert_equal(nx.laplacian_matrix(self.WG,weight='other'),OL) 49 50 def test_normalized_laplacian(self): 51 "Generalized Graph Laplacian" 52 GL=numpy.array([[ 1.00, -0.408, -0.408, -0.577, 0.00], 53 [-0.408, 1.00, -0.50, 0.00 , 0.00], 54 [-0.408, -0.50, 1.00, 0.00, 0.00], 55 [-0.577, 0.00, 0.00, 1.00, 0.00], 56 [ 0.00, 0.00, 0.00, 0.00, 0.00]]) 57 Lsl = numpy.array([[ 0.75 , -0.2887, -0.2887, -0.3536, 0.], 58 [-0.2887, 0.6667, -0.3333, 0. , 0.], 59 [-0.2887, -0.3333, 0.6667, 0. , 0.], 60 [-0.3536, 0. , 0. , 0.5 , 0.], 61 [ 0. , 0. , 0. , 0. , 0.]]) 62 63 assert_almost_equal(nx.normalized_laplacian_matrix(self.G),GL,decimal=3) 64 assert_almost_equal(nx.normalized_laplacian_matrix(self.MG),GL,decimal=3) 65 assert_almost_equal(nx.normalized_laplacian_matrix(self.WG),GL,decimal=3) 66 assert_almost_equal(nx.normalized_laplacian_matrix(self.WG,weight='other'),GL,decimal=3) 67 assert_almost_equal(nx.normalized_laplacian_matrix(self.Gsl), Lsl, decimal=3) 68 69 def test_directed_laplacian(self): 70 "Directed Laplacian" 71 # Graph used as an example in Sec. 4.1 of Langville and Meyer, 72 # "Google's PageRank and Beyond". The graph contains dangling nodes, so 73 # the pagerank random walk is selected by directed_laplacian 74 G = nx.DiGraph() 75 G.add_edges_from(((1,2), (1,3), (3,1), (3,2), (3,5), (4,5), (4,6), 76 (5,4), (5,6), (6,4))) 77 GL = numpy.array([[ 0.9833, -0.2941, -0.3882, -0.0291, -0.0231, -0.0261], 78 [-0.2941, 0.8333, -0.2339, -0.0536, -0.0589, -0.0554], 79 [-0.3882, -0.2339, 0.9833, -0.0278, -0.0896, -0.0251], 80 [-0.0291, -0.0536, -0.0278, 0.9833, -0.4878, -0.6675], 81 [-0.0231, -0.0589, -0.0896, -0.4878, 0.9833, -0.2078], 82 [-0.0261, -0.0554, -0.0251, -0.6675, -0.2078, 0.9833]]) 83 assert_almost_equal(nx.directed_laplacian_matrix(G, alpha=0.9), GL, decimal=3) 84 85 # Make the graph strongly connected, so we can use a random and lazy walk 86 G.add_edges_from((((2,5), (6,1)))) 87 GL = numpy.array([[ 1. , -0.3062, -0.4714, 0. , 0. , -0.3227], 88 [-0.3062, 1. , -0.1443, 0. , -0.3162, 0. ], 89 [-0.4714, -0.1443, 1. , 0. , -0.0913, 0. ], 90 [ 0. , 0. , 0. , 1. , -0.5 , -0.5 ], 91 [ 0. , -0.3162, -0.0913, -0.5 , 1. , -0.25 ], 92 [-0.3227, 0. , 0. , -0.5 , -0.25 , 1. ]]) 93 assert_almost_equal(nx.directed_laplacian_matrix(G, walk_type='random'), GL, decimal=3) 94 95 GL = numpy.array([[ 0.5 , -0.1531, -0.2357, 0. , 0. , -0.1614], 96 [-0.1531, 0.5 , -0.0722, 0. , -0.1581, 0. ], 97 [-0.2357, -0.0722, 0.5 , 0. , -0.0456, 0. ], 98 [ 0. , 0. , 0. , 0.5 , -0.25 , -0.25 ], 99 [ 0. , -0.1581, -0.0456, -0.25 , 0.5 , -0.125 ], 100 [-0.1614, 0. , 0. , -0.25 , -0.125 , 0.5 ]]) 101 assert_almost_equal(nx.directed_laplacian_matrix(G, walk_type='lazy'), GL, decimal=3) 102
