uncertain_blockmodel.py 61.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
# This program is free software; you can redistribute it and/or modify it under
# the terms of the GNU Lesser General Public License as published by the Free
# Software Foundation; either version 3 of the License, or (at your option) any
# later version.
12
#
13
14
15
16
# 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 Lesser General Public License for more
# details.
17
#
18
19
# You should have received a copy of the GNU Lesser General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>.
20

Alex Henrie's avatar
Alex Henrie committed
21
22
from .. import _prop, Graph, GraphView, _get_rng, PropertyMap, \
    edge_endpoint_property
23
24
25
26
27
28
29
30

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

31
32
import collections

33
def get_uentropy_args(kargs):
34
    ea = get_entropy_args(kargs, ignore=["latent_edges", "density"])
35
36
    uea = libinference.uentropy_args(ea)
    uea.latent_edges = kargs.get("latent_edges", True)
37
    uea.density = kargs.get("density", True)
38
39
    return uea

40
class UncertainBaseState(object):
41
42
    r"""Base state for uncertain network inference."""

43
    def __init__(self, g, nested=True, state_args={}, bstate=None,
44
                 self_loops=False, init_empty=False):
45
46
47

        self.g = g

48
        state_args = dict(state_args)
49
        if bstate is None:
50
51
52
            if init_empty:
                self.u = Graph(directed=g.is_directed())
                self.u.add_vertex(g.num_vertices())
53
54
55
56
57
                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))
58
59
            else:
                self.u = g.copy()
60
                self.eweight = self.u.new_ep("int", val=1)
61
        else:
62
            self.u = bstate.g.copy()
63
64
65
66
            if nested:
                self.eweight = bstate.levels[0].eweight
            else:
                self.eweight = bstate.eweight
67
68
69
70
71
72
73
74
            self.eweight = self.u.own_property(self.eweight.copy())
            if nested:
                bstate = bstate.copy(g=self.u,
                                     state_args=dict(bstate.state_args,
                                                     eweight=self.eweight))
            else:
                bstate = bstate.copy(g=self.u, eweight=self.eweight)

75
        self.u.set_fast_edge_removal()
76
77
78
79
80
81
82
83
84
85

        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:
86
                M = (N * (N + 1)) / 2
87
            else:
88
                M = (N * (N - 1)) / 2
89
90
91
92
93

        self.M = M

        if bstate is None:
            if nested:
94
95
96
                state_args["state_args"] = state_args.get("state_args", {})
                state_args["state_args"].update(dict(eweight=self.eweight))
                self.nbstate = NestedBlockState(self.u, **state_args)
97
98
99
100
101
102
103
104
105
106
107
108
109
                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

110
        edges = self.g.get_edges()
111
112
113
114
115
116
        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])

117
118
        init_q_cache()

119
120
    def __getstate__(self):
        return dict(g=self.g, nested=self.nbstate is not None,
121
                    bstate=(self.nbstate if self.nbstate is not None else self.bstate),
122
123
124
125
126
                    self_loops=self.self_loops)

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

127
    def get_block_state(self):
128
129
130
131
132
133
134
135
        """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
136

137
    def entropy(self, latent_edges=True, density=True, **kwargs):
138
        """Return the entropy, i.e. negative log-likelihood."""
139
        S = self._state.entropy(latent_edges, density)
140
        if self.nbstate is None:
141
            S += self.bstate.entropy(**kwargs)
142
        else:
143
            S += self.nbstate.entropy(**kwargs)
144
145

        if kwargs.get("test", True) and _bm_test():
146
            args = kwargs.copy()
147
148
149
150
151
152
153
154
155
156
157
            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

158
159
160
161
162
163
164
165
166
    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)
167

168
169
170
171
172
    def set_state(self, g, w):
        if w.value_type() != "int32_t":
            w = w.copy("int32_t")
        self._state.set_state(g._Graph__graph, w._get_any())

173
    def _algo_sweep(self, algo, r=.5, **kwargs):
174
        kwargs = kwargs.copy()
175
176
        beta = kwargs.get("beta", 1.)
        niter = kwargs.get("niter", 1)
177
        edges_only = kwargs.pop("edges_only", False)
178
179
180
181
182
        verbose = kwargs.get("verbose", False)
        slist = self.slist
        tlist = self.tlist
        dentropy_args = dict(self.bstate._entropy_args,
                             **kwargs.get("entropy_args", {}))
183
        entropy_args = get_uentropy_args(dentropy_args)
184
185
        kwargs.get("entropy_args", {}).pop("latent_edges", None)
        kwargs.get("entropy_args", {}).pop("density", None)
186
        state = self._state
187
188
189
190
191
192

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

        kwargs.pop("xlog", None)
        kwargs.pop("xstep", None)
        kwargs.pop("xdefault", None)
193
194
195
196

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

197
198
199
200
201
202
203
204
205
        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
206
            if self.nbstate is None:
207
                dS, nattempts, nmoves = algo(self.bstate, **kwargs)
208
            else:
209
210
211
212
213
214
215
                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))
216
217
218

        return dS, nattempts, nmoves

219
    def mcmc_sweep(self, r=.5, multiflip=True, **kwargs):
220
        r"""Perform sweeps of a Metropolis-Hastings acceptance-rejection sampling MCMC to
