CITRARO salvatore's profile
avatar

CITRARO salvatore

Recommendations:  0

Review:  1

Review:  1

08 Mar 2024
article picture

Comparison of modularity-based approaches for nodes clustering in hypergraphs

A theoretical and empirical evaluation of modularities for hypergraphs

Recommended by based on reviews by salvatore citraro and 1 anonymous reviewer

Hypergraphs, as a framework to model higher-order interactions, have attracted a lot of attention in recent years. One particularly fruitful research direction consists of transposing well-defined notions in simple graphs to this new paradigm. A difficulty, but also an interesting opportunity, of this task is that a single concept in simple graphs might correspond to multiple ones in the domain to which it is transposed. The problem has for instance been discussed for link streams in Latapy et al. (2018), for notions as simple as node neighborhoods or the notion of shortest path. In the present article (Poda and Matias 2024), Poda and Matias focus on the concept of modularity and, indeed, they identify multiple definitions of modularity for hypergraphs in the literature (Chodrow et al., 2021, Kaminski et al., 2021). The first interesting contribution is the unification of these different representations using a common framework. They can thus compare, based solely on the definitions themselves, theoretical similarities and differences between those modularities for hypergraphs.

In the second part of their contribution, they turn towards the empirical evaluation of these methods.  Community detection has a long tradition of experimental articles, comparing on selected benchmarks the strengths and weaknesses of selected methods, from the seminal work from Lancichinetti and Fortunato (Lancichinetti et al., 2009), to recent works comparing, for instance, modularity methods in dynamic graphs (Cazabet et al., 2020). The authors thus point to existing implementations and start comparing them using existing benchmarks for hypergraphs (Brusa and Matias, 2022, Kaminski et al., 2023). This confrontation between theoretical definition and actual networks with varying properties allows them to identify methods that do not perform as expected. Furthermore, they do not solely focus on classification performance but also evaluate other factors such as scalability. Their findings reveal that all methods perform poorly in this aspect. These observations pave the way for future work.

To conclude, this work is a very relevant contribution to the field. One could say that the first empirical comparison of methods in a particular field is a sign that it has become mature, and that is maybe one of the conclusions to draw from this article.

References

Poda, V., & Matias, C. (2024). Comparison of modularity-based approaches for nodes clustering in hypergraphs. arXiv preprint. HAL, https://hal.science/hal-04414337v2
 
Chodrow, P. S., N. Veldt, and A. R. Benson (2021). Generative hypergraph clustering: From blockmodels to modularity. Science Advances 7(28), eabh1303. 
https://doi.org/10.1126/sciadv.abh1303
 
Kaminski, B., P. Pralat, and F. Theberge (2021). Community detection algorithm using hypergraph modularity. In R. M. Benito, C. Cherifi, H. Cherifi, E. Moro, L. M. Rocha, and M. Sales-Pardo (Eds.), Complex Networks & Their Applications IX, pp. 152-163. 
 
Lancichinetti, A., & Fortunato, S. (2009). Community detection algorithms: a comparative analysis. Physical review E, 80(5), 056117.
https://doi.org/10.1103/PhysRevE.80.056117
 
Latapy, M., Viard, T., & Magnien, C. (2018). Stream graphs and link streams for the modeling of interactions over time. Social Network Analysis and Mining, 8, 1-29.
https://doi.org/10.1007/s13278-018-0537-7
 
Cazabet, R., Boudebza, S., & Rossetti, G. (2020). Evaluating community detection algorithms for progressively evolving graphs. Journal of Complex Networks, 8(6), cnaa027.
https://doi.org/10.1093/comnet/cnaa027
 
Brusa, L. and C. Matias (2022). HyperSBM: Stochastic blockmodel for hypergraphs. R package, https://github.com/LB1304/HyperSBM 
 
Kaminski, B., P. Pralat, and F. Theberge (2023). Hypergraph Artificial Benchmark for Community Detection (h-ABCD). Journal of Complex Networks 11(4), cnad028 
https://doi.org/10.21203/rs.3.rs-2471638/v1

avatar

CITRARO salvatore

Recommendations:  0

Review:  1