Document Open Access Logo

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

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

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2023.58.pdf
  • Filesize: 1.15 MB
  • 23 pages

Document Identifiers

Author Details

Vikrant Ashvinkumar
  • Department of Computer Science, Rutgers University, New Brunswick, NJ, USA
Sepehr Assadi
  • Department of Computer Science, Rutgers University, New Brunswick, NJ, USA
  • Cheriton School of Computer Science, University of Waterloo, Canada
Chengyuan Deng
  • Department of Computer Science, Rutgers University, New Brunswick, NJ, USA
Jie Gao
  • Department of Computer Science, Rutgers University, New Brunswick, NJ, USA
Chen Wang
  • Department of Computer Science, Rutgers University, New Brunswick, NJ, USA

Funding

  • Assadi, Sepehr: Assadi is supported in part by a Alfred P. Sloan Research Fellowship, and Assadi and Wang are supported in part by a NSF CAREER Grant CCF-2047061, a gift from Google Research, and a Rutgers Research Council Fulcrum Award.
  • Gao, Jie: Ashvinkumar, Deng and Gao have been supported by NSF Grant CCF-2118953, CRCNS-2207440, CCF-2208663, and CNS-2137245.

Acknowledgements

We thank Karthik C.S. for some preliminary discussions.

Cite As Get BibTex