221
222
223
224
225
226
        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``.
227
228
        """

229
230
231
232
233
234
        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)
235

236
237
238
    def multiflip_mcmc_sweep(self, **kwargs):
        r"""Alias for :meth:`~UncertainBaseState.mcmc_sweep` with ``multiflip=True``."""
        return self.mcmc_sweep(multiflip=True, **kwargs)
239
240

    def get_edge_prob(self, u, v, entropy_args={}, epsilon=1e-8):
241
        r"""Return conditional posterior log-probability of edge :math:`(u,v)`."""
242
        entropy_args = dict(self.bstate._entropy_args, **entropy_args)
243
        ea = get_uentropy_args(entropy_args)
244
        return self._state.get_edge_prob(u, v, ea, epsilon)
245

246
    def get_edges_prob(self, elist, entropy_args={}, epsilon=1e-8):
247
        r"""Return conditional posterior log-probability of an edge list, with
248
249
        shape :math:`(E,2)`."""
        entropy_args = dict(self.bstate._entropy_args, **entropy_args)
250
        ea = get_uentropy_args(entropy_args)
251
252
253
254
        elist = numpy.asarray(elist, dtype="uint64")
        probs = numpy.zeros(elist.shape[0])
        self._state.get_edges_prob(elist, probs, ea, epsilon)
        return probs
255

256
257
258
259
260
261
262
263
264
265
266
    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

267
268
269
270
271
272
    def collect_marginal(self, g=None):
        r"""Collect marginal inferred network during MCMC runs.

        Parameters
        ----------
        g : :class:`~graph_tool.Graph` (optional, default: ``None``)
273
            Previous marginal graph.
274
275
276
277

        Returns
        -------
        g : :class:`~graph_tool.Graph`
278
            New marginal graph, with internal edge :class:`~graph_tool.EdgePropertyMap`
279
280
281
282
            ``"eprob"``, containing the marginal probabilities for each edge.

        Notes
        -----
283
        The posterior marginal probability of an edge :math:`(i,j)` is defined as
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302

        .. 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")

303
        u = self.get_graph()
304
        libinference.collect_marginal(g._Graph__graph,
305
                                      u._Graph__graph,
306
307
308
309
310
311
                                      _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

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
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
    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

355
class UncertainBlockState(UncertainBaseState):
356
357
    r"""Inference state of an uncertain graph, using the stochastic block model as a
    prior.
358
359
360
361

    Parameters
    ----------
    g : :class:`~graph_tool.Graph`
362
        Measured graph.
363
    q : :class:`~graph_tool.EdgePropertyMap`
364
365
366
367
368
369
370
        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``)
371
        If ``True``, a :class:`~graph_tool.inference.nested_blockmodel.NestedBlockState`
372
        will be used, otherwise
373
        :class:`~graph_tool.inference.blockmodel.BlockState`.
374
375
    state_args : ``dict`` (optional, default: ``{}``)
        Arguments to be passed to
376
377
378
        :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``)
379
380
381
382
383
384
        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.

385
386
    References
    ----------
387
388
389
    .. [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`
390
391
    """

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

395
396
        super().__init__(g, nested=nested, state_args=state_args, bstate=bstate,
                         self_loops=self_loops, **kwargs)
397
398
399
        self._q = q
        self._q_default = q_default

400
        self.p = (q.fa.sum() + (self.M - g.num_edges()) * q_default) / self.M
401
402

        self.q = self.g.new_ep("double", vals=log(q.fa) - log1p(-q.fa))
403
        self.q.fa -= log(self.p) - log1p(-self.p)
404
405
406
407
408
409
410
411
412
413
        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))

414
415
        self.aE = aE
        if numpy.isnan(aE):
416
417
418
            self.E_prior = False
        else:
            self.E_prior = True
