提升最大平衡二分图问题性能的新局部搜索框架
193 浏览量
更新于2024-08-27
收藏 567KB PDF 举报
本文主要探讨了"New Heuristic Approaches for Maximum Balanced Biclique Problem"，该研究关注于解决最大平衡二分图问题（Maximum Balanced Biclique Problem，MBBP）。MBBP是最大团问题（Maximum Clique Problem，MCP）的重要扩展，由于在工业界具有广泛的应用，如社交网络分析、生物信息学中的蛋白质相互作用网络等，寻找最大平衡二分图对于理解复杂系统中的结构和关系至关重要。
作者们提出了一种新的局部搜索框架，这个框架的核心是结合了四种优化策略来增强MBBP的求解效率。框架的核心在于交替进行两个阶段：一是通过添加顶点对（vertex pairs）进行扩展，二是通过移除顶点对进行重启。这展示了对算法动态调整和迭代优化的重视。
首先，针对顶点对的添加，文章提出了三种不同的选择策略。这些策略可能是基于度分布、连接性分析或者邻域搜索，旨在尽可能地增加新加入的二分图的平衡性，即两个顶点集的大小之差尽可能小。
其次，为了提高重启阶段的效率，研究人员设计了一个强大的自适应重启（Robust Self-Adaptive Restarting Heuristic），这种策略可以根据算法当前的状态和性能动态调整，比如当遇到局部最优陷阱时，通过移除部分顶点对，重新启动搜索过程，从而跳出局部最优，探索全局最优解。
在大规模图（massive graphs）的情况下，这种局部搜索框架尤为重要，因为它能够在处理大量节点和边的情况下保持高效的搜索，避免了全局搜索的高时间复杂性。同时，通过自适应性和灵活性，它能够更好地应对不同规模和复杂度的问题实例。
论文在2018年发表在《信息科学》（Information Sciences）期刊上，从接收修订到最终在线发布的时间线清晰可见，这表明研究者对其研究成果有严谨的学术态度。这篇论文为MBBP问题提供了创新的求解策略，对提升算法在实际应用中的性能和效率有着重要的贡献。
364 Y. Wang et al. / Information Sciences 432 (2018) 362–375
u
1
u
2
u
3
u
4
v
1
v
2
v
3
v
4
Fig. 1. A bipartite graph from Example 1.
from the literature, including randomly generated classical instances [27] and a broad range of massive bipartite graphs
with nearly one billion edges. Experimental results demonstrate that PSRS significantly outperforms previous algorithms
and improves upon the best known solution quality for certain difficult instances.
In order to improve the performance of PSRS on massive bipartite graphs, we propose two additional heuristics. The
third heuristic is a two-mode perturbation (TMP) heuristic, which combines the greedy selection rule based on pscore with
a randomized selection strategy. PSRS typically chooses the pair of vertices for addition with the greatest pscore. However,
for massive bipartite graphs, it is very time consuming to find the pair of vertices with the greatest pscore, because there
are too many candidate vertex pairs. Additionally, most real-world massive bipartite graphs are very sparse, meaning pure
greedy heuristics can easily lead the search into local optima. Based on these two considerations, we improve the selection
heuristic by incorporating a randomized selection strategy with a certain probability, leading to the TMP heuristic. This
reduces the average cost of choosing the vertex pair for addition, and also introduces additional diversification.
The final heuristic is the k-bipartite core reduction rule (KCR), which is used to reduce the scale of massive bipartite
graphs by deleting vertices that are impossible to include in any optimal solutions. This rule is based on a heuristic called
the k-bipartite core, which is inspired by the heuristic of the k-core [18] .
We improve the PSRS algorithm by using the third and fourth heuristics, and the resulting algorithm is called PSRS+
(PSRS with TMP and KCR), which is more effective for massive graphs. We select 17 massive bipartite graphs from [9] and
use them to test the performances of EA/SM, PSRS, and PSRS+. Experiments demonstrate that PSRS+ greatly improves upon
PSRS and significantly outperforms EA/SM on all massive real graphs.
We also conduct experimental analysis and additional investigations on the heuristics presented in this work. Specifi-
cally, we compare PSRS and PSRS+ with several alternative versions that operate without using one of the aforementioned
heuristics. The experimental results demonstrate the effectiveness of the proposed heuristics.
In the next section, we introduce some necessary background knowledge and previous MBBP algorithms. We then pro-
pose a local search framework based on pair operations. Next, we describe our novel scoring function, self-adaptive restart-
ing heuristic, and PSRS algorithm. We then present the TMP heuristic and KCR reduction rule, and present the PSRS+ algo-
rithm. Sections 6 and 7 present the experimental results for PSRS and PSRS+, as well as experiments validating the effec-
tiveness of the proposed novel heuristics on some benchmarks. Finally, we provide some concluding remarks.
2. Background
2.1. Basic definitions and notations
Given a bipartite graph G = ( U, V, E ), G can be divided into two disjoint vertex sets U = { u
1
, u
2
, . . . , u
n
} and V = { v
1
,
v
2
, . . . , v
m
} such that every edge connects one vertex in U to one vertex in V. E = { e
1
, e
2
, . . . , e
t
} is the set of edges.
The neighborhood of a vertex u ∈ U is N ( u ) = { v ∈ V |( v, u ) ∈ E }. Similarly, the neighborhood of a vertex v ∈ V is N ( v ) = { u ∈ U |( v,
u ) ∈ E }. The degree of a vertex v is the size of its neighborhood and is denoted | N ( v )|. The size of a bipartite graph is defined
as max {| U |, | V |}. A balanced bipartite graph is a bipartite graph in which both disjoint sets of vertices are of the same
cardinality (i.e., | U| = | V | = n ).
Example 1. Fig. 1 presents a bipartite graph G = ( U, V, E ), where U = { u
1
, u
2
, u
3
, u
4
}, V = { v
1
, v
2
, v
3
, v
4
}, and E = {( u
1
, v
1
),
( u
1
, v
2
), ( u
2
, v
1
), ( u
2
, v
2
), ( u
2
, v
3
), ( u
2
, v
4
), ( u
3
, v
2
), ( u
3
, v
3
), ( u
3
, v
4
), ( u
4
, v
2
), ( u
4
, v
3
), ( u
4
, v
4
)}.
A biclique B = ( U
b
, V
b
, E
b
) of a given bipartite graph G is a subgraph of G where for each pair of vertices u ∈ U
b
and v ∈ V
b
,
( u, v ) ∈ E
b
. If | B | = | U
b
| = | V
b
| = k, then we say that B is a balanced biclique of size k . A balanced biclique is said to be
maximal if it cannot be extended to a larger balanced biclique. The MBBP problem is to find the balanced biclique with the
most vertices in a bipartite graph. In other words, k should be maximized. For example, in the graph depicted in Fig. 1 , the
vertices u
2
, u
3
, and u
4
, and v
2
, v
3
, and v
4
, as well as the nine edges between them, constitute a biclique of size three, which
happens to be the maximum balanced biclique in the bipartite graph.
剩余13页未读，继续阅读
2015-04-14 上传
2009-11-19 上传
2010-05-28 上传
2019-10-30 上传
2021-04-23 上传
2021-02-11 上传
2021-02-22 上传
2021-02-08 上传
2021-02-20 上传
weixin_38555019
- 粉丝: 10
- 资源: 921
我的内容管理
展开
最新资源
- BottleJS快速入门：演示JavaScript依赖注入优势
- vConsole插件使用教程：输出与复制日志文件
- Node.js v12.7.0版本发布 - 适合高性能Web服务器与网络应用
- Android中实现图片的双指和双击缩放功能
- Anum Pinki英语至乌尔都语开源词典：23000词汇会话
- 三菱电机SLIMDIP智能功率模块在变频洗衣机的应用分析
- 用JavaScript实现的剪刀石头布游戏指南
- Node.js v12.22.1版发布 - 跨平台JavaScript环境新选择
- Infix修复发布：探索新的中缀处理方式
- 罕见疾病酶替代疗法药物非临床研究指导原则报告
- Node.js v10.20.0 版本发布，性能卓越的服务器端JavaScript
- hap-java-client：Java实现的HAP客户端库解析
- Shreyas Satish的GitHub博客自动化静态站点技术解析
- vtomole个人博客网站建设与维护经验分享
- MEAN.JS全栈解决方案：打造MongoDB、Express、AngularJS和Node.js应用
- 东南大学网络空间安全学院复试代码解析
