期刊
INFORMATION SCIENCES
卷 432, 期 -, 页码 362-375出版社
ELSEVIER SCIENCE INC
DOI: 10.1016/j.ins.2017.12.012
关键词
The maximum balanced biclique problem; Local search; Massive graphs; Robust self-adaptive restarting heuristic
资金
- NSFC [61370156, 61503074, 61502464, 61402070, 61403077, 61403076]
- China National 973 program [2014CB340301]
The maximum balanced biclique problem (MBBP) is an important extension of the maximum clique problem (MCP), which has wide industrial applications. In this paper, we propose a new local search framework for MBBP where four heuristics are incorporated to improve its performance. Our framework alternates between an extension phase via adding vertex pairs and a restarting phase via removing vertex pairs. Three heuristics are proposed for selecting the pairs for addition and removal. The first heuristic is a prediction score function to greedily select the vertex pairs for addition, which makes use of the structural information of the problem. The second heuristic is a self-adaptive restarting heuristic that removes a dynamic number of vertex pairs from the candidate solution to allow the search to continue from a new search area. The third heuristic is proposed for solving massive graphs and is called the two-mode perturbation heuristic. It is used for selecting pairs of vertices for addition and lowers the average complexity for this task. We also introduce a k-bipartite core reduction rule to decrease the scale of all massive instances, which helps our algorithm find optimal solutions for many massive instances. These techniques lead to two efficient local search algorithms for MBBP. Experimental results demonstrate that the proposed algorithms can scale up to massive instances with billions of edges and that the proposed algorithms outperform state-of-the-art MBBP algorithms on standard benchmarks. (C) 2017 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据