摘要：AbstractStructural balance theory describes stable configurations of topologies of signed interpersonal appraisal networks. Various mathematical models have been proposed to explain how initially unbalanced appraisal networks evolve to structural balance. However, the existing models either diverge in finite time, or could get stuck in jammed states, or converge to only non-all-to-all graphs starting from certain sets of initial conditions. It remains an open problem how non-all-to-all structural balance emerges via local dynamics of interpersonal appraisals. In this paper, we first compare two well-justified definitions of structural balance, i.e., the triad-wise structural balance and the two-faction structural balance, and establish the conditions with clear graph-theoretic interpretations, under which these two definitions of structural balance are equivalent. Secondly, we propose a simple model of gossip-like appraisal dynamics in which the appraisal network, starting from any initial condition, almost surely achieves structural balance in finite time, while its topology remains unchanged. Our model is based on three widely adopted sociological mechanisms: the symmetry mechanism, the influence mechanism and the homophily mechanism. Our main theoretical contribution is manifold: First, we show that the equilibrium set of our gossip-like appraisal dynamics corresponds to the set of all the possible triad-wise structural balance configurations of the appraisal networks. Second, we prove that, for any initial condition, the appraisal network almost surely achieves triad-wise structural balance in finite time. Third, we provide a sufficient condition, under which the appraisal networks almost-surely achieve two-faction structural balance in finite time.
关键词：KeywordsStructural balanceNetwork formationGraph theoryMulti-agent systems
