论文标题
从树匹配到稀疏图对齐
From tree matching to sparse graph alignment
论文作者
论文摘要
在本文中，我们考虑了稀疏图的对齐，为此我们介绍了邻居树匹配算法（NTMA）。对于相关的erdős-rényi随机图，我们证明算法在多项式时间内返回 - 正正确匹配的顶点的正分数和不匹配的分数消失。该结果与$ o（1）$中的平均图相同，而相关参数$ s $可以从1处界定，在该条件下，随机图对准特别具有挑战性。作为分析的副产品，我们引入了树之间的匹配度量，并为几种相关的随机树模型表征它。这些结果可能具有独立的兴趣，例如，用于确定两个随机树是相关还是独立的有效测试。
In this paper we consider alignment of sparse graphs, for which we introduce the Neighborhood Tree Matching Algorithm (NTMA). For correlated Erdős-Rényi random graphs, we prove that the algorithm returns -- in polynomial time -- a positive fraction of correctly matched vertices, and a vanishing fraction of mismatches. This result holds with average degree of the graphs in $O(1)$ and correlation parameter $s$ that can be bounded away from 1, conditions under which random graph alignment is particularly challenging. As a byproduct of the analysis we introduce a matching metric between trees and characterize it for several models of correlated random trees. These results may be of independent interest, yielding for instance efficient tests for determining whether two random trees are correlated or independent.
