Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/linalg/bethehessianmatrix.py: 41%

1"""Bethe Hessian or deformed Laplacian matrix of graphs.""" 

2import networkx as nx 

3from networkx.utils import not_implemented_for 

4 

5__all__ = ["bethe_hessian_matrix"] 

6 

7 

8@not_implemented_for("directed") 

9@not_implemented_for("multigraph") 

10@nx._dispatch 

11def bethe_hessian_matrix(G, r=None, nodelist=None): 

12 r"""Returns the Bethe Hessian matrix of G. 

13 

14 The Bethe Hessian is a family of matrices parametrized by r, defined as 

15 H(r) = (r^2 - 1) I - r A + D where A is the adjacency matrix, D is the 

16 diagonal matrix of node degrees, and I is the identify matrix. It is equal 

17 to the graph laplacian when the regularizer r = 1. 

18 

19 The default choice of regularizer should be the ratio [2]_ 

20 

21 .. math:: 

22 r_m = \left(\sum k_i \right)^{-1}\left(\sum k_i^2 \right) - 1 

23 

24 Parameters 

25 ---------- 

26 G : Graph 

27 A NetworkX graph 

28 r : float 

29 Regularizer parameter 

30 nodelist : list, optional 

31 The rows and columns are ordered according to the nodes in nodelist. 

32 If nodelist is None, then the ordering is produced by ``G.nodes()``. 

33 

34 Returns 

35 ------- 

36 H : scipy.sparse.csr_array 

37 The Bethe Hessian matrix of `G`, with parameter `r`. 

38 

39 Examples 

40 -------- 

41 >>> k = [3, 2, 2, 1, 0] 

42 >>> G = nx.havel_hakimi_graph(k) 

43 >>> H = nx.bethe_hessian_matrix(G) 

44 >>> H.toarray() 

45 array([[ 3.5625, -1.25 , -1.25 , -1.25 , 0. ], 

46 [-1.25 , 2.5625, -1.25 , 0. , 0. ], 

47 [-1.25 , -1.25 , 2.5625, 0. , 0. ], 

48 [-1.25 , 0. , 0. , 1.5625, 0. ], 

49 [ 0. , 0. , 0. , 0. , 0.5625]]) 

50 

51 See Also 

52 -------- 

53 bethe_hessian_spectrum 

54 adjacency_matrix 

55 laplacian_matrix 

56 

57 References 

58 ---------- 

59 .. [1] A. Saade, F. Krzakala and L. Zdeborová 

60 "Spectral Clustering of Graphs with the Bethe Hessian", 

61 Advances in Neural Information Processing Systems, 2014. 

62 .. [2] C. M. Le, E. Levina 

63 "Estimating the number of communities in networks by spectral methods" 

64 arXiv:1507.00827, 2015. 

65 """ 

66 import scipy as sp 

67 

68 if nodelist is None: 

69 nodelist = list(G) 

70 if r is None: 

71 r = sum(d**2 for v, d in nx.degree(G)) / sum(d for v, d in nx.degree(G)) - 1 

72 A = nx.to_scipy_sparse_array(G, nodelist=nodelist, format="csr") 

73 n, m = A.shape 

74 # TODO: Rm csr_array wrapper when spdiags array creation becomes available 

75 D = sp.sparse.csr_array(sp.sparse.spdiags(A.sum(axis=1), 0, m, n, format="csr")) 

76 # TODO: Rm csr_array wrapper when eye array creation becomes available 

77 I = sp.sparse.csr_array(sp.sparse.eye(m, n, format="csr")) 

78 return (r**2 - 1) * I - r * A + D