419
420
421
422

        self._state = libinference.make_uncertain_state(self.bstate._state,
                                                        self)
    def __getstate__(self):
423
        state = super().__getstate__()
424
425
        return dict(state,  q=self._q, q_default=self._q_default,
                    aE=self.aE)
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443

    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())

444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
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
472
473
    .. [peixoto-latent-2020] Tiago P. Peixoto, "Latent Poisson models for
       networks with heterogeneous density", :arxiv:`2002.07803`
474
475
476
477
478
    """

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

479
480
        super().__init__(g, nested=nested, state_args=state_args, bstate=bstate,
                         self_loops=self_loops, **kwargs)
481
482
483
484
485
486
487
488
489
490
491
492
493
494

        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):
495
        state = super().__getstate__()
496
        return dict(state, aE=self.aE)
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518

    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())

519
class MeasuredBlockState(UncertainBaseState):
520
521
    r"""Inference state of a measured graph, using the stochastic block model as a
    prior.
522
523
524
525

    Parameters
    ----------
    g : :class:`~graph_tool.Graph`
526
        Measured graph.
527
    n : :class:`~graph_tool.EdgePropertyMap`
528
529
        Edge property map of type ``int``, containing the total number of
        measurements for each edge.
530
    x : :class:`~graph_tool.EdgePropertyMap`
531
532
533
534
        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.
Tiago Peixoto's avatar
Tiago Peixoto committed
535
    x_default : ``int`` (optional, default: ``0``)
536
537
538
539
540
541
542
543
544
545
546
        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``)
547
        If ``True``, a :class:`~graph_tool.inference.nested_blockmodel.NestedBlockState`
548
        will be used, otherwise
549
        :class:`~graph_tool.inference.blockmodel.BlockState`.
550
551
    state_args : ``dict`` (optional, default: ``{}``)
        Arguments to be passed to
552
553
554
        :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``)
555
556
557
558
559
        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.
560
561
562

    References
    ----------
563
564
565
    .. [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`
566
567
    """

568
569
    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),
570
                 aE=numpy.nan, nested=True, state_args={}, bstate=None,
571
                 self_loops=False, **kwargs):
572

573
574
        super().__init__(g, nested=nested, state_args=state_args, bstate=bstate,
                         **kwargs)
575

576
577
        self.aE = aE
        if numpy.isnan(aE):
578
579
580
            self.E_prior = False
        else:
            self.E_prior = True
581
582
583
584
585

        self.n = n
        self.x = x
        self.n_default = n_default
        self.x_default = x_default
586
587
588
589
        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)
590
591
592
593
594

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

    def __getstate__(self):
595
        state = super().__getstate__()
596
        return dict(state, n=self.n, x=self.x, n_default=self.n_default,
597
                    x_default=self.x_default,
598
                    fn_params=dict(alpha=self.alpha, beta=self.beta),
599
                    fp_params=dict(mu=self.mu, nu=self.nu), aE=self.aE)
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616

    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."""
617
        self._state.set_hparams(alpha, beta, mu, nu)
618
619
620
621
622
623
        self.alpha = alpha
        self.beta = beta
        self.mu = mu
        self.nu = nu

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

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

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

    Parameters
    ----------
    g : :class:`~graph_tool.Graph`
644
        Measured graph.
645
    n : :class:`~graph_tool.EdgePropertyMap`
646
647
        Edge property map of type ``int``, containing the total number of
        measurements for each edge.
648
    x : :class:`~graph_tool.EdgePropertyMap`
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
        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``)
665
        If ``True``, a :class:`~graph_tool.inference.nested_blockmodel.NestedBlockState`
666
        will be used, otherwise
667
        :class:`~graph_tool.inference.blockmodel.BlockState`.
668
669
    state_args : ``dict`` (optional, default: ``{}``)
        Arguments to be passed to
670
671
672
        :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``)
673
674
675
676
677
678
        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.

679
680
    References
    ----------
681
682
683
    .. [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`
684
685
    """

686
687
    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),
688
                 aE=numpy.nan, nested=True, state_args={}, bstate=None,
689
                 self_loops=False, **kwargs):
690

691
692
        super().__init__(g, nested=nested, state_args=state_args, bstate=bstate,
                         **kwargs)
693
694
        self.aE = aE
        if numpy.isnan(aE):
695
696
697
698
699
700
701
702
703
            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)
704
        self.beta = fn_params.get("beta", 10)
705
        self.mu = fp_params.get("mu", 1)
706
        self.nu = fp_params.get("nu", 10)
707
708
709
710
711
712
713
714
715
716
717

        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)
718
        self.q.fa = ra - rb
719
        dra, drb = self.transform(self.n_default, self.x_default)
720
        self.q_default = dra - drb
721

722
        self.S_const = (self.M - self.g.num_edges()) * drb + rb.sum()
723
724
725
726
727
728

        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):
729
730
731
732
        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))
733
734
735
736
737
738
739
740
741
742
743
        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):
744
        state = super().__getstate__()
745
        return dict(state, n=self.n, x=self.x, n_default=self.n_default,
746
                    x_default=self.x_default,
747
                    fn_params=dict(alpha=self.alpha, beta=self.beta),
748
                    fp_params=dict(mu=self.mu, nu=self.nu), aE=self.aE)
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764

    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))

765
766
767
768
769
770
771
772
773
774
775
776
777
778
    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``.
        """

779
780
        return super().mcmc_sweep(r=r, multiflip=multiflip, h=h, hstep=hstep,
                                  **kwargs)
781

782
    def _algo_sweep(self, algo, r=.5, h=.1, hstep=1, niter=1, **kwargs):
783
        if numpy.random.random() < h:
784
785
786
787
            dS = nt = nm = 0
            for i in range(niter):
                hs = [self.alpha, self.beta, self.mu, self.nu]
                j = numpy.random.randint(len(hs))
788

789
790
                f_dh = [max(0, hs[j] - hstep), hs[j] + hstep]
                pf = 1./(f_dh[1] - f_dh[0])
791

792
793
                old_hs = hs[j]
                hs[j] = f_dh[0] + numpy.random.random() * (f_dh[1] - f_dh[0])
794

795
796
                b_dh = [max(0, hs[j] - hstep), hs[j] + hstep]
                pb = 1./min(1, hs[j])
797

798
799
                latent_edges = kwargs.get("entropy_args", {}).get("latent_edges", True)
                density = False
800

801
                Sb = self._state.entropy(latent_edges, density)
802
                self.set_hparams(*hs)
803
804
805
806
807
808
809
810
811
812
                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)
