.png){kind=icon}
返回
On solving simplified diversified top-k s-plex problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2023.106187.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Finding cohesive groups in a graph, which has been extensively studied by many researchers, is a fundamental and critical problem for various real-world applications, such as community search, motif discovery and anomaly detection. Unfortunately, the cohesive groups rarely appear as cliques and are usually highly overlapping, so few cohesive groups can be found by searching maximum or top-k maximal cliques. In other words, maximum or top-k maximal cliques are too strict for representing cohesive groups. To handle this problem, the DTKSP problem was introduced earlier in the literature to find k maximal s-plexes that cover maximum vertices with the lowest overlapping in a given graph. In this paper, we consider the Simplified Diversified Top-k s-Plex (S-DTKSP) problem, by aiming to find k maximal s-plexes that cover the maximum vertices without considering the size of overlap. We prove that the S-DTKSP problem is NP-hard and propose an integer linear programming for S-DTKSP problem. Then, we propose an iterated local search (ILS) algorithm with a tabu strategy to efficiently find a good solution. The proposed algorithms are evaluated on large real -world instances. The experimental results demonstrate that our approaches can solve the S-DTKSP problem effectively and efficiently than two baseline algorithms.
Keyword:
Approximation algorithm
Iterated local search
Tabu search
Scoring function
S-DTKSP problem
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
引用论文
.png){kind=icon}
Preparations and Polymerizations ofp-Substituted Phenyl Vinyl Sulfides. Vinyl Polymerization 168
PREAI
分享收藏
分享收藏
查看更多内容