{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T02:32:43Z","timestamp":1783045963402,"version":"3.54.6"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2026,2,28]]},"abstract":"<jats:p>\n                    Signed networks represent interactions among users (nodes), with edges labeled as positive for friendly relations and negative for antagonistic ones. The\n                    <jats:sc>2-Polarized-Communities<\/jats:sc>\n                    (\n                    <jats:sc>2pc<\/jats:sc>\n                    ) combinatorial optimization problem seeks two disjoint polarized communities in a signed network, so as to satisfy three conditions: most edges within each community are positive, most edges between communities are negative, and the number of edges satisfying these conditions is high compared to the number of nodes in the communities. The\n                    <jats:sc>Densest Subgraph<\/jats:sc>\n                    (\n                    <jats:sc>ds<\/jats:sc>\n                    ) problem in unsigned networks consists in finding a subgraph that exhibits maximum ratio between number of edges and number of nodes. Although the\n                    <jats:sc>2pc<\/jats:sc>\n                    problem intuitively suggests finding a dense subgraph, no prior work has explored the implicitly optimized density measure or algorithmic methods from the rich, yet distinct, literature on the\n                    <jats:sc>ds<\/jats:sc>\n                    problem (in unsigned networks) and applied them to\n                    <jats:sc>2pc<\/jats:sc>\n                    . This work bridges this gap by formally establishing a link between the two problems and introducing a highly efficient and effective greedy algorithm inspired by\n                    <jats:sc>ds<\/jats:sc>\n                    methods to solve\n                    <jats:sc>2pc<\/jats:sc>\n                    . Experimental results on synthetic and real datasets demonstrate the superior performance of our method compared to competing approaches in terms of both accuracy and efficiency.\n                  <\/jats:p>","DOI":"10.1145\/3779064","type":"journal-article","created":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T13:02:43Z","timestamp":1764594163000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Polarized Communities Meet Densest Subgraph: Efficient and Effective Polarization Detection in Signed Networks"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7052-1114","authenticated-orcid":false,"given":"Francesco","family":"Gullo","sequence":"first","affiliation":[{"name":"University of L\u2019Aquila, L\u2019Aquila, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8506-1974","authenticated-orcid":false,"given":"Domenico","family":"Mandaglio","sequence":"additional","affiliation":[{"name":"University of Calabria, Rende, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8142-503X","authenticated-orcid":false,"given":"Andrea","family":"Tagarelli","sequence":"additional","affiliation":[{"name":"University of Calabria, Rende, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,1,13]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"crossref","unstructured":"Rediet Abebe T.-H. Hubert Chan Jon Kleinberg Zhibin Liang David Parkes Mauro Sozio and Charalampos E. Tsourakakis. 2021. Opinion dynamics optimization by varying susceptibility to persuasion via non-convex local search. ACM Transactions on Knowledge Discovery from Data 16 2 (2021) 1\u201334.","DOI":"10.1145\/3466617"},{"key":"e_1_3_2_3_2","doi-asserted-by":"crossref","unstructured":"Victor Amelkin Petko Bogdanov and Ambuj K. Singh. 2019. A distance measure for the analysis of polar opinion dynamics in social networks. ACM Transactions on Knowledge Discovery from Data 13 4 (2019) 1\u201334.","DOI":"10.1145\/3332168"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033116.57574.95"},{"key":"e_1_3_2_5_2","first-page":"539","volume-title":"Proceedings of the ICWSM Conference","author":"Beigi Ghazaleh","year":"2016","unstructured":"Ghazaleh Beigi, Jiliang Tang, and Huan Liu. 2016. Signed link analysis in social media networks. In Proceedings of the ICWSM Conference, 539\u2013542."},{"key":"e_1_3_2_6_2","first-page":"961","volume-title":"Proceedings of the CIKM Conference","author":"Bonchi Francesco","year":"2019","unstructured":"Francesco Bonchi, Edoardo Galimberti, Aristides Gionis, Bruno Ordozgoiti, and Giancarlo Ruffo. 2019. Discovering polarized communities in signed networks. In Proceedings of the CIKM Conference, 961\u2013970."},{"key":"e_1_3_2_7_2","first-page":"573","volume-title":"Proceedings of the WWW Conference","author":"Boob Digvijay","year":"2020","unstructured":"Digvijay Boob, Yu Gao, Richard Peng, Saurabh Sawlani, Charalampos Tsourakakis, Di Wang, and Junxing Wang. 2020. Flowless: Extracting densest subgraphs without flow computations. In Proceedings of the WWW Conference, 573\u2013583."},{"key":"e_1_3_2_8_2","first-page":"84","volume-title":"Proceedings of the APPROX Work","author":"Moses Charikar","year":"2003","unstructured":"Charikar Moses. 2003. Greedy approximation algorithms for finding dense components in a graph. In Proceedings of the APPROX Work, 84\u201395."},{"key":"e_1_3_2_9_2","first-page":"524","volume-title":"Proceedings of the FOCS Symposium","author":"Charikar M.","year":"2003","unstructured":"M. Charikar, V. Guruswami, and A. Wirth. 2003. Clustering with qualitative information. In Proceedings of the FOCS Symposium, 524\u2013533."},{"key":"e_1_3_2_10_2","first-page":"1531","volume-title":"Proceedings of the SODA Conference","author":"Chekuri Chandra","year":"2022","unstructured":"Chandra Chekuri, Kent Quanrud, and Manuel R. Torres. 2022. Densest subgraph: Supermodularity, iterative peeling, and flow. In Proceedings of the SODA Conference, 1531\u20131555."},{"key":"e_1_3_2_11_2","first-page":"278","volume-title":"Proceedings of the KDD Conference","author":"Chen Jingbang","year":"2024","unstructured":"Jingbang Chen, Qiuyang Mang, Hangrui Zhou, Richard Peng, Yu Gao, and Chenhao Ma. 2024. Scalable algorithm for finding balanced subgraphs with tolerance in signed networks. In Proceedings of the KDD Conference, 278\u2013287."},{"key":"e_1_3_2_12_2","first-page":"615","volume-title":"Proceedings of the CIKM Conference","author":"Chiang Kai-Yang","year":"2012","unstructured":"Kai-Yang Chiang, Joyce Jiyoung Whang, and Inderjit S. Dhillon. 2012. Scalable clustering of signed networks using balance normalized cut. In Proceedings of the CIKM Conference, 615\u2013624."},{"key":"e_1_3_2_13_2","first-page":"1505","volume-title":"Proceedings of the KDD Conference","author":"Chu Lingyang","year":"2016","unstructured":"Lingyang Chu, Zhefeng Wang, Jian Pei, Jiannan Wang, Zijin Zhao, and Enhong Chen. 2016. Finding gangs in war from signed networks. In Proceedings of the KDD Conference, 1505\u20131514."},{"key":"e_1_3_2_14_2","first-page":"89","volume-title":"Proceedings of the ICWSM Conference","author":"Conover M.","year":"2011","unstructured":"M. Conover, J. Ratkiewicz, M. Francisco, B. Goncalves, F. Menczer, and A. Flammini. 2011. Political polarization on twitter. In Proceedings of the ICWSM Conference, 89\u201396."},{"key":"e_1_3_2_15_2","first-page":"1088","volume-title":"Proceedings of the AISTATS Conference","author":"Cucuringu Mihai","year":"2019","unstructured":"Mihai Cucuringu, Peter Davies, Aldo Glielmo, and Hemant Tyagi. 2019. SPONGE: A generalized eigenproblem for clustering signed networks. In Proceedings of the AISTATS Conference, 1088\u20131098."},{"key":"e_1_3_2_16_2","first-page":"557","volume-title":"Proceedings of the CIKM Conference","author":"Derr Tyler","year":"2018","unstructured":"Tyler Derr, Charu C. Aggarwal, and Jiliang Tang. 2018. Signed network modeling based on structural balance theory. In Proceedings of the CIKM Conference, 557\u2013566."},{"key":"e_1_3_2_17_2","first-page":"929","volume-title":"Proceedings of the ICDM Conference","author":"Derr Tyler","year":"2018","unstructured":"Tyler Derr, Yao Ma, and Jiliang Tang. 2018. Signed graph convolutional networks. In Proceedings of the ICDM Conference, 929\u2013934."},{"issue":"12","key":"e_1_3_2_18_2","first-page":"3766","article-title":"Densest subgraph discovery on large graphs: Applications, challenges, and techniques","volume":"15","author":"Fang Yixiang","year":"2022","unstructured":"Yixiang Fang, Wensheng Luo, and Chenhao Ma. 2022. Densest subgraph discovery on large graphs: Applications, challenges, and techniques. Proceedings of the VLDB Conference 15, 12 (2022), 3766\u20133769.","journal-title":"Proceedings of the VLDB Conference"},{"key":"e_1_3_2_19_2","first-page":"81","volume-title":"Proceedings of the WSDM Conference","author":"Garimella Kiran","year":"2017","unstructured":"Kiran Garimella, Gianmarco De Francisci Morales, Aristides Gionis, and Michael Mathioudakis. 2017. Reducing controversy by connecting opposing views. In Proceedings of the WSDM Conference, 81\u201390."},{"key":"e_1_3_2_20_2","unstructured":"Andrew V. Goldberg. 1984. Finding a Maximum Density Subgraph. University of California Berkeley Berkeley CA."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-024-06581-4"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1307\/mmj\/1028989917"},{"key":"e_1_3_2_23_2","first-page":"26966","article-title":"Faster and scalable algorithms for densest subgraph and decomposition","volume":"35","author":"Harb Elfarouk","year":"2022","unstructured":"Elfarouk Harb, Kent Quanrud, and Chandra Chekuri. 2022. Faster and scalable algorithms for densest subgraph and decomposition. In Proceedings of the NIPS Conference, Vol. 35, 26966\u201326979.","journal-title":"Proceedings of the NIPS Conference"},{"key":"e_1_3_2_24_2","first-page":"627","volume-title":"Proceedings of the FOCS Symposium","author":"Hastad J.","year":"1996","unstructured":"J. Hastad. 1996. Clique is hard to approximate within \\(n^{1-\\epsilon}\\) . In Proceedings of the FOCS Symposium, 627."},{"key":"e_1_3_2_25_2","first-page":"244","volume-title":"Proceedings of the SDM Conference","author":"He Yixuan","year":"2022","unstructured":"Yixuan He, Gesine Reinert, Songchao Wang, and Mihai Cucuringu. 2022. SSSNET: Semi-supervised signed network clustering. In Proceedings of the SDM Conference, 244\u2013252."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1126\/sciadv.abq2044"},{"key":"e_1_3_2_27_2","first-page":"1343","volume-title":"Proceedings of the WWW Conference","author":"Kunegis J\u00e9r\u00f4me","year":"2013","unstructured":"J\u00e9r\u00f4me Kunegis. 2013. KONECT\u2014The Koblenz network collection. In Proceedings of the WWW Conference, 1343\u20131350. Retrieved from http:\/\/konect.cc"},{"key":"e_1_3_2_28_2","first-page":"559","volume-title":"Proceedings of the SDM Conference","author":"Kunegis J\u00e9r\u00f4me","year":"2010","unstructured":"J\u00e9r\u00f4me Kunegis, Stephan Schmidt, Andreas Lommatzsch, J\u00fcrgen Lerner, Ernesto William De Luca, and Sahin Albayrak. 2010. Spectral analysis of signed graphs for clustering, prediction and visualization. In Proceedings of the SDM Conference, 559\u2013570."},{"key":"e_1_3_2_29_2","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1145\/3614419.3644013","volume-title":"Proceedings of the of the ACM Web Science Conference","author":"La Cava Lucio","year":"2024","unstructured":"Lucio La Cava, Domenico Mandaglio, and Andrea Tagarelli. 2024. Polarization in decentralized online social networks. In Proceedings of the of the ACM Web Science Conference, 48\u201352."},{"key":"e_1_3_2_30_2","first-page":"15","volume-title":"Proceedings of the NLDB Conference","author":"Lai Mirko","year":"2018","unstructured":"Mirko Lai, Viviana Patti, Giancarlo Ruffo, and Paolo Rosso. 2018. Stance evolution and twitter interactions in an Italian political debate. In Proceedings of the NLDB Conference, 15\u201327."},{"key":"e_1_3_2_31_2","doi-asserted-by":"crossref","unstructured":"Tommaso Lanciano Atsushi Miyauchi Adriano Fazzone and Francesco Bonchi. 2024. A survey on the densest subgraph problem and its variants. ACM Computing Surveys 56 8 (2024) 1\u201340.","DOI":"10.1145\/3653298"},{"key":"e_1_3_2_32_2","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/978-1-4419-6045-0_10","volume-title":"Managing and Mining Graph Data","volume":"40","author":"Lee Victor E.","year":"2010","unstructured":"Victor E. Lee, Ning Ruan, Ruoming Jin, and Charu C. Aggarwal. 2010. A survey of algorithms for dense subgraph discovery. In Managing and Mining Graph Data. C. Aggarwal and H. Wang (Eds.), Vol. 40, Springer, Boston, 303\u2013336."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1093\/poq\/nfw005"},{"key":"e_1_3_2_34_2","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http:\/\/snap.stanford.edu\/data"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.engappai.2024.108851"},{"key":"e_1_3_2_36_2","first-page":"4772","volume-title":"Proceedings of the AAAI Conference","author":"Li Yu","year":"2020","unstructured":"Yu Li, Yuan Tian, Jiawei Zhang, and Yi Chang. 2020. Learning signed network embedding via graph attention. In Proceedings of the AAAI Conference, 4772\u20134779."},{"key":"e_1_3_2_37_2","first-page":"1066","volume-title":"Proceedings of the KDD Conference","author":"Liu Haoxin","year":"2021","unstructured":"Haoxin Liu, Ziwei Zhang, Peng Cui, Yafeng Zhang, Qiang Cui, Jiashuo Liu, and Wenwu Zhu. 2021. Signed graph neural network with latent groups. In Proceedings of the KDD Conference, 1066\u20131075."},{"key":"e_1_3_2_38_2","doi-asserted-by":"crossref","unstructured":"Fragkiskos D. Malliaros Christos Giatsidis Apostolos N. Papadopoulos and Michalis Vazirgiannis. 2020. The core decomposition of networks: Theory algorithms and applications. The VLDB Journal 29 1 (2020) 61\u201392.","DOI":"10.1007\/s00778-019-00587-4"},{"key":"e_1_3_2_39_2","first-page":"4421","volume-title":"Proceedings of the NIPS Conference","author":"Mercado Pedro","year":"2016","unstructured":"Pedro Mercado, Francesco Tudisco, and Matthias Hein. 2016. Clustering signed networks with the geometric mean of Laplacians. In Proceedings of the NIPS Conference, 4421\u20134429."},{"key":"e_1_3_2_40_2","first-page":"1339","volume-title":"Proceedings of the WWW Conference","author":"Niu Jason","year":"2023","unstructured":"Jason Niu and Ahmet Erdem Sariy\u00fcce. 2023. On cohesively polarized communities in signed networks. In Proceedings of the WWW Conference, 1339\u20131347."},{"key":"e_1_3_2_41_2","first-page":"1378","volume-title":"Proceedings of the WWW Conference","author":"Ordozgoiti Bruno","year":"2020","unstructured":"Bruno Ordozgoiti, Antonis Matakos, and Aristides Gionis. 2020. Finding large balanced subgraphs in signed networks. In Proceedings of the WWW Conference, 1378\u20131388."},{"key":"e_1_3_2_42_2","doi-asserted-by":"crossref","unstructured":"Seyed-Vahid Sanei-Mehri Apurba Das Hooman Hashemi and Srikanta Tirthapura. 2021. Mining largest maximal quasi-cliques. ACM Transactions on Knowledge Discovery from Data 15 5 (2021) 1\u201321.","DOI":"10.1145\/3446637"},{"key":"e_1_3_2_43_2","first-page":"939","volume-title":"Proceedings of the ACL Conference","author":"Sedoc Joao","year":"2017","unstructured":"Joao Sedoc, Jean Gallier, Dean Foster, and Lyle Ungar. 2017. Semantic word clusters using signed spectral clustering. In Proceedings of the ACL Conference, 939\u2013949."},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2025.3570354"},{"key":"e_1_3_2_45_2","first-page":"104","volume-title":"Proceedings of the KDD Conference","author":"Tsourakakis Charalampos","year":"2013","unstructured":"Charalampos Tsourakakis, Francesco Bonchi, Aristides Gionis, Francesco Gullo, and Maria Tsiarli. 2013. Denser than the densest subgraph: Extracting optimal quasi-cliques with quality guarantees. In Proceedings of the KDD Conference, 104\u2013112."},{"key":"e_1_3_2_46_2","first-page":"1122","volume-title":"Proceedings of the WWW Conference","author":"Tsourakakis Charalampos E.","year":"2015","unstructured":"Charalampos E. Tsourakakis. 2015. The K-clique densest subgraph problem. In Proceedings of the WWW Conference, 1122\u20131132."},{"key":"e_1_3_2_47_2","first-page":"10974","volume-title":"Proceedings of the NIPS Conference","volume":"33","author":"Tzeng Ruo-Chun","year":"2020","unstructured":"Ruo-Chun Tzeng, Bruno Ordozgoiti, and Aristides Gionis. 2020. 2020. Discovering conflicting groups in signed networks. In Proceedings of the NIPS Conference, Vol. 33, 10974\u201310985."},{"key":"e_1_3_2_48_2","first-page":"362","volume-title":"Proceedings of the WWW Conference","author":"Xiao Han","year":"2020","unstructured":"Han Xiao, Bruno Ordozgoiti, and Aristides Gionis. 2020. Searching for polarization in signed graphs: A local spectral approach. In Proceedings of the WWW Conference, 362\u2013372."},{"key":"e_1_3_2_49_2","first-page":"1004","volume-title":"Proceedings of the ICDE Conference","author":"Yao Kai","year":"2022","unstructured":"Kai Yao, Lijun Chang, and Lu Qin. 2022. Computing maximum structural balanced cliques in signed graphs. In Proceedings of the ICDE Conference, 1004\u20131016."},{"issue":"2","key":"e_1_3_2_50_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3625826","article-title":"Maximizing the diversity of exposure in online social networks by identifying users with increased susceptibility to persuasion","volume":"18","author":"Zareie Ahmad","year":"2023","unstructured":"Ahmad Zareie and Rizos Sakellariou. 2023. Maximizing the diversity of exposure in online social networks by identifying users with increased susceptibility to persuasion. ACM Transactions on Knowledge Discovery from Data 18, 2 (2023), 1\u201321.","journal-title":"ACM Transactions on Knowledge Discovery from Data"},{"key":"e_1_3_2_51_2","first-page":"655","volume-title":"IEEE Transactions on Knowledge and Data Engineering","volume":"37","author":"Zhang Qiqi","year":"2025","unstructured":"Qiqi Zhang, Lingyang Chu, Zijin Zhao, and Jian Pei. 2025. Finding antagonistic communities in signed uncertain graphs. IEEE Transactions on Knowledge and Data Engineering 37, 2 (2025), 655\u2013669."},{"key":"e_1_3_2_52_2","doi-asserted-by":"crossref","unstructured":"Xiaolong Zheng Daniel Dajun Zeng and Fei-Yue Wang. 2015. Social balance in signed networks. Information Systems Frontiers 17 5 (2015) 1077\u20131095.","DOI":"10.1007\/s10796-014-9483-8"},{"issue":"2","key":"e_1_3_2_53_2","first-page":"689","article-title":"Community detection in graph: An embedding method","volume":"9","author":"Zhu Junyou","year":"2021","unstructured":"Junyou Zhu, Chunyu Wang, Chao Gao, Fan Zhang, Zhen Wang, and Xuelong Li. 2021. Community detection in graph: An embedding method. IEEE Transactions on Network Science and Engineering 9, 2 (2021), 689\u2013702.","journal-title":"IEEE Transactions on Network Science and Engineering"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3779064","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T14:54:39Z","timestamp":1768316079000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3779064"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,13]]},"references-count":52,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,2,28]]}},"alternative-id":["10.1145\/3779064"],"URL":"https:\/\/doi.org\/10.1145\/3779064","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,13]]},"assertion":[{"value":"2025-05-13","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-15","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-01-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}