Topical Section: Structure and Dynamics of Signed Networks — Guest Editors: Renaud Lambiotte (University of Oxford) and Vincent Traag (Leiden University)No Access

Department of Methodology & Statistics, Utrecht University, Utrecht, The Netherlands

Centre for Complex Systems Studies, Utrecht University, Utrecht, The Netherlands

Corresponding author.

Search for more papers by this author

ERIK-JAN VAN KESTEREN

https://orcid.org/0000-0003-1548-1663

Department of Methodology & Statistics, Utrecht University, Utrecht, The Netherlands

Search for more papers by this author

SOFIA CHELMI

Department of Methodology & Statistics, Utrecht University, Utrecht, The Netherlands

Search for more papers by this author

, and

JAVIER GARCIA-BERNARDO

https://orcid.org/0000-0002-6119-1790

Department of Methodology & Statistics, Utrecht University, Utrecht, The Netherlands

Centre for Complex Systems Studies, Utrecht University, Utrecht, The Netherlands

Search for more papers by this author

https://doi.org/10.1142/S0219525925400028Cited by:0 (Source: Crossref)

View article

Abstract

Decision-making processes often involve voting. Human interactions with exogenous entities such as legislations or products can be effectively modeled as two-mode (bipartite) signed networks — where people can either vote positively, negatively, or abstain from voting on the entities. Detecting communities in such networks could help us understand underlying properties: for example ideological camps or consumer preferences. While community detection is an established practice separately for bipartite and signed networks, it remains largely unexplored in the case of bipartite signed networks. In this paper, we systematically evaluate the efficacy of community detection methods on projected bipartite signed networks using a synthetic benchmark and real-world datasets. Our findings reveal that when no communities are present in the data, these methods often recover spurious user communities. When communities are present, the algorithms exhibit promising performance, although their performance is highly susceptible to parameter choice. This indicates that researchers using community detection methods in the context of bipartite signed networks should not take the communities found at face value: it is essential to assess the robustness of parameter choices or perform domain-specific external validation.

Keywords:

References

