基于子拉普拉斯矩阵行列式的节点集影响力研究

Quantifying Influences of Node Groups with Determinants of Sub-Laplacian Matrices

摘要: 关键节点集识别是复杂网络控制与传播动力学理论中的基本问题之一。传统方法存在全局结构信息依赖性强、计算复杂度高、缺乏宏观调控指导等局限性。本研究首次提出子拉普拉斯矩阵(Sub-Laplacian Matrix)概念。指定一个节点集，原始拉普拉斯矩阵中对应的行与列构成的矩阵，称为子拉普拉斯矩阵。理论推导表明，该矩阵对角元表征节点全局连接度、非对角元反映节点集内部连接强度、行列式值可有效度量这一节点集的影响力、谱特性揭示了节点集与网络整体的耦合机制。采用子拉普拉斯矩阵识别了小世界网络(Watts-Strogatz small-world model, WSSW)、BASF网络(Barabasi-Albert scale-free model)和真实网络中多个节点集的影响力。与接地拉普拉斯矩阵(Grounded Laplacian)方法比较，本方法具有三重优势：(1) 仅需节点集局部结构信息与外部连接数；(2) 能为传播动力学调控提供宏观参数指导；(3) 显著缩小了量化重要节点集合影响力的计算成本，解决了计算复杂度随规模呈爆发式增长的NPC问题。子拉普拉斯矩阵，为决策者制定社交接触范围的宏观指导策略以延缓疾病传播进程或舆论扩散态势提供依据，也为决策执行者对特定节点集合影响力的量化评估提供了定量方法。

Abstract: Critical node set identification is one of the fundamental issues in complex network control and propagation dynamics theory. Traditional methods have limitations such as high dependency on global structural information, high computational complexity, and lack of guidance for macro-regulation. This research proposes the concept of Sub-Laplacian Matrix for the first time. By extracting the corresponding rows and columns of the target node set in the original Laplacian matrix, a feature matrix is constructed. Its determinant value is proven to serve as an effective metric for node set influence. Theoretical derivation shows that the diagonal elements of this matrix characterize the global connectivity of nodes, the off-diagonal elements reflect the internal connection strength of the node set, and its spectral properties reveal the coupling mechanism between the node set and the overall network. Using different network models such as small world networks (Watts-Strogatz small-world model, WSSW), BASF (Barabasi-Albert scale-free model) networks, and real-world networks, this paper compares sub-Laplacian matrices with traditional node set identification methods, verifying the effectiveness and advantages of determinant-based representation of node set importance. Compared with traditional grounded Laplacian-based methods, our approach exhibits threefold superiority: (1) Requiring only local structural information and external connection counts of node sets; (2) Enabling macroscopic parameter guidance for propagation dynamics regulation; (3) Significantly reducing the scale and effectively lowering the computational cost for quantifying the influence of important node sets (this problem is an NPC problem leading to exponential growth in computational complexity with scale). The research results not only provide macro guidance strategies for policymakers to formulate social contact scope to delay disease spread progression or public opinion diffusion trends, but also offer decision implementers with quantitative evaluation criteria for the influence of specific node sets.