Community detectability and structural balance dynamics in signed networks

Abstract

We investigate signed networks with community structure with respect to their spectrum and their evolution under a dynamical model of structural balance, a prominent theory of signed social networks. The spectrum of the adjacency matrix generated by a stochastic block model with two equal size communities shows detectability transitions in which the community structure becomes manifest when its signal eigenvalue appears outside the main spectral band. The spectrum also exhibits "sociality" transitions involving the homogeneous structure representing the average tie value. We derive expressions for the eigenvalues associated with the community and homogeneous structure as well as the transition boundaries, all in good agreement with numerical results. Using the stochastically-generated networks as initial conditions for a simple model of structural balance dynamics yields three outcome regimes: two hostile factions that correspond with the initial communities, two hostile factions uncorrelated with those communities, and a single harmonious faction of all nodes. The detectability transition predicts the boundary between the assortative and mixed two-faction states and the sociality transition predicts that between the mixed and harmonious states. Our results may yield insight into the dynamics of cooperation and conflict among actors with distinct social identities.

References in corpus (17)

• Community structure in social and biological networks
• Finding community structure in networks using the eigenvectors of matrices
• Mixing patterns in networks
• Stochastic blockmodels and community structure in networks
• Community detection in networks: A user guide
• Community detection in networks with positive and negative links
• Phase transition in the detection of modules in sparse networks
• Graph spectra and the detectability of community structure in networks
• Analysis of a continuous-time model of structural balance
• The Heider balance - a continuous approach
• Balance in signed networks
• Detectability thresholds and optimal algorithms for community structure in dynamic networks
• Dynamical Models Explaining Social Balance and Evolution of Cooperation
• Universality of Wigner random matrices: a Survey of Recent Results
• Spectral properties of complex networks
• Spectra of random graphs with community structure and arbitrary degrees
• Detectability of Macroscopic Structures in Directed Asymmetric Stochastic Block Model