Community Detection in Large-Scale Complex Networks via Structural Entropy Game
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912205143801856 |
|---|---|
| author | Xian, Yantuan Li, Pu Peng, Hao Yu, Zhengtao Xiang, Yan Yu, Philip S. |
| author_facet | Xian, Yantuan Li, Pu Peng, Hao Yu, Zhengtao Xiang, Yan Yu, Philip S. |
| contents | Community detection is a critical task in graph theory, social network analysis, and bioinformatics, where communities are defined as clusters of densely interconnected nodes. However, detecting communities in large-scale networks with millions of nodes and billions of edges remains challenging due to the inefficiency and unreliability of existing methods. Moreover, many current approaches are limited to specific graph types, such as unweighted or undirected graphs, reducing their broader applicability. To address these issues, we propose a novel heuristic community detection algorithm, termed CoDeSEG, which identifies communities by minimizing the two-dimensional (2D) structural entropy of the network within a potential game framework. In the game, nodes decide to stay in current community or move to another based on a strategy that maximizes the 2D structural entropy utility function. Additionally, we introduce a structural entropy-based node overlapping heuristic for detecting overlapping communities, with a near-linear time complexity.Experimental results on real-world networks demonstrate that CoDeSEG is the fastest method available and achieves state-of-the-art performance in overlapping normalized mutual information (ONMI) and F1 score. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_15130 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Community Detection in Large-Scale Complex Networks via Structural Entropy Game Xian, Yantuan Li, Pu Peng, Hao Yu, Zhengtao Xiang, Yan Yu, Philip S. Social and Information Networks Community detection is a critical task in graph theory, social network analysis, and bioinformatics, where communities are defined as clusters of densely interconnected nodes. However, detecting communities in large-scale networks with millions of nodes and billions of edges remains challenging due to the inefficiency and unreliability of existing methods. Moreover, many current approaches are limited to specific graph types, such as unweighted or undirected graphs, reducing their broader applicability. To address these issues, we propose a novel heuristic community detection algorithm, termed CoDeSEG, which identifies communities by minimizing the two-dimensional (2D) structural entropy of the network within a potential game framework. In the game, nodes decide to stay in current community or move to another based on a strategy that maximizes the 2D structural entropy utility function. Additionally, we introduce a structural entropy-based node overlapping heuristic for detecting overlapping communities, with a near-linear time complexity.Experimental results on real-world networks demonstrate that CoDeSEG is the fastest method available and achieves state-of-the-art performance in overlapping normalized mutual information (ONMI) and F1 score. |
| title | Community Detection in Large-Scale Complex Networks via Structural Entropy Game |
| topic | Social and Information Networks |
| url | https://arxiv.org/abs/2501.15130 |