Message-Passing Algorithms for Sparse Network Alignment
Message-Passing Algorithms for Sparse Network Alignment
复制标题
DOI：
10.1145/2435209.2435212
复制
发表时间：
2013-03-01
影响因子：
3.6
通讯作者：
Wang, Ying
中科院分区：
文献类型：
--
作者：
Bayati, Mohsen;Gleich, David F.;Wang, Ying
网络对齐概括和统一了在两个图的顶点之间形成匹配或对齐的几种方法。我们研究了网络对齐问题的数学规划框架及其稀疏变体，其中两个图的顶点之间只有少量匹配是可能的。我们提出了一种新的消息传递算法，可以非常高效地计算出图大到几十万个顶点的稀疏网络对齐问题的近似解。我们还在两个合成匹配问题、两个生物信息学问题和三个大型本体比对问题上，将我们的算法与两个最好的网络比对问题的两个最好的求解器进行了大量的模拟比较，其中包括一个具有已知标记比对的多语言问题。
Network alignment generalizes and unifies several approaches for forming a matching or alignment between the vertices of two graphs. We study a mathematical programming framework for network alignment problem and a sparse variation of it where only a small number of matches between the vertices of the two graphs are possible. We propose a new message passing algorithm that allows us to compute, very efficiently, approximate solutions to the sparse network alignment problems with graph sizes as large as hundreds of thousands of vertices. We also provide extensive simulations comparing our algorithms with two of the best solvers for network alignment problems on two synthetic matching problems, two bioinformatics problems, and three large ontology alignment problems including a multilingual problem with a known labeled alignment.