Feb, 2016

ABRA: 使用 Rademacher 平均值在静态和动态图中逼近介数中心度

PDF
TL;DR利用随机采样和统计学习理论，我们提出了 ABRA 算法，可以高效地计算和维护所有节点或边的介数中心性，相较于目前同等质量保证和样本数的最先进算法更具优势。
发现论文，激发创造
  • ONBRA: 时态网络中时间介数中心性的严格估计

    本文提出了 ONBRA 算法作为第一种基于抽样的近似算法，用来计算带有时间信息网络中节点的时间介数中心性，为减少计算代价带来质量保证。

    Mar, 2022

  • 使用渐进采样和非均匀 Rademacher Bounds 估算介数中心性的 SILVAN 算法

    提出一种新型高效算法 SILVAN，基于蒙特卡洛实证 Rademacher 平均值的新约束，通过渐进采样方法计算网络图中各节点的中介中心性，建立新的估算方案提供节点中介中心性的非均匀偏差边界并确定样本所需的数量，相比于其他算法在样本数量和准确度上表现更好。

    Jun, 2021

  • 大规模计算经典亲密中心性

    本文提出了一种高度可扩展的算法，用于在图中估计所有节点的经典接近度中心性，并针对出站和入站中心性的概括，提出了有效的算法，并在大型网络上进行了广泛实验，证明了其高可扩展性和准确性。

    Aug, 2014

  • 关于分类时空中介中心性的多项式可解性

    本文研究了在时间图中如何高效地计算顶点的中介中心性，提出了多种 “最短路径” 的概念，并探讨了哪种概念能够在多项式时间内解决问题。

    May, 2021

  • 一种多项式时间逼近算法用于全节点网络可靠性

    在无向图中，基于 “簇弹出” 算法的期望运行时间受输入规模的多项式限制，得到了全多项式时间随机逼近方案 (FPRAS) 来解决全终端网络可靠性问题。

    Sep, 2017

  • 通过添加链接提高节点的中介中心性

    本文考虑如何通过有限数量的新边缘与节点相连以增加节点的居间度量。我们研究了最大化某个节点的居间度量和排名的问题，并提出了一种简单的贪婪法近似算法，以及一种用于更新节点居间度量的动态算法。我们的算法大大提高了节点的居间性和排名，并在多个真实网络中表现出竞争的基线。

    Feb, 2017

  • 吸收随机游走中心性：理论与算法

    该研究提出了一种基于吸收随机游走的新型图中心性概念，旨在确定相对于查询节点集 Q 而言，图 G 中最具中心性的 k 个节点，并探究该问题的一些性质及基于谱聚类和个性化 PageRank 的高效算法。

    Sep, 2015

  • 利用因果意识图神经网络预测动态图中的时序中心度

    利用 De Bruijn 图神经网络（DBGNN）来预测时间序列数据中的时间路径中心性，显著改善了静态图卷积神经网络对于中介中心性和紧密中心性的预测。

    Oct, 2023

  • 时间中介中的算法问题

    研究时变图中各种概念下的最优时空路径，发现计算其顶点之间的中心度具有可计算与难以计算的不同情况，其计算复杂度与所选的最优路径概念相关，是社交网络分析中常用的一种有用工具。

    Jun, 2020

  • 图算法的平均灵敏度

    对图算法的平均敏感度进行系统研究，并提供了具有低平均敏感度的近似算法，其中主要应用了局部计算算法和已知次线性时间算法的分析方法。

    Apr, 2019