Weakly negative circles and best clustering in signed graphs

Michael J. Gottstein1, Leila Parsaei-Majd2, Thomas Zaslavsky3
1Mathematics and Computer Science Department, Marywood University, Scranton, PA 18509, U.S.A.
2University of Potsdam, Germany
3Department of Mathematics and Statistics, Binghamton University, Binghamton, NY 13902-6000, U.S.A.

Abstract

Clustering a signed graph means partitioning the vertices into clusters so that every positive edge, and no negative edge, is within a cluster. The obstruction to clustering is circles with exactly one negative edge (“weakly negative circles’’). The correlation clustering problem is to cluster with the minimum number \(Q\) of edges that violate the clustering rule. A lower bound is \(w\), the maximum number of edge-disjoint weakly negative circles. If every two such circles are edge disjoint, then \(Q=w\). We characterize the signed graphs in which no two weakly negative circles share any edges. A corollary is a straightforward recognition algorithm for such signed graphs. An unsolved problem is to characterize the signed graphs with \(Q=w\).

Keywords: signed graph clustering, correlation clustering, weakly negative circle