| from nose import SkipTest |
| |
| import networkx as nx |
| from networkx.generators.degree_seq import havel_hakimi_graph |
| |
| class TestLaplacian(object): |
| numpy=1 # nosetests attribute, use nosetests -a 'not numpy' to skip test |
| @classmethod |
| def setupClass(cls): |
| global numpy |
| global assert_equal |
| global assert_almost_equal |
| try: |
| import numpy |
| from numpy.testing import assert_equal,assert_almost_equal |
| except ImportError: |
| raise SkipTest('NumPy not available.') |
| |
| def setUp(self): |
| deg=[3,2,2,1,0] |
| self.G=havel_hakimi_graph(deg) |
| self.WG=nx.Graph( (u,v,{'weight':0.5,'other':0.3}) |
| for (u,v) in self.G.edges_iter() ) |
| self.WG.add_node(4) |
| self.MG=nx.MultiGraph(self.G) |
| |
| # Graph with selfloops |
| self.Gsl = self.G.copy() |
| for node in self.Gsl.nodes(): |
| self.Gsl.add_edge(node, node) |
| |
| |
| def test_laplacian(self): |
| "Graph Laplacian" |
| NL=numpy.array([[ 3, -1, -1, -1, 0], |
| [-1, 2, -1, 0, 0], |
| [-1, -1, 2, 0, 0], |
| [-1, 0, 0, 1, 0], |
| [ 0, 0, 0, 0, 0]]) |
| WL=0.5*NL |
| OL=0.3*NL |
| assert_equal(nx.laplacian_matrix(self.G),NL) |
| assert_equal(nx.laplacian_matrix(self.MG),NL) |
| assert_equal(nx.laplacian_matrix(self.G,nodelist=[0,1]), |
| numpy.array([[ 1, -1],[-1, 1]])) |
| assert_equal(nx.laplacian_matrix(self.WG),WL) |
| assert_equal(nx.laplacian_matrix(self.WG,weight=None),NL) |
| assert_equal(nx.laplacian_matrix(self.WG,weight='other'),OL) |
| |
| def test_normalized_laplacian(self): |
| "Generalized Graph Laplacian" |
| GL=numpy.array([[ 1.00, -0.408, -0.408, -0.577, 0.00], |
| [-0.408, 1.00, -0.50, 0.00 , 0.00], |
| [-0.408, -0.50, 1.00, 0.00, 0.00], |
| [-0.577, 0.00, 0.00, 1.00, 0.00], |
| [ 0.00, 0.00, 0.00, 0.00, 0.00]]) |
| Lsl = numpy.array([[ 0.75 , -0.2887, -0.2887, -0.3536, 0.], |
| [-0.2887, 0.6667, -0.3333, 0. , 0.], |
| [-0.2887, -0.3333, 0.6667, 0. , 0.], |
| [-0.3536, 0. , 0. , 0.5 , 0.], |
| [ 0. , 0. , 0. , 0. , 0.]]) |
| |
| assert_almost_equal(nx.normalized_laplacian_matrix(self.G),GL,decimal=3) |
| assert_almost_equal(nx.normalized_laplacian_matrix(self.MG),GL,decimal=3) |
| assert_almost_equal(nx.normalized_laplacian_matrix(self.WG),GL,decimal=3) |
| assert_almost_equal(nx.normalized_laplacian_matrix(self.WG,weight='other'),GL,decimal=3) |
| assert_almost_equal(nx.normalized_laplacian_matrix(self.Gsl), Lsl, decimal=3) |
| |
| def test_directed_laplacian(self): |
| "Directed Laplacian" |
| # Graph used as an example in Sec. 4.1 of Langville and Meyer, |
| # "Google's PageRank and Beyond". The graph contains dangling nodes, so |
| # the pagerank random walk is selected by directed_laplacian |
| G = nx.DiGraph() |
| G.add_edges_from(((1,2), (1,3), (3,1), (3,2), (3,5), (4,5), (4,6), |
| (5,4), (5,6), (6,4))) |
| GL = numpy.array([[ 0.9833, -0.2941, -0.3882, -0.0291, -0.0231, -0.0261], |
| [-0.2941, 0.8333, -0.2339, -0.0536, -0.0589, -0.0554], |
| [-0.3882, -0.2339, 0.9833, -0.0278, -0.0896, -0.0251], |
| [-0.0291, -0.0536, -0.0278, 0.9833, -0.4878, -0.6675], |
| [-0.0231, -0.0589, -0.0896, -0.4878, 0.9833, -0.2078], |
| [-0.0261, -0.0554, -0.0251, -0.6675, -0.2078, 0.9833]]) |
| assert_almost_equal(nx.directed_laplacian_matrix(G, alpha=0.9), GL, decimal=3) |
| |
| # Make the graph strongly connected, so we can use a random and lazy walk |
| G.add_edges_from((((2,5), (6,1)))) |
| GL = numpy.array([[ 1. , -0.3062, -0.4714, 0. , 0. , -0.3227], |
| [-0.3062, 1. , -0.1443, 0. , -0.3162, 0. ], |
| [-0.4714, -0.1443, 1. , 0. , -0.0913, 0. ], |
| [ 0. , 0. , 0. , 1. , -0.5 , -0.5 ], |
| [ 0. , -0.3162, -0.0913, -0.5 , 1. , -0.25 ], |
| [-0.3227, 0. , 0. , -0.5 , -0.25 , 1. ]]) |
| assert_almost_equal(nx.directed_laplacian_matrix(G, walk_type='random'), GL, decimal=3) |
| |
| GL = numpy.array([[ 0.5 , -0.1531, -0.2357, 0. , 0. , -0.1614], |
| [-0.1531, 0.5 , -0.0722, 0. , -0.1581, 0. ], |
| [-0.2357, -0.0722, 0.5 , 0. , -0.0456, 0. ], |
| [ 0. , 0. , 0. , 0.5 , -0.25 , -0.25 ], |
| [ 0. , -0.1581, -0.0456, -0.25 , 0.5 , -0.125 ], |
| [-0.1614, 0. , 0. , -0.25 , -0.125 , 0.5 ]]) |
| assert_almost_equal(nx.directed_laplacian_matrix(G, walk_type='lazy'), GL, decimal=3) |
