论文标题
发现本地最大的两分子图
Discovering Locally Maximal Bipartite Subgraphs
论文作者
论文摘要
最大顶点基数的诱导二分子亚图是分析图的重要概念。但是，已知在大图中发现它们在计算上很难。因此，我们在这项工作中考虑了这个问题的较弱的概念，在这种问题中，我们放弃了最大程度的限制，而倾向于包容性最大。因此，我们旨在发现局部最大的两部分子图。为此，我们提出了三种提取此类子图的启发式方法，并将其结果与全球问题的解决方案进行了比较。对于后者，我们采用快速卫星赛车的算法强度。我们提出的三个启发式方法基于贪婪的策略，模拟退火方法和遗传算法。我们评估了所有四种算法的时间需求以及在几个基准数据集上发现的两部分子图的顶点基数
Induced bipartite subgraphs of maximal vertex cardinality are an essential concept for the analysis of graphs. Yet, discovering them in large graphs is known to be computationally hard. Therefore, we consider in this work a weaker notion of this problem, where we discard the maximality constraint in favor of inclusion maximality. Thus, we aim to discover locally maximal bipartite subgraphs. For this, we present three heuristic approaches to extract such subgraphs and compare their results to the solutions of the global problem. For the latter, we employ the algorithmic strength of fast SAT-solvers. Our three proposed heuristics are based on a greedy strategy, a simulated annealing approach, and a genetic algorithm, respectively. We evaluate all four algorithms with respect to their time requirement and the vertex cardinality of the discovered bipartite subgraphs on several benchmark datasets
