This paper proposes and investigates a Boolean gossip model as a simplified but non-trivial probabilistic Boolean network. With positive node interactions, in view of standard theories from Markov chains, we prove that the node states asymptotically converge to an agreement at a binary random variable, whose distribution is characterized for large-scale networks by mean-field approximation. Using combinatorial analysis, we also successfully count the number of communication classes of the positive Boolean network explicitly in terms of the topology of the underlying interaction graph, where remarkably minor variation in local structures can drastically change the number of network communication classes. With general Boolean interaction rules, emergence of absorbing network Boolean dynamics is shown to be determined by the network structure with necessary and sufficient conditions established regarding when the Boolean gossip process defines absorbing Markov chains. Particularly, it is shown that for the majority of the Boolean interaction rules, except for nine out of the total @math possible nonempty sets of binary Boolean functions, whether the induced chain is absorbing has nothing to do with the topology of the underlying interaction graph, as long as connectivity is assumed. These results illustrate possibilities of relating dynamical properties of Boolean networks to graphical properties of the underlying interactions.
Virus Spreading . Virus spreading across a computer network can be modeled as a Boolean network, where @math and @math represent infected and healthy computers, respectively @cite_23 . The proposed Boolean gossip process may characterize more possibilities for two computers during an interaction: two computers, infected or not, are both infected ( @math ); two computers, infected or not, are both cured ( @math ), etc.
@cite_23
2118820208
The influence of the network characteristics on the virus spread is analyzed in a new-the N -intertwined Markov chain-model, whose only approximation lies in the application of mean field theory. The mean field approximation is quantified in detail. The N -intertwined model has been compared with the exact 2N-state Markov model and with previously proposed ldquohomogeneousrdquo or ldquolocalrdquo models. The sharp epidemic threshold tauc , which is a consequence of mean field theory, is rigorously shown to be equal to tauc = 1 (lambdamax(A)) , where lambdamax(A) is the largest eigenvalue-the spectral radius-of the adjacency matrix A . A continued fraction expansion of the steady-state infection probability at node j is presented as well as several upper bounds.