Exact matching of random graphs with constant correlation
Exact matching of random graphs with constant correlation
复制标题
DOI：
10.1007/s00440-022-01184-3
复制
发表时间：
2021-10
影响因子：
2
通讯作者：
Cheng Mao;M. Rudelson;K. Tikhomirov
中科院分区：
文献类型：
--
作者：
Cheng Mao;M. Rudelson;K. Tikhomirov
本文研究了Erdens-Rényi图的图匹配或网络映射问题，它可以看作是图同构问题的一个噪声平均情形.设GandbeG（n，p）Erdens-Rényi图，与它们的邻接矩阵相同。假设和是相关的。对于表示G和G的顶点之间的潜在匹配的置换，用置换G的顶点得到的图表示。观察和，我们的目标是恢复匹配。本文证明了对任意的常数，存在依赖常数和绝对常数，并具有如下性质。让，和。有一个多项式时间算法F使得。这是第一个以高概率恢复相关Erdens-Rényi图顶点间精确匹配的多项式时间算法。该算法是基于比较的划分树与图的顶点。
This paper deals with the problem ofgraph matchingornetwork alignmentfor Erdős–Rényi graphs, which can be viewed as a noisy average-case version of the graph isomorphism problem. LetGandbeG(n,p) Erdős–Rényi graphs marginally, identified with their adjacency matrices. Assume thatGandare correlated such that. For a permutationrepresenting a latent matching between the vertices ofGand, denote bythe graph obtained from permuting the vertices ofGby. Observingand, we aim to recover the matching. In this work, we show that for every, there isdepending onand absolute constantswith the following property. Let,, and. There is a polynomial-time algorithmFsuch that. This is the first polynomial-time algorithm that recovers theexact matchingbetween vertices of correlated Erdős–Rényi graphs withconstant correlationwith high probability. The algorithm is based on comparison ofpartition treesassociated with the graph vertices.