Efficient random graph matching via degree profiles
Efficient random graph matching via degree profiles
复制标题
DOI：
10.1007/s00440-020-00997-4
复制
发表时间：
2018-11
影响因子：
2
通讯作者：
Jian Ding;Zongming Ma;Yihong Wu;Jiaming Xu
中科院分区：
文献类型：
--
作者：
Jian Ding;Zongming Ma;Yihong Wu;Jiaming Xu
随机图匹配是指恢复两个具有相关边的随机图之间的底层顶点对应关系;一个突出的例子是当两个随机图由Erdens-Rényi图给出时。这可以被看作是图同构问题的平均情况和噪声版本。在此模型下，极大似然估计等价于求解一个难处理的二次分配问题。本文提出了一种快速算法，该算法在保证两个图的平均度至少为且两个图的边相差最多分数的条件下，以很高的概率完美地恢复了真实的顶点对应。对于稠密图和稀疏图，这可以分别改进为和，都是在多项式时间内。该方法是基于适当选择的距离统计的程度配置文件（经验分布的程度的邻居）。在此之前，最著名的结果是，对于某个常数，用一个时间算法和用一个多项式时间算法分别得到和。
Random graph matching refers to recovering the underlying vertex correspondence between two random graphs with correlated edges; a prominent example is when the two random graphs are given by Erdős-Rényi graphs. This can be viewed as an average-case and noisy version of the graph isomorphism problem. Under this model, the maximum likelihood estimator is equivalent to solving the intractable quadratic assignment problem. This work develops an-time algorithm which perfectly recovers the true vertex correspondence with high probability, provided that the average degree is at leastand the two graphs differ by at mostfraction of edges. For dense graphs and sparse graphs, this can be improved toandrespectively, both in polynomial time. The methodology is based on appropriately chosen distance statistics of the degree profiles (empirical distribution of the degrees of neighbors). Before this work, the best known result achievesandfor some constantcwith an-time algorithm andandwith a polynomial-time algorithm.