uncertain_blockmodel.py 63.9 KB
Newer Older
1
2
3
4
5
#! /usr/bin/env python
# -*- coding: utf-8 -*-
#
# graph_tool -- a general graph manipulation python module
#
Tiago Peixoto's avatar
Tiago Peixoto committed
6
# Copyright (C) 2006-2020 Tiago de Paula Peixoto <tiago@skewed.de>
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#
# 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/>.

from __future__ import division, absolute_import, print_function
import sys
if sys.version_info < (3,):
    range = xrange

26
27
from .. import _degree, _prop, Graph, GraphView, libcore, _get_rng, \
    PropertyMap, edge_endpoint_property
28
29
30
31
32
33
34
35

from .. dl_import import dl_import
dl_import("from . import libgraph_tool_inference as libinference")

from . blockmodel import *
from . nested_blockmodel import *
from . blockmodel import _bm_test

36
37
import collections

38
def get_uentropy_args(kargs):
39
    ea = get_entropy_args(kargs, ignore=["latent_edges", "density"])
40
41
    uea = libinference.uentropy_args(ea)
    uea.latent_edges = kargs.get("latent_edges", True)
42
    uea.density = kargs.get("density", True)
43
44
    return uea

45
class UncertainBaseState(object):
46
47
    r"""Base state for uncertain network inference."""

48
    def __init__(self, g, nested=True, state_args={}, bstate=None,
49
                 self_loops=False, init_empty=False):
50
51
52
53

        self.g = g

        if bstate is None:
54
55
56
            if init_empty:
                self.u = Graph(directed=g.is_directed())
                self.u.add_vertex(g.num_vertices())
57
58
59
60
61
                self.eweight = self.u.new_ep("int", val=1)
            elif "g" in state_args:
                self.u = state_args.pop("g")
                self.eweight = state_args.pop("eweight",
                                              self.u.new_ep("int", val=1))
62
63
            else:
                self.u = g.copy()
64
                self.eweight = self.u.new_ep("int", val=1)
65
66
67
68
69
70
        else:
            self.u = bstate.g
            if nested:
                self.eweight = bstate.levels[0].eweight
            else:
                self.eweight = bstate.eweight
71
        self.u.set_fast_edge_removal()
72
73
74
75
76
77
78
79
80
81

        self.self_loops = self_loops
        N = self.u.num_vertices()
        if self.u.is_directed():
            if self_loops:
                M = N * N
            else:
                M = N * (N - 1)
        else:
            if self_loops:
82
                M = (N * (N + 1)) / 2
83
            else:
84
                M = (N * (N - 1)) / 2
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

        self.M = M

        if bstate is None:
            if nested:
                state_args["state_args"] = state_args.get("state_args", {})
                state_args["state_args"]["eweight"] = self.eweight
                state_args["sampling"] = True
                self.nbstate = NestedBlockState(self.u, **dict(state_args,
                                                               sampling=True))
                self.bstate = self.nbstate.levels[0]
            else:
                self.nbstate = None
                self.bstate = BlockState(self.u, eweight=self.eweight,
                                         **state_args)
        else:
            if nested:
                self.nbstate = bstate
                self.bstate = bstate.levels[0]
            else:
                self.nbstate = None
                self.bstate = bstate

108
        edges = self.g.get_edges()
109
110
111
112
113
114
        edges = numpy.concatenate((edges,
                                   numpy.ones(edges.shape,
                                              dtype=edges.dtype) * (N + 1)))
        self.slist = Vector_size_t(init=edges[:,0])
        self.tlist = Vector_size_t(init=edges[:,1])

115
116
        init_q_cache()

117
    def get_block_state(self):
118
119
120
121
122
123
124
125
        """Return the underlying block state, which can be either
        :class:`~graph_tool.inference.blockmodel.BlockState` or
        :class:`~graph_tool.inference.nested_blockmodel.NestedBlockState`.
        """
        if self.nbstate is None:
            return self.bstate
        else:
            return self.nbstate
126

127
    def entropy(self, latent_edges=True, density=True, **kwargs):
128
        """Return the entropy, i.e. negative log-likelihood."""
129
        S = self._state.entropy(latent_edges, density)
130
        if self.nbstate is None:
131
            S += self.bstate.entropy(**kwargs)
132
        else:
133
            S += self.nbstate.entropy(**kwargs)
134
135

        if kwargs.get("test", True) and _bm_test():
136
            args = kwargs.copy()
137
138
139
140
141
142
143
144
145
146
147
            assert not isnan(S) and not isinf(S), \
                "invalid entropy %g (%s) " % (S, str(args))
            args["test"] = False
            state_copy = self.copy()
            Salt = state_copy.entropy(latent_edges, density, **args)

            assert math.isclose(S, Salt, abs_tol=1e-8), \
                "entropy discrepancy after copying (%g %g %g)" % (S, Salt,
                                                                  S - Salt)
        return S

