Community detection based on structural balance in signed networks

Peng Zhang, Xianyu Xu, Leyang Xue

TL;DR

This paper introduces a community detection method for signed networks (networks with both positive and negative links) that prioritizes structural balance over simple link signs. By quantifying how much individual links contribute to local "balanced" motifs (like triangles where "the enemy of my enemy is my friend"), the algorithm identifies stable communities even when they contain internal friction.

What Problem Does This Paper Address?

In traditional network analysis, we usually look for "communities" where nodes are densely connected. In signed networks—which model relationships like friendship (+) and hostility (-)—the standard assumption is that positive links belong inside a community and negative links belong between them.

However, real-world social groups are rarely perfectly harmonious. Internal conflicts exist, yet the groups remain stable. The authors argue that community stability isn't just about the absence of negative links, but the presence of structural balance. For example, if two people in a group dislike the same outsider, that shared dislike actually strengthens the group's internal bond. Existing methods often fail to capture this nuance, either ignoring negative links or treating them purely as indicators of a split.

Methods

The authors propose a motif-based community detection method that operates in two main stages:

  1. Quantifying Link Importance via Local Balance: Instead of looking at the whole network's balance (which is computationally expensive), they focus on triadic motifs (triangles). They utilize four fundamental triangular structures ($M_1$ to $M_4$).

  2. $M_1$ (all positive) and $M_3$ (two negative, one positive) are traditionally balanced.

  3. They also include $M_4$ (three negative links) as a "weakly balanced" motif common in social systems.
  4. They calculate a weight $p_{ij}$ for every link, representing the ratio of times a link appears in a balanced motif versus all possible motifs. This transforms the raw adjacency matrix into a weight matrix ($P$) that reflects local structural stability.
  5. Modularity Optimization: The authors adapt the standard modularity function ($Q$), replacing the traditional adjacency matrix with their new weight matrix $P$. They then use a spectral approach—finding the eigenvector associated with the largest eigenvalue of the modularity matrix—to partition the nodes into distinct communities.

Datasets

The researchers validated their approach using both synthetic and empirical data:

  • Synthetic Networks: Generated using a Stochastic Block Model variant that allows fine-grained control over link density ($p^{in}$), the probability of positive links between communities ($p^+_{out}$), and negative links within communities ($p^-_{in}$).
  • Slovene Parliamentary Party Network: A 10-node network representing political parties in 1994, with relationships ranging from "very hostile" to "very friendly."
  • Gahuku-Gama Subtribes Network: A 16-node network of subtribes in the New Guinea highlands, mapping political alliances and "class struggles."

Key Insights and Ideas

  • Balance > Sign: A negative link isn't always a "break" signal. If a negative link helps complete a balanced triangle, it contributes to the local stability of that community.
  • Robustness to Noise: The method is remarkably insensitive to the overall "imbalance" of a network. Even in highly chaotic or hostile environments, it can pick out the most structurally sound clusters.
  • Local Priority: By focusing on 3-node motifs (triangles) rather than global balance, the method becomes computationally practical while still capturing the sociological essence of group formation.

Key Results

  • Superiority over DM: The proposed method was compared against the well-known Doreian and Mrvar (DM) algorithm. In synthetic tests where communities had high internal negative links ($p^-_{in} = 1$), the motif-based method significantly outperformed DM in Jaccard similarity (accuracy) as link density increased.
  • Handling Inter-community Positivity: The method remained effective even when there were significant positive links between different communities—a scenario that typically confuses standard algorithms.
  • Real-World Accuracy:
    • In the Slovene Parliament test, the algorithm perfectly identified the two main political blocs.
  • In the Gahuku-Gama test, it accurately clustered the 16 subtribes into three groups that closely align with known ground-truth alliances.

Limitations and Future Work

  • Motif Complexity: The current work relies on 3-node motifs (triangles). While effective, the authors note that larger motifs (4-node or 5-node) could potentially provide even deeper insights into community structure, though at a higher computational cost.
  • Scalability: While the spectral approach is standard, the paper does not extensively discuss the performance on "big data" scales (millions of nodes), which is a common challenge for motif-based weighting.
  • Dynamic Networks: The authors suggest that future research could apply this balance-centric view to evolving networks to see how communities collapse or merge as structural balance shifts over time.

Summary updated

Abstract

In signed networks, some existing community detection methods treat negative connections as intercommunity links and positive ones as intracommunity links. However, it is important to recognize that negative links on real-world networks also play a key role in maintaining community stability. In this work, our aim is to identify communities that are not only densely connected but also harmonious or balanced in terms of the nature of their relationships. Such communities are more likely to be stable over time and less prone to conflicts. Consequently, we propose a motif-based method to identify communities by quantifying the importance of links in the local structural balance. The results in synthetic and real-world networks show that the proposed method has a higher performance in identifying the community. In addition, it demonstrates strong robustness, i.e., remains insensitive to the balance of the network, and accurately classifies communities in real-world networks.
BibTeX
@misc{zhang2023community,
  author = {Peng Zhang and Xianyu Xu and Leyang Xue},
  title = {{Community detection based on structural balance in signed networks}},
  year = {2023},
  eprint = {2308.07990},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2308.07990},
}
Figure