Affiliations: Austria Research Institute, Bd. V. Pârvan 4,
cam. 045B, Timişoara RO-300223, Romania. [email protected]
Note: [] Address for correspondence: Austria Research Institute, Bd. V.
Pârvan 4, cam. 045B, Timişoara RO-300223, Romania
Abstract: We study nondeterministic and probabilistic versions of a discrete
dynamical system (due to T. Antal, P. L. Krapivsky, and S. Redner [3]) inspired
by Heider's social balance theory. We investigate the convergence
time of this dynamics on several classes of graphs. Our contributions include:
1. We point out the connection between the triad dynamics and a
generalization of annihilating walks to hypergraphs. In particular, this
connection allows us to completely characterize the recurrent states in graphs
where each edge belongs to at most two triangles. 2. We also solve the case of hypergraphs that do not contain edges
consisting of one or two vertices. 3. We show that on the so-called "triadic
cycle" graph, the convergence time is linear. 4. We obtain a cubic upper bound on the convergence time on
2-regular triadic simplexes G. This bound can be further improved to a quantity
that depends on the Cheeger constant of G. In particular this provides some
rigorous counterparts to experimental observations in [25]. We also point out an application to the analysis of the random walk
algorithm on certain instances of the 3-XOR-SAT problem.
Keywords: social balance, discrete dynamical systems, rapidly mixingMarkov chains, XOR-SAT