148
149
150
151
152
153
154
155
156
    def virtual_remove_edge(self, u, v, entropy_args={}):
        dentropy_args = dict(self.bstate._entropy_args, **entropy_args)
        entropy_args = get_uentropy_args(dentropy_args)
        return self._state.remove_edge_dS(int(u), int(v), entropy_args)

    def virtual_add_edge(self, u, v, entropy_args={}):
        dentropy_args = dict(self.bstate._entropy_args, **entropy_args)
        entropy_args = get_uentropy_args(dentropy_args)
        return self._state.add_edge_dS(int(u), int(v), entropy_args)
157
158

    def _algo_sweep(self, algo, r=.5, **kwargs):
159
        kwargs = kwargs.copy()
160
161
        beta = kwargs.get("beta", 1.)
        niter = kwargs.get("niter", 1)
162
        edges_only = kwargs.pop("edges_only", False)
163
164
165
166
167
        verbose = kwargs.get("verbose", False)
        slist = self.slist
        tlist = self.tlist
        dentropy_args = dict(self.bstate._entropy_args,
                             **kwargs.get("entropy_args", {}))
168
        entropy_args = get_uentropy_args(dentropy_args)
169
170
        kwargs.get("entropy_args", {}).pop("latent_edges", None)
        kwargs.get("entropy_args", {}).pop("density", None)
171
        state = self._state
172
173
174
175
176
177

        mcmc_state = DictState(dict(kwargs, **locals()))

        kwargs.pop("xlog", None)
        kwargs.pop("xstep", None)
        kwargs.pop("xdefault", None)
178
179
180
181

        if _bm_test():
            Si = self.entropy(**dentropy_args)

182
183
184
185
186
187
188
189
190
        if self.nbstate is None:
            self.bstate._clear_egroups()
        else:
            self.nbstate._clear_egroups()
        if numpy.random.random() < r:
            edges = True
            dS, nattempts, nmoves = self._mcmc_sweep(mcmc_state)
        else:
            edges = False
191
            if self.nbstate is None:
192
                dS, nattempts, nmoves = algo(self.bstate, **kwargs)
193
            else:
194
195
196
197
198
199
200
                dS, nattempts, nmoves = algo(self.nbstate, **kwargs)

        if _bm_test():
            Sf = self.entropy(**dentropy_args)
            assert math.isclose(dS, (Sf - Si), abs_tol=1e-8), \
                "inconsistent entropy delta %g (%g): %s %s" % (dS, Sf - Si, edges,
                                                               str(dentropy_args))
201
202
203

        return dS, nattempts, nmoves

204
    def mcmc_sweep(self, r=.5, multiflip=True, **kwargs):
205
        r"""Perform sweeps of a Metropolis-Hastings acceptance-rejection sampling MCMC to
206
207
208
209
210
211
        sample network partitions and latent edges. The parameter ``r`` controls
        the probability with which edge move will be attempted, instead of
        partition moves. The remaining keyword parameters will be passed to
        :meth:`~graph_tool.inference.blockmodel.BlockState.mcmc_sweep` or
        :meth:`~graph_tool.inference.blockmodel.BlockState.multiflip_mcmc_sweep`,
        if ``multiflip=True``.
212
213
        """

214
215
216
217
218
219
        if multiflip:
            return self._algo_sweep(lambda s, **kw: s.multiflip_mcmc_sweep(**kw),
                                    r=r, **kwargs)
        else:
            return self._algo_sweep(lambda s, **kw: s.mcmc_sweep(**kw),
                                    r=r, **kwargs)
220

221
222
223
    def multiflip_mcmc_sweep(self, **kwargs):
        r"""Alias for :meth:`~UncertainBaseState.mcmc_sweep` with ``multiflip=True``."""
        return self.mcmc_sweep(multiflip=True, **kwargs)
224
225

    def get_edge_prob(self, u, v, entropy_args={}, epsilon=1e-8):
226
        r"""Return conditional posterior log-probability of edge :math:`(u,v)`."""
227
        entropy_args = dict(self.bstate._entropy_args, **entropy_args)
228
        ea = get_uentropy_args(entropy_args)
229
        return self._state.get_edge_prob(u, v, ea, epsilon)
230

231
    def get_edges_prob(self, elist, entropy_args={}, epsilon=1e-8):
232
        r"""Return conditional posterior log-probability of an edge list, with
233
234
        shape :math:`(E,2)`."""
        entropy_args = dict(self.bstate._entropy_args, **entropy_args)
235
        ea = get_uentropy_args(entropy_args)
236
237
238
239
        elist = numpy.asarray(elist, dtype="uint64")
        probs = numpy.zeros(elist.shape[0])
        self._state.get_edges_prob(elist, probs, ea, epsilon)
        return probs
240

241
242
243
244
245
246
247
248
249
250
251
    def get_graph(self):
        r"""Return the current inferred graph."""
        if self.self_loops:
            u = GraphView(self.u, efilt=self.eweight.fa > 0)
        else:
            es = edge_endpoint_property(self.u, self.u.vertex_index, "source")
            et = edge_endpoint_property(self.u, self.u.vertex_index, "target")
            u = GraphView(self.u, efilt=numpy.logical_and(self.eweight.fa > 0,
                                                          es.fa != et.fa))
        return u

