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 scipy global assert_equal global assert_almost_equal try: import numpy import scipy from numpy.testing import assert_equal, assert_almost_equal except ImportError: raise SkipTest('SciPy 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()) 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).todense(), NL) assert_equal(nx.laplacian_matrix(self.MG).todense(), NL) assert_equal(nx.laplacian_matrix(self.G, nodelist=[0, 1]).todense(), numpy.array([[1, -1], [-1, 1]])) assert_equal(nx.laplacian_matrix(self.WG).todense(), WL) assert_equal(nx.laplacian_matrix(self.WG, weight=None).todense(), NL) assert_equal(nx.laplacian_matrix(self.WG, weight='other').todense(), 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).todense(), GL, decimal=3) assert_almost_equal(nx.normalized_laplacian_matrix(self.MG).todense(), GL, decimal=3) assert_almost_equal(nx.normalized_laplacian_matrix(self.WG).todense(), GL, decimal=3) assert_almost_equal(nx.normalized_laplacian_matrix(self.WG, weight='other').todense(), GL, decimal=3) assert_almost_equal(nx.normalized_laplacian_matrix(self.Gsl).todense(), 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]]) L = nx.directed_laplacian_matrix(G, alpha=0.9, nodelist=sorted(G)) assert_almost_equal(L, 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.]]) L = nx.directed_laplacian_matrix(G, alpha=0.9, nodelist=sorted(G), walk_type='random') assert_almost_equal(L, 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]]) L = nx.directed_laplacian_matrix(G, alpha=0.9, nodelist=sorted(G), walk_type='lazy') assert_almost_equal(L, GL, decimal=3)