Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/linalg/bethehessianmatrix.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """Bethe Hessian or deformed Laplacian matrix of graphs.""" | |
2 import networkx as nx | |
3 from 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 def bethe_hessian_matrix(G, r=None, nodelist=None): | |
11 r"""Returns the Bethe Hessian matrix of G. | |
12 | |
13 The Bethe Hessian is a family of matrices parametrized by r, defined as | |
14 H(r) = (r^2 - 1) I - r A + D where A is the adjacency matrix, D is the | |
15 diagonal matrix of node degrees, and I is the identify matrix. It is equal | |
16 to the graph laplacian when the regularizer r = 1. | |
17 | |
18 The default choice of regularizer should be the ratio [2] | |
19 | |
20 .. math:: | |
21 r_m = \left(\sum k_i \right)^{-1}\left(\sum k_i^2 \right) - 1 | |
22 | |
23 Parameters | |
24 ---------- | |
25 G : Graph | |
26 A NetworkX graph | |
27 | |
28 r : float | |
29 Regularizer parameter | |
30 | |
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 | |
36 Returns | |
37 ------- | |
38 H : Numpy matrix | |
39 The Bethe Hessian matrix of G, with paramter r. | |
40 | |
41 Examples | |
42 -------- | |
43 >>> k = [3, 2, 2, 1, 0] | |
44 >>> G = nx.havel_hakimi_graph(k) | |
45 >>> H = nx.modularity_matrix(G) | |
46 | |
47 | |
48 See Also | |
49 -------- | |
50 bethe_hessian_spectrum | |
51 to_numpy_array | |
52 adjacency_matrix | |
53 laplacian_matrix | |
54 | |
55 References | |
56 ---------- | |
57 .. [1] A. Saade, F. Krzakala and L. Zdeborová | |
58 "Spectral clustering of graphs with the bethe hessian", | |
59 Advances in Neural Information Processing Systems. 2014. | |
60 .. [2] C. M. Lee, E. Levina | |
61 "Estimating the number of communities in networks by spectral methods" | |
62 arXiv:1507.00827, 2015. | |
63 """ | |
64 import scipy.sparse | |
65 | |
66 if nodelist is None: | |
67 nodelist = list(G) | |
68 if r is None: | |
69 r = ( | |
70 sum([d ** 2 for v, d in nx.degree(G)]) / sum([d for v, d in nx.degree(G)]) | |
71 - 1 | |
72 ) | |
73 A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, format="csr") | |
74 n, m = A.shape | |
75 diags = A.sum(axis=1) | |
76 D = scipy.sparse.spdiags(diags.flatten(), [0], m, n, format="csr") | |
77 I = scipy.sparse.eye(m, n, format="csr") | |
78 return (r ** 2 - 1) * I - r * A + D |