Exploring the low-energy landscape of large-scale signed social networks

Analogously to a spin glass, a large-scale signed social network is characterized by the presence of disorder, expressed in this context (and in the social network literature) by the concept of structural balance. If, as we have recently shown, the signed social networks currently available have a limited amount of true disorder (or frustration), it is also interesting to investigate how this frustration is organized, by exploring the landscape of near-optimal structural balance. What we obtain in this paper is that while one of the networks analyzed shows a unique valley of minima, and a funneled landscape that gradually and smoothly worsens as we move away from the optimum, another network shows instead several distinct valleys of optimal or near-optimal structural balance, separated by energy barriers determined by internally balanced subcommunities of users, a phenomenon similar to the replica-symmetry breaking of spin glasses. Multiple, essentially isoenergetic, arrangements of these communities are possible. Passing from one valley to another requires one to destroy the internal arrangement of these balanced subcommunities and then to reform it again. It is essentially this process of breaking the internal balance of the subcommunities which gives rise to the energy barriers.

Figure 1

Distribution of the energies for all near-optimal replicas. The leftmost bar of each histogram corresponds to ${\delta }_{\text{up}}$.

Figure 2

Relative Hamming distance between low-energy replicas.

Figure 3

Indices $n\left(\nu \right)$, $c\left(\nu \right)$, and $z\left(\nu \right)$ for the two networks. The rightmost panel in each row reports the dimensions of the connected components identified in the subgraph $W\left(\nu \right)$ of spins under the two peaks of $c\left(\nu \right)$ centered at $\nu =1/3$ and at $\nu =1/2$. Letters $C_1$, $C_2$, and $C_3$ indicate the three Slashdot communities identified in the spikes pointed to by the arrows.

Figure 4

Epinions. (a) Distance among replicas vs energy of a replica. The replicas of Fig. 1a are binned into six bins according to their energy, and the mean of the relative Hamming distances is computed. The vertical axis [and color (gray) code] represents the mean over bins of the relative distances. The replicas of least energy are also closer, and the distance grows regularly with the energy. (b) Sample minimal energy paths connecting the global and a local minimum. For visualization purposes, the trajectories are depicted as radially distributed according to a polar coordinate, with the global optimum placed in the origin. The vertical axis [and color (gray) code] represents the energy. The radius of the disks represent the average distance among the replicas in correspondence of the six bins of (a). The horizontal parts on the paths correspond to isoenergetic flips.

Figure 5

Slashdot. (a) Three valleys of minima corresponding to the three peaks in Fig. 1b are called low, medium, and high, according to their energy. For each pair of minima ${\mathbf{s}}^{\left(i\right)}$ and ${\mathbf{s}}^{\left(j\right)}$, the scatter plot shows differences in energy $|h\left({\mathbf{s}}^{\left(i\right)}\right)-h\left({\mathbf{s}}^{\left(j\right)}\right)|$ versus the relative Hamming distance $d$ for both intra and intervalley peaks. The two valleys medium and high are near and both more distant from the low valley. (b) A few sample trajectories connecting minima in different valleys. The radius of the disks corresponds to the average intravalley distance among the replicas. The height of the trajectories is indicative of the energy barrier between the valleys. To improve readability, the degenerate spin flips are not shown. (c) The three internally balanced communities $C_i$ (described in Tables and and Fig. 6) and their average magnetization in the three valleys of near-optimal balance.

Figure 6

Slashdot: the three internally balanced subnetworks $C_1$, $C_2$, and $C_3$ of Table . The adjacency matrices (first row) and the corresponding signed graphs (second row) are shown. Blue (full) dots correspond to $+1$ edges, red (empty) to $-1$. In the corresponding graph, blue (thick) lines correspond to $+1$ edges, red (thin) lines to $-1$. The color code for the nodes reflects the sum of the external edges: blue (darker) means positive sum, red (lighter) negative, and white no external edges.

Figure 7

Relative energy of the motifs flipping with frequencies $\nu =1/2$ and $\nu =1/3$. These motifs are grouped according to their size. The gray scale (color online) represents their number. In all histograms the relative energy (energy through the cut set divided by the corresponding number of edges) is concentrated around 0.5, meaning that half of the edges are frustrated in the ground state. Therefore, the peaks at $\nu =1/2$ and $\nu =1/3$ contain mostly isoenergetic motifs. These are described in Tables and .

Figure 8

Epinions: origin of the size-1 motifs for $\nu =1/2$ and $\nu =1/3$. Plots of the ${\rho }_0$, ${\rho }_{1/2}$, and ${\rho }_1$ ratios for the 2172 isoenergetic size-1 motifs identified under the peak at $\nu =1/2$ (circles) and for the 442 size-1 isoenergetic motifs belonging to the peak at $\nu =1/3$ (points). The case ${\rho }_{1/2}$ (referring to gauge transformations that change 50$\%$ of the edges through the cut set) is more frequent under the $\nu =1/3$ peak than under the $\nu =1/2$ one.