The study focuses on complex networks that are underlying graphs with an embedded dynamical system. We aim to reduce the number of edges in the network while minimizing its impact on network dynamics. We present an algorithmic framework that produces sparse graphs meaning graphs with fewer edges on reaction-diffusion complex systems on undirected graphs. We formulate the sparsification problem as a data assimilation problem on a Reduced order model space(ROM) space along with constraints targeted towards preserving the eigenmodes of the Laplacian matrix under perturbations(L = D - A, where D is the diagonal matrix of degrees and A is the adjacency matrix of the graph). We propose approximations for finding the eigenvalues and eigenvectors of the Laplacian matrix subject to perturbations. We demonstrate the effectiveness of our approach on several real-world graphs.
翻译:本研究关注于包含动力学系统的复杂网络,即基于嵌入式动态系统的底层图。我们的目标是减少网络中的边的数量,同时最小化其对网络动力学的影响。我们提出了一种算法框架,可以在无向图上的反应-扩散复杂系统中生成稀疏图,即意味着图形上的边更少。我们将稀疏化问题构建为约束在减小阶数模型空间下的数据同化问题,并针对保持Laplacian矩阵在扰动下的特征模式的约束提出了预估计算特征值和特征向量的方法。我们在几个真实世界的图上演示了我们方法的有效性。