### view env/lib/python3.9/site-packages/networkx/linalg/bethehessianmatrix.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
line wrap: on
line source

"""Bethe Hessian or deformed Laplacian matrix of graphs."""
import networkx as nx
from networkx.utils import not_implemented_for

__all__ = ["bethe_hessian_matrix"]

@not_implemented_for("directed")
@not_implemented_for("multigraph")
def bethe_hessian_matrix(G, r=None, nodelist=None):
r"""Returns the Bethe Hessian matrix of G.

The Bethe Hessian is a family of matrices parametrized by r, defined as
H(r) = (r^2 - 1) I - r A + D where A is the adjacency matrix, D is the
diagonal matrix of node degrees, and I is the identify matrix. It is equal
to the graph laplacian when the regularizer r = 1.

The default choice of regularizer should be the ratio 

.. math::
r_m = \left(\sum k_i \right)^{-1}\left(\sum k_i^2 \right) - 1

Parameters
----------
G : Graph
A NetworkX graph

r : float
Regularizer parameter

nodelist : list, optional
The rows and columns are ordered according to the nodes in nodelist.
If nodelist is None, then the ordering is produced by G.nodes().

Returns
-------
H : Numpy matrix
The Bethe Hessian matrix of G, with paramter r.

Examples
--------
>>> k = [3, 2, 2, 1, 0]
>>> G = nx.havel_hakimi_graph(k)
>>> H = nx.modularity_matrix(G)

--------
bethe_hessian_spectrum
to_numpy_array
laplacian_matrix

References
----------
..  A. Saade, F. Krzakala and L. Zdeborová
"Spectral clustering of graphs with the bethe hessian",
Advances in Neural Information Processing Systems. 2014.
..  C. M. Lee, E. Levina
"Estimating the number of communities in networks by spectral methods"
arXiv:1507.00827, 2015.
"""
import scipy.sparse

if nodelist is None:
nodelist = list(G)
if r is None:
r = (
sum([d ** 2 for v, d in nx.degree(G)]) / sum([d for v, d in nx.degree(G)])
- 1
)
A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, format="csr")
n, m = A.shape
diags = A.sum(axis=1)
D = scipy.sparse.spdiags(diags.flatten(), , m, n, format="csr")
I = scipy.sparse.eye(m, n, format="csr")
return (r ** 2 - 1) * I - r * A + D