252
253
254
255
256
257
    def collect_marginal(self, g=None):
        r"""Collect marginal inferred network during MCMC runs.

        Parameters
        ----------
        g : :class:`~graph_tool.Graph` (optional, default: ``None``)
258
            Previous marginal graph.
259
260
261
262

        Returns
        -------
        g : :class:`~graph_tool.Graph`
263
            New marginal graph, with internal edge :class:`~graph_tool.EdgePropertyMap`
264
265
266
267
            ``"eprob"``, containing the marginal probabilities for each edge.

        Notes
        -----
268
        The posterior marginal probability of an edge :math:`(i,j)` is defined as
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287

        .. math::

           \pi_{ij} = \sum_{\boldsymbol A}A_{ij}P(\boldsymbol A|\boldsymbol D)

        where :math:`P(\boldsymbol A|\boldsymbol D)` is the posterior
        probability given the data.

        """

        if g is None:
            g = Graph(directed=self.g.is_directed())
            g.add_vertex(self.g.num_vertices())
            g.gp.count = g.new_gp("int", 0)
            g.ep.count = g.new_ep("int")

        if "eprob" not in g.ep:
            g.ep.eprob = g.new_ep("double")

288
        u = self.get_graph()
289
        libinference.collect_marginal(g._Graph__graph,
290
                                      u._Graph__graph,
291
292
293
294
295
296
                                      _prop("e", g, g.ep.count))
        g.gp.count += 1
        g.ep.eprob.fa = g.ep.count.fa
        g.ep.eprob.fa /= g.gp.count
        return g

297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
    def collect_marginal_multigraph(self, g=None):
        r"""Collect marginal latent multigraph during MCMC runs.

        Parameters
        ----------
        g : :class:`~graph_tool.Graph` (optional, default: ``None``)
            Previous marginal multigraph.

        Returns
        -------
        g : :class:`~graph_tool.Graph`
            New marginal graph, with internal edge
            :class:`~graph_tool.EdgePropertyMap` ``"w"`` and ``"wcount"``,
            containing the edge multiplicities and their respective counts.

        Notes
        -----

        The mean posterior marginal multiplicity distribution of a multi-edge
        :math:`(i,j)` is defined as

        .. math::

           \pi_{ij}(w) = \sum_{\boldsymbol G}\delta_{w,G_{ij}}P(\boldsymbol G|\boldsymbol D)

        where :math:`P(\boldsymbol G|\boldsymbol D)` is the posterior
        probability of a multigraph :math:`\boldsymbol G` given the data.

        """

        if g is None:
            g = Graph(directed=self.g.is_directed())
            g.add_vertex(self.g.num_vertices())
            g.ep.w = g.new_ep("vector<int>")
            g.ep.wcount = g.new_ep("vector<int>")

        libinference.collect_marginal_count(g._Graph__graph,
                                            self.u._Graph__graph,
                                            _prop("e", self.u, self.eweight),
                                            _prop("e", g, g.ep.w),
                                            _prop("e", g, g.ep.wcount))
        return g

340
class UncertainBlockState(UncertainBaseState):
341
342
    r"""Inference state of an uncertain graph, using the stochastic block model as a
    prior.
343
344
345
346

    Parameters
    ----------
    g : :class:`~graph_tool.Graph`
347
        Measured graph.
348
    q : :class:`~graph_tool.EdgePropertyMap`
349
350
351
352
353
354
355
        Edge probabilities in range :math:`[0,1]`.
    q_default : ``float`` (optional, default: ``0.``)
        Non-edge probability in range :math:`[0,1]`.
    aE : ``float`` (optional, default: ``NaN``)
        Expected total number of edges used in prior. If ``NaN``, a flat
        prior will be used instead.
    nested : ``boolean`` (optional, default: ``True``)
356
        If ``True``, a :class:`~graph_tool.inference.nested_blockmodel.NestedBlockState`
357
        will be used, otherwise
358
        :class:`~graph_tool.inference.blockmodel.BlockState`.
359
360
    state_args : ``dict`` (optional, default: ``{}``)
        Arguments to be passed to
361
362
363
        :class:`~graph_tool.inference.nested_blockmodel.NestedBlockState` or
        :class:`~graph_tool.inference.blockmodel.BlockState`.
    bstate : :class:`~graph_tool.inference.nested_blockmodel.NestedBlockState` or :class:`~graph_tool.inference.blockmodel.BlockState`  (optional, default: ``None``)
364
365
366
367
368
369
        If passed, this will be used to initialize the block state
        directly.
    self_loops : bool (optional, default: ``False``)
        If ``True``, it is assumed that the uncertain graph can contain
        self-loops.

370
371
    References
    ----------
372
373
374
    .. [peixoto-reconstructing-2018] Tiago P. Peixoto, "Reconstructing
       networks with unknown and heterogeneous errors", Phys. Rev. X 8
       041011 (2018). :doi:`10.1103/PhysRevX.8.041011`, :arxiv:`1806.07956`
375
376
    """

