Inscriere cercetatori

Premii Ad Astra

premii Ad Astra

Asociația Ad Astra a anunțat câștigătorii Premiilor Ad Astra 2022: Proiectul și-a propus identificarea și popularizarea modelelor de succes, a rezultatelor excepționale ale cercetătorilor români din țară și din afara ei.

Asociatia Ad Astra a cercetatorilor romani lanseaza BAZA DE DATE A CERCETATORILOR ROMANI DIN DIASPORA. Scopul acestei baze de date este aceea de a stimula colaborarea dintre cercetatorii romani de peste hotare dar si cu cercetatorii din Romania. Cercetatorii care doresc sa fie nominalizati in aceasta baza de date sunt rugati sa trimita un email la

On the dynamics of Social Balance on general networks (with an application to XOR-SAT)

Domenii publicaţii > Ştiinţe informatice + Tipuri publicaţii > Articol în revistã ştiinţificã

Autori: Gabriel Istrate

Editorial: Maurice Margenstern and Jerome Durand-Lose (special issue editors), Fundamenta Informaticae, 91 (2), p.341-356, 2009.


We study nondeterministic and probabilistic versions of a discrete dynamical system (due to T. Antal, P. L. Krapivsky, and S. Redner) 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 previous experimental observations.
We also point out an application to the analysis of the random walk algorithm on certain instances of the 3-XOR-SAT problem.

A preprint is freely available from

Cuvinte cheie: social balance, dynamical systems, Markov chains