专栏首页arxiv.org翻译专栏图对齐问题中的部分恢复(CS DA)
原创

图对齐问题中的部分恢复(CS DA)

在本文中,我们考虑了图对齐问题,这是在给定两个图的情况下恢复节点之间一对一映射(最大化边缘重叠)的问题。该问题可以看作是众所周知的图同构问题的嘈杂版本,并且出现在许多应用中,包括社交网络去匿名和细胞生物学。我们这里的重点是部分恢复,即,我们寻找一对一的映射,该映射在图的一部分节点上正确,而不是在所有节点上正确,并且我们假设问题的两个输入图是参数的相关Erdös-Rényi图(Ñ ,q,s )。然后,我们的主要贡献是为(Ñ ,q,s ) 在这种情况下,随着节点数量的增加,部分恢复是很有可能的 ñ去无穷大。这些条件是紧凑的,易于解释,并且覆盖了绝大多数参数空间。

原文标题:Partial Recovery in the Graph Alignment Problem

原文:In this paper, we consider the graph alignment problem, which is the problem of recovering, given two graphs, a one-to-one mapping between nodes that maximizes edge overlap. This problem can be viewed as a noisy version of the well-known graph isomorphism problem and appears in many applications, including social network deanonymization and cellular biology. Our focus here is on partial recovery, i.e., we look for a one-to-one mapping which is correct on a fraction of the nodes of the graph rather than on all of them, and we assume that the two input graphs to the problem are correlated Erdös-Rényi graphs of parameters (n,q,s). Our main contribution is then to give necessary and sufficient conditions on (n,q,s) under which partial recovery is possible with high probability as the number of nodes n goes to infinity. These conditions are compact, easily interpretable, and cover a vast majority of the parameter space.

原文作者:Georgina Hall, Laurent Massoulié

原文地址:https://arxiv.org/abs/2007.00533

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 研究用于社交媒体中仇恨语音检测的深度学习方法(CS CL)

    互联网的迅猛发展有助于增强个人的表达能力,但滥用表达自由的行为也导致各种网络犯罪和反社会活动的增加。仇恨言论就是一个这样的问题,需要非常认真地解决,否则,这可能...

    刘子蔚
  • 具有深度强化学习的以人为中心的协作机器人(CS AI)

    我们为以人为本的协作系统提出了一个基于强化学习的框架。该框架是积极主动的,它通过最大限度地减少完成任务所花费的总时间,在及时采取措施的利益与采取不当措施的风险之...

    刘子蔚
  • 策略渐变方法的操作员视图(CS AI)

    我们将策略梯度方法转换为两个运算符的重复应用:策略改进运算符 一世,它映射任何策略 π 更好的一个 一世π和投影运算符 P,它找到的最佳近似值 一世π在可实现的...

    刘子蔚
  • 协作机器人的数字孪生:案例研究(CS CY)

    人机协作(HRC)可以在传统上难以实现自动化的领域(例如装配)中提高自动化水平。但是,对适应性和人类存在动力的需求使人机协作系统的全部潜力难以实现。 本文探讨了...

    小童
  • 经典Keller- Segel模型的完全离散逼近分析:下界和先验界(CS NA)

    本文研究了经典凯勒-西格尔模型的趋化性问题。它由一个非线性抛物方程系统组成,其中未知数是细胞(或生物体)的平均密度(守恒变量)和化学吸引的平均密度。

    非过度曝光
  • 在拥挤场景中基于多视点几何的对多人三维姿态估计

    中文摘要:外极约束是目前多机三维人体姿态估计方法中特征匹配和深度估计的核心问题。尽管该公式在稀疏人群场景中的表现令人满意,但在密集人群场景中,其有效性经常受到挑...

    用户7454122
  • Linux系统内部的名称解析与安全认证(原创)

    我们都知道计算机最喜欢的是数字,而人类喜欢的是语言,所以我们在计算机上运行的进程、定义的用户、端口号、协议、ip地址等都需要转换成数字的形式让计算机明白,在Li...

    用户2645267
  • 研究具有奇异性的DAE系统的临界清除时间灵敏度(CS SY)

    标准电力系统模型是参数相关的微分代数方程(DAE)类型。由于存在瞬态事件,电压崩溃可能作为瞬态负载流解的分支出现,该分支由系统轨迹在失去电压因果关系的状态空间中...

    用户6853689
  • 医疗分诊的人工智能决策支持(AL)

    我们将先进的机器学习和自然语言处理技术应用于大约一百万个远程咨询记录中,我们开发了一种分类系统,该系统现已通过认证,并已在欧洲最大的远程医疗提供商中使用。该系统...

    田冠宇
  • 神经结构搜索与一个有效的多目标进化框架(CS CV)

    深度学习方法已经非常成功地解决了许多复杂的任务,如图像分类和分割,语音识别和机器翻译。然而,由于超参数搜索空间大、训练时间长以及缺乏超参数选择的技术指导原则,手...

    凌茜

扫码关注云+社区

领取腾讯云代金券