Browse by volume Browse by section Browse by topic Browse by conference

Section: Network Science
Topic: Statistics

Comparison of modularity-based approaches for nodes clustering in hypergraphs

Poda, Veronica1 ; Matias, Catherine2   
1 University of Trento, Via Sommarive, 14, 38123, Povo, Italy
2 Laboratoire de Probabilités, Statistique et Modélisation, 4, Place Jussieu 75005 Paris, France

10.24072/pcjournal.404 - Peer Community Journal, Volume 4 (2024), article no. e37.

Get full text PDF Peer reviewed and recommended by PCI

Statistical analysis and node clustering in hypergraphs constitute an emerging topic suffering from a lack of standardization. In contrast to the case of graphs, the concept of nodes' community in hypergraphs is not unique and encompasses various distinct situations. In this work, we conducted a comparative analysis of the performance of modularity-based methods for clustering nodes in binary hypergraphs. To address this, we begin by presenting, within a unified framework, the various hypergraph modularity criteria proposed in the literature, emphasizing their differences and respective focuses. Subsequently, we provide an overview of the state-of-the-art codes available to maximize hypergraph modularities for detecting node communities in hypergraphs. Through exploration of various simulation settings with controlled ground truth clustering, we offer a comparison of these methods using different quality measures, including true clustering recovery, running time, (local) maximization of the objective, and the number of clusters detected. Our contribution marks the first attempt to clarify the advantages and drawbacks of these newly available methods. This effort lays the foundation for a better understanding of the primary objectives of modularity-based node clustering methods for binary hypergraphs.

Published online:
DOI: 10.24072/pcjournal.404
Type: Research article
Keywords: Community detection, Higher-order interaction, Hypergraph, Modularity, Node clustering
Poda, Veronica 1; Matias, Catherine 2

