Evaluating Stability in Massive Social Networks: Efficient Streaming Algorithms for Structural Balance

Vikrant Ashvinkumar, Sepehr Assadi, Chengyuan Deng, Jie Gao, Chen Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 nO(12) to O(n2 log3 n/ε2 + n log n · (1/ε)O(14)) time for (1 + ε)-approximation. These results may be of independent interest.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023
EditorsNicole Megow, Adam Smith
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772969
DOIs
StatePublished - Sep 2023
Event26th 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 2023Sep 13 2023

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume275
ISSN (Print)1868-8969

Conference

Conference26th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2023 and the 27th International Conference on Randomization and Computation, RANDOM 2023
Country/TerritoryUnited States
CityAtlanta
Period9/11/239/13/23

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Streaming algorithms
  • pseudo-randomness generator
  • structural balance

Fingerprint

Dive into the research topics of 'Evaluating Stability in Massive Social Networks: Efficient Streaming Algorithms for Structural Balance'. Together they form a unique fingerprint.

Cite this