graph_blockmodel_entropy.hh 4.01 KB
Newer Older
1
2
// graph-tool -- a general graph modification and manipulation thingy
//
Tiago Peixoto's avatar
Tiago Peixoto committed
3
// Copyright (C) 2006-2018 Tiago de Paula Peixoto <tiago@skewed.de>
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 3
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <http://www.gnu.org/licenses/>.

#ifndef GRAPH_BLOCKMODEL_ENTROPY_HH
#define GRAPH_BLOCKMODEL_ENTROPY_HH

#include "../support/util.hh"

namespace graph_tool
{

// ====================
// Entropy calculation
// ====================

enum deg_dl_kind
{
    ENT,
    UNIFORM,
    DIST
};

struct entropy_args_t
{
    bool dense;
    bool multigraph;
    bool exact;
    bool adjacency;
    bool recs;
44
    bool deg_entropy;
45
46
47
48
49
    bool partition_dl;
    bool degree_dl;
    deg_dl_kind  degree_dl_kind;
    bool edges_dl;
    bool recs_dl;
50
    double beta_dl;
51
    bool Bfield;
52
53
54
55
56
57
58
};

// Sparse entropy terms
// ====================

// exact microcanonical deg-corr entropy
template <class Graph>
59
inline double eterm_exact(size_t r, size_t s, size_t mrs, const Graph& g)
60
61
62
{
    double val = lgamma_fast(mrs + 1);

63
    if (graph_tool::is_directed(g) || r != s)
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
    {
        return -val;
    }
    else
    {
#ifndef __clang__
        constexpr double log_2 = log(2);
#else
        const double log_2 = log(2);
#endif
        return -val - mrs * log_2;
    }
}

template <class Graph>
inline double vterm_exact(size_t mrp, size_t mrm, size_t wr, bool deg_corr,
80
                          const Graph& g)
81
82
83
{
    if (deg_corr)
    {
84
        if (graph_tool::is_directed(g))
85
86
87
88
89
90
            return lgamma_fast(mrp + 1) + lgamma_fast(mrm + 1);
        else
            return lgamma_fast(mrp + 1);
    }
    else
    {
91
        if (graph_tool::is_directed(g))
92
            return (mrp + mrm) * safelog_fast(wr);
93
        else
94
            return mrp * safelog_fast(wr);
95
96
97
98
99
    }
}

// "edge" term of the entropy
template <class Graph>
100
inline double eterm(size_t r, size_t s, size_t mrs, const Graph& g)
101
{
102
    if (!graph_tool::is_directed(g) && r == s)
103
104
        mrs *= 2;

105
    double val = xlogx_fast(mrs);
106

107
    if (graph_tool::is_directed(g) || r != s)
108
109
110
111
112
113
114
115
        return -val;
    else
        return -val / 2;
}

// "vertex" term of the entropy
template <class Graph>
inline double vterm(size_t mrp, size_t mrm, size_t wr, bool deg_corr,
116
                    Graph& g)
117
118
119
{
    double one = 0.5;

120
    if (graph_tool::is_directed(g))
121
122
123
        one = 1;

    if (deg_corr)
124
        return one * (xlogx_fast(mrm) + xlogx_fast(mrp));
125
    else
126
        return one * (mrm * safelog_fast(wr) + mrp * safelog_fast(wr));
127
128
129
130
131
132
133
134
135
}



// Dense entropy
// =============

// "edge" term of the entropy
template <class Graph>
136
137
inline double eterm_dense(size_t r, size_t s, uint64_t ers, uint64_t wr_r,
                          uint64_t wr_s, bool multigraph, const Graph& g)
138
{
139
    uint64_t nrns; // avoid overflow for nr < 2^32
140
141
142
143
144
145

    if (ers == 0)
        return 0.;

    assert(wr_r + wr_s > 0);

146
    if (r != s || graph_tool::is_directed(g))
147
148
149
150
151
152
153
154
155
156
157
158
159
    {
        nrns = wr_r * wr_s;
    }
    else
    {
        if (multigraph)
            nrns = (wr_r * (wr_r + 1)) / 2;
        else
            nrns = (wr_r * (wr_r - 1)) / 2;
    }

    double S;
    if (multigraph)
160
        S = lbinom_fast<false>(nrns + ers - 1, ers); // do not use lbinom_fast<true>!
161
    else
162
        S = lbinom_fast<false>(nrns, ers);
163
164
165
    return S;
}

166
167
168
169
170
// Edges description length
template <class Graph>
double get_edges_dl(size_t B, size_t E, Graph& g)
{
    size_t NB = (graph_tool::is_directed(g)) ? B * B : (B * (B + 1)) / 2;
171
    return lbinom_fast<false>(NB + E - 1, E);
172
173
}

174
175
176
} // namespace graph_tool

#endif // GRAPH_BLOCKMODEL_ENTROPY_HH