813
        else:
814
            return super()._algo_sweep(algo, r, niter=niter, **kwargs)
815
816
817
818
819

    def _mcmc_sweep(self, mcmc_state):
        return libinference.mcmc_uncertain_sweep(mcmc_state,
                                                 self._state,
                                                 _get_rng())
820
821
822
823
824

class DynamicsBlockStateBase(UncertainBaseState):
    def __init__(self, g, s, t, x=None, aE=numpy.nan, nested=True,
                 state_args={}, bstate=None, self_loops=False,
                 **kwargs):
825
826
827
828
        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."""

829
830
        super().__init__(g, nested=nested, state_args=state_args, bstate=bstate,
                         self_loops=self_loops)
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
        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):
858
        r"""Sets the model parameters via the dictionary ``params``."""
859
860
861
862
        self.params = dict(self.params, **params)
        self._state.set_params(self.params)

    def __getstate__(self):
863
        state = super().__getstate__()
864
        return dict(state, s=self.s, t=self.t, x=self.x, aE=self.aE,
865
866
867
868
869
870
871
872
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
                    **self.params)

    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):
938
939
        """Return latent edge covariates."""
        return self.x
940
941

    def get_edge_prob(self, u, v, x, entropy_args={}, epsilon=1e-8):
942
        r"""Return conditional posterior log-probability of edge :math:`(u,v)`."""
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
        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`
958
            New marginal graph, with internal edge :class:`~graph_tool.EdgePropertyMap`
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
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:
            g.ep.xsum = g.new_ep("double")
            g.ep.x2sum = g.new_ep("double")
            g.ep.x = g.new_ep("double")
            g.ep.xdev = g.new_ep("double")

        u = self.get_graph()
        x = self.get_x()
        libinference.collect_xmarginal(g._Graph__graph,
                                       u._Graph__graph,
                                       _prop("e", u, x),
                                       _prop("e", g, g.ep.count),
                                       _prop("e", g, g.ep.xsum),
                                       _prop("e", g, g.ep.x2sum))
        g.gp.count += 1
        g.ep.eprob.fa = g.ep.count.fa / g.gp.count
        g.ep.x.fa = g.ep.xsum.fa / g.gp.count
        g.ep.xdev.fa = sqrt(g.ep.x2sum.fa / g.gp.count - g.ep.x.fa ** 2)
        return g

For faster browsing, not all history is shown. View entire blame