具有谱性质保证的线性时间相关控制洗牌:针对随机正则图

《Information》:Linear-Time Correlation-Controlled Shuffling on Random Regular Graphs with Spectral Guarantees

【字体: 大 中 小 】 时间:2026年08月28日 来源:Information 4.3

编辑推荐:

   本文提出了一种线性时间的相关性控制打乱方法,通过在随机正则图上对其中一个变量进行局部交换来衰减皮尔逊相关系数。每一轮按固定的边顺序处理,且仅接受顶点不相交的交换,从而产生贪心匹配而非标准的交换过程更新。该分析使用诱导的一阶矩算子。边接受概率的均匀下界给出拉普拉斯支配关系,而顶

  本文提出了一种线性时间的相关性控制打乱方法,通过在随机正则图上对其中一个变量进行局部交换来衰减皮尔逊相关系数。每一轮按固定的边顺序处理,且仅接受顶点不相交的交换,从而产生贪心匹配而非标准的交换过程更新。该分析使用诱导的一阶矩算子。边接受概率的均匀下界给出拉普拉斯支配关系,而顶点保持未匹配的概率下界则控制负谱。在环删除后的实现图连通且具有非零谱隙的条件下,期望相关性的绝对值呈指数收缩。对于每一个固定的同号衰减目标,均存在一个激活概率可在期望意义上达到该目标。有限样本校准采用固定预算的多分辨率直接搜索,且不假设单调性。由于该方法仅施加置换,边际分布被精确保持。在固定度和固定校准预算下,校准与打乱均随样本量线性扩展。实验结果表明目标误差较小、边际分布精确保持、且运行时呈近似线性扩展。匹配度的谱消融实验进一步表明,在度和边数保持不变的情况下,高谱隙随机正则图的均值相关性衰减速度显著快于低谱隙正则循环图。
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号