Vikrant Ashvinkumar, Sepehr Assadi, Chengyuan Deng, Jie Gao, and Chen Wang. Evaluating Stability in Massive Social Networks: Efficient Streaming Algorithms for Structural Balance. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 58:1-58:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.58

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/ε²) to O(n²log³n/ε² + n log n ⋅ (1/ε)^O(1/ε⁴)) time for (1+ε)-approximation. These results may be of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming, sublinear and near linear time algorithms
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • Streaming algorithms
  • structural balance
  • pseudo-randomness generator

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Robert P. Abelson and Milton J. Rosenberg. Symbolic psycho-logic: A model of attitudinal cognition. Behavioral Science, 3(1):1-13, 1958. Google Scholar
  2. Amit Agarwal, Moses Charikar, Konstantin Makarychev, and Yury Makarychev. O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing - STOC '05, New York, New York, USA, 2005. ACM Press. Google Scholar
  3. Kook Jin Ahn, Graham Cormode, Sudipto Guha, Andrew McGregor, and Anthony Wirth. Correlation clustering in data streams. In Francis R. Bach and David M. Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pages 2237-2246. JMLR.org, 2015. Google Scholar
  4. Kook Jin Ahn and Sudipto Guha. Graph sparsification in the semi-streaming model. In Susanne Albers, Alberto Marchetti-Spaccamela, Yossi Matias, Sotiris E. Nikoletseas, and Wolfgang Thomas, editors, Automata, Languages and Programming, 36th Internatilonal Colloquium, ICALP 2009, volume 5556 of Lecture Notes in Computer Science, pages 328-338. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-02930-1_27.
  5. Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: ranking and clustering. In Harold N. Gabow and Ronald Fagin, editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 684-693. ACM, 2005. Google Scholar
  6. Claudio Altafini. Dynamics of opinion forming in structurally balanced social networks. PloS one, 7(6):e38135, 2012. Google Scholar
  7. T Antal, P L Krapivsky, and S Redner. Social balance on networks: The dynamics of friendship and enmity, 2006. Google Scholar
  8. Samin Aref, Andrew J Mason, and Mark C Wilson. A modeling and computational study of the frustration index in signed networks. Networks, 75(1):95-110, January 2020. Google Scholar
  9. Sepehr Assadi, Yu Chen, and Sanjeev Khanna. Polynomial pass lower bounds for graph streaming algorithms. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019., pages 265-276, 2019. Google Scholar
  10. Sepehr Assadi and Ran Raz. Near-quadratic lower bounds for two-pass graph streaming algorithms. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, pages 342-353. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00040.
  11. Sepehr Assadi and Chen Wang. Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 10:1-10:20, Dagstuhl, Germany, 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ITCS.2022.10.
  12. Adi Avidor and Michael Langberg. The multi-multiway cut problem. Theor. Comput. Sci., 377(1):35-42, May 2007. Google Scholar
  13. Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Mach. Learn., 56(1-3):89-113, 2004. URL: https://doi.org/10.1023/B:MACH.0000033116.57574.95.
  14. Francisco Barahona. On the computational complexity of Ising spin glass models. Journal of Physics A: Mathematical and General, 15(10):3241-3253, 1982. Google Scholar
  15. MohammadHossein Bateni, Hossein Esfandiari, and Vahab S. Mirrokni. Almost optimal streaming algorithms for coverage problems. In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2017, pages 13-23, 2017. Google Scholar
  16. Anubhav Baweja, Justin Jia, and David P. Woodruff. An efficient semi-streaming PTAS for tournament feedback arc set with few passes. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, volume 215 of LIPIcs, pages 16:1-16:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. Google Scholar
  17. Soheil Behnezhad, Moses Charikar, Weiyun Ma, and Li-Yang Tan. Almost 3-approximate correlation clustering in constant rounds. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, pages 720-731. IEEE, 2022. URL: https://doi.org/10.1109/FOCS54457.2022.00074.
  18. Soheil Behnezhad, Moses Charikar, Weiyun Ma, and Li-Yang Tan. Single-pass streaming algorithms for correlation clustering. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, pages 819-849. SIAM, 2023. URL: https://doi.org/10.1137/1.9781611977554.ch33.
  19. András A. Benczúr and David R. Karger. Approximating s-t minimum cuts in Õ(n²) time. In Gary L. Miller, editor, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 47-55. ACM, 1996. URL: https://doi.org/10.1145/237814.237827.
  20. Andrej Bogdanov and Emanuele Viola. Pseudorandom bits for polynomials. SIAM J. Comput., 39(6):2464-2486, 2010. URL: https://doi.org/10.1137/070712109.
  21. Dorwin Cartwright and Frank Harary. Structural balance: a generalization of Heider’s theory. Psychol. Rev., 63(5):277-293, September 1956. Google Scholar
  22. Amit Chakrabarti, Prantar Ghosh, Andrew McGregor, and Sofya Vorotnikova. Vertex ordering problems in directed graph streams. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pages 1786-1802, 2020. Google Scholar
  23. Sayak Chakrabarty and Konstantin Makarychev. Single-pass pivot algorithm for correlation clustering. keep it simple! arXiv preprint arXiv:2305.13560, 2023. Google Scholar
  24. Moses Charikar, Venkatesan Guruswami, and Anthony Wirth. Clustering with qualitative information. In Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), pages 524-533, 2003. Google Scholar
  25. Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, and Grigory Yaroslavtsev. Near optimal LP rounding algorithm for correlation clustering on complete and complete k-partite graphs. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, pages 219-228. ACM, 2015. Google Scholar
  26. Flavio Chierichetti, Nilesh N. Dalvi, and Ravi Kumar. Correlation clustering in mapreduce. In Sofus A. Macskassy, Claudia Perlich, Jure Leskovec, Wei Wang, and Rayid Ghani, editors, The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '14, pages 641-650. ACM, 2014. Google Scholar
  27. Vincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, and Jakub Tarnawski. Correlation clustering in constant many parallel rounds. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, volume 139 of Proceedings of Machine Learning Research, pages 2069-2078. PMLR, 2021. URL: http://proceedings.mlr.press/v139/cohen-addad21b.html.
  28. Vincent Cohen-Addad, Euiwoong Lee, and Alantha Newman. Correlation clustering with Sherali-Adams. CoRR, abs/2207.10889, 2022. Google Scholar
  29. Bhaskar DasGupta, German Andres Enciso, Eduardo Sontag, and Yi Zhang. Algorithmic and complexity results for decompositions of biological networks into monotone subsystems. Biosystems., 90(1):161-178, July 2007. Google Scholar
  30. James A Davis. Clustering and structural balance in graphs. Human relations, 20(2):181-187, 1967. Google Scholar
  31. Ioannis Giotis and Venkatesan Guruswami. Correlation clustering with a fixed number of clusters. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA '06, pages 1167-1176, 2006. Google Scholar
  32. Frank Harary. On the notion of balance of a signed graph. Michigan Math. J., 2(2), January 1953. Google Scholar
  33. Frank Harary. Signed graphs for portfolio analysis in risk management. IMA Journal of Management Mathematics, 13(3):201-210, 2002. Google Scholar
  34. Frank Harary. On the measurement of structural balance. Behavioral Science, 4(4):316-323, 2007. Google Scholar
  35. Fritz Heider. Attitudes and cognitive organization. J. Psychol., 21:107-112, January 1946. Google Scholar
  36. Fritz Heider. The Psychology of Interpersonal Relations. Psychology Press, 1982. Google Scholar
  37. Falk Hüffner, Nadja Betzler, and Rolf Niedermeier. Separator-based data reduction for signed graph balancing. J. Comb. Optim., 20(4):335-360, November 2010. Google Scholar
  38. Giovanni Iacono, Fahimeh Ramezani, Nicola Soranzo, and Claudio Altafini. Determining the distance to monotonicity of a biological network: a graph-theoretical approach. IET Syst. Biol., 4(3):223-235, May 2010. Google Scholar
  39. Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, STOC '02, pages 767-775, New York, NY, USA, May 2002. Association for Computing Machinery. Google Scholar
  40. Funda Kivran-Swaine, Priya Govindan, and Mor Naaman. The impact of network structure on breaking ties in online social networks: unfollowing on twitter. In Proceedings of the SIGCHI conference on human factors in computing systems, pages 1101-1104. ACM, 2011. Google Scholar
  41. Shachar Lovett. Unconditional pseudorandom generators for low degree polynomials. Theory Comput., 5(1):69-82, 2009. URL: https://doi.org/10.4086/toc.2009.v005a003.
  42. Andrew McGregor. Graph stream algorithms: a survey. SIGMOD Rec., 43(1):9-20, 2014. URL: https://doi.org/10.1145/2627692.2627694.
  43. Michael Moore. An international application of Heider’s balance theory. Eur. J. Soc. Psychol., 8(3):401-405, July 1978. Google Scholar
  44. Joseph Naor and Moni Naor. Small-bias probability spaces: Efficient constructions and applications. SIAM J. Comput., 22(4):838-856, 1993. URL: https://doi.org/10.1137/0222053.
  45. Christos Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. In Proceedings of the twentieth annual ACM symposium on Theory of computing, STOC '88, pages 229-234, New York, NY, USA, January 1988. Google Scholar
  46. Ron M. Roth. Introduction to coding theory. Cambridge University Press, 2006. Google Scholar
  47. Christopher Sibona. Unfriending on facebook: Context collapse and unfriending behaviors. In 2014 47th Hawaii International Conference on System Sciences, pages 1676-1685. ieeexplore.ieee.org, January 2014. Google Scholar
  48. Jiliang Tang, Yi Chang, Charu Aggarwal, and Huan Liu. A survey of signed network mining in social media. ACM Computing Surveys (CSUR), 49(3):1-37, 2016. Google Scholar
  49. Andreia Sofia Teixeira, Francisco C Santos, and Alexandre P Francisco. Emergence of social balance in signed networks. In Complex Networks VIII, pages 185-192. Springer International Publishing, 2017. Google Scholar
  50. Haotian Wang, Feng Luo, and Jie Gao. Co-evolution of opinion and social tie dynamics towards structural balance. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA’22), pages 3362-3388, January 2022. Google Scholar
  51. Bo Xu, Yun Huang, Haewoon Kwak, and Noshir Contractor. Structures of broken ties: Exploring unfollow behavior on twitter. In Proceedings of the 2013 Conference on Computer Supported Cooperative Work, CSCW '13, pages 871-876, 2013. URL: https://doi.org/10.1145/2441776.2441875.
  52. Mihalis Yannakakis. Edge-Deletion problems. SIAM J. Comput., 10(2):297-309, May 1981. Google Scholar
  53. Thomas Zasĺavsky. Balanced decompositions of a signed graph. J. Combin. Theory Ser. B, 43(1):1-13, August 1987. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact