抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
グラフマッチングは,2つのエッジ相関グラフ間の潜在頂点対応を見出し,異なる分野にわたる多数の応用を見出した。本論文では,シードグラフマッチング問題(すなわち,事前写像頂点ペア)が前もって与えられると仮定した。殆どの以前の研究は,全ての種子を補正する必要があるが,種子が部分的に正しい設定に焦点を当てる。特に,エッジが親ERグラフG(n,p)から独立にサンプリングされる2つの相関グラフを考察した。2つのグラフの頂点間のマッピングを,未知のβ分率が正しい種子として提供した。最初に,1ホップ近傍における共通シードの数に基づく頂点と一致する簡単なアルゴリズムを解析し,さらに,2ホップ近傍における種子を用いる新しいアルゴリズムを提案した。1ホップと2ホップアルゴリズムの両方に対する完全マッチングの非漸近性能保証を確立し,グラフがスパースであるとき,この新しい2ホップアルゴリズムが1ホップアルゴリズムよりも実質的に少ない正しいシードを必要とすることを示した。さらに,著者らの新しい性能保証を1ホップおよび2ホップアルゴリズムに組み合わせることによって,グラフスパース性の全範囲にわたって,既知の結果(正しいシードの必要な画分に関して)を達成し,p≧n ̄-5/6の時に,サイト10.14778/2794367.2794371,lubars2018の修正における以前の結果を大幅に改善した。例えば,pが一定またはp=n ̄-3/4の場合,Ω(√nlogn)だけが完全マッチングに対して正しいシードサフスを補正し,一方,以前に知られている結果は,それぞれΩ(n)およびΩ(n ̄3/4logn)正しい種子を要求した。数値実験は,著者らの理論的発見を確認し,様々な合成および実グラフに対する著者らの2ホップアルゴリズムの優位性を実証した。【JST・京大機械翻訳】
