New heuristic approaches for maximum balanced biclique problem
New heuristic approaches for maximum balanced biclique problem
复制标题
DOI：
10.1016/j.ins.2017.12.012
复制
发表时间：
2018-03
期刊：
影响因子：
--
通讯作者：
Yiyuan Wang;Shaowei Cai;Minghao Yin
中科院分区：
文献类型：
--
作者：
Yiyuan Wang;Shaowei Cai;Minghao Yin
最大平衡双团问题（MBBP）是最大团问题（MCP）的一个重要推广，具有广泛的工业应用。在本文中，我们提出了一个新的本地搜索框架MBBP四个算法被纳入，以提高其性能。我们的框架交替之间的扩展阶段通过添加顶点对和重新启动阶段通过删除顶点对。提出了三种算法来选择要添加和删除的对。第一个启发式算法是一个预测得分函数，它利用问题的结构信息来选择要添加的顶点对。第二个启发式算法是一个自适应的重新开始的启发式算法，它从候选解中删除动态数量的顶点对，以允许搜索从一个新的搜索区域继续。第三种启发式算法被提出用于求解大规模图，称为双模式扰动启发式算法。它用于选择要添加的顶点对，并降低此任务的平均复杂度。我们还引入了一个k-二分核约简规则来减少所有海量实例的规模，这有助于我们的算法找到许多海量实例的最优解。这些技术导致两个有效的局部搜索算法MBBP。实验结果表明，所提出的算法可以扩展到大量的实例与数十亿的边缘，所提出的算法优于国家的最先进的MBBP算法在标准的基准测试。
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.