{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,21]],"date-time":"2025-11-21T05:14:12Z","timestamp":1763702052139,"version":"3.45.0"},"reference-count":59,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T00:00:00Z","timestamp":1762732800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T00:00:00Z","timestamp":1762732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"National Science Foundation","award":["OAC- 2107089"],"award-info":[{"award-number":["OAC- 2107089"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Knowl Inf Syst"],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Extreme polarization stands as a crucial concern for fostering a healthier web ecosystem. Locating the polarized groups is pivotal in this context. These groups involve nodes forming robust agreements with each other and engaging in collective conflicts with other groups. Previous studies tackle this problem by focusing on the balanced subgraphs in which all (or small) cycles have an even number of negative edges. However, balanced subgraphs in real-world signed networks are often not inherently polarized, such as those with solely positive edges, and any method that targets balanced subgraphs results in sizable communities with dominantly positive interactions. Building on this concern, we propose to utilize cohesion to find polarized subgraphs in this work. Specifically, we identify pairs of cohesively polarized communities where each node within a community has many positive connections with the nodes in the same community and numerous negative connections with the nodes in the opposing community. We introduce a novel measure, called dichotomy, to capture both cohesion and polarization in a given pair of polarized communities. We show that optimizing dichotomy is NP-hard. As a heuristic approach, we employ balanced triangles to develop a hierarchical dense subgraph discovery algorithm, called atom decomposition, that establishes effective seedbeds for polarized communities in signed networks. To address the challenges posed by real-world signed networks, we introduce two additional algorithms to find polarized communities: photon and electron decompositions. Photon decomposition filters out the nodes that engage in unbalanced triangles and yields numerous cohesively balanced communities. Electron decomposition favors polarized triangles over positive triangles to find polarized communities with high dichotomy. Through comprehensive experiments, we demonstrate that our approaches excel in identifying cohesively polarized communities, surpassing the state-of-the-art methods across various metrics. We give interesting anecdotal findings by using our algorithms on a political network among governments in the Cold War era and a business network of company relationships\/competitions. Overall, our algorithms exhibit greater effectiveness and efficiency than existing methods, rendering them practical for large-scale networks.<\/jats:p>","DOI":"10.1007\/s10115-025-02583-3","type":"journal-article","created":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T03:58:11Z","timestamp":1762747091000},"page":"12001-12028","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Characterizing and locating polarized communities in signed networks"],"prefix":"10.1007","volume":"67","author":[{"given":"Jason","family":"Niu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ahmet Erdem","family":"Sar\u0131y\u00fcce","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,11,10]]},"reference":[{"issue":"5","key":"2583_CR1","doi-asserted-by":"publisher","first-page":"784","DOI":"10.1177\/000312240707200507","volume":"72","author":"D Baldassarri","year":"2007","unstructured":"Baldassarri D, Bearman P (2007) Dynamics of political polarization. Am Sociol Rev 72(5):784\u2013811","journal-title":"Am Sociol Rev"},{"issue":"4","key":"2583_CR2","doi-asserted-by":"publisher","first-page":"680","DOI":"10.1111\/j.1460-2466.2010.01509.x","volume":"60","author":"J Brundidge","year":"2010","unstructured":"Brundidge J (2010) Encountering difference in the contemporary public sphere: the contribution of the internet to the heterogeneity of political discussion networks. J Commun 60(4):680\u2013700","journal-title":"J Commun"},{"doi-asserted-by":"crossref","unstructured":"Esteban JM, Ray D (1994) On the measurement of polarization. Econometrica: Journal of the Econometric Society, pp 819\u2013851","key":"2583_CR3","DOI":"10.2307\/2951734"},{"doi-asserted-by":"crossref","unstructured":"Garimella K, De\u00a0Francisci\u00a0Morales G, Gionis A, et\u00a0al (2017) Reducing controversy by connecting opposing views. In: Proceedings of the tenth ACM international conference on web search and data mining, pp 81\u201390","key":"2583_CR4","DOI":"10.1145\/3018661.3018703"},{"issue":"1","key":"2583_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3140565","volume":"1","author":"K Garimella","year":"2018","unstructured":"Garimella K, Morales GDF, Gionis A et al (2018) Quantifying controversy on social media. ACM Trans Soc Comput 1(1):1\u201327","journal-title":"ACM Trans Soc Comput"},{"doi-asserted-by":"crossref","unstructured":"Kumar S, Hamilton WL, Leskovec J, et\u00a0al (2018) Community interaction and conflict on the web. In: Proceedings of the 2018 world wide web conference, pp 933\u2013943","key":"2583_CR6","DOI":"10.1145\/3178876.3186141"},{"unstructured":"Mejova Y, Zhang AX, Diakopoulos N, et\u00a0al (2014) Controversy and sentiment in online news. arXiv preprint arXiv:1409.8152","key":"2583_CR7"},{"doi-asserted-by":"publisher","unstructured":"Liao QV, Fu WT (2014a) Can you hear me now? Mitigating the echo chamber effect by source position indicators. In: Proceedings of the 17th ACM conference on computer supported cooperative work & social computing. association for computing machinery, New York, NY, USA, CSCW \u201914, pp 184\u2013196, https:\/\/doi.org\/10.1145\/2531602.2531711","key":"2583_CR8","DOI":"10.1145\/2531602.2531711"},{"doi-asserted-by":"crossref","unstructured":"Liao QV, Fu WT (2014b) Expert voices in echo chambers: effects of source expertise indicators on exposure to diverse opinions. In: Proceedings of the SIGCHI conference on human factors in computing systems, pp 2745\u20132754","key":"2583_CR9","DOI":"10.1145\/2556288.2557240"},{"issue":"3","key":"2583_CR10","doi-asserted-by":"publisher","first-page":"033114","DOI":"10.1063\/1.4913758","volume":"25","author":"AJ Morales","year":"2015","unstructured":"Morales AJ, Borondo J, Losada JC et al (2015) Measuring political polarization: Twitter shows the two sides of venezuela. Chaos Interdiscip J Nonlinear Sci 25(3):033114","journal-title":"Chaos Interdiscip J Nonlinear Sci"},{"issue":"8","key":"2583_CR11","first-page":"1655","volume":"66","author":"VV Vydiswaran","year":"2015","unstructured":"Vydiswaran VV, Zhai C, Roth D et al (2015) Overcoming bias to learn about controversial topics. J Am Soc Inf Sci 66(8):1655\u20131672","journal-title":"J Am Soc Inf Sci"},{"doi-asserted-by":"crossref","unstructured":"Bonchi F, Galimberti E, Gionis A, et\u00a0al (2019) Discovering polarized communities in signed networks. In: Proceedings of the 28th ACM international conference on information and knowledge management, pp 961\u2013970","key":"2583_CR12","DOI":"10.1145\/3357384.3357977"},{"key":"2583_CR13","first-page":"10974","volume":"33","author":"RC Tzeng","year":"2020","unstructured":"Tzeng RC, Ordozgoiti B, Gionis A (2020) Discovering conflicting groups in signed networks. Adv Neural Inf Process Syst 33:10974\u201385","journal-title":"Adv Neural Inf Process Syst"},{"key":"2583_CR14","first-page":"362","volume":"2020","author":"H Xiao","year":"2020","unstructured":"Xiao H, Ordozgoiti B, Gionis A (2020) Searching for polarization in signed graphs: a local spectral approach. Proc Web Conf 2020:362\u2013372","journal-title":"Proc Web Conf"},{"issue":"1","key":"2583_CR15","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1080\/00223980.1946.9917275","volume":"21","author":"F Heider","year":"1946","unstructured":"Heider F (1946) Attitudes and cognitive organization. J Psychol 21(1):107\u2013112","journal-title":"J Psychol"},{"issue":"5","key":"2583_CR16","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1037\/h0046049","volume":"63","author":"D Cartwright","year":"1956","unstructured":"Cartwright D, Harary F (1956) Structural balance: a generalization of heider\u2019s theory. Psychol Rev 63(5):277","journal-title":"Psychol Rev"},{"issue":"4","key":"2583_CR17","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1093\/comnet\/cnx044","volume":"6","author":"S Aref","year":"2018","unstructured":"Aref S, Wilson MC (2018) Measuring partial balance in signed networks. J Compl Netw 6(4):566\u2013595","journal-title":"J Compl Netw"},{"key":"2583_CR18","first-page":"1378","volume":"2020","author":"B Ordozgoiti","year":"2020","unstructured":"Ordozgoiti B, Matakos A, Gionis A (2020) Finding large balanced subgraphs in signed networks. Proc Web Conf 2020:1378\u20131388","journal-title":"Proc Web Conf"},{"unstructured":"Cohen J (2008) Trusses: cohesive subgraphs for social network analysis. National Security Agency Technical Report 16(3.1)","key":"2583_CR19"},{"key":"2583_CR20","first-page":"1339","volume":"2023","author":"J Niu","year":"2023","unstructured":"Niu J, Sar\u0131y\u00fcce AE (2023) On cohesively polarized communities in signed networks. Companion Proc ACM Web Conf 2023:1339\u20131347","journal-title":"Companion Proc ACM Web Conf"},{"issue":"2","key":"2583_CR21","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1307\/mmj\/1028989917","volume":"2","author":"F Harary","year":"1953","unstructured":"Harary F (1953) On the notion of balance of a signed graph. Mich Math J 2(2):143\u2013146","journal-title":"Mich Math J"},{"key":"2583_CR22","doi-asserted-by":"publisher","DOI":"10.2307\/j.ctv31r2nfj","volume-title":"Introduction to mathematical sociology","author":"P Bonacich","year":"2012","unstructured":"Bonacich P, Lu P (2012) Introduction to mathematical sociology. Princeton University Press"},{"doi-asserted-by":"crossref","unstructured":"Huang X, Cheng H, Qin L, et\u00a0al (2014) Querying k-truss community in large and dynamic graphs. In: SIGMOD, pp 1311\u20131322","key":"2583_CR23","DOI":"10.1145\/2588555.2610495"},{"doi-asserted-by":"crossref","unstructured":"Sar\u0131y\u00fcce AE, Seshadhri C, P\u0131nar A, et\u00a0al (2015) Finding the hierarchy of dense subgraphs using nucleus decompositions. In: WWW, pp 927\u2013937","key":"2583_CR24","DOI":"10.1145\/2736277.2741640"},{"doi-asserted-by":"crossref","unstructured":"Sariyuce AE, Pinar A (2016) Fast hierarchy construction for dense subgraphs. Proc VLDB Endowment 10(3)","key":"2583_CR25","DOI":"10.14778\/3021924.3021927"},{"unstructured":"Figueiredo R, Frota Y (2013) An improved branch-and-cut code for the maximum balanced subgraph of a signed graph. arXiv preprint arXiv:1312.4345","key":"2583_CR26"},{"issue":"2","key":"2583_CR27","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1016\/j.ejor.2013.12.036","volume":"236","author":"R Figueiredo","year":"2014","unstructured":"Figueiredo R, Frota Y (2014) The maximum balanced subgraph of a signed graph: applications and solution approaches. Eur J Oper Res 236(2):473\u2013487","journal-title":"Eur J Oper Res"},{"doi-asserted-by":"crossref","unstructured":"Charikar M (2000) Greedy approximation algorithms for finding dense components in a graph. In: International workshop on approximation algorithms for combinatorial optimization, Springer, pp 84\u201395","key":"2583_CR28","DOI":"10.1007\/3-540-44436-X_10"},{"doi-asserted-by":"crossref","unstructured":"Chu L, Wang Z, Pei J, et\u00a0al (2016) Finding gangs in war from signed networks. In: Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp 1505\u20131514","key":"2583_CR29","DOI":"10.1145\/2939672.2939855"},{"issue":"1","key":"2583_CR30","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1023\/B:MACH.0000033116.57574.95","volume":"56","author":"N Bansal","year":"2004","unstructured":"Bansal N, Blum A, Chawla S (2004) Correlation clustering. Mach Learn 56(1):89\u2013113","journal-title":"Mach Learn"},{"doi-asserted-by":"crossref","unstructured":"Coleman T, Saunderson J, Wirth A (2008) A local-search 2-approximation for 2-correlation-clustering. In: European symposium on algorithms, Springer, pp 308\u2013319","key":"2583_CR31","DOI":"10.1007\/978-3-540-87744-8_26"},{"unstructured":"Alvarez-Hamelin JI, Barrat A, Vespignani A (2006) Large scale networks fingerprinting and visualization using the k-core decomposition. In: NIPS, pp 41\u201350","key":"2583_CR32"},{"doi-asserted-by":"crossref","unstructured":"Angel A, Koudas N, Sarkas N, et\u00a0al (2012) Dense subgraph maintenance under streaming edge weight updates for real-time story identification. arXiv preprint arXiv:1203.0060","key":"2583_CR33","DOI":"10.14778\/2168651.2168658"},{"issue":"14","key":"2583_CR34","doi-asserted-by":"publisher","first-page":"e150","DOI":"10.1093\/bioinformatics\/btl243","volume":"22","author":"E Fratkin","year":"2006","unstructured":"Fratkin E, Naughton BT, Brutlag DL et al (2006) Motifcut: regulatory motifs finding with maximum density subgraphs. Bioinformatics 22(14):e150\u2013e157","journal-title":"Bioinformatics"},{"unstructured":"Gibson D, Kumar R, Tomkins A (2005) Discovering large dense subgraphs in massive graphs. In: Proceedings of the 31st international conference on Very large data bases, Citeseer, pp 721\u2013732","key":"2583_CR35"},{"doi-asserted-by":"crossref","unstructured":"Lee VE, Ruan N, Jin R, et\u00a0al (2010) A survey of algorithms for dense subgraph discovery. In: Managing and mining graph data, vol\u00a040","key":"2583_CR36","DOI":"10.1007\/978-1-4419-6045-0_10"},{"doi-asserted-by":"crossref","unstructured":"Tsourakakis C, Bonchi F, Gionis A, et\u00a0al (2013) Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees. KDD \u201913","key":"2583_CR37","DOI":"10.1145\/2487575.2487645"},{"doi-asserted-by":"crossref","unstructured":"Gionis A, Tsourakakis CE (2015) Dense subgraph discovery: Tutorial. In: KDD, pp 2313\u20132314","key":"2583_CR38","DOI":"10.1145\/2783258.2789987"},{"issue":"11","key":"2583_CR39","first-page":"1719","volume":"12","author":"Y Fang","year":"2019","unstructured":"Fang Y, Yu K, Cheng R et al (2019) Efficient algorithms for densest subgraph discovery. PVLDB 12(11):1719\u20131732","journal-title":"PVLDB"},{"key":"2583_CR40","first-page":"379","volume":"2021","author":"AE Sariyuce","year":"2021","unstructured":"Sariyuce AE (2021) Motif-driven dense subgraph discovery in directed and labeled networks. Proc Web Conf 2021:379\u2013390","journal-title":"Proc Web Conf"},{"issue":"2","key":"2583_CR41","first-page":"710","volume":"33","author":"R Li","year":"2019","unstructured":"Li R, Dai Q, Qin L et al (2019) Signed clique search in signed networks: concepts and algorithms. IEEE Trans Knowl Data Eng 33(2):710\u201327","journal-title":"IEEE Trans Knowl Data Eng"},{"doi-asserted-by":"crossref","unstructured":"Cadena J, Vullikanti AK, Aggarwal CC (2016) On dense subgraphs in signed network streams. In: 2016 IEEE 16th international conference on data mining (ICDM), IEEE, pp 51\u201360","key":"2583_CR42","DOI":"10.1109\/ICDM.2016.0016"},{"doi-asserted-by":"crossref","unstructured":"Sun R, Zhu Q, Chen C, et\u00a0al (2020) Discovering cliques in signed networks based on balance theory. In: International conference on database systems for advanced applications, pp 666\u2013674","key":"2583_CR43","DOI":"10.1007\/978-3-030-59416-9_43"},{"key":"2583_CR44","first-page":"339","volume":"2020","author":"Z Chen","year":"2020","unstructured":"Chen Z, Yuan L, Lin X et al (2020) Efficient maximal balanced clique enumeration in signed networks. Proc Web Conf 2020:339\u2013349","journal-title":"Proc Web Conf"},{"doi-asserted-by":"crossref","unstructured":"Gao J, Hao F, Min G, et\u00a0al (2021) Maximal multipolarized cliques search in signed networks. In: Proceedings of the 44th international ACM SIGIR conference on research and development in information retrieval, pp 2227\u20132231","key":"2583_CR45","DOI":"10.1145\/3404835.3463014"},{"doi-asserted-by":"crossref","unstructured":"Zhao J, Sun R, Zhu Q, et\u00a0al (2020) Community identification in signed networks: a k-truss based model. In: Proc of the 29th ACM international conf. on information & knowledge management, pp 2321\u20132324","key":"2583_CR46","DOI":"10.1145\/3340531.3412117"},{"doi-asserted-by":"crossref","unstructured":"Wu Y, Sun R, Chen C, et\u00a0al (2020) Maximum signed (k, r)-truss identification in signed networks. In: Proc of the 29th ACM international conf. on information & knowledge management, pp 3337\u20133340","key":"2583_CR47","DOI":"10.1145\/3340531.3417457"},{"issue":"1","key":"2583_CR48","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41598-020-71838-6","volume":"10","author":"S Aref","year":"2020","unstructured":"Aref S, Dinh L, Rezapour R et al (2020) Multilevel structural evaluation of signed directed social networks based on balance theory. Sci Rep 10(1):1\u201312","journal-title":"Sci Rep"},{"doi-asserted-by":"crossref","unstructured":"Huang X, Lu W, Lakshmanan LV (2016) Truss decomposition of probabilistic graphs: semantics and algorithms. In: SIGMOD, pp 77\u201390","key":"2583_CR49","DOI":"10.1145\/2882903.2882913"},{"issue":"1","key":"2583_CR50","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.99.012320","volume":"99","author":"A Kirkley","year":"2019","unstructured":"Kirkley A, Cantwell GT, Newman M (2019) Balance in signed networks. Phys Rev E 99(1):012320","journal-title":"Phys Rev E"},{"doi-asserted-by":"crossref","unstructured":"Guha R, Kumar R, Raghavan P, et\u00a0al (2004) Propagation of trust and distrust. In: Proceedings of the 13th international conference on World Wide Web, pp 403\u2013412","key":"2583_CR51","DOI":"10.1145\/988672.988727"},{"doi-asserted-by":"crossref","unstructured":"Leskovec J, Huttenlocher D, Kleinberg J (2010) Signed networks in social media. In: Proceedings of the SIGCHI conference on human factors in computing systems, pp 1361\u20131370","key":"2583_CR52","DOI":"10.1145\/1753326.1753532"},{"unstructured":"Leskovec J, Krevl A (2014) SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data","key":"2583_CR53"},{"doi-asserted-by":"crossref","unstructured":"Lai M, Patti V, Ruffo G, et\u00a0al (2018) Stance evolution and twitter interactions in an italian political debate. In: International conference on applications of natural language to information systems, Springer, pp 15\u201327","key":"2583_CR54","DOI":"10.1007\/978-3-319-91947-8_2"},{"doi-asserted-by":"crossref","unstructured":"Kunegis J (2013) Konect: The koblenz network collection. WWW Companion, pp 1343\u20131350","key":"2583_CR55","DOI":"10.1145\/2487788.2488173"},{"unstructured":"Niu J, Sar\u0131y\u00fcce AE (2024) Extended version. https:\/\/tinyurl.com\/polarizedExtended","key":"2583_CR56"},{"doi-asserted-by":"crossref","unstructured":"Doreian P, Mrvar A (2019) Structural balance and signed international relations. Journal of Social Structure 16(1)","key":"2583_CR57","DOI":"10.21307\/joss-2019-012"},{"unstructured":"Jurney R (2017) Relato business graph database. https:\/\/data.world\/datasyndrome\/relato-business-graph-database","key":"2583_CR58"},{"unstructured":"Center for Computational Research (2021), University at Buffalo. http:\/\/hdl.handle.net\/10477\/79221","key":"2583_CR59"}],"container-title":["Knowledge and Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-025-02583-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10115-025-02583-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-025-02583-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,21]],"date-time":"2025-11-21T05:07:30Z","timestamp":1763701650000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10115-025-02583-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,10]]},"references-count":59,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["2583"],"URL":"https:\/\/doi.org\/10.1007\/s10115-025-02583-3","relation":{},"ISSN":["0219-1377","0219-3116"],"issn-type":[{"type":"print","value":"0219-1377"},{"type":"electronic","value":"0219-3116"}],"subject":[],"published":{"date-parts":[[2025,11,10]]},"assertion":[{"value":"19 November 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 August 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 August 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 November 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}