Locally Balancing Signed Graphs

Signed graphs capture both positive and negative relationships between entities, with balance being a fundamental concept. In these graphs, a vertex is considered balanced if all cycles it belongs to contain an even number of negative edges. On the other hand, unbalanced vertices often experience cognitive dissonance and emotional disturbance, motivating efforts to modify the graph to achieve balance for these vertices. Yet, most existing research emphasizes global balance, focusing on lengthy cycles that represent distant interactions. In contrast, this paper shifts the focus to local balance, where a vertex is deemed balanced when the triangles (length-three cycles) it participates in are positive, reflecting more immediate relationships. Building on this, we introduce the Locally Balancing Signed Graph (LBS) problem, which aims to maximize the number of locally balanced vertices through graph modification. Despite the NP-hard nature of the LBS problem and the absence of properties such as monotonicity and submodularity, our novel greedy method effectively addresses these challenges. We further enhance our method with dynamic computation and pruning techniques. Extensive experiments show the efficacy of our greedy method in solving the LBS problem and underscore the substantial runtime reductions achieved through our optimization techniques.