Abstract: Critical nodes group identification problem has become a hot research in the microscopic level of complex networks. In the big data era, existing methods based on simulations and measures often fail in local solutions with the increasing scale and complexity of complex networks. Meanwhile, the mainstream integer linear programming (ILP) model has the drawback of neglecting internal structures of connected components. Hence, for the critical nodes group identification problem, it needs to carry on a further research on formulating mathematical models from the topological structure and function of networks. In order to solve these problems, this paper proposes a 0-1 nonconvex quadratically constrained quadratic programming (QCQP) model by minimizing the number of pairwise nodes within second-order pathway. Simultaneously, a heuristic algorithm is designed by combining greedy search and local exchange to solve critical nodes problem for large-scale networks. Finally, many synthetic and real-world networks are conducted in the experiments to validate the effectiveness and efficiency of the proposed approach.

Key words: critical nodes group, critical nodes group identification, complex networks, quadratic programming model, heuristic algorithms

摘要： 关键节点组识别问题，因其应用背景广泛，目前已经成为复杂网络微观层面的重要研究内容。随着大数据时代的到来，网络的规模愈加庞大，结构愈为复杂，现有基于仿真模拟和指标度量的传统识别方法受到很大局限，常常陷入局部最优解。同时，基于整数线性规划的识别模型存在不能够区分网络连通分支内部结构的缺陷。因此，亟需从网络整体结构和功能出发对关键节点组识别问题建模进行深入研究。为此，基于0-1二次约束二次规化理论建立识别模型，通过最小化二阶路径内连通节点对的个数，实现区分连通分支内部结构的能力。同时，提出了一种将贪婪搜索和局部置换相结合的启发式算法，以适应大规模网络的关键节点组识别。最后，在多组人工网络和真实网络数据集上实验分析，验证所提出模型和算法的正确性和有效性。

关键词: 关键节点组, 关键节点组识别, 复杂网络, 二次规划模型, 启发式算法