Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/networkx/linalg/bethehessianmatrix.py: 44%

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

2 

3import networkx as nx 

4from networkx.utils import not_implemented_for 

5 

6__all__ = ["bethe_hessian_matrix"] 

7 

8 

9@not_implemented_for("directed") 

10@not_implemented_for("multigraph") 

11@nx._dispatchable 

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

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

14 

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

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

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

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

19 

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

21 

22 .. math:: 

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

24 

25 Parameters 

26 ---------- 

27 G : Graph 

28 A NetworkX graph 

29 r : float 

30 Regularizer parameter 

31 nodelist : list, optional 

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

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

34 

35 Returns 

36 ------- 

37 H : scipy.sparse.csr_array 

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

39 

40 Examples 

41 -------- 

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

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

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

45 >>> H.toarray() 

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

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

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

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

50 [ 0. , 0. , 0. , 0. , 0.5625]]) 

51 

52 See Also 

53 -------- 

54 bethe_hessian_spectrum 

55 adjacency_matrix 

56 laplacian_matrix 

57 

58 References 

59 ---------- 

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

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

62 Advances in Neural Information Processing Systems, 2014. 

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

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

65 arXiv:1507.00827, 2015. 

66 """ 

67 import scipy as sp 

68 

69 if nodelist is None: 

70 nodelist = list(G) 

71 if r is None: 

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

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

74 n, m = A.shape 

75 D = sp.sparse.dia_array((A.sum(axis=1), 0), shape=(m, n)).tocsr() 

76 I = sp.sparse.eye_array(m, n, format="csr") 

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