Optimal graph Laplacian
Optimal graph Laplacian
复制标题
DOI：
10.1016/j.automatica.2019.02.005
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
Kazuhiro Sato
中科院分区：
文献类型：
--
作者：
Kazuhiro Sato
本文提供了一种最接近的图拉普拉斯矩阵的构造方法，从测量数据的图拉普拉斯动力学，包括生化，同步，和多智能体系统。我们考虑的情况下，网络结构，即，一个给定的图的边缘之间的关系，是已知的。将寻找最近图拉普拉斯算子的问题转化为一个凸优化问题。因此，我们的问题可以使用内点方法来解决。此外，我们还可以实现交替方向的乘法器（ADMM）为我们的问题。然而，由于使用内点法和ADMM的每次迭代的复杂度分别大于O（n6）和O（n3），其中n是网络的节点数。也就是说，如果n很大，内点方法和ADMM不能在实际时间内解决我们的问题。为了解决这个问题，我们提出了一个简单而有效的算法，计算复杂度为O（n 2）。仿真实验表明，我们的方法是有用的执行数据驱动的建模图拉普拉斯动力学。
This paper provides a construction method of the nearest graph Laplacian to a matrix identified from measurement data of graph Laplacian dynamics that include biochemical, synchronization, and multi-agent systems. We consider the case in which the network structure, ie, the relationship between edges of a given graph, is known. A problem of finding the nearest graph Laplacian is formulated as a convex optimization problem. Thus, our problem can be solved using interior point methods. Moreover, we can also implement the alternating direction method of multipliers (ADMM) for our problem. However, the complexities of each iteration due to the use of interior point methods and ADMM are larger than O (n 6) and O (n 3), respectively, where n is the number of nodes of the network. That is, if n is large, interior point methods and ADMM cannot solve our problem within a practical time. To resolve this issue, we propose a simple and efficient algorithm with calculation complexity O (n 2). The simulation experiments demonstrate that our method is useful to perform data-driven modeling of graph Laplacian dynamics.