## Abstract

Structural balance theory studies stability in networks. Given a n-vertex complete graph G = (V, E) whose edges are labeled positive or negative, the graph is considered balanced if every triangle either consists of three positive edges (three mutual “friends”), or one positive edge and two negative edges (two “friends” with a common “enemy”). From a computational perspective, structural balance turns out to be a special case of correlation clustering with the number of clusters at most two. The two main algorithmic problems of interest are: (i) detecting whether a given graph is balanced, or (ii) finding a partition that approximates the frustration index, i.e., the minimum number of edge flips that turn the graph balanced. We study these problems in the streaming model where edges are given one by one and focus on memory efficiency. We provide randomized single-pass algorithms for: (i) determining whether an input graph is balanced with O(log n) memory, and (ii) finding a partition that induces a (1 + ε)-approximation to the frustration index with O(n · polylog(n)) memory. We further provide several new lower bounds, complementing different aspects of our algorithms such as the need for randomization or approximation. To obtain our main results, we develop a method using pseudorandom generators (PRGs) to sample edges between independently-chosen vertices in graph streaming. Furthermore, our algorithm that approximates the frustration index improves the running time of the state-of-the-art correlation clustering with two clusters (Giotis-Guruswami algorithm [SODA 2006]) from n^{O}(1^{/ε}^{2)} to O(n^{2} log^{3} n/ε^{2} + n log n · (1/ε)^{O}(1^{/ε}^{4)}) time for (1 + ε)-approximation. These results may be of independent interest.

Original language | English (US) |
---|---|

Title of host publication | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023 |

Editors | Nicole Megow, Adam Smith |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959772969 |

DOIs | |

State | Published - Sep 2023 |

Event | 26th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2023 and the 27th International Conference on Randomization and Computation, RANDOM 2023 - Atlanta, United States Duration: Sep 11 2023 → Sep 13 2023 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 275 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 26th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2023 and the 27th International Conference on Randomization and Computation, RANDOM 2023 |
---|---|

Country/Territory | United States |

City | Atlanta |

Period | 9/11/23 → 9/13/23 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- Streaming algorithms
- pseudo-randomness generator
- structural balance