Abstract
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 $2^{16}-1$ 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.
Introduction
Boolean networks are fundamental for modeling complex systems, ranging from gene regulatory networks to social opinion dynamics. However, a persistent challenge in the field is the trade-off between the rigidity of deterministic models and the mathematical opacity of general probabilistic models. This research introduces "Boolean Gossip Networks," a framework that bridges this gap by exploring how the underlying graph topology—the physical structure of "who talks to whom"—directly dictates the long-term dynamical behavior of the system.
The Boolean Gossip Model
In this model, nodes on a graph maintain binary states (0 or 1) and update them through random pairwise interactions. When two nodes interact, they apply a logical rule (a Boolean function) to determine their next states.
The researchers employed a multi-faceted mathematical approach to analyze these interactions:
- Markov Chain Theory: The entire network state is treated as a point in a $2^n$-dimensional space, allowing for the analysis of transition probabilities.
- Combinatorial Analysis: The concept of "L-reduced states" was introduced to simplify complex binary strings into essential transitions, facilitating the counting of communication classes.
- Mean-Field Approximation: For large-scale networks, the authors derived ordinary differential equations (ODEs) to approximate the global density of nodes in state '1'.
Key Insights: The "Rule of Nine" and Odd Cycles
A central finding of the study is the "Rule of Nine." Out of the $2^{16}-1$ possible non-empty sets of binary Boolean functions, the system's ability to reach an "absorbing" state (getting stuck in a stable configuration) is independent of graph topology for the vast majority of cases, provided the graph is connected.
However, for exactly nine special sets of rules, the topology becomes the deciding factor. Specifically, the presence of an odd cycle in the graph determines the system's fate. In graphs without odd cycles (bipartite graphs), the system behaves as an absorbing Markov chain. Conversely, the introduction of even a single edge that creates an odd cycle can prevent the system from ever reaching a stable consensus.
Analytical Results and Convergence
The study provides explicit counts for communication classes ($\chi$) across various topologies:
- Line Graphs: $\chi = 2n$
- Cycle Graphs: $\chi = m+3$ (for $n=2m$) or $m+2$ (for $n=2m+1$)
- General Bipartite Graphs: $\chi = 5$
- General Non-Bipartite Graphs: $\chi = 3$
Furthermore, the authors derived a closed-form ODE solution for node density over time: $$\delta(t) = \frac{\delta_0}{(1 - \delta_0)e^{2(1-2p_*)t/n} + \delta_0}$$ This result demonstrates that if the probability of an "OR" interaction ($p_*$) exceeds 0.5, the network will asymptotically converge to a state of all 1s; otherwise, it converges to all 0s.
Conclusion and Future Work
This work establishes a rigorous link between local interaction rules, global graph topology, and the resulting network dynamics. While currently limited to binary, pairwise, and asynchronous interactions, it provides a complete roadmap for understanding absorption in Boolean gossip processes. Future research will look to extend these findings to multi-state networks and more complex, multi-node interaction schemes.
Summary updated