  Structural balance theory describes stable configurations of topologies of
signed interpersonal appraisal networks. Existing models explaining the
convergence of appraisal networks to structural balance either diverge in
finite time, or could get stuck in jammed states, or converge to only complete
graphs. In this paper, we study the open problem how steady non-all-to-all
structural balance emerges via local dynamics of interpersonal appraisals. We
first compare two well-justified definitions of structural balance for general
non-all-to-all graphs, i.e., the triad-wise structural balance and the
two-faction structural balance, and thoroughly study their relations. Secondly,
based on three widely adopted sociological mechanisms: the symmetry mechanism,
the influence mechanism, and the homophily mechanism, we propose two simple
models of gossip-like appraisal dynamics, the symmetry-influence-homophily
(SIH) dynamics and the symmetry-influence-opinion-homophily (SIOH) dynamics. In
these models, the appraisal network starting from any initial condition almost
surely achieves non-all-to-all triad-wise and two-faction structural balance in
finite time respectively. Moreover, the SIOH dynamics capture the co-evolution
of interpersonal appraisals and individuals' opinions. Regarding the
theoretical contributions, we show that the equilibrium set of the SIH (SIOH
resp.) dynamics corresponds to the set of all the possible triad-wise
(two-faction resp.) structural balance configurations of the appraisal
networks. Moreover, we prove that, for any initial condition, the appraisal
networks in the SIH (SIOH resp.) dynamics almost surely achieve triad-wise
(two-faction resp.) structural balance in finite time. Numerical studies of the
SIH dynamics also imply some insightful take-home messages on whether
multilateral relations reduce or exacerbate conflicts.
