BriefGPT.xyz
Apr, 2024
图对齐问题：基本限制与高效算法
The graph alignment problem: fundamental limits and efficient algorithms
HTML
PDF
Luca Ganassali
TL;DR
该论文研究图对齐问题，即图同构问题的噪声版本，旨在找到两个图节点之间保留大多数边的匹配。研究集中在随机图中，在理解该问题的基本信息论极限以及设计和分析能够恢复数据中潜在对齐的算法方面表现出兴趣。针对这些算法，我们给出了在它们成功或失败的情况下的高概率保证。
Abstract
This thesis studies the
graph alignment
problem, the
noisy version
of the
graph isomorphism
problem, which aims to find a matching between
→