graph_blockmodel_entropy.hh 3.69 KB
 Tiago Peixoto committed Sep 21, 2017 1 2 3 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 44 45 46 47 48 49 50 51 52 53 54 55 ``````// graph-tool -- a general graph modification and manipulation thingy // // Copyright (C) 2006-2017 Tiago de Paula Peixoto // // 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 . #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; bool partition_dl; bool degree_dl; deg_dl_kind degree_dl_kind; bool edges_dl; bool recs_dl; }; // Sparse entropy terms // ==================== // exact microcanonical deg-corr entropy template `````` Tiago Peixoto committed Nov 19, 2017 56 ``````inline double eterm_exact(size_t r, size_t s, size_t mrs, const Graph& g) `````` Tiago Peixoto committed Sep 21, 2017 57 58 59 ``````{ double val = lgamma_fast(mrs + 1); `````` Tiago Peixoto committed Nov 19, 2017 60 `````` if (graph_tool::is_directed(g) || r != s) `````` Tiago Peixoto committed Sep 21, 2017 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 `````` { 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 inline double vterm_exact(size_t mrp, size_t mrm, size_t wr, bool deg_corr, `````` Tiago Peixoto committed Nov 19, 2017 77 `````` const Graph& g) `````` Tiago Peixoto committed Sep 21, 2017 78 79 80 ``````{ if (deg_corr) { `````` Tiago Peixoto committed Nov 19, 2017 81 `````` if (graph_tool::is_directed(g)) `````` Tiago Peixoto committed Sep 21, 2017 82 83 84 85 86 87 `````` return lgamma_fast(mrp + 1) + lgamma_fast(mrm + 1); else return lgamma_fast(mrp + 1); } else { `````` Tiago Peixoto committed Nov 19, 2017 88 `````` if (graph_tool::is_directed(g)) `````` Tiago Peixoto committed Sep 21, 2017 89 90 91 92 93 94 95 96 `````` return (mrp + mrm) * safelog(wr); else return mrp * safelog(wr); } } // "edge" term of the entropy template `````` Tiago Peixoto committed Nov 19, 2017 97 ``````inline double eterm(size_t r, size_t s, size_t mrs, const Graph& g) `````` Tiago Peixoto committed Sep 21, 2017 98 ``````{ `````` Tiago Peixoto committed Nov 19, 2017 99 `````` if (!graph_tool::is_directed(g) && r == s) `````` Tiago Peixoto committed Sep 21, 2017 100 101 102 103 `````` mrs *= 2; double val = xlogx(mrs); `````` Tiago Peixoto committed Nov 19, 2017 104 `````` if (graph_tool::is_directed(g) || r != s) `````` Tiago Peixoto committed Sep 21, 2017 105 106 107 108 109 110 111 112 `````` return -val; else return -val / 2; } // "vertex" term of the entropy template inline double vterm(size_t mrp, size_t mrm, size_t wr, bool deg_corr, `````` Tiago Peixoto committed Nov 19, 2017 113 `````` Graph& g) `````` Tiago Peixoto committed Sep 21, 2017 114 115 116 ``````{ double one = 0.5; `````` Tiago Peixoto committed Nov 19, 2017 117 `````` if (graph_tool::is_directed(g)) `````` Tiago Peixoto committed Sep 21, 2017 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 `````` one = 1; if (deg_corr) return one * (xlogx(mrm) + xlogx(mrp)); else return one * (mrm * safelog(wr) + mrp * safelog(wr)); } // Dense entropy // ============= // "edge" term of the entropy template inline double eterm_dense(size_t r, size_t s, int ers, double wr_r, `````` Tiago Peixoto committed Nov 19, 2017 134 `````` double wr_s, bool multigraph, const Graph& g) `````` Tiago Peixoto committed Sep 21, 2017 135 136 137 138 139 140 141 142 143 ``````{ // we should not use integers here, since they may overflow double nrns; if (ers == 0) return 0.; assert(wr_r + wr_s > 0); `````` Tiago Peixoto committed Nov 19, 2017 144 `````` if (r != s || graph_tool::is_directed(g)) `````` Tiago Peixoto committed Sep 21, 2017 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 `````` { 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) S = lbinom(nrns + ers - 1, ers); // do not use lbinom_fast! else S = lbinom(nrns, ers); return S; } } // namespace graph_tool #endif // GRAPH_BLOCKMODEL_ENTROPY_HH``````