若干最大松弛团问题的启发式和精确求解算法研究

In graph theory, clique is a vertex set whose induce graph is a complete graph, while relaxed clique is an extension of classical clique model, which refers to a vertex set whose induced graph is a dense graph. In recent years, people realize that relaxed cliques can be widely used in in diverse domains such as economic data mining, social network analysis and computational biology. In this sense, the optimization problems related to relaxed clique are quite fundamental. In this project, we mainly concentrate on the design of heuristic and exact algorithms for several NP-Hard maximum relaxed clique problems, including maximum k-plex problems, maximum k-club problems and maximum balanced biclique problem. Techniques such as local search, branch-and-bound, graph reduction, integer linear programming are used to improve the efficiency of the algorithms. With consideration to the popular big-data analysis, we also take special care of the computational efficiency of the new algorithms on large real-life networks. The research is expected to set up new benchmark art algorithms to maximum relaxed clique problems, as well as propose new theories and design new tools for combinatorial optimization. The applicant consistently designs state-of-the-art heuristic and exact algorithms for clique and related problems in the last 3 years, which show the capacity of accomplishing this research. The duration of this research is estimated to be 3 years.

在图论中，团是导出子图为完全图的顶点集合。松弛团作为经典团模型的扩展，指的是导出子图为稠密图的顶点集合。近几年，人们意识到松弛团可以广泛应用在金融数据挖掘、社交网络分析、计算生物等领域中，其相关最优化问题也是一类重要的基础问题。基于此，本项目将主要研究几类NP难最大松弛团问题，包括最大k-plex问题，最大k-club问题以及最大二分平衡团问题，并探讨其启发式和精确求解算法。研究拟通过局部搜索、分支定界搜索、大图缩减、整数线性规划等多种技术来充分提升的算法的计算能力。结合当前大数据分析的背景，研究还将重点关注大规模社交网络上的最大松弛团问题求解。本项目有望为相关问题设定新的基准算法, 并为组合优化提供新的理论和工具。申请者有较强的科研基础，近三年来持续在团及相关问题上提出了当前表现最好的启发式和精确算法。目前科研进展顺利，预计三年完成。

在图论中，松弛团指的类似团的稠密图。松弛团包括多类具体定义，如k-plex松弛团指的是每个点最多和图内k个点不相邻的稠密图。近十年来，松弛团不仅在数据挖掘、社交网络分析等领域展现重要的应用价值，其相关问题也是组合优化、计算机科学领域的研究重点之一。在本项目中，我们以经典的k-plex松弛团为主要目标，研究了最大松弛团，极大松弛团的相关算法。具体来说，本课题研究成果包括：1）研究了极大k-plex枚举问题，设计了高效的精确枚举算法，并证明算法具有已知最优渐进指数复杂度上界，且提出了实现算法所需的高效的数据结构和并行策略；2）研究了最大k-plex搜索问题，创新性地设计了基于边的缩减策略，基于图染色的上界估计策略，并由此得到一个更为快速的分支搜索算法；3)扩展k-plex研究成果到其他松弛团问题上，包括最大k-defective团问题，最大k-bundle问题，团枚举问题，团分割问题等，并为上述问题设计高效的实验算法；4）研究了一部分松弛团相关问题，如为平衡边分割设计基于局部搜索的近似算法，为最小和图染色给出新的下界估计方法等。研究使用的主要工具包括精确分支搜索，搜索树估算，局部搜索，实验分析等。算法在大图上表现优异，代码皆开源且可复现。成果可在图数据挖掘等领域进行推广应用。