Finding Near-Optimal Maximum Set of Disjoint $k$-Cliques in Real-World Social Networks
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908316504948736 |
|---|---|
| author | Lin, Wenqing Chen, Xin Xie, Haoxuan Wang, Sibo Luo, Siqiang |
| author_facet | Lin, Wenqing Chen, Xin Xie, Haoxuan Wang, Sibo Luo, Siqiang |
| contents | A $k$-clique is a dense graph, consisting of $k$ fully-connected nodes, that finds numerous applications, such as community detection and network analysis. In this paper, we study a new problem, that finds a maximum set of disjoint $k$-cliques in a given large real-world graph with a user-defined fixed number $k$, which can contribute to a good performance of teaming collaborative events in online games. However, this problem is NP-hard when $k \geq 3$, making it difficult to solve. To address that, we propose an efficient lightweight method that avoids significant overheads and achieves a $k$-approximation to the optimal, which is equipped with several optimization techniques, including the ordering method, degree estimation in the clique graph, and a lightweight implementation. Besides, to handle dynamic graphs that are widely seen in real-world social networks, we devise an efficient indexing method with careful swapping operations, leading to the efficient maintenance of a near-optimal result with frequent updates in the graph. In various experiments on several large graphs, our proposed approaches significantly outperform the competitors by up to 2 orders of magnitude in running time and 13.3\% in the number of computed disjoint $k$-cliques, which demonstrates the superiority of the proposed approaches in terms of efficiency and effectiveness. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_20299 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Finding Near-Optimal Maximum Set of Disjoint $k$-Cliques in Real-World Social Networks Lin, Wenqing Chen, Xin Xie, Haoxuan Wang, Sibo Luo, Siqiang Social and Information Networks Databases Data Structures and Algorithms A $k$-clique is a dense graph, consisting of $k$ fully-connected nodes, that finds numerous applications, such as community detection and network analysis. In this paper, we study a new problem, that finds a maximum set of disjoint $k$-cliques in a given large real-world graph with a user-defined fixed number $k$, which can contribute to a good performance of teaming collaborative events in online games. However, this problem is NP-hard when $k \geq 3$, making it difficult to solve. To address that, we propose an efficient lightweight method that avoids significant overheads and achieves a $k$-approximation to the optimal, which is equipped with several optimization techniques, including the ordering method, degree estimation in the clique graph, and a lightweight implementation. Besides, to handle dynamic graphs that are widely seen in real-world social networks, we devise an efficient indexing method with careful swapping operations, leading to the efficient maintenance of a near-optimal result with frequent updates in the graph. In various experiments on several large graphs, our proposed approaches significantly outperform the competitors by up to 2 orders of magnitude in running time and 13.3\% in the number of computed disjoint $k$-cliques, which demonstrates the superiority of the proposed approaches in terms of efficiency and effectiveness. |
| title | Finding Near-Optimal Maximum Set of Disjoint $k$-Cliques in Real-World Social Networks |
| topic | Social and Information Networks Databases Data Structures and Algorithms |
| url | https://arxiv.org/abs/2503.20299 |