377
    def __init__(self, g, q, q_default=0., aE=numpy.nan, nested=True, state_args={},
378
                 bstate=None, self_loops=False, **kwargs):
379
380
381
382

        super(UncertainBlockState, self).__init__(g, nested=nested,
                                                  state_args=state_args,
                                                  bstate=bstate,
383
384
                                                  self_loops=self_loops,
                                                  **kwargs)
385
386
387
        self._q = q
        self._q_default = q_default

388
        self.p = (q.fa.sum() + (self.M - g.num_edges()) * q_default) / self.M
389
390

        self.q = self.g.new_ep("double", vals=log(q.fa) - log1p(-q.fa))
391
        self.q.fa -= log(self.p) - log1p(-self.p)
392
393
394
395
396
397
398
399
400
401
        if q_default > 0:
            self.q_default = log(q_default) - log1p(q_default)
            self.q_default -= log(self.p) - log1p(-self.p)
        else:
            self.q_default = -numpy.inf

        self.S_const = (log1p(-q.fa[q.fa<1]).sum() +
                        log1p(-q_default) * (self.M - self.g.num_edges())
                        - self.M * log1p(-self.p))

402
403
        self.aE = aE
        if numpy.isnan(aE):
404
405
406
            self.E_prior = False
        else:
            self.E_prior = True
407
408
409
410
411

        self._state = libinference.make_uncertain_state(self.bstate._state,
                                                        self)
    def __getstate__(self):
        return dict(g=self.g, q=self._q, q_default=self._q_default,
412
                    aE=self.aE, nested=self.nbstate is not None,
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
                    bstate=(self.nbstate.copy() if self.nbstate is not None else
                            self.bstate.copy()), self_loops=self.self_loops)

    def __setstate__(self, state):
        self.__init__(**state)

    def copy(self, **kwargs):
        """Return a copy of the state."""
        return UncertainBlockState(**dict(self.__getstate__(), **kwargs))

    def __copy__(self):
        return self.copy()

    def __repr__(self):
        return "<UncertainBlockState object with %s, at 0x%x>" % \
            (self.nbstate if self.nbstate is not None else self.bstate,
             id(self))

    def _mcmc_sweep(self, mcmc_state):
        return libinference.mcmc_uncertain_sweep(mcmc_state,
                                                 self._state,
                                                 _get_rng())

436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
class LatentMultigraphBlockState(UncertainBaseState):
    r"""Inference state of an erased Poisson multigraph, using the stochastic
    block model as a prior.

    Parameters
    ----------
    g : :class:`~graph_tool.Graph`
        Measured graph.
    aE : ``float`` (optional, default: ``NaN``)
        Expected total number of edges used in prior. If ``NaN``, a flat
        prior will be used instead.
    nested : ``boolean`` (optional, default: ``True``)
        If ``True``, a :class:`~graph_tool.inference.nested_blockmodel.NestedBlockState`
        will be used, otherwise
        :class:`~graph_tool.inference.blockmodel.BlockState`.
    state_args : ``dict`` (optional, default: ``{}``)
        Arguments to be passed to
        :class:`~graph_tool.inference.nested_blockmodel.NestedBlockState` or
        :class:`~graph_tool.inference.blockmodel.BlockState`.
    bstate : :class:`~graph_tool.inference.nested_blockmodel.NestedBlockState` or :class:`~graph_tool.inference.blockmodel.BlockState`  (optional, default: ``None``)
        If passed, this will be used to initialize the block state
        directly.
    self_loops : bool (optional, default: ``False``)
        If ``True``, it is assumed that the uncertain graph can contain
        self-loops.

    References
    ----------
Tiago Peixoto's avatar
Tiago Peixoto committed
464
465
    .. [peixoto-latent-2020] Tiago P. Peixoto, "Latent Poisson models for
       networks with heterogeneous density", :arxiv:`2002.07803`
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
    """

    def __init__(self, g, aE=numpy.nan, nested=True, state_args={},
                 bstate=None, self_loops=False, **kwargs):

        super(LatentMultigraphBlockState, self).__init__(g, nested=nested,
                                                         state_args=state_args,
                                                         bstate=bstate,
                                                         self_loops=self_loops,
                                                         **kwargs)

        self.q = self.g.new_ep("double", val=numpy.inf)
        self.q_default = -numpy.inf
        self.S_const = 0

        self.aE = aE
        if numpy.isnan(aE):
            self.E_prior = False
        else:
            self.E_prior = True

        self._state = libinference.make_uncertain_state(self.bstate._state,
                                                        self)
    def __getstate__(self):
        return dict(g=self.g, aE=self.aE, nested=self.nbstate is not None,
                    bstate=(self.nbstate.copy() if self.nbstate is not None else
                            self.bstate.copy()), self_loops=self.self_loops)

    def __setstate__(self, state):
        self.__init__(**state)

    def copy(self, **kwargs):
        """Return a copy of the state."""
        return LatentMultigraphBlockState(**dict(self.__getstate__(), **kwargs))

    def __copy__(self):
        return self.copy()

    def __repr__(self):
        return "<LatentMultigraphBlockState object with %s, at 0x%x>" % \
            (self.nbstate if self.nbstate is not None else self.bstate,
             id(self))

    def _mcmc_sweep(self, mcmc_state):
        mcmc_state.edges_only = True
        return libinference.mcmc_uncertain_sweep(mcmc_state,
                                                 self._state,
                                                 _get_rng())