[1] S. Fortunato, Community detection in graphs, Phys. Rep. 486 (2010) 75–174, https://doi.org/10.1016/j.physrep.2009.11.002. Crossref, Web of Science, Google Scholar
[2] M. J. Barber, Modularity and community detection in bipartite networks, Phys. Rev. E 76 (2007) 066102, https://doi.org/10.1103/PhysRevE.76.066102. Crossref, Web of Science, Google Scholar
[3] T.-C. Yen and D. B. Larremore, Community detection in bipartite networks with stochastic block models, Phys. Rev. E 102 (2020) 032309, https://doi.org/10.1103/PhysRevE.102. 032309. Crossref, Web of Science, Google Scholar
[4] S. J. Beckett, Improved community detection in weighted bipartite networks, R. Soc. Open Sci. 3 (2016) 140536, https://doi.org/10.1098/rsos.140536. Crossref, Web of Science, Google Scholar
[5] P. Doreian and A. Mrvar, A partitioning approach to structural balance, Soc. Netw. 18 (1996) 149–168, https://doi.org/10.1016/0378-8733(95)00259-6. Crossref, Web of Science, Google Scholar
[6] M. Tomasso, L. Rusnak and J. Tešić, Advances in scaling community discovery methods for signed graph networks, J. Complex Netw. 10 (2022) cnac013, https://doi.org/10.1093/comnet/cnac013. Crossref, Web of Science, Google Scholar
[7] M. Cucuringu, P. Davies, A. Glielmo and H. Tyagi, SPONGE: A generalized eigenproblem for clustering signed networks, in Proc. Twenty-Second Int. Conf. Artificial Intelligence and Statistics, Vol. 89 (Proceedings of Machine Learning Research, 2019), pp. 1088–1098, https://doi.org/10.48550/arXiv.1904.08575. Google Scholar
[8] V. A. Traag and J. Bruggeman, Community detection in networks with positive and negative links, Phys. Rev. E 80 (2009) 036115, https://doi.org/10.1103/PhysRevE.80.036115. Crossref, Web of Science, Google Scholar
[9] P. Doreian and A. Mrvar, Partitioning signed social networks, Soc. Netw. 31 (2009) 1–11, https://doi.org/10.1016/j.socnet.2008.08.001. Crossref, Web of Science, Google Scholar
[10] Z. P. Neal, A sign of the times? Weak and strong polarization in the U.S. Congress, 1973–2016, Soc. Netw. 60 (2020) 103–112, https://doi.org/10.1016/j.socnet.2018.07.007. Crossref, Google Scholar
[11] J. Leskovec, D. Huttenlocher and J. Kleinberg, Signed networks in social media, in Proc. SIGCHI Conf. Human Factors in Computing Systems (ACM, Atlanta Georgia USA, 2010), pp. 1361–1370, https://doi.org/10.1145/1753326.1753532. Crossref, Google Scholar
[12] M. Kros, E. Jaspers and M. van Zalk, Avoidance, antipathy, and aggression: A three-wave longitudinal network study on negative networks, status, and heteromisos, Soc. Netw. 64 (2021) 122–133, https://doi.org/10.1016/j.socnet.2020.08.006. Crossref, Web of Science, Google Scholar
[13] Office of the Clerk, U.S. House of Representatives, https://clerk.house.gov/. Google Scholar
[14] Menéame — Portada de noticias de, https://www.meneame.net/. Google Scholar
[15] P. F. Jonsson, T. Cavanna, D. Zicha and P. A. Bates, Cluster analysis of networks generated through homology: Automatic identification of important protein communities involved in cancer metastasis, BMC Bioinform. 7 (2006) 2, https://doi.org/10.1186/1471-2105-7-2. Crossref, Web of Science, Google Scholar
[16] L. A. Adamic and N. Glance, The political blogosphere and the 2004 U.S. election: Divided they blog, in Proc. 3rd Int. Workshop on Link Discovery LinkKDD ’05, (Association for Computing Machinery, New York, NY, USA, 2005), pp. 36–43, https://doi.org/10.1145/1134271.1134277. Crossref, Google Scholar
[17] M. Girvan and M. Newman, Community structure in social and biological networks, Proc. Natl. Acad. Sci. USA 99(12) (2002) 7821–7826, https://doi.org/10.1073/pnas.122653799. Crossref, Web of Science, Google Scholar
[18] S. Talaga, M. Stella, T. J. Swanson and A. S. Teixeira, Polarization and multiscale structural balance in signed networks, Commun. Phys. 6 (2023) 1–15, https://doi.org/10.1038/s42005-023-01467-8. Crossref, Web of Science, Google Scholar
[19] F. Bonchi, E. Galimberti, A. Gionis, B. Ordozgoiti and G. Ruffo, Discovering polarized communities in signed networks, in Proc. 28th ACM Int. Conf. Information and Knowledge Management CIKM ’19 (Association for Computing Machinery, New York, NY, USA, 2019), pp. 961–970, https://doi.org/10.1145/3357384.3357977. Crossref, Google Scholar
[20] F. Heider, The Psychology of Interpersonal Relations (John Wiley & Sons, Hoboken, NJ, US, 1958), https://doi.org/10.1037/10628-000. Crossref, Google Scholar
[21] D. Cartwright and F. Harary, Structural balance: A generalization of Heider’s theory, Psychol. Rev. 63(5) (1956) 277–293, https://doi.org/10.1037/h0046049. Crossref, Web of Science, Google Scholar
[22] E. Estrada and M. Benzi, Walk-based measure of balance in signed networks: Detecting lack of balance in social networks, Phys. Rev. E 90 (2014) 042802, https://doi.org/10.1103/PhysRevE.90.042802. Crossref, Web of Science, Google Scholar
[23] S. Aref and M. C. Wilson, Measuring partial balance in signed networks, J. Complex Netw. 6 (2018) 566–595, https://doi.org/10.1093/comnet/cnx044. Crossref, Web of Science, Google Scholar
[24] E. Estrada, Rethinking structural balance in signed social networks, Discret. Appl. Math. 268 (2019) 70–90, https://doi.org/10.1016/j.dam.2019.04.019. Crossref, Web of Science, Google Scholar
[25] P. Doreian and A. Mrvar, Structural balance and signed international relations, J. Soc. Struct. 16 (2015) 1–49, https://doi.org/10.21307/joss-2019-012. Crossref, Google Scholar
[26] F. Diaz-Diaz, P. Bartesaghi and E. Estrada, Local balance of signed networks: Definition and application to reveal historical events in international relations arXiv:abs/2303.03774v2. Google Scholar
[27] E. Fraxanet, M. Pellert, S. Schweighofer, V. Gómez and D. Garcia, Unpacking polarization: Antagonism and alignment in signed networks of online interaction, arXiv:abs/2307.06571v2. Google Scholar
[28] S. Aref and M. C. Wilson, Balance and frustration in signed networks, J. Complex Netw. 7 (2019) 163–189, https://doi.org/10.1093/comnet/cny015. Crossref, Web of Science, Google Scholar
[29] J. A. Davis, Clustering and structural balance in graphs, Hum. Relat. 20 (1967) 181–187, https://doi.org/10.1177/001872676702000206. Crossref, Web of Science, Google Scholar
[30] A. S. Asratian, Bipartite Graphs and Their Applications (Cambridge University Press, Cambridge, UK, 1998). Crossref, Google Scholar
[31] D. J. Watts and S. H. Strogatz, Collective dynamics of ‘small-world’ networks, Nature 393 (1998) 440–442, https://doi.org/10.1038/30918. Crossref, Web of Science, Google Scholar
[32] T. Derr, C. Johnson, Y. Chang and J. Tang, Balance in signed bipartite networks, in Proc. 28th ACM Int. Conf. Information and Knowledge Management (Association for Computing Machinery, 2019), pp. 1221–1230. Crossref, Google Scholar
[33] J. Lee, G. Li and J. D. Wilson, Varying-coefficient models for dynamic networks, Comput. Stat. Data Anal. 152 (2020) 107052, https://doi.org/10.1016/j.csda.2020.107052. Crossref, Web of Science, Google Scholar
[34] C. Andris, D. Lee, M. J. Hamilton, M. Martino, C. E. Gunning and J. A. Selden, The rise of partisanship and super-cooperators in the U.S. House of representatives, PLoS ONE 10 (2015) e0123507, https://doi.org/10.1371/journal.pone.0123507. Crossref, Web of Science, Google Scholar
[35] J. M. Enelow and M. J. Hinich, The Spatial Theory of Voting: An Introduction (CUP Archive, 1984). Google Scholar
[36] K. T. Poole and H. Rosenthal, A spatial model for legislative roll call analysis, Am. J. Political Sci. 29(2) (1985) 357–384, https://doi.org/10.2307/2111172. Crossref, Web of Science, Google Scholar
[37] K. T. Poole, Spatial Models of Parliamentary Voting, Analytical Methods for Social Research (Cambridge University Press, Cambridge, 2005). Crossref, Google Scholar
[38] J. Clinton, S. Jackman and D. Rivers, The statistical analysis of roll call data, Am. J. Political Sci. 98 (2004) 355–370, https://doi.org/10.1017/S0003055404001194. Google Scholar
[39] X. Yu and A. Rodríguez, Spatial voting models in circular spaces: A case study of the U.S. House of Representatives, Ann. Appl. Stat. 15 (2021) 1897–1922, https://doi.org/10.1214/21-AOAS1454. Crossref, Google Scholar
[40] R. Carroll, Ideal Point Estimation in Political Science (Oxford University Press, 2023). https://doi.org/10.1093/obo/9780199756223-0360. Google Scholar
[41] J. Moody and P. J. Mucha, Portrait of political party polarization, Netw. Sci. 1 (2013) 119–121, https://doi.org/10.1017/nws.2012.3. Crossref, Google Scholar
[42] A. S. Waugh, L. Pei, J. H. Fowler, P. J. Mucha and M. A. Porter, Party polarization in congress: A network science approach, arXiv:0907.3509, 10.48550/ARXIV.0907.3509. Google Scholar
[43] Y. Zhang, A. J. Friend, A. L. Traud, M. A. Porter, J. H. Fowler and P. J. Mucha, Community structure in congressional cosponsorship networks, Physica A 387 (2008) 1705–1712, https://doi.org/10.1016/j.physa.2007.11.004. Crossref, Web of Science, Google Scholar
[44] P. J. Mucha, T. Richardson, K. Macon, M. A. Porter and J.-P. Onnela, Community structure in time-dependent, multiscale, and multiplex networks, Science 328 (2010) 876–878, https://doi.org/10.1126/science.1184819. Crossref, Web of Science, Google Scholar
[45] J. D. Wilson, N. T. Stevens and W. H. Woodall, Modeling and detecting change in temporal networks via a dynamic degree corrected stochastic block model, arXiv:1605.04049. Google Scholar
[46] J. Huang, H. Shen, Q. Cao, S. Tao and X. Cheng, Signed bipartite graph neural networks, arXiv:2108.09638. Google Scholar
[47] P. Barberá, Birds of the same feather tweet together: Bayesian ideal point estimation using twitter data, Political Anal. 23 (2015) 76–91, https://doi.org/10.1093/pan/mpu011. Crossref, Web of Science, Google Scholar
[48] R. Kubinec, Generalized ideal point models for time-varying and missing-data inference, Open Sci. Found. Preprints 10 (2019) 6. Google Scholar
[49] A. T. Institute, SigNet package (2023), https://github.com/alan-turing-institute/ SigNet. Google Scholar
[50] J. Reichardt and S. Bornholdt, Statistical mechanics of community detection, Phys. Rev. E 74 (2006) 016110, https://doi.org/10.1103/PhysRevE.74.016110. Crossref, Web of Science, Google Scholar
[51] G. Csardi and T. Nepusz, The igraph software package for complex network research, InterJournal, Complex Systems (2006) 1695, https://igraph.org. Google Scholar
[52] W. M. Rand, Objective criteria for the evaluation of clustering methods, J. Am. Stat. Assoc. 66 (1971) 846–850, https://doi.org/10.1080/01621459.1971.10482356. Crossref, Web of Science, Google Scholar
[53] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot and E. Duchesnay, Scikit-learn: Machine learning in python, J. Mach. Learn. Res. 12 (2011) 2825–2830. Web of Science, Google Scholar
[54] N. Mccarty, The policy effects of political polarization, in The Transformation of American Politics, eds. P. Pierson and T. Skocpol (Princeton University Press, 2007), pp. 223–255, https://doi.org/10.1515/9781400837502-013. Crossref, Google Scholar
[55] L. Hubert and P. Arabie, Comparing partitions, J. Classif. 2 (1985) 193–218, https://doi.org/10.1007/BF01908075. Crossref, Web of Science, Google Scholar
[56] N. X. Vinh, J. Epps and J. Bailey, Information theoretic measures for clusterings comparison: Is a correction for chance necessary? in Proc. 26th. Machine Learning (ACM, Montreal, QC, Canada, 2009), pp. 1073–1080, https://doi.org/10.1145/1553374.1553511. Crossref, Google Scholar
[57] A. Rosenberg and J. Hirschberg, V-Measure: A conditional entropy-based external cluster evaluation measure, in Proc. 2007 Joint Conf. Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL), ed. J. Eisner (Association for Computational Linguistics, Prague, Czech Republic, 2007), pp. 410–420. Google Scholar
[58] P. W. Holland, K. B. Laskey and S. Leinhardt, Stochastic blockmodels: First steps, Soc. Netw. 5 (1983) 109–137, https://doi.org/10.1016/0378-8733(83)90021-7. Crossref, Web of Science, Google Scholar
[59] T. P. Peixoto, Bayesian stochastic blockmodeling, in Advances in Network Clustering and Blockmodeling (John Wiley & Sons, 2019), pp. 289–332, https://doi.org/10.1002/9781119 483298.ch11. Crossref, Google Scholar
[60] T. P. Peixoto, Nonparametric weighted stochastic block models, Phys. Rev. E 97 (2018) 012306, https://doi.org/10.1103/PhysRevE.97.012306. Crossref, Web of Science, Google Scholar
[61] T. P. Peixoto, The graph-tool python library, figshare (2017), https://doi.org/10.6084/M9.FIGSHARE.1164194. Google Scholar