Fugu-MT 論文翻訳(概要): Random Graph Matching with Improved Noise Robustness

論文の概要: Random Graph Matching with Improved Noise Robustness

arxiv url: http://arxiv.org/abs/2101.11783v1
Date: Thu, 28 Jan 2021 02:39:27 GMT
ステータス: 処理完了
システム内更新日: 2021-01-31 17:59:00.125877
Title: Random Graph Matching with Improved Noise Robustness
Title（参考訳）: ノイズロバスト性向上によるランダムグラフマッチング
Authors: Cheng Mao, Mark Rudelson, and Konstantin Tikhomirov
Abstract要約: 本稿では確率モデルに基づくグラフマッチングの新しいアルゴリズムを提案する。我々のアルゴリズムは、$alpha le 1 / (log log n)C$ のとき、その基礎となるマッチングを高い確率で復元する。これにより、以前の作業で達成された条件 $alpha le 1 / (log n)C$ が改善される。
参考スコア（独自算出の注目度）: 2.294014185517203
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Graph matching, also known as network alignment, refers to finding a bijection between the vertex sets of two given graphs so as to maximally align their edges. This fundamental computational problem arises frequently in multiple fields such as computer vision and biology. Recently, there has been a plethora of work studying efficient algorithms for graph matching under probabilistic models. In this work, we propose a new algorithm for graph matching and show that, for two Erd\H{o}s-R\'enyi graphs with edge correlation $1-\alpha$, our algorithm recovers the underlying matching with high probability when $\alpha \le 1 / (\log \log n)^C$, where $n$ is the number of vertices in each graph and $C$ denotes a positive universal constant. This improves the condition $\alpha \le 1 / (\log n)^C$ achieved in previous work.
Abstract（参考訳）: ネットワークアライメントとも呼ばれるグラフマッチングは、与えられた2つのグラフの頂点セット間のバイジェクションを見つけ、エッジを最大にアライメントすることを意味します。この基本的な計算問題は、コンピュータビジョンや生物学などの複数の分野で頻繁に発生します。近年、確率モデルの下でのグラフマッチングの効率的なアルゴリズムの研究が数多く行われている。本研究では, グラフマッチングの新しいアルゴリズムを提案し, エッジ相関 1-\alpha$ を持つ2つの Erd\H{o}s-R\'enyi グラフに対して, このアルゴリズムは $\alpha \le 1 / (\log \log n)^C$ が各グラフの頂点数で, C$ は正の普遍定数を表す。これは前作で達成した $\alpha \le 1 / (\log n)^C$ の条件を改善する。