Signed graph embedding: when everybody can sit closer to friends than enemies

Anne-Marie Kermarrec, Christopher ThravesarXiv 2014 · arXiv

Introduction

Social network analysis traditionally relies on signed graphs, where edges represent positive (friendship) or negative (enmity) relationships. For decades, the gold standard for understanding these networks was Balance Theory—often summarized by the adage "the enemy of my enemy is my friend." However, real-world data from modern social media frequently violates these rigid structural rules. This paper introduces a new geometric framework called valid drawing, which proposes that social order is defined by spatial proximity: individuals should be positioned closer to their friends than to their enemies in Euclidean space.

The Geometric Framework

The authors propose that a "valid" representation of a social network is an embedding where, for every individual, all their friends are strictly closer to them than any of their enemies. This model generalizes previous concepts like "clusterizable graphs." The paper establishes a clear hierarchy of social structures: Balanced ⊂ Clusterizable ⊂ Drawable in 1D ⊂ Drawable in 2D. This hierarchy demonstrates that valid drawings can capture more complex and nuanced social interactions than traditional theories.

Figure 2: The four fundamental signed triangle configurations. In these diagrams, solid lines represent positive (friendship) edges, while dashed lines represent negative (enmity) edges.

Characterizing 1D and 2D Embeddings

The research focuses on the conditions under which a signed graph can be validly embedded in low-dimensional spaces.

One-Dimensional Embeddings

For the one-dimensional case (the line), the authors identify a deep connection to chordal graphs—graphs where every cycle of four or more vertices has a "chord" connecting two non-adjacent vertices. They prove that for a complete signed graph to be drawable in 1D, its positive subgraph (the network of friendship edges) must be chordal. This allows the use of classical graph-theoretic tools, such as Perfect Elimination Orderings, to solve modern social networking problems.

Two-Dimensional Embeddings

In the two-dimensional plane, the authors use trigonometric proofs to identify "forbidden patterns" that prevent valid drawings. They identify the "Negative Triangle" (a specific 5-vertex configuration) and the "Negative Cluster" as primary structures that cannot exist in a 2D valid drawing because the geometry of the plane cannot simultaneously satisfy all required distance constraints.

Algorithmic Design and Complexity

The paper provides an efficient $O(n^2)$ algorithm to determine if a complete signed graph (where every relationship is known) can be drawn on a line. The algorithm leverages the properties of chordal graphs to construct the layout if it is possible.

However, the authors also show that for incomplete graphs, where some relationships are unknown, the problem of determining drawability becomes NP-Complete. This highlights a significant computational gap between well-mapped communities and sparse networks.

Conclusion

By shifting the focus from structural balance to spatial distance, this paper provides a flexible and intuitive model for social network analysis. While the 1D case is well-characterized, the full characterization of 2D and higher-dimensional embeddings remains an open challenge. Future work could involve extending the model to include weighted edges (e.g., "best friend" vs. "acquaintance") to create more nuanced recommendation and analysis systems.

Summary updated

BibTeX
@misc{kermarrec2014signed,
  author = {Anne-Marie Kermarrec and Christopher Thraves},
  title = {{Signed graph embedding: when everybody can sit closer to friends than enemies}},
  year = {2014},
  eprint = {1405.5023},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1405.5023},
}
Figure