Hide keyboard shortcuts

Hot-keys on this page

r m x p   toggle line displays

j k   next/prev highlighted chunk

0   (zero) top of page

1   (one) first highlighted chunk

1""" 

2Laplacian of a compressed-sparse graph 

3""" 

4 

5# Authors: Aric Hagberg <hagberg@lanl.gov> 

6# Gael Varoquaux <gael.varoquaux@normalesup.org> 

7# Jake Vanderplas <vanderplas@astro.washington.edu> 

8# License: BSD 

9 

10import numpy as np 

11from scipy.sparse import isspmatrix 

12 

13 

14############################################################################### 

15# Graph laplacian 

16def laplacian(csgraph, normed=False, return_diag=False, use_out_degree=False): 

17 """ 

18 Return the Laplacian matrix of a directed graph. 

19 

20 Parameters 

21 ---------- 

22 csgraph : array_like or sparse matrix, 2 dimensions 

23 compressed-sparse graph, with shape (N, N). 

24 normed : bool, optional 

25 If True, then compute symmetric normalized Laplacian. 

26 return_diag : bool, optional 

27 If True, then also return an array related to vertex degrees. 

28 use_out_degree : bool, optional 

29 If True, then use out-degree instead of in-degree. 

30 This distinction matters only if the graph is asymmetric. 

31 Default: False. 

32 

33 Returns 

34 ------- 

35 lap : ndarray or sparse matrix 

36 The N x N laplacian matrix of csgraph. It will be a NumPy array (dense) 

37 if the input was dense, or a sparse matrix otherwise. 

38 diag : ndarray, optional 

39 The length-N diagonal of the Laplacian matrix. 

40 For the normalized Laplacian, this is the array of square roots 

41 of vertex degrees or 1 if the degree is zero. 

42 

43 Notes 

44 ----- 

45 The Laplacian matrix of a graph is sometimes referred to as the 

46 "Kirchoff matrix" or the "admittance matrix", and is useful in many 

47 parts of spectral graph theory. In particular, the eigen-decomposition 

48 of the laplacian matrix can give insight into many properties of the graph. 

49 

50 Examples 

51 -------- 

52 >>> from scipy.sparse import csgraph 

53 >>> G = np.arange(5) * np.arange(5)[:, np.newaxis] 

54 >>> G 

55 array([[ 0, 0, 0, 0, 0], 

56 [ 0, 1, 2, 3, 4], 

57 [ 0, 2, 4, 6, 8], 

58 [ 0, 3, 6, 9, 12], 

59 [ 0, 4, 8, 12, 16]]) 

60 >>> csgraph.laplacian(G, normed=False) 

61 array([[ 0, 0, 0, 0, 0], 

62 [ 0, 9, -2, -3, -4], 

63 [ 0, -2, 16, -6, -8], 

64 [ 0, -3, -6, 21, -12], 

65 [ 0, -4, -8, -12, 24]]) 

66 """ 

67 if csgraph.ndim != 2 or csgraph.shape[0] != csgraph.shape[1]: 

68 raise ValueError('csgraph must be a square matrix or array') 

69 

70 if normed and (np.issubdtype(csgraph.dtype, np.signedinteger) 

71 or np.issubdtype(csgraph.dtype, np.uint)): 

72 csgraph = csgraph.astype(float) 

73 

74 create_lap = _laplacian_sparse if isspmatrix(csgraph) else _laplacian_dense 

75 degree_axis = 1 if use_out_degree else 0 

76 lap, d = create_lap(csgraph, normed=normed, axis=degree_axis) 

77 if return_diag: 

78 return lap, d 

79 return lap 

80 

81 

82def _setdiag_dense(A, d): 

83 A.flat[::len(d)+1] = d 

84 

85 

86def _laplacian_sparse(graph, normed=False, axis=0): 

87 if graph.format in ('lil', 'dok'): 

88 m = graph.tocoo() 

89 needs_copy = False 

90 else: 

91 m = graph 

92 needs_copy = True 

93 w = m.sum(axis=axis).getA1() - m.diagonal() 

94 if normed: 

95 m = m.tocoo(copy=needs_copy) 

96 isolated_node_mask = (w == 0) 

97 w = np.where(isolated_node_mask, 1, np.sqrt(w)) 

98 m.data /= w[m.row] 

99 m.data /= w[m.col] 

100 m.data *= -1 

101 m.setdiag(1 - isolated_node_mask) 

102 else: 

103 if m.format == 'dia': 

104 m = m.copy() 

105 else: 

106 m = m.tocoo(copy=needs_copy) 

107 m.data *= -1 

108 m.setdiag(w) 

109 return m, w 

110 

111 

112def _laplacian_dense(graph, normed=False, axis=0): 

113 m = np.array(graph) 

114 np.fill_diagonal(m, 0) 

115 w = m.sum(axis=axis) 

116 if normed: 

117 isolated_node_mask = (w == 0) 

118 w = np.where(isolated_node_mask, 1, np.sqrt(w)) 

119 m /= w 

120 m /= w[:, np.newaxis] 

121 m *= -1 

122 _setdiag_dense(m, 1 - isolated_node_mask) 

123 else: 

124 m *= -1 

125 _setdiag_dense(m, w) 

126 return m, w