摘要:
研究背景 强连通分量的检测是学术数据分析中一项至关重要的图算法，广泛应用于论文聚类、学术影响力测度等任务。然而，现有的大多数强连通分量检测方法主要针对一般图而设计，并未充分考虑引文图所特有的边类型与时间顺序等属性。与普通图不同，引用图中的边通常遵循学术论文的发表时间顺序，若直接沿用一般图上的增量强连通分量方法（如基于在整个图中维护（弱）拓扑序，或在有向无环图中维护（弱）拓扑序，一旦检测到强连通分量即停止），将会产生大量不必要的节点与边遍历，导致代价过高。这表明在不断扩张的引用图环境下，充分利用文献引用图自身的特性来进行高效增量强连通分量检测至关重要。为此，我们还需要设计一种有界的增量算法，在处理连续更新的过程中尽量限制被访问的节点与边数量。
目的 现有的增量强连通分量检测方法主要针对一般有向图而设计，未充分利用文献引用图特有的时间顺序与边的属性，导致在学术场景中对大量不必存在强连通分量的边和节点进行了额外遍历。本研究聚焦引文图的增量强连通分量检测，既包括单步更新又覆盖批量更新，旨在降低无效遍历、提高检测效率，并在不断增量扩张的引用环境下（新论文、新引用的持续加入）仍能稳定地维护强连通分量结构，对学术分析、数据质量提升等具有重要价值。
方法 本文首先基于引文图特性对其进行划分，我们将原图G(V, E) 分区为三类子图：Gm(Vm, Em), Gs(Vs, Es), Gr(Vr, Er),并维护一组跨边Ec，使得非单点强连通分量仅出现在Gm和Gs内。因此，可以合理利用“不同边类型”以及“学术论文时间顺序”的特征，减少对不相关子图的遍历。在划分的基础上，只需要增量维护局部拓扑序即可，即：在Gm和Gs上维护局部拓扑顺序，只在局部受影响的区域更新拓扑序，避免全局范围的大规模更新。在引文划分和局部拓扑序的基础上，本文设计了增量有界的强连通分量检测算法，包括两部分。1）单增量算法：在每次插入节点或边时，动态维护分区和局部拓扑序，保证只处理受影响的部分；2）批量增量算法：在一批插入后，通过减少无效边而进一步降低遍历成本，同样只在局部范围进行更新，避免全图级的重复计算。
结果 单增量算法相比已有的增量方法，强连通分量检测效率最少提高7.9倍，受影响的节点数也相应大幅减少，减少7.7倍以上。批增量算法在多条边／节点同时插入时，较现有基准最少快4.5倍，且能在检测过程中减少79%以上的无效边遍历。整体空间开销与现有方法相当或更优。
结论 首次针对引文图的特性提出单步和批量两种有界增量算法，利用图划分与局部拓扑序有效减少不必要遍历。通过在真实数据和合成数据上进行实验，验证算法在速度和空间上的优异表现，展示了对学术分析下游任务的促进作用。理论上，在增量环境中维护强连通分量的最坏时间复杂度得到有界性保证；实践中，可在学术搜索、引用追踪、论文推荐等应用场景中推广。进一步研究方向包括：1）适应减量更新，目前主要关注插入更新，后续可扩展到对学术数据的减量算法进行高效支持；2）错误引用的清理，基于所检测的强连通分量，识别并移除潜在错误引用从而提升数据质量。
下载: