对于鄂尔多斯 - 仁义图通过尾分布进行无核图匹配

作者：Mahdi Bozorg,Saber Salehkaleybar,Matin Hashemi

摘要：图匹配问题是指恢复两个相关图之间的节点到节点的对应关系。之前的工作理论上表明，在稀疏的Erdos-Renyi图中恢复是可行的，当且仅当在一个图中的一对节点之间以及另一个图中的相应节点之间具有边缘的概率是大约Ω（log（n）/ n），其中n是节点数。在本文中，我们提出了一种图匹配算法，该算法在不使用预匹配节点对的种子集作为输入的情况下，在Θ（log（n）/ n）的区域中在鄂尔多斯 - 仁义图中获得具有高概率的正确匹配。该算法基于其邻居节点的经验度分布的尾部，为高度节点分配结构创新特征。然后，它根据这些特征匹配高度节点，最后获得剩余节点的匹配。我们在Θ（log（n）/ n）和Θ（log2（n）/ n）的区域中评估所提出的算法的性能。实验表明，它优于以往两个区域的匹配结果。

原文标题：Seedless Graph Matching via Tail of Degree Distribution for Correlated Erdos-Renyi Graphs

原文摘要：

地址：https://arxiv.org/abs/1907.06334