ioftools / networkxMiCe / networkxmaster / 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)