515
class MeasuredBlockState(UncertainBaseState):
516
517
    r"""Inference state of a measured graph, using the stochastic block model as a
    prior.
518
519
520
521

    Parameters
    ----------
    g : :class:`~graph_tool.Graph`
522
        Measured graph.
523
    n : :class:`~graph_tool.EdgePropertyMap`
524
525
        Edge property map of type ``int``, containing the total number of
        measurements for each edge.
526
    x : :class:`~graph_tool.EdgePropertyMap`
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
        Edge property map of type ``int``, containing the number of
        positive measurements for each edge.
    n_default : ``int`` (optional, default: ``1``)
        Total number of measurements for each non-edge.
    x_default : ``int`` (optional, default: ``1``)
        Total number of positive measurements for each non-edge.
    fn_params : ``dict`` (optional, default: ``dict(alpha=1, beta=1)``)
        Beta distribution hyperparameters for the probability of missing
        edges (false negatives).
    fp_params : ``dict`` (optional, default: ``dict(mu=1, nu=1)``)
        Beta distribution hyperparameters for the probability of spurious
        edges (false positives).
    aE : ``float`` (optional, default: ``NaN``)
        Expected total number of edges used in prior. If ``NaN``, a flat
        prior will be used instead.
    nested : ``boolean`` (optional, default: ``True``)
543
        If ``True``, a :class:`~graph_tool.inference.nested_blockmodel.NestedBlockState`
544
        will be used, otherwise
545
        :class:`~graph_tool.inference.blockmodel.BlockState`.
546
547
    state_args : ``dict`` (optional, default: ``{}``)
        Arguments to be passed to
548
549
550
        :class:`~graph_tool.inference.nested_blockmodel.NestedBlockState` or
        :class:`~graph_tool.inference.blockmodel.BlockState`.
    bstate : :class:`~graph_tool.inference.nested_blockmodel.NestedBlockState` or :class:`~graph_tool.inference.blockmodel.BlockState`  (optional, default: ``None``)
551
552
553
554
555
        If passed, this will be used to initialize the block state
        directly.
    self_loops : bool (optional, default: ``False``)
        If ``True``, it is assumed that the uncertain graph can contain
        self-loops.
556
557
558

    References
    ----------
559
560
561
    .. [peixoto-reconstructing-2018] Tiago P. Peixoto, "Reconstructing
       networks with unknown and heterogeneous errors", Phys. Rev. X 8
       041011 (2018). :doi:`10.1103/PhysRevX.8.041011`, :arxiv:`1806.07956`
562
563
    """

564
565
    def __init__(self, g, n, x, n_default=1, x_default=0,
                 fn_params=dict(alpha=1, beta=1), fp_params=dict(mu=1, nu=1),
566
                 aE=numpy.nan, nested=True, state_args={}, bstate=None,
567
                 self_loops=False, **kwargs):
568
569
570

        super(MeasuredBlockState, self).__init__(g, nested=nested,
                                                 state_args=state_args,
571
                                                 bstate=bstate, **kwargs)
572

573
574
        self.aE = aE
        if numpy.isnan(aE):
575
576
577
            self.E_prior = False
        else:
            self.E_prior = True
578
579
580
581
582

        self.n = n
        self.x = x
        self.n_default = n_default
        self.x_default = x_default
583
584
585
586
        self.alpha = fn_params.get("alpha", 1)
        self.beta = fn_params.get("beta", 1)
        self.mu = fp_params.get("mu", 1)
        self.nu = fp_params.get("nu", 1)
587
588
589
590
591
592
593

        self._state = libinference.make_measured_state(self.bstate._state,
                                                       self)

    def __getstate__(self):
        return dict(g=self.g, n=self.n, x=self.x, n_default=self.n_default,
                    x_default=self.x_default,
594
                    fn_params=dict(alpha=self.alpha, beta=self.beta),
595
                    fp_params=dict(mu=self.mu, nu=self.nu), aE=self.aE,
596
                    nested=self.nbstate is not None,
597
598
                    bstate=(self.nbstate if self.nbstate is not None
                            else self.bstate), self_loops=self.self_loops)
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618

    def __setstate__(self, state):
        self.__init__(**state)

    def copy(self, **kwargs):
        """Return a copy of the state."""
        return MeasuredBlockState(**dict(self.__getstate__(), **kwargs))

    def __repr__(self):
        return "<MeasuredBlockState object with %s, at 0x%x>" % \
            (self.nbstate if self.nbstate is not None else self.bstate,
             id(self))

    def _mcmc_sweep(self, mcmc_state):
        return libinference.mcmc_measured_sweep(mcmc_state,
                                                self._state,
                                                _get_rng())

    def set_hparams(self, alpha, beta, mu, nu):
        """Set edge and non-edge hyperparameters."""
