一种结合索引优化的新型并行方法在桁架维护中的应用

《IEEE Transactions on Big Data》：A Novel Parallel Approach with Index Optimization for Truss Maintenance

　　

k-truss是一种凝聚子图，其中每条边都包含在子图内的至少k个三角形中。它常用于社区搜索和密集子图发现。尽管k-truss可以在多项式时间内计算出来，但要获取一个随时间通过边插入和删除而变化的动态图中的所有k-truss在计算上仍然非常耗时。为了解决这一挑战，先前的研究提出了truss维护方法，这些方法会在动态图发生变化时更新受影响的k-truss。然而，现有方法由于潜在的冲突，仅利用了并行性或辅助索引中的一种，这限制了它们的整体性能。为了解决这一限制，我们提出了一种新颖的并行方法，并结合了索引优化，有效解决了并行性和索引维护之间的冲突。具体来说，我们首先基于辅助索引建立了一种新的truss维护理论，确保了我们维护解决方案的可行性和正确性。其次，我们设计了两种有效的边划分策略来提高所提算法的并行性。最后，我们实现了两种高效的并行算法，这些算法与辅助索引配合使用以降低维护成本。在真实世界图上的广泛实验表明，我们的方法性能优于所有基线方法，最高可提高一个数量级。