Feb, 2024

平衡偏倚度分布的根茎

PDF
TL;DR通过应用根茎的概念到以顶点为中心的消息驱动图处理，本文旨在解决由图中高入度分布所引起的负载不平衡问题。通过构建图的根茎，为任意数量的单个大入度顶点创建多个命名顶点地址。然后允许其他顶点指向任何命名地址，从而共享入度负载。模拟实验结果表明，在包含高度偏斜的入度分布的测试输入图数据集上，BFS 图遍历在大型芯片尺寸上的性能提升。这些改进来自于在内存处理元素之间共享入度计算工作负载，同时降低芯片内网络的争用。
发现论文，激发创造
  • 任意度分布的随机图及其应用

    本文研究了任意度数分布的随机图的理论，并且将其应用到真实世界的图形中进行验证，结果显示在有些情况下预测得很准确，而在另一些情况下与现实存在明显差异，表明随机图并没有完全捕捉到网络中的社会结构。

    Jul, 2000

  • 海量社交图快速可扩展分析

    本研究旨在探讨如何在当今大规模图形上开展可扩展性的图形处理，提出了一种新的图形坐标系统的设计空间，即通过将图嵌入到坐标空间的方式精确地近似节点距离，从而实现常数时间内的距离查询和最短路径查询，在 43 百万个节点的图中能提供更准确的结果，且可以很容易地扩展到定位节点对之间的最短路径，解决了大规模图形分析的难题。

    Jul, 2011

  • 基于 k 近邻图的索引优化在高维数据中的近似查询

    研究高维向量数据的查询技术，提出了三种度调整方法并给出了优化参数，经验证，在高维图像和文本数据的检索准确性方面表现优于以前的方法。

    Oct, 2018

  • 具有聚类特性的稀疏随机图

    本文介绍了一种扩展了边远离独立性的稀疏随机图的一般模型，并且通过构造非齐性随机超图来替代每个超边，再通过与某个积分算子的范数相关来解释巨型连通性的临界点，并将该巨型连通量与某些（非 Poisson）多类型分支过程的生存概率关联起来，同时研究度分布和数量小子图的细节。

    Jul, 2008

  • 复杂网络的攻击脆弱性

    本文研究了复杂网络在节点和边受到攻击的响应。通过计算平均反向测地线长度和最大连接子图的大小，数值地研究了几种复杂网络模型和科学合作以及互联网流量这些现实网络的性能。通过对初始网络或在去除过程中当前网络重新计算度和中介中心性，使用了四种去除策略，发现所使用的重新计算攻击策略往往比基于初始网络的攻击策略更具有破坏性。最后，还研究了复杂网络中介中心性和度之间的相关性

    Feb, 2002

  • 基于优先级的平衡图分区再流算法

    介绍了一种新型的基于 restreaming 的算法，使用带有乘性权重的约束管理策略来优化流式过程的排序，同时借鉴了平衡标签传播的优先级概念来进行分区优化，得到了与现有算法相比在真实世界图上具有更好性能的结果。

    Jul, 2020

  • 平衡下的路由

    该论文介绍了有向图平衡的概念，利用该概念解决了多个有关有向图中的路由问题。另外，还给出了针对平衡的有向图的最大流问题的快速算法。

    Mar, 2016

  • 基于负载中心度的研究学者兴趣挖掘方法

    本文提出了一种基于负载中心的研究学者兴趣挖掘算法（LCBIM），通过论文和专利数据计算权重并生成主题图，依据各主题的区域结构紧密计算节点负载中心度，从而提取科研学者的兴趣。

    Mar, 2022

  • 基于不均衡拓扑的半监督节点分类学习

    本论文主要探讨了在学习节点表示过程中，类不平衡问题是如何影响图像的，同时提出了一种识别和解决图拓扑不平衡问题的新方法，并在系统实验中证明了该方法在缓解拓扑不平衡问题和促进半监督节点分类中的有效性和通用性，同时揭示了不同 GNN 架构对拓扑不平衡的敏感性。

    Oct, 2021

  • 图上的最大熵分布

    研究了给定预期度序列的加权图上最大熵分布。使用指数族分布的一般理论，导出了顶点参数的最大似然估计量 (MLE) 的存在和唯一性，同时证明了单个样本的 MLE 在大图极限下的一致性，以及推出了加权图的 Erdos-Gallai 准则和顶点势的独立边权。

    Jan, 2013