Seeded graph matching
Seeded graph matching
复制标题
DOI：
10.1016/j.patcog.2018.09.014
复制
发表时间：
2019-03-01
影响因子：
8
通讯作者：
Priebe, Carey E.
中科院分区：
文献类型：
--
作者：
Fishkind, Donniell E.;Adali, Sancar;Priebe, Carey E.
给定两个图，图匹配问题是对齐两个顶点集，以使两个图之间的邻接不一致的数量最小化。种子图匹配问题是当我们第一次被给予一个我们要完成的部分对齐时的图匹配问题。在这篇文章中，我们修改了Vogelstein等人（2015）的最先进的近似图匹配算法"FAQ"，使其成为一种快速近似种子图匹配算法，使其适用于包括具有不同大小顶点集的图，并扩展该算法，以便为每个单独的顶点提供可能匹配的提名列表。我们证明了我们的算法的有效性，通过模拟和真实的数据实验，事实上，知识，甚至一些种子可以是非常有效的，当我们的种子图匹配算法被用来恢复自然存在的对齐，只有部分观察。(C)2018作者爱思唯尔有限公司出版
Given two graphs, the graph matching problem is to align the two vertex sets so as to minimize the number of adjacency disagreements between the two graphs. The seeded graph matching problem is the graph matching problem when we are first given a partial alignment that we are tasked with completing. In this article, we modify the state-of-the-art approximate graph matching algorithm "FAQ" of Vogelstein et al. (2015) to make it a fast approximate seeded graph matching algorithm, adapt its applicability to include graphs with differently sized vertex sets, and extend the algorithm so as to provide, for each individual vertex, a nomination list of likely matches. We demonstrate the effectiveness of our algorithm via simulation and real data experiments; indeed, knowledge of even a few seeds can be extremely effective when our seeded graph matching algorithm is used to recover a naturally existing alignment that is only partially observed. (C) 2018 The Authors. Published by Elsevier Ltd.