Restart and Random Walk in Local Search for Maximum Vertex Weight Cliques with Evaluations in Clustering Aggregation
Abstract
The Maximum Vertex Weight Clique (MVWC) problem is NP-hard and also important in real-world applications. In this paper we propose to use the restart and the random walk strategies to improve local search for MVWC. If a solution is revisited in some particular situation, the search will restart. In addition, when the local search has no other options except dropping vertices, it will use random walk. Experimental results show that our solver outperforms state-of-the-art solvers in DIMACS and finds a new best-known solution. Also it is the unique solver which is comparable with state-of-the-art methods on both BHOSLIB and large crafted graphs. Furthermore we evaluated our solver in clustering aggregation. Experimental results on a number of real data sets demonstrate that our solver outperforms the state-of-the-art for solving the derived MVWC problem and helps improve the final clustering results.
Cite
Text
Fan et al. "Restart and Random Walk in Local Search for Maximum Vertex Weight Cliques with Evaluations in Clustering Aggregation." International Joint Conference on Artificial Intelligence, 2017. doi:10.24963/IJCAI.2017/87Markdown
[Fan et al. "Restart and Random Walk in Local Search for Maximum Vertex Weight Cliques with Evaluations in Clustering Aggregation." International Joint Conference on Artificial Intelligence, 2017.](https://mlanthology.org/ijcai/2017/fan2017ijcai-restart/) doi:10.24963/IJCAI.2017/87BibTeX
@inproceedings{fan2017ijcai-restart,
title = {{Restart and Random Walk in Local Search for Maximum Vertex Weight Cliques with Evaluations in Clustering Aggregation}},
author = {Fan, Yi and Li, Nan and Li, Chengqian and Ma, Zongjie and Latecki, Longin Jan and Su, Kaile},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2017},
pages = {622-630},
doi = {10.24963/IJCAI.2017/87},
url = {https://mlanthology.org/ijcai/2017/fan2017ijcai-restart/}
}