619
        self._state.set_hparams(alpha, beta, mu, nu)
620
621
622
623
624
625
        self.alpha = alpha
        self.beta = beta
        self.mu = mu
        self.nu = nu

    def get_p_posterior(self):
626
        """Get beta distribution parameters for the posterior probability of missing edges."""
627
628
        T = self._state.get_T()
        M = self._state.get_M()
629
        return M - T + self.alpha, T + self.beta
630
631

    def get_q_posterior(self):
632
        """Get beta distribution parameters for the posterior probability of spurious edges."""
633
634
635
636
        N = self._state.get_N()
        X = self._state.get_X()
        T = self._state.get_T()
        M = self._state.get_M()
637
        return X - T + self.mu, N - X - (M - T) + self.nu
638
639

class MixedMeasuredBlockState(UncertainBaseState):
640
    r"""Inference state of a measured graph with heterogeneous errors, using the
641
642
643
644
645
    stochastic block model as a prior.

    Parameters
    ----------
    g : :class:`~graph_tool.Graph`
646
        Measured graph.
647
    n : :class:`~graph_tool.EdgePropertyMap`
648
649
        Edge property map of type ``int``, containing the total number of
        measurements for each edge.
650
    x : :class:`~graph_tool.EdgePropertyMap`
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
        Edge property map of type ``int``, containing the number of
        positive measurements for each edge.
    n_default : ``int`` (optional, default: ``1``)
        Total number of measurements for each non-edge.
    x_default : ``int`` (optional, default: ``1``)
        Total number of positive measurements for each non-edge.
    fn_params : ``dict`` (optional, default: ``dict(alpha=1, beta=10)``)
        Beta distribution hyperparameters for the probability of missing
        edges (false negatives).
    fp_params : ``dict`` (optional, default: ``dict(mu=1, nu=10)``)
        Beta distribution hyperparameters for the probability of spurious
        edges (false positives).
    aE : ``float`` (optional, default: ``NaN``)
        Expected total number of edges used in prior. If ``NaN``, a flat
        prior will be used instead.
    nested : ``boolean`` (optional, default: ``True``)
667
        If ``True``, a :class:`~graph_tool.inference.nested_blockmodel.NestedBlockState`
668
        will be used, otherwise
669
        :class:`~graph_tool.inference.blockmodel.BlockState`.
670
671
    state_args : ``dict`` (optional, default: ``{}``)
        Arguments to be passed to
672
673
674
        :class:`~graph_tool.inference.nested_blockmodel.NestedBlockState` or
        :class:`~graph_tool.inference.blockmodel.BlockState`.
    bstate : :class:`~graph_tool.inference.nested_blockmodel.NestedBlockState` or :class:`~graph_tool.inference.blockmodel.BlockState`  (optional, default: ``None``)
675
676
677
678
679
680
        If passed, this will be used to initialize the block state
        directly.
    self_loops : bool (optional, default: ``False``)
        If ``True``, it is assumed that the uncertain graph can contain
        self-loops.

681
682
    References
    ----------
683
684
685
    .. [peixoto-reconstructing-2018] Tiago P. Peixoto, "Reconstructing
       networks with unknown and heterogeneous errors", Phys. Rev. X 8
       041011 (2018). :doi:`10.1103/PhysRevX.8.041011`, :arxiv:`1806.07956`
686
687
    """

688
689
    def __init__(self, g, n, x, n_default=1, x_default=0,
                 fn_params=dict(alpha=1, beta=10), fp_params=dict(mu=1, nu=10),
690
                 aE=numpy.nan, nested=True, state_args={}, bstate=None,
691
                 self_loops=False, **kwargs):
692
693
694

        super(MixedMeasuredBlockState, self).__init__(g, nested=nested,
                                                      state_args=state_args,
695
                                                      bstate=bstate, **kwargs)
696
697
        self.aE = aE
        if numpy.isnan(aE):
698
699
700
701
702
703
704
705
706
            self.E_prior = False
        else:
            self.E_prior = True

        self.n = n
        self.x = x
        self.n_default = n_default
        self.x_default = x_default
        self.alpha = fn_params.get("alpha", 1)
707
        self.beta = fn_params.get("beta", 10)
708
        self.mu = fp_params.get("mu", 1)
709
        self.nu = fp_params.get("nu", 10)
710
711
712
713
714
715
716
717
718
719
720

        self._state = None

        self.q = self.g.new_ep("double")
        self.sync_q()

        self._state = libinference.make_uncertain_state(self.bstate._state,
                                                        self)

    def sync_q(self):
        ra, rb = self.transform(self.n.fa, self.x.fa)
721
        self.q.fa = ra - rb
722
        dra, drb = self.transform(self.n_default, self.x_default)
723
        self.q_default = dra - drb
724

725
        self.S_const = (self.M - self.g.num_edges()) * drb + rb.sum()
