Fugu-MT 論文翻訳(概要): Efficiently matching random inhomogeneous graphs via degree profiles

論文の概要: Efficiently matching random inhomogeneous graphs via degree profiles

arxiv url: http://arxiv.org/abs/2310.10441v1
Date: Mon, 16 Oct 2023 14:25:43 GMT
ステータス: 処理完了
システム内更新日: 2023-10-17 13:57:51.360451
Title: Efficiently matching random inhomogeneous graphs via degree profiles
Title（参考訳）: 次数プロファイルによるランダム不均質グラフの効率的なマッチング
Authors: Jian Ding, Yumou Fei, Yuanzheng Wang
Abstract要約: 最小平均次数が少なくとも$Omega(log2 n)$である限り、効率的なマッチングアルゴリズムが見つかる。等級プロファイルによるマッチングアルゴリズムの着想と拡張により、最小平均次数が少なくとも$Omega(log-2 n)$である限り、効率的なマッチングアルゴリズムが得られる。
参考スコア（独自算出の注目度）: 11.485620556026571
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In this paper, we study the problem of recovering the latent vertex correspondence between two correlated random graphs with vastly inhomogeneous and unknown edge probabilities between different pairs of vertices. Inspired by and extending the matching algorithm via degree profiles by Ding, Ma, Wu and Xu (2021), we obtain an efficient matching algorithm as long as the minimal average degree is at least $\Omega(\log^{2} n)$ and the minimal correlation is at least $1 - O(\log^{-2} n)$.
Abstract（参考訳）: 本稿では,異なる頂点間の不均一性および未知のエッジ確率を持つ2つの相関ランダムグラフ間の潜時頂点対応を復元する問題について検討する。 Ding, Ma, Wu および Xu (2021) による等級プロファイルによるマッチングアルゴリズムの着想と拡張により、最小平均次数が少なくとも$\Omega(\log^{2} n)$であり、最小相関が少なくとも$1 - O(\log^{-2} n)$である限り、効率的なマッチングアルゴリズムが得られる。

関連論文リスト

A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation [12.869436542291144]
本稿では,2つの相関した ErdHos--R'enyi グラフと,エッジが潜時対応によって相関している$n$ とをマッチングする効率的なアルゴリズムを提案する。我々のアルゴリズムは実行時間を持ち、エッジの相関が無くなる限り、潜時マッチングを回復することに成功した。
論文参考訳（メタデータ） (2023-06-01T00:58:50Z)
Efficient Algorithms for Exact Graph Matching on Correlated Stochastic Block Models with Constant Correlation [7.914348940034351]
本稿では,グラフとコミュニティ構造をマッチングする効率的なアルゴリズムを提案する。我々のアルゴリズムは2つの相関ブロックモデル間の正確なマッチングを実現する最初の低次時間アルゴリズムである。
論文参考訳（メタデータ） (2023-05-31T09:06:50Z)
Matching Correlated Inhomogeneous Random Graphs using the $k$-core Estimator [5.685589351789462]
我々は、両グラフの大きな共通部分グラフを誘導する対応を出力するいわゆるemph$k$-core推定器について検討する。相関ブロックモデル,Chung-Lu幾何グラフ,および相関ランダムグラフの精度と部分的回復に関する新たな結果を導出するために,我々の一般的な枠組みを専門化している。
論文参考訳（メタデータ） (2023-02-10T18:21:35Z)
Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
論文参考訳（メタデータ） (2023-02-02T08:33:36Z)
Random graph matching at Otter's threshold via counting chandeliers [16.512416293014493]
そこで本研究では,各木に根付いた重み付き木を数えることで構築した類似度スコアに基づく,グラフマッチングの効率的なアルゴリズムを提案する。これは、明示的な一定の相関で成功し、スパースグラフと密度グラフの両方に適用する最初のグラフマッチングアルゴリズムである。
論文参考訳（メタデータ） (2022-09-25T20:00:28Z)
Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文参考訳（メタデータ） (2021-06-22T11:07:38Z)
Random Graph Matching with Improved Noise Robustness [2.294014185517203]
本稿では確率モデルに基づくグラフマッチングの新しいアルゴリズムを提案する。我々のアルゴリズムは、$alpha le 1 / (log log n)C$ のとき、その基礎となるマッチングを高い確率で復元する。これにより、以前の作業で達成された条件 $alpha le 1 / (log n)C$ が改善される。
論文参考訳（メタデータ） (2021-01-28T02:39:27Z)
Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文参考訳（メタデータ） (2020-09-18T02:18:44Z)
Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。本研究の結果は, 同時一次および二重側収束の形で表される。
論文参考訳（メタデータ） (2020-08-23T20:36:49Z)
Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文参考訳（メタデータ） (2020-06-24T11:37:33Z)
Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文参考訳（メタデータ） (2020-02-26T16:19:09Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。