Enhancement: network community discovery algorithms walktrap and spinglass (R-package igraph)

[mberlim]

Template for bug reports

• JASP version:
• OS name and version:
• Analysis:
• Steps to reproduce:

Template for enhancement requests

* Enhancement: * Purpose:

[TarandeepKang]

I noticed this request, because I have recently developed an interest in applied network analysis, and thus have made a number of other related feature requests. This request has been open for number of years, so I wondered if any progress has been made? If not, I would like to enthusiastically second this request!

I would like to highlight their discovery algorithms are broadly useful, and are widely applied. See below for a discussion of different methods, and a relevant application from my own field of research:

Yang, Z., Algesheimer, R., & Tessone, C. J. (2016). A Comparative Analysis of Community Detection Algorithms on Artificial Networks. Scientific Reports, 6(1), Article 1. https://doi.org/10.1038/srep30750

Fortunato, S., & Hric, D. (2016). Community detection in networks: A user guide. Physics Reports, 659, 1–44. https://doi.org/10.1016/j.physrep.2016.09.002

de Feijter, M., Kocevska, D., Blanken, T. F., van der Velpen, I. F., Ikram, M. A., & Luik, A. I. (2022). The network of psychosocial health in middle-aged and older adults during the first COVID-19 lockdown. Social Psychiatry and Psychiatric Epidemiology, 57(12), 2469–2479. https://doi.org/10.1007/s00127-022-02308-9

Levin, Y., Bachem, R., Goodwin, R., Hamama-Raz, Y., Leshem, E., & Ben-Ezra, M. (2022). Relationship between adjustment disorder symptoms and probable diagnosis before and after second lockdown in Israel: Longitudinal symptom network analysis. BJPsych Open, 8(6), e186. https://doi.org/10.1192/bjo.2022.588

[TarandeepKang]

I thought I would check on the status of this request, and provide some updated literature and further details about widely used computational functions

Five community detection approaches are widely used in the literature, walktrap (walktrap.community function - RDocumentation) spinglass (spinglass.community function - RDocumentation), Louvain https://igraph.org/r/doc/cluster_louvain.html and Leiden https://igraph.org/r/doc/cluster_leiden.html in igraph and the spectral method in rSpectral Roy et al., (2018) (R: Spectral clustering for 'igraph' objects (r-project.org)) which has recently been shown to be superior in certain situations, see below.

The new clustAnalytics package extends igraph's capabilities by adding a nonparametric bootstrap and information theoretic metrics for cluster stability, as well as a method of determining cluster significance and some other features (i.e. application of community detection to weighted and directed graphs).

Note that some of the citations given in the package documentation are preprints, where this is the case, and a full published version exists, I provide this instead:

Blondel, V. D., Guillaume, J.-L., Lambiotte, R., & Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008(10), P10008. https://doi.org/10.1088/1742-5468/2008/10/P10008 Brusco, M., Steinley, D., & Watts, A. L. (2022). A comparison of spectral clustering and the walktrap algorithm for community detection in network psychometrics. Psychological Methods, https://doi.org/10.1037/met0000509 Csardi, G., & Nepusz, T. (2005). The Igraph Software Package for Complex Network Research. InterJournal, Complex Systems, 1695. Csárdi, G., Nepusz, T., Müller, K., Horvát, S., Traag, V., Zanini, F., & Noom, D. (2023). igraph for R: R interface of the igraph library for graph theory and network analysis. Zenodo. https://doi.org/10.5281/zenodo.8046777 Newman, M. E. J. (2006). Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103(23), 8577–8582. https://doi.org/10.1073/pnas.0601602103 Newman, M. E. J. (2013). Spectral methods for community detection and graph partitioning. Physical Review E, 88(4), 042822. https://doi.org/10.1103/PhysRevE.88.042822 Newman, M. E. J., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical Review E, 69(2), 026113. https://doi.org/10.1103/PhysRevE.69.026113 Pons, P., & Latapy, M. (2006). Computing Communities in Large Networks Using Random Walks. Journal of Graph Algorithms and Applications, 10(2), 191–218. https://doi.org/10.7155/jgaa.00124 Reichardt, J., & Bornholdt, S. (2006). Statistical mechanics of community detection. Physical Review E, 74(1), 016110. https://doi.org/10.1103/PhysRevE.74.016110 Renedo-Mirambell, M., & Arratia, A. (2023). clustAnalytics: An R Package for Assessing Stability and Significance of Communities in Networks. The R Journal, 15(2), 134–144. https://doi.org/10.32614/RJ-2023-057 Roy, M., Sorokina, O., McLean, C., Tapia-González, S., DeFelipe, J., Armstrong, J. D., & Grant, S. G. N. (2018). Regional Diversity in the Postsynaptic Proteome of the Mouse Brain. Proteomes, 6(3), Article 3. https://doi.org/10.3390/proteomes6030031 Traag, V. A., & Bruggeman, J. (2009). Community detection in networks with positive and negative links. Physical Review E, 80(3), 036115. https://doi.org/10.1103/PhysRevE.80.036115 Traag, V. A., Waltman, L., & van Eck, N. J. (2019). From Louvain to Leiden: Guaranteeing well-connected communities. Scientific Reports, 9(1), Article 1. https://doi.org/10.1038/s41598-019-41695-z