726
727
728
729
730
731

        if self._state is not None:
            self._state.set_q_default(self.q_default)
            self._state.set_S_const(self.S_const)

    def transform(self, na, xa):
732
733
734
735
        ra = (scipy.special.betaln(na - xa + self.alpha, xa + self.beta) -
              scipy.special.betaln(self.alpha, self.beta))
        rb = (scipy.special.betaln(xa + self.mu, na - xa + self.nu) -
              scipy.special.betaln(self.mu, self.nu))
736
737
738
739
740
741
742
743
744
745
746
747
748
        return ra, rb

    def set_hparams(self, alpha, beta, mu, nu):
        """Set edge and non-edge hyperparameters."""
        self.alpha = alpha
        self.beta = beta
        self.mu = mu
        self.nu = nu
        self.sync_q()

    def __getstate__(self):
        return dict(g=self.g, n=self.n, x=self.x, n_default=self.n_default,
                    x_default=self.x_default,
749
                    fn_params=dict(alpha=self.alpha, beta=self.beta),
750
                    fp_params=dict(mu=self.mu, nu=self.nu), aE=self.aE,
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
                    nested=self.nbstate is not None,
                    bstate=(self.nbstate if self.nbstate is not None
                            else self.bstate), self_loops=self.self_loops)

    def __setstate__(self, state):
        self.__init__(**state)

    def copy(self, **kwargs):
        """Return a copy of the state."""
        return MixedMeasuredBlockState(**dict(self.__getstate__(), **kwargs))

    def __copy__(self):
        return self.copy()

    def __setstate__(self, state):
        self.__init__(**state)

    def __repr__(self):
        return "<MixedMeasuredBlockState object with %s, at 0x%x>" % \
            (self.nbstate if self.nbstate is not None else self.bstate,
             id(self))

773
774
775
776
777
778
779
780
781
782
783
784
785
786
    def mcmc_sweep(self, r=.5, h=.1, hstep=1, multiflip=True, **kwargs):
        r"""Perform sweeps of a Metropolis-Hastings acceptance-rejection sampling MCMC to
        sample network partitions and latent edges. The parameter ``r`` controls
        the probability with which edge move will be attempted, instead of
        partition moves. The parameter ``h`` controls the relative probability
        with which hyperparamters moves will be attempted, and ``hstep`` is the
        size of the step.

        The remaining keyword parameters will be passed to
        :meth:`~graph_tool.inference.blockmodel.BlockState.mcmc_sweep` or
        :meth:`~graph_tool.inference.blockmodel.BlockState.multiflip_mcmc_sweep`,
        if ``multiflip=True``.
        """

787
788
789
790
        return super(MixedMeasuredBlockState, self).mcmc_sweep(r=r,
                                                               multiflip=multiflip,
                                                               h=h, hstep=hstep,
                                                               **kwargs)
791

792
    def _algo_sweep(self, algo, r=.5, h=.1, hstep=1, niter=1, **kwargs):
793
        if numpy.random.random() < h:
794
795
796
797
            dS = nt = nm = 0
            for i in range(niter):
                hs = [self.alpha, self.beta, self.mu, self.nu]
                j = numpy.random.randint(len(hs))
798

799
800
                f_dh = [max(0, hs[j] - hstep), hs[j] + hstep]
                pf = 1./(f_dh[1] - f_dh[0])
801

802
803
                old_hs = hs[j]
                hs[j] = f_dh[0] + numpy.random.random() * (f_dh[1] - f_dh[0])
804

805
806
                b_dh = [max(0, hs[j] - hstep), hs[j] + hstep]
                pb = 1./min(1, hs[j])
807

808
809
                latent_edges = kwargs.get("entropy_args", {}).get("latent_edges", True)
                density = False
810

811
                Sb = self._state.entropy(latent_edges, density)
812
                self.set_hparams(*hs)
813
814
815
816
817
818
819
820
821
822
                Sa = self._state.entropy(latent_edges, density)

                nt += 1
                if Sa < Sb or numpy.random.random() < exp(-(Sa-Sb) + log(pb) - log(pf)):
                    dS += Sa - Sb
                    nm +=1
                else:
                    hs[j] = old_hs
                    self.set_hparams(*hs)
            return (dS, nt, nm)
823
        else:
824
825
826
            return super(MixedMeasuredBlockState, self)._algo_sweep(algo, r,
                                                                    niter=niter,
                                                                    **kwargs)
827
828
829
830
831

    def _mcmc_sweep(self, mcmc_state):
        return libinference.mcmc_uncertain_sweep(mcmc_state,
                                                 self._state,
                                                 _get_rng())
832
833
834
835
836

class DynamicsBlockStateBase(UncertainBaseState):
    def __init__(self, g, s, t, x=None, aE=numpy.nan, nested=True,
                 state_args={}, bstate=None, self_loops=False,
                 **kwargs):
837
838
839
840
        r"""Base state for network reconstruction based on dynamical data, using
        the stochastic block model as a prior. This class is not meant to be
        instantiated directly, only indirectly via one of its subclasses."""

