图约减技术在松弛团问题中的应用与研究

The Application and Research of Graph Reduction Techniques in the Relaxation Group Problem

摘要: 松弛团问题是图论中一个关键问题，旨在寻找图中满足相应约束条件的松弛团模型。伴随着数据规模的日益增长，如何有效地对松弛团问题进行约减，以降低问题的求解难度显得尤为重要。图约减技术由此应运而生，本文主要研究了图约减技术在松弛团中的应用与研究。具体来说，本文以经典的最大k-club问题和最大k-defective clique问题为例，根据各自问题的结构特点，设计实现了高效的约减算法G_NP和G_KD。Network Data Repository数据集以及Facebook社交网络数据集上的实验结果表明：所提出的G_NP和G_KD算法能够有效地对不同参数要求下的最大k-club问题和最大k-defective clique问题进行求解。特别是当参数k较小时，对于部分用例，能够约减大约20%的顶点，大幅度地降低了问题后续的求解难度。而当参数k较大时，所设计的上下界函数较为宽松，导致约减的效果有所下降，但即便如此，依旧能够约减掉一部分的顶点。

Abstract: The relaxed clique problem is a key problem in graph theory, which aims to find a relaxed clique model that satisfies the corresponding constraints in the graph. With the increasing size of data, it is particularly important to effectively reduce the relaxed clique problem to reduce the difficulty of solving the problem. Graph reduction technology has emerged as a result. This paper mainly studies the application and research of graph reduction technology in relaxed cliques. Specifically, this paper takes the classic maximum k-club problem and the maximum k-defective clique problem as examples, and designs and implements efficient reduction algorithms G_NP and G_KD according to the structural characteristics of each problem. The experimental results on the Network Data Repository dataset and the Facebook social network dataset show that the proposed G_NP and G_KD algorithms can effectively solve the maximum k-club problem and the maximum k-defective clique problem under different parameter requirements. In particular, when the parameter k is small, for some use cases, about 20% of the vertices can be reduced, which greatly reduces the difficulty of solving the problem later. When the parameter k is large, the designed upper and lower bound functions are relatively loose, resulting in a decrease in the reduction effect, but even so, some vertices can still be reduced.