clustAnalytics: An R Package for Assessing Stability and Significance of Communities in Networks

Department of Computer Sciences,

marti.renedo@upc.edu

Soft Computing Research Group (SOCO)

argimiro@cs.upc.edu

Abstract

This paper introduces the R package clustAnalytics, which comprises a set of criteria for assessing the significance and stability of communities in networks found by any clustering algorithm. clustAnalytics works with graphs of class igraph from the R-package igraph, extended to handle weighted and/or directed graphs. clustAnalytics provides a set of community scoring functions, and methods to systematically compare their values to those of a suitable null model, which are of use when testing for cluster significance. It also provides a non parametric bootstrap method combined with similarity metrics derived from information theory and combinatorics, useful when testing for cluster stability, as well as a method to synthetically generate a weighted network with a ground truth community structure based on the preferential attachment model construction, producing networks with communities and scale-free degree distribution.

Arratia, Argimiro, and Martı́ Renedo-Mirambell. 2021. “Clustering Assessment in Weighted Networks.” PeerJ Computer Science 7 (e600): 1–27.

Brock, Guy, Vasyl Pihur, Susmita Datta, and Somnath Datta. 2021. clValid: Validation of Clustering Results. https://CRAN.R-project.org/package=clValid.

Csardi, Gabor, and Tamas Nepusz. 2006. “The Igraph Software Package for Complex Network Research.” InterJournal, Complex Systems 1695 (5): 1–9.

Fortunato, Santo. 2010. “Community Detection in Graphs.” Physics Reports 486 (3): 75–174. https://doi.org/https://doi.org/10.1016/j.physrep.2009.11.002.

Hajek, Bruce, and Suryanarayana Sankagiri. 2019. “Community Recovery in a Preferential Attachment Graph.” IEEE Transactions on Information Theory 65 (11): 6853–74. https://doi.org/10.1109/TIT.2019.2927624.

Hennig, Christian. 2007. “Cluster-Wise Assessment of Cluster Stability.” Computational Statistics & Data Analysis 52 (1): 258–71. https://doi.org/https://doi.org/10.1016/j.csda.2006.11.025.

Huang, Hanwen, Yufeng Liu, and J. S. Marron. 2014. Sigclust: Statistical Significance of Clustering. https://CRAN.R-project.org/package=sigclust.

Hubert, L., and P. Arabie. 1985. “Comparing Partitions.” Journal of Classification 2 (1): 193–218. https://doi.org/https://doi.org/10.1007/BF01908075.

McAssey, Michael P., and Fetsje Bijma. 2015. “A Clustering Coefficient for Complete Weighted Networks.” Network Science 3 (2): 183–95. https://doi.org/http://dx.doi.org/10.1017/nws.2014.26.

Meilă, Marina. 2007. “Comparing Clusterings - an Information Based Distance.” Journal of Multivariate Analysis 98 (5): 873–95. https://doi.org/http://dx.doi.org/10.1016/j.jmva.2006.11.013.

Pons, Pascal, and Matthieu Latapy. 2005. “Computing Communities in Large Networks Using Random Walks.” In International Symposium on Computer and Information Sciences, 284–93. Springer. https://doi.org/https://doi.org/10.1007/11569596_31.

Raghavan, Usha Nandini, Réka Albert, and Soundar Kumara. 2007. “Near Linear Time Algorithm to Detect Community Structures in Large-Scale Networks.” Physical Review E 76 (3).

Rao, A. Ramachandra, Rabindranath Jana, and Suraj Bandyopadhyay. 1996. “A Markov Chain Monte Carlo Method for Generating Random (0, 1)-Matrices with Given Marginals.” Sankhyā: The Indian Journal of Statistics, Series A (1961-2002) 58 (2): 225–42.

Renedo-Mirambell, Martı́, and Argimiro Arratia. 2023. “Identifying Bias in Network Clustering Quality Metrics.” PeerJ Computer Science 9:e1523. https://doi.org/https://doi.org/10.7717/peerj-cs.1523.

Yang, Jaewon, and Jure Leskovec. 2015. “Defining and Evaluating Network Communities Based on Ground-Truth.” Knowledge and Information Systems 42 (1): 181–213. https://doi.org/http://dx.doi.org/10.1007/s10115-013-0693-z.

Zachary, Wayne W. 1977. “An Information Flow Model for Conflict and Fission in Small Groups.” Journal of Anthropological Research 33 (4): 452–73.