Frequency-driven tabu search for the maximum s-plex problem
Frequency-driven tabu search for the maximum s-plex problem
复制标题
DOI：
10.1016/j.cor.2017.05.005
复制
发表时间：
2017-10
期刊：
影响因子：
--
通讯作者：
Yi Zhou;Jin-Kao Hao
中科院分区：
文献类型：
--
作者：
Yi Zhou;Jin-Kao Hao
最大丛问题是社会网络分析等研究中的一个重要模型。在这项研究中，我们提出了一个有效的频率驱动的多邻域禁忌搜索算法（FD-TS）来解决这个问题的非常大的网络。所提出的FD-TS算法依赖于两个变换算子（AddandSwap）来定位高质量的解决方案，以及一个频率驱动的扰动算子（Press）来逃避和搜索所识别的局部最优陷阱。我们报告了来自SNAP Collection和第10届DIMACS挑战赛的47个大规模现实生活（稀疏）图的计算结果，以及来自第2届DIMACS挑战赛的52个（密集）图（附录中还提供了48个图的结果）。我们证明了我们的方法的有效性，目前表现最好的算法进行比较。
The maximums-plex problem is an important model for social network analysis and other studies. In this study, we present an effective frequency-driven multi-neighborhood tabu search algorithm (FD-TS) to solve the problem on very large networks. The proposed FD-TS algorithm relies on two transformation operators (AddandSwap) to locate high-quality solutions, and a frequency-driven perturbation operator (Press) to escape and search beyond the identified local optimum traps. We report computational results for 47 massive real-life (sparse) graphs from the SNAP Collection and the 10th DIMACS Challenge, as well as 52 (dense) graphs from the 2nd DIMACS Challenge (results for 48 more graphs are also provided in the Appendix). We demonstrate the effectiveness of our approach by presenting comparisons with the current best-performing algorithms.