Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/linalg/bethehessianmatrix.py @ 1:56ad4e20f292 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
author guerler
date Fri, 31 Jul 2020 00:32:28 -0400
parents
children
comparison
equal deleted inserted replaced
0:d30785e31577 1:56ad4e20f292
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')