841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
        super(DynamicsBlockStateBase, self).__init__(g, nested=nested,
                                                     state_args=state_args,
                                                     bstate=bstate,
                                                     self_loops=self_loops)
        self.s = [g.own_property(x) for x in s]
        self.t = [g.own_property(x) for x in t]
        if x is None:
            x = self.u.new_ep("double")
        else:
            x = self.u.copy_property(x, g=x.get_graph())
        self.x = x

        self.aE = aE
        if numpy.isnan(aE):
            self.E_prior = False
        else:
            self.E_prior = True

        for k in kwargs.keys():
            v = kwargs[k]
            if isinstance(v, PropertyMap):
                kwargs[k] = g.own_property(v)
            elif (isinstance(v, collections.Iterable) and len(v) > 0 and
                  isinstance(v[0], PropertyMap)):
                kwargs[k] = [g.own_property(x) for x in v]
        self.params = kwargs
        self.os = [ns._get_any() for ns in s]
        self.ot = [nt._get_any() for nt in t]
        self._state = self._make_state()

    def set_params(self, params):
872
        r"""Sets the model parameters via the dictionary ``params``."""
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
        self.params = dict(self.params, **params)
        self._state.set_params(self.params)

    def __getstate__(self):
        return dict(g=self.g, s=self.s, t=self.t, x=self.x, aE=self.aE,
                    nested=self.nbstate is not None,
                    bstate=(self.nbstate.copy() if self.nbstate is not None else
                            self.bstate.copy()), self_loops=self.self_loops,
                    **self.params)

    def __setstate__(self, state):
        self.__init__(**state)

    def copy(self, **kwargs):
        """Return a copy of the state."""
        return type(self)(**dict(self.__getstate__(), **kwargs))

    def __copy__(self):
        return self.copy()

    def __repr__(self):
        return "<%s object with %s, at 0x%x>" % \
            (self.__class__.__name__,
             self.nbstate if self.nbstate is not None else self.bstate,
             id(self))

    def _move_proposal(self, name, beta, step, rg, transform, entropy_args):
        x = x_orig = self.params[name]

        if isinstance(x, collections.Iterable):
            idx = numpy.random.randint(len(x))
            x = x[idx]
        else:
            idx = None

        if transform is not None:
            x = transform[1](x)

        if rg is not None:
            mi = max(rg[0], x - step)
            ma = min(rg[1], x + step)
        else:
            mi = x - step
            ma = x + step
        nx = numpy.random.random() * (ma - mi) + mi

        a = 0
        if rg is not None:
            a -= -log(ma - mi)
            mi = max(rg[0], nx - step)
            ma = min(rg[1], nx + step)
            a += -log(ma - mi)

        if transform is not None:
            nx = transform[0](nx)

        latent_edges = entropy_args.get("latent_edges", True)
        density = False

        Sb = self._state.entropy(latent_edges, density)

        if idx is not None:
            y = self.params[name]
            y[idx] = nx
            nx = y

        self.set_params({name:nx})
        Sa = self._state.entropy(latent_edges, density)

        a += beta * (Sb - Sa)

        if a > 0 or numpy.random.random() < exp(a):
            self.set_params({name:nx})
            return Sa-Sb, 1, 1

        if idx is not None:
            y = self.params[name]
            y[idx] = x_orig
            x_orig = y
        self.set_params({name:x_orig})

        return 0, 0, 0

    def get_x(self):
957
958
        """Return latent edge covariates."""
        return self.x
959
960

    def get_edge_prob(self, u, v, x, entropy_args={}, epsilon=1e-8):
961
        r"""Return conditional posterior log-probability of edge :math:`(u,v)`."""
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
        entropy_args = dict(self.bstate._entropy_args, **entropy_args)
        ea = get_uentropy_args(entropy_args)
        return self._state.get_edge_prob(u, v, x, ea, epsilon)

    def collect_marginal(self, g=None):
        r"""Collect marginal inferred network during MCMC runs.

        Parameters
        ----------
        g : :class:`~graph_tool.Graph` (optional, default: ``None``)
            Previous marginal graph.

        Returns
        -------
        g : :class:`~graph_tool.Graph`
977
            New marginal graph, with internal edge :class:`~graph_tool.EdgePropertyMap`
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
            ``"eprob"``, containing the marginal probabilities for each edge.

        Notes
        -----
        The posterior marginal probability of an edge :math:`(i,j)` is defined as

        .. math::

           \pi_{ij} = \sum_{\boldsymbol A}A_{ij}P(\boldsymbol A|\boldsymbol D)

        where :math:`P(\boldsymbol A|\boldsymbol D)` is the posterior
        probability given the data.

        """

        if g is None:
            g = Graph(directed=self.g.is_directed())
            g.add_vertex(self.g.num_vertices())
            g.gp.count = g.new_gp("int", 0)
            g.ep.count = g.new_ep("int")
            g.ep.eprob = g.new_ep("double")

        if "x" not in g.ep:
For faster browsing, not all history is shown. View entire blame