{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:20:25Z","timestamp":1759335625893,"version":"3.41.2"},"reference-count":59,"publisher":"Oxford University Press (OUP)","issue":"3","license":[{"start":{"date-parts":[[2022,4,25]],"date-time":"2022-04-25T00:00:00Z","timestamp":1650844800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,4,25]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Community detection is a common task in social network analysis with applications in a variety of fields including medicine, criminology and business. Despite the popularity of community detection, there is no clear consensus on the most effective methodology for signed networks. In this article, we summarize the development of community detection in signed networks and evaluate current state-of-the-art techniques on several real-world datasets. First, we give a comprehensive background of community detection in signed graphs. Next, we compare various adaptations of the Laplacian matrix in recovering ground-truth community labels via spectral clustering in small signed graph datasets. Then, we evaluate the scalability of leading algorithms on small, large, dense and sparse real-world signed graph networks. We conclude with a discussion of our novel findings and recommendations for extensions and improvements in state-of-the-art techniques for signed graph community discovery in real-world signed graphs.<\/jats:p>","DOI":"10.1093\/comnet\/cnac013","type":"journal-article","created":{"date-parts":[[2022,4,15]],"date-time":"2022-04-15T03:59:58Z","timestamp":1649995198000},"source":"Crossref","is-referenced-by-count":5,"title":["Advances in scaling community discovery methods for signed graph networks"],"prefix":"10.1093","volume":"10","author":[{"given":"Maria","family":"Tomasso","sequence":"first","affiliation":[{"name":"Department of Computer Science, Texas State University , 601 University Ave, San Marcos, TX 78666, USA"}]},{"given":"Lucas J","family":"Rusnak","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Texas State University , 601 University Ave, San Marcos, TX 78666, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9972-9760","authenticated-orcid":false,"given":"Jelena","family":"Te\u0161i\u0107","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Texas State University , 601 University Ave, San Marcos, TX 78666, USA"}]}],"member":"286","published-online":{"date-parts":[[2022,6,15]]},"reference":[{"key":"2022061515081337900_B1","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1109\/IBIGDELFT.2018.8625349","article-title":"Application areas of community detection: a review","author":"Karatas,","year":"2018","journal-title":"2018 International Congress on Big Data, Deep Learning and Fighting Cyber Terrorism (IBIGDELFT)"},{"key":"2022061515081337900_B2","article-title":"Social network analysis at scale: graph-based analysis of Twitter trends and communities","volume-title":"Master\u2019s Thesis","author":"Nogueira de Moura,","year":"2020"},{"key":"2022061515081337900_B3","doi-asserted-by":"crossref","first-page":"14339","DOI":"10.1038\/srep14339","article-title":"Community detection in signed networks: the role of negative ties in different scales","volume":"5","author":"Esmailian,","year":"2015","journal-title":"Sci. Rep."},{"key":"2022061515081337900_B4","doi-asserted-by":"crossref","first-page":"7821","DOI":"10.1073\/pnas.122653799","article-title":"Community structure in social and biological networks","volume":"99","author":"Girvan,","year":"2002","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2022061515081337900_B5","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/j.physd.2006.09.028","article-title":"Social balance on networks: the dynamics of friendship and enmity","volume":"224","author":"Antal,","year":"2006","journal-title":"Physica D"},{"key":"2022061515081337900_B6","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1145\/1772690.1772756","article-title":"Predicting positive and negative links in online social networks","author":"Leskovec,","year":"2010","journal-title":"Proceedings of the 19th International Conference on World Wide Web"},{"key":"2022061515081337900_B7","doi-asserted-by":"crossref","first-page":"2176","DOI":"10.1038\/s41598-021-81767-7","article-title":"Topological impact of negative links on the stability of resting-state brain network","volume":"11","author":"Saberi,","year":"2021","journal-title":"Sci. Rep."},{"article-title":"SNAP datasets: Stanford large network dataset collection","year":"2014","author":"Leskovec,","key":"2022061515081337900_B8"},{"key":"2022061515081337900_B9","doi-asserted-by":"crossref","DOI":"10.1145\/2956185","article-title":"A survey of signed network mining in social media","author":"Tang,","year":"2016"},{"article-title":"Spectral theory of unsigned and signed graphs. Applications to graph clustering: a survey","year":"2016","author":"Gallier,","key":"2022061515081337900_B10"},{"key":"2022061515081337900_B11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1086\/soutjanth.10.1.3629074","article-title":"Cultures of the Central Highlands, New Guinea","volume":"10","author":"Read,","year":"1954","journal-title":"Southwest. J. Anthropol."},{"key":"2022061515081337900_B12","article-title":"A novitiate in a period of change: an experimental and case study of relationships","volume-title":"Ph.D. Thesis","author":"Sampson,","year":"1968"},{"key":"2022061515081337900_B13","doi-asserted-by":"crossref","DOI":"10.4135\/9781608718276","article-title":"Resort to war: 1816 - 2007","author":"Sarkees,","year":"2010"},{"key":"2022061515081337900_B14","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1080\/00223980.1946.9917275","article-title":"Attitudes and cognitive organization","volume":"21","author":"Heider,","year":"1946","journal-title":"J. Psychol."},{"key":"2022061515081337900_B15","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1307\/mmj\/1028989917","article-title":"On the notion of balance of a signed graph","volume":"2","author":"Harary,","year":"1953","journal-title":"Michigan Math. J."},{"key":"2022061515081337900_B16","doi-asserted-by":"crossref","first-page":"1333","DOI":"10.1109\/TKDE.2007.1061","article-title":"Community mining from signed social networks","volume":"19","author":"Yang,","year":"2007","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"2022061515081337900_B17","doi-asserted-by":"crossref","first-page":"016114","DOI":"10.1103\/PhysRevE.80.016114","article-title":"Analysis of community structure in networks of correlated data","volume":"80","author":"G\u00f3mez,","year":"2009","journal-title":"Phys. Rev. E"},{"key":"2022061515081337900_B18","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1002\/ejsp.2420080313","article-title":"An international application of Heider\u2019s balance theory","volume":"8","author":"Moore,","year":"1978","journal-title":"Eur. J. Soc. Psychol"},{"key":"2022061515081337900_B19","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1002\/ejsp.2420090309","article-title":"Structural balance and international relations","volume":"9","author":"Moore,","year":"1979","journal-title":"Eur. J. Soc. Psychol."},{"key":"2022061515081337900_B20","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1017\/S000712340000973X","article-title":"A landscape theory of aggregation","volume":"23","author":"Axelrod,","year":"1993","journal-title":"Br. J. Polit. Sci."},{"key":"2022061515081337900_B21","first-page":"1","article-title":"A unified framework for spectral clustering in sparse graphs","volume":"22","author":"Dall\u2019Amico,","year":"2021","journal-title":"J Mach. Learn. Res."},{"key":"2022061515081337900_B22","first-page":"18","article-title":"Normalized cuts and image segmentation","volume":"22","author":"Shi,","year":"2000","journal-title":"IEEE Trans. Patt. Anal. Mach. Intell."},{"key":"2022061515081337900_B23","doi-asserted-by":"crossref","DOI":"10.1007\/s11222-007-9033-z","article-title":"A tutorial on spectral clustering","author":"von Luxburg,","year":"2007"},{"key":"2022061515081337900_B24","first-page":"1027","article-title":"K-means++: the advantages of careful seeding","author":"Arthur,","year":"2006","journal-title":"Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms"},{"key":"2022061515081337900_B25","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1145\/1014052.1014118","article-title":"Kernel k-means: spectral clustering and normalized cuts","volume-title":"Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining","author":"Dhillon,","year":"2004"},{"key":"2022061515081337900_B26","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1137\/S1064827595287997","article-title":"A fast and high quality multilevel scheme for partitioning irregular graphs","volume":"20","author":"Karypis,","year":"1999","journal-title":"SIAM J. Scientific Comput."},{"key":"2022061515081337900_B27","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1137\/1.9781611972801.49","article-title":"Spectral analysis of signed graphs for clustering, prediction and visualization","author":"Kunegis,","year":"2010","journal-title":"Proceedings of the 2010 SIAM International Conference on Data Mining"},{"key":"2022061515081337900_B28","first-page":"207","article-title":"Matrices in the theory of signed simple graphs. In Advances in Discrete Mathematics and Its Applications (Mysore, 2008)","author":"Zaslavsky,","year":"2010","journal-title":"Ramanujan Math. Soc. Lect. Notes Ser., Mysore"},{"key":"2022061515081337900_B29","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1137\/1.9781611974010.7","article-title":"Spectral embedding of signed networks","volume-title":"Proceedings of the 2015 SIAM International Conference on Data Mining","author":"Zheng,","year":"2015"},{"key":"2022061515081337900_B30","first-page":"4421","article-title":"Clustering signed networks with the geometric mean of Laplacians","volume-title":"Advances in Neural Information Processing Systems 29","author":"Mercado,","year":"2016"},{"key":"2022061515081337900_B31","first-page":"4526","article-title":"Spectral clustering of signed graphs via matrix power means","volume-title":"Proceedings of the 36th International Conference on Machine Learning","author":"Mercado,","year":"2019"},{"key":"2022061515081337900_B32","first-page":"615","article-title":"Scalable clustering of signed networks using balance normalized cut","volume-title":"Proceedings of the 21st ACM International Conference on Information and Knowledge Management CIKM \u201912)","author":"Chiang,","year":"2012"},{"key":"2022061515081337900_B33","first-page":"1177","article-title":"Prediction and clustering in signed networks: a local to global perspective","volume":"15","author":"Chiang,","year":"2014","journal-title":"J Mach. Learn. Res."},{"key":"2022061515081337900_B34","first-page":"1088","article-title":"SPONGE: a generalized eigenproblem for clustering signed networks","volume-title":"Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics","author":"Cucuringu,","year":"2019"},{"key":"2022061515081337900_B35","first-page":"577","article-title":"Constrained k-means clustering with background knowledge","volume-title":"Proceedings of the Eighteenth International Conference on Machine Learning (ICML \u201901)","author":"Wagstaff,","year":"2001"},{"key":"2022061515081337900_B36","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1137\/S1064827500366124","article-title":"Toward the optimal preconditioned eigensolver: locally optimal block preconditioned conjugate gradient method","volume":"23","author":"Knyazev,","year":"2001","journal-title":"SIAM J. Sci. Comput."},{"key":"2022061515081337900_B37","doi-asserted-by":"crossref","first-page":"730","DOI":"10.1086\/226141","article-title":"Social structure from multiple networks. i. blockmodels of roles and positions","volume":"81","author":"White,","year":"1976","journal-title":"Am. J. Sociol."},{"key":"2022061515081337900_B38","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1145\/502512.502552","article-title":"Clustering spatial data using random walks","volume-title":"Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Harel,","year":"2001"},{"key":"2022061515081337900_B39","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/j.socnet.2018.08.008","article-title":"Fast clustering for signed graphs based on random walk gap","volume":"60","author":"Hua,","year":"2020","journal-title":"Soc. Netw."},{"key":"2022061515081337900_B40","article-title":"Characterizing attitudinal network graphs through frustration cloud","volume":"6","author":"Rusnak,","year":"2021","journal-title":"Data Mining Knowl. Discov."},{"key":"2022061515081337900_B41","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1109\/TAC.2012.2224251","article-title":"Consensus problems on networks with antagonistic interactions","volume":"58","author":"Altafini,","year":"2013","journal-title":"IEEE Trans. Automatic Control"},{"key":"2022061515081337900_B42","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1145\/2339530.2339612","article-title":"Low rank modeling of signed networks","volume-title":"Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Hsieh,","year":"2012"},{"key":"2022061515081337900_B43","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1137\/1.9781611977172.28","article-title":"SSSNET: semi-supervised signed network clustering","author":"He,","year":"2022","journal-title":"Proceedings of the 2022 SIAM International Conference on Data Mining (SDM)"},{"key":"2022061515081337900_B44","doi-asserted-by":"crossref","first-page":"752","DOI":"10.1145\/3437963.3441778","article-title":"Balance maximization in signed networks via edge deletions","volume-title":"Proceedings of the 14th ACM International Conference on Web Search and Data Mining","author":"Sharma,","year":"2021"},{"key":"2022061515081337900_B45","doi-asserted-by":"crossref","DOI":"10.1145\/3477314.3507243","article-title":"Cluster boosting and data discovery in social networks","author":"Tomasso,","year":"2022","journal-title":"Proceedings of the 37th ACM\/SIGAPP Symposium on Applied Computing Learning"},{"key":"2022061515081337900_B46","doi-asserted-by":"crossref","first-page":"741","DOI":"10.1145\/1526709.1526809","article-title":"The Slashdot zoo: mining a social network with negative edges","volume-title":"Proceedings of the 18th International Conference on World Wide Web","author":"Kunegis,","year":"2009"},{"article-title":"SigNet","year":"2019","author":"Cucuringu,","key":"2022061515081337900_B47"},{"key":"2022061515081337900_B48","article-title":"Clustering Signed Networks with the Geometric Mean of Laplacians","volume-title":"Proceedings of Advances in Neural Information Processing Systems 29 (NIPS 2016)","author":"Mercado,","year":"2016"},{"key":"2022061515081337900_B49","first-page":"4526","article-title":"Spectral Clustering of Signed Graphs via Matrix Power Means","volume-title":"Proceedings of the 36th International Conference on Machine Learning","author":"Mercado,","year":"2019"},{"journal-title":"SSSNET: semi-supervised signed network clustering","year":"2022","author":"He,","key":"2022061515081337900_B50"},{"journal-title":"graphB: Python software package for graph analysis at scale","year":"2020","author":"Te\u0161i\u0107,","key":"2022061515081337900_B51"},{"journal-title":"graphC: Python software package for signed graph clustering comparison","year":"2022","author":"Tomasso","key":"2022061515081337900_B52"},{"key":"2022061515081337900_B53","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1145\/2464464.2464471","article-title":"Producing a unified graph representation from multiple social network views","volume-title":"Proceedings of the 5th Annual ACM Web Science Conference","author":"Greene,","year":"2013"},{"key":"2022061515081337900_B54","doi-asserted-by":"crossref","first-page":"386","DOI":"10.1037\/1082-989X.9.3.386","article-title":"Properties of the Hubert-Arabie adjusted rand index","volume":"9","author":"Steinley,","year":"2004","journal-title":"Psychol. Methods"},{"article-title":"LEAP - high performance computing cluster","year":"2020","author":"Division of Information Technology,","key":"2022061515081337900_B55"},{"key":"2022061515081337900_B56","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3458817.3476153","article-title":"Discovering and balancing fundamental cycles in large signed graphs","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis","author":"Alabandi,","year":"2021"},{"key":"2022061515081337900_B57","first-page":"193","article-title":"BalanSiNG: fast and scalable generation of realistic signed networks","author":"Jung,","year":"2020","journal-title":"EDBT"},{"article-title":"Python Time Library, Python 3 documentation","year":"2020","author":"Foundation,","key":"2022061515081337900_B58"},{"key":"2022061515081337900_B59","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1145\/988672.988727","article-title":"Propagation of trust and distrust","volume-title":"Proceedings of the 13th International Conference on World Wide Web","author":"Guha,","year":"2004"}],"container-title":["Journal of Complex Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comnet\/article-pdf\/10\/3\/cnac013\/44082209\/cnac013.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comnet\/article-pdf\/10\/3\/cnac013\/44082209\/cnac013.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T03:12:26Z","timestamp":1675307546000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comnet\/article\/doi\/10.1093\/comnet\/cnac013\/6608828"}},"subtitle":[],"editor":[{"given":"Tiago P","family":"Peixoto","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2022,4,25]]},"references-count":59,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,4,25]]}},"URL":"https:\/\/doi.org\/10.1093\/comnet\/cnac013","relation":{},"ISSN":["2051-1329"],"issn-type":[{"type":"electronic","value":"2051-1329"}],"subject":[],"published-other":{"date-parts":[[2022,6,1]]},"published":{"date-parts":[[2022,4,25]]},"article-number":"cnac013"}}