Abstract
In this paper, we propose and study a randomized Boolean gossiping process, where nodes taking value from $\{0,1\}$ pairwise meet over an underlying graph in a random manner at each time step and the two interacting nodes update their states by random logistic rules drawn from the set $\{{\it AND}, {\it OR}\}$. This model is a generalization of the classical gossiping process and serves as a simplified probabilistic Boolean network. First of all, using standard theories from Markov chain we show that almost surely, the network state asymptotically converge to a consensus. We also establish a characterization of the distribution of this limit for large-scale networks with all-to-all communication in light of mean-field approximation methods. Next, we study how the number of communication classes in the network state space relates to the topology of the underlying interaction graph and obtain a full characterization: A line interaction graph with $n$ nodes generates $2n$ communication classes; A cycle graph with $2n$ nodes generates $n+3$ communication classes, and a cycle graph with $2n+1$ nodes generates $n+2$ communication classes; For any connected graph which is not a line or a cycle, the number of communication classes is either five or three, where three is achieved if and only if the graph contains an odd cycle.
Introduction
Boolean networks are fundamental tools for modeling complex systems, ranging from gene regulatory circuits to social influence dynamics. While traditional models are often deterministic or follow specific gossip protocols, real-world interactions are inherently stochastic. This paper introduces "Randomized Boolean Gossiping," a model that bridges the gap between simple gossip protocols and Probabilistic Boolean Networks (PBNs). We investigate whether a network using random AND/OR logic eventually stabilizes and how the physical topology of the network constrains the possible transitions between system configurations.
Methodology
The model consists of $n$ nodes, each holding a binary state $x_i \in \{0,1\}$. At each discrete time step, an edge $(i, j)$ is selected from the underlying graph. With probability $q$, both nodes update their states to $x_i(t+1) = x_j(t+1) = x_i(t) \lor x_j(t)$ (the OR rule); with probability $1-q$, they update to $x_i(t+1) = x_j(t+1) = x_i(t) \land x_j(t)$ (the AND rule).
To analyze this system, the authors employ:
- Markov Chain Theory: Treating the network configuration as a state in a finite Markov chain to prove convergence to absorbing states (all 0s or all 1s).
- Mean-Field Approximation: For large-scale, all-to-all (complete) graphs, using differential equations to model the evolution of the density of nodes in state 1.
- State Space Analysis: Characterizing "communication classes"—sets of states that are mutually reachable—to understand the global navigability of the network across different topologies.
Convergence and Mean-Field Dynamics
A primary result of this study is that the system almost surely reaches a consensus state (either all 0s or all 1s) in finite time. The random application of AND/OR rules does not lead to persistent oscillations but rather to stable absorbing states.
In the limit of large, fully connected networks, the system's final fate is determined by the probability $q$ of the OR rule. We identify a critical threshold at $q = 0.5$. If $q > 0.5$, the network tends toward a consensus of 1s; if $q < 0.5$, it converges to 0s. This represents a "tug-of-war" between the information-expanding OR rule and the information-contracting AND rule.
Topological Characterization of State Space
The most significant contribution of this work is the discovery of how graph topology acts as a filter for the system's state space. The number of communication classes—which represents the "granularity" of reachable configurations—varies drastically based on the graph's structure.
Our analysis provides a complete characterization:
- Line Graphs: For a line graph with $n$ nodes, there are $2n$ communication classes.
- Cycle Graphs: A cycle with $2n$ nodes (as shown in the figure above) generates $n+3$ classes, while a cycle with $2n+1$ nodes generates $n+2$ classes.
- General Connected Graphs: For any graph that is neither a line nor a cycle, the number of classes collapses to just 5 or 3. Specifically, the presence of an odd cycle (e.g., a triangle or pentagon) reduces the number of classes to 3.
This finding highlights the "Power of the Odd Cycle": a small local structural feature can fundamentally simplify the global reachability of the entire network.
Conclusion
Randomized Boolean Gossiping provides a robust framework for understanding stochastic interactions in networks. While consensus is inevitable, the path to that consensus is strictly governed by the underlying topology. Future work will explore the speed of convergence and the impact of more complex logic rules (e.g., XOR, NOT) and dynamic graph structures on these processes.
Summary updated