Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / linalg / bethehessianmatrix.py @ 5cef0f13

History | View | Annotate | Download (2.69 KB)

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
# fixture for nose tests
89
def setup_module(module):
90
    from nose import SkipTest
91
    try:
92
        import numpy
93
    except:
94
        raise SkipTest("NumPy not available")