Mercurial > repos > shellac > guppy_basecaller

comparison env/lib/python3.7/site-packages/networkx/linalg/bethehessianmatrix.py @ 2:6af9afd405e9 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 0a63dd5f4d38a1f6944587f52a8cd79874177fc1"
author shellac
date Thu, 14 May 2020 14:56:58 -0400
parents 26e78fe6e8c4
children
comparison
equal deleted inserted replaced
1:75ca89e9b81c 2:6af9afd405e9
1 # -*- coding: utf-8 -*-
2 # Copyright (C) 2004-2019 by
3 # Aric Hagberg <hagberg@lanl.gov>
4 # Dan Schult <dschult@colgate.edu>
5 # Pieter Swart <swart@lanl.gov>
6 # Jean-Gabriel Young <jeangabriel.young@gmail.com>
7 # All rights reserved.
8 # BSD license.
9 #
10 # Authors: Jean-Gabriel Young (jeangabriel.young@gmail.com)
11 """Bethe Hessian or deformed Laplacian matrix of graphs."""
12 import networkx as nx
13 from networkx.utils import not_implemented_for
14
15 __all__ = ['bethe_hessian_matrix']
16
17
18 @not_implemented_for('directed')
19 @not_implemented_for('multigraph')
20 def bethe_hessian_matrix(G, r=None, nodelist=None):
21 r"""Returns the Bethe Hessian matrix of G.
22
23 The Bethe Hessian is a family of matrices parametrized by r, defined as
24 H(r) = (r^2 - 1) I - r A + D where A is the adjacency matrix, D is the
25 diagonal matrix of node degrees, and I is the identify matrix. It is equal
26 to the graph laplacian when the regularizer r = 1.
27
28 The default choice of regularizer should be the ratio [2]
29
30 .. math::
31 r_m = \left(\sum k_i \right)^{-1}\left(\sum k_i^2 \right) - 1
32
33 Parameters
34 ----------
35 G : Graph
36 A NetworkX graph
37
38 r : float
39 Regularizer parameter
40
41 nodelist : list, optional
42 The rows and columns are ordered according to the nodes in nodelist.
43 If nodelist is None, then the ordering is produced by G.nodes().
44
45
46 Returns
47 -------
48 H : Numpy matrix
49 The Bethe Hessian matrix of G, with paramter r.
50
51 Examples
52 --------
53 >>> import networkx as nx
54 >>> k =[3, 2, 2, 1, 0]
55 >>> G = nx.havel_hakimi_graph(k)
56 >>> H = nx.modularity_matrix(G)
57
58
59 See Also
60 --------
61 bethe_hessian_spectrum
62 to_numpy_matrix
63 adjacency_matrix
64 laplacian_matrix
65
66 References
67 ----------
68 .. [1] A. Saade, F. Krzakala and L. Zdeborová
69 "Spectral clustering of graphs with the bethe hessian",
70 Advances in Neural Information Processing Systems. 2014.
71 .. [2] C. M. Lee, E. Levina
72 "Estimating the number of communities in networks by spectral methods"
73 arXiv:1507.00827, 2015.
74 """
75 import scipy.sparse
76 if nodelist is None:
77 nodelist = list(G)
78 if r is None:
79 r = sum([d ** 2 for v, d in nx.degree(G)]) /\
80 sum([d for v, d in nx.degree(G)]) - 1
81 A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, format='csr')
82 n, m = A.shape
83 diags = A.sum(axis=1)
84 D = scipy.sparse.spdiags(diags.flatten(), [0], m, n, format='csr')
85 I = scipy.sparse.eye(m, n, format='csr')
86 return (r ** 2 - 1) * I - r * A + D
87
88
89 # fixture for pytest
90 def setup_module(module):
91 import pytest
92 numpy = pytest.importorskip('numpy')