1 University of Trento, Via Sommarive, 14, 38123, Povo, Italy
2 Laboratoire de Probabilités, Statistique et Modélisation, 4, Place Jussieu 75005 Paris, France
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{10_24072_pcjournal_404,
     author = {Poda, Veronica and Matias, Catherine},
     title = {Comparison of modularity-based approaches for nodes clustering in hypergraphs},
     journal = {Peer Community Journal},
     eid = {e37},
     publisher = {Peer Community In},
     volume = {4},
     year = {2024},
     doi = {10.24072/pcjournal.404},
     language = {en},
     url = {https://peercommunityjournal.org/articles/10.24072/pcjournal.404/}
}
TY  - JOUR
AU  - Poda, Veronica
AU  - Matias, Catherine
TI  - Comparison of modularity-based approaches for nodes clustering in hypergraphs
JO  - Peer Community Journal
PY  - 2024
VL  - 4
PB  - Peer Community In
UR  - https://peercommunityjournal.org/articles/10.24072/pcjournal.404/
DO  - 10.24072/pcjournal.404
LA  - en
ID  - 10_24072_pcjournal_404
ER  - 
%0 Journal Article
%A Poda, Veronica
%A Matias, Catherine
%T Comparison of modularity-based approaches for nodes clustering in hypergraphs
%J Peer Community Journal
%D 2024
%V 4
%I Peer Community In
%U https://peercommunityjournal.org/articles/10.24072/pcjournal.404/
%R 10.24072/pcjournal.404
%G en
%F 10_24072_pcjournal_404
Poda, Veronica; Matias, Catherine. Comparison of modularity-based approaches for nodes clustering in hypergraphs. Peer Community Journal, Volume 4 (2024), article  no. e37. doi : 10.24072/pcjournal.404. https://peercommunityjournal.org/articles/10.24072/pcjournal.404/

Peer reviewed and recommended by PCI : 10.24072/pci.networksci.100181

Conflict of interest of the recommender and peer reviewers:
The recommender in charge of the evaluation of the article and the reviewers declared that they have no conflict of interest (as defined in the code of conduct of PCI) with the authors or with the content of the article.

[1] Angelini, M.; Caltagirone, F.; Krzakala, F.; Zdeborová, L. Spectral detection on sparse hypergraphs, 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2015, pp. 66-73 | DOI

[2] Battiston, F.; Cencetti, G.; Iacopini, I.; Latora, V.; Lucas, M.; Patania, A.; Young, J.; Petri, G. Networks beyond pairwise interactions: Structure and dynamics, Phys Rep, Volume 874 (2020), pp. 1-92 | DOI

[3] Bick, C.; Gross, E.; Harrington, H.; Schaub, M. What Are Higher-Order Networks?, SIAM Review, Volume 65 (2023), pp. 686-731 | DOI

[4] Blondel, V.; Guillaume, J.; Lambiotte, R.; Lefebvre, E. Fast unfolding of communities in large networks, Journal of Statistical Mechanics: Theory and Experiment (2008), p. 10008 | DOI

[5] Brusa, L.; Matias, C. HyperSBM: Stochastic Blockmodel for Hypergraphs, R package, 2022 (https://github.com/LB1304/HyperSBM)

[6] Brusa, L.; Matias, C. Model-based clustering in simple hypergraphs through a stochastic blockmodel, arXiv (2022) | DOI

[7] Cafieri, S.; Hansen, P.; Liberti, L. Loops and multiple edges in modularity maximization of networks, Phys Rev E, Volume 81 (2010) no. 4, p. 046102 | DOI

[8] Cazabet, R. A theoretical and empirical evaluation of modularities for hypergraphs, Peer Community in Network Science, Volume 100181 (2024) | DOI

[9] Chelaru, M.; Eagleman, S.; Andrei, A.; Milton, R.; Kharas, N.; Dragoi, V. High-Order Correlations Explain the Collective Behavior of Cortical Populations in Executive, But Not Sensory Areas, Neuron, Volume 109 (2021), pp. 3954-3961 | DOI

[10] Chien, I.; Lin, C.; Wang, I. On the Minimax Misclassification Ratio of Hypergraph Community Detection, IEEE Transactions on Information Theory, Volume 65 (2019), pp. 8095-8118 | DOI

[11] Chodrow, P.; Veldt, N.; Benson, A. Generative hypergraph clustering: From blockmodels to modularity, Science Advances, Volume 7 (2021), p. 1303 | DOI

[12] Chodrow, P.; Veldt, N.; Benson, A. HyperModularity, Julia package (2022) (https://github.com/nveldt/HyperModularity.jl)

[13] Chodrow, P.; Eikmeier, N.; Haddock, J. Nonbacktracking Spectral Clustering of Nonuniform Hypergraphs, SIAM Journal on Mathematics of Data Science, Volume 5 (2023), pp. 251-279 | DOI

[14] Chung, F.; Lu, L. Connected Components in Random Graphs with Given Expected Degree Sequences, Annals of Combinatorics, Volume 6 (2002), pp. 125-145 | DOI

[15] Clauset, A.; Newman, M.; Moore, C. Finding community structure in very large networks, Physical Review E, Volume 70 (2004), p. 066111 | DOI

[16] Flamm, C.; Stadler, B.; Stadler, P. Chapter 13 - Generalized Topologies: Hypergraphs, Chemical Reactions, and Biological Evolution, Advances in Mathematical Chemistry and Applications, Villaveces. Bentham Science Publishers, 2015, pp. 300-328 | DOI

[17] Ghoshdastidar, D.; Dukkipati, A. Consistency of spectral hypergraph partitioning under planted partition model, Ann Statist, Volume 45 (2017), pp. 289-315 | DOI

[18] Hubert, L.; Arabie, P. Comparing Partitions, J Classif, Volume 2 (1985), pp. 193-218 | DOI

[19] Kamiński, B.; Poulin, V.; Prałat, P.; Szufel, P.; Théberge, F. Clustering via hypergraph modularity, PLoS ONE, Volume 14 (2019), p. 0224307 | DOI

[20] Kamiński, B.; Poulin, V.; Prałat, P.; Szufel, P.; Théberge, F. Clustering via hypergraph modularity - Companion source code and files, Python code (2019) (https://gist.github.com/pszufe)

[21] Kamiński, B.; Prałat, P.; Théberge, F. Community Detection Algorithm Using Hypergraph Modularity, Complex Networks & Their Applications IX, 2021, pp. 152-163 | DOI

[22] Kamiński, B.; Prałat, P.; Théberge, F. Artificial Benchmark for Hypergraphs Community Detection (ABCDH) - A Random Hypergraph Model with Community Structure, Julia code (2023) (https://github.com/bkamins/ABCDHypergraphGenerator.jl)

[23] Kamiński, B.; Prałat, P.; Théberge, F. Hypergraph Artificial Benchmark for Community Detection (h–ABCD), Journal of Complex Networks, Volume 11 (2023), p. 028 | DOI

[24] Kumar, T.; Vaidyanathan, S.; Ananthapadmanabhan, H.; Parthasarathy, S.; Ravindran, B. Hypergraph clustering by iteratively reweighted modularity maximization, Appl. Netw. Sci, Volume 5 (2020), p. 52 | DOI

[25] Lancichinetti, A.; Fortunato, S.; Radicchi, F. Benchmark graphs for testing community detection algorithms, Phys. Rev. E, Volume 78 (2008) no. 4, p. 046110 | DOI

[26] Lee, G.; Choe, M.; Shin, K. How Do Hyperedges Overlap in Real-World Hypergraphs? - Patterns, Measures, and Generators, Proceedings of the Web Conference 2021. WWW ’21, Association for Computing Machinery, Ljubljana, Slovenia, 2021, pp. 3396-3407 | DOI

[27] Massen, C.; Doye, J. Identifying communities within energy landscapes, Phys Rev E, Volume 71 (2005) no. 4, p. 046101 | DOI

[28] Muyinda, N.; De Baets, B.; Rao, S. Non-king elimination, intransitive triad interactions, and species coexistence in ecological competition networks, Theor Ecol, Volume 13 (2020), pp. 385-397 | DOI

[29] Newman, M.; Girvan, M. Finding and evaluating community structure in networks, Physical Review E, Volume 69 (2004), p. 026113 | DOI

[30] Newman, M. Equivalence between modularity optimization and maximum likelihood methods for community detection, Phys. Rev. E, Volume 94 (2016) no. 5, p. 052315 | DOI

[31] Ng, T.; Murphy, T. Model-based clustering for random hypergraphs, Adv Data Anal Classif, Volume 16 (2022), pp. 691-723 | DOI

[32] PNNL Lab HyperNetX, Python Library (v2.0.3), 2023 (https://pnnl.github.io/HyperNetX/index.html)

[33] Poda, V.; Matias, C. Scripts for: Comparison of modularity-based approaches for nodes clustering in hypergraphs, Zenodo, 2024 | DOI

[34] Poda, V.; Matias, C. Supplementary Material for: Comparison of modularity-based approaches for nodes clustering in hypergraphs, Zenodo, 2024 | DOI

[35] Roy, S.; Ravindran, B. Measuring Network Centrality Using Hypergraphs, Proceedings of the Second ACM IKDD Conference on Data Sciences (CoDS ’15), Bangalore, India, 2015, pp. 59-68 | DOI

[36] Ruggeri, N.; Contisciani, M.; Battiston, F.; Bacco, C. Community detection in large hypergraphs, Science Advances, Volume 9 (2023), p. 9159 | DOI

[37] Squartini, T.; Garlaschelli, D. Analytical maximum-likelihood method to detect patterns in real networks, New J Phys, Volume 13 (2011) no. 083001 | DOI

[38] Stephan, L.; Zhu, Y. Sparse random hypergraphs: Non-backtracking spectra and community detection, IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), 2022, pp. 567-575 | DOI

[39] Torres, L.; Blevins, A.; Bassett, D.; Eliassi-Rad, T. The Why, How, and When of Representations for Complex Systems, SIAM Rev, Volume 63 (2021), pp. 435-485 | DOI

[40] Wolff, K. The sociology of Georg Simmel, The free press (1950)

[41] Yang, Z.; Algesheimer, R.; Tessone, C. A Comparative Analysis of Community Detection Algorithms on Artificial Networks, Sci Rep, Volume 6 (2016) no. 30750 | DOI

[42] Zhang, Q.; Tan, V. Exact Recovery in the General Hypergraph Stochastic Block Model, IEEE Trans Inf Theory, Volume 69 (2023), pp. 453-471 | DOI

Cited by Sources: