论文阅读:Scalable Algorithms for Densest Subgraph Discovery

摘要

密集子图发现（DSD）作为图数据挖掘的基础问题，旨在从图中找到密度最高的子图。虽然已有许多DSD算法，但它们在处理大规模图时往往不可扩展或效率低下。本文提出了在无向图和有向图上求解DSD问题的高效并行算法，通过优化迭代过程和减少迭代次数来计算核心数。同时引入了新的子图模型——w诱导子图，以避免不必要的枚举，从而提高算法效率。实验结果表明，所提算法在无向图和有向图上的性能均优于现有算法，具有良好的可扩展性和效率。

介绍

密集子图发现问题在图数据挖掘中具有重要意义，广泛应用于网络社区检测、DNA调控基序发现、图索引构建以及虚假关注者检测等领域。尽管已有许多DSD算法，但大多数算法为串行算法，仅能利用单个CPU核心的计算资源，难以处理大规模图数据。因此，本文提出了高效的并行算法以解决这一问题。

相关工作

• 无向图DSD算法：许多无向图DSD算法基于k-core分解。Charikar提出了第一个2-近似算法，通过迭代剥离度最小的顶点来寻找密集子图。Fang等人证明了k-core的最大核心数是2-近似解，并开发了高效的算法。
• 有向图DSD算法：Ma等人提出了[x, y]-core的概念，通过迭代剥离度最小的顶点来计算有向图的密集子图。Bahmani等人提出了基于MapReduce的并行算法，解决了有向图和无向图的DSD问题。

算法细节

无向图密集子图发现算法

1. k-core计算：通过迭代剥离度最小的顶点，直到所有顶点的度数都不小于k。

   • 初始化：设置每个顶点的度数为初始h-index。
   • 迭代剥离：并行更新每个顶点的h-index，直到所有顶点的h-index值不再变化。
   • 提前停止：如果两次连续迭代中的最大h-index值和相应顶点数不变，则停止迭代，返回k*-core。
   • 时间复杂度：最坏情况下时间复杂度为O(t * m)，其中t是迭代次数，m是图中的边数。

2. 并行优化：

   • 并行设计：基于共享内存模型的并行算法，有效利用多核处理器提升计算速度。
   • 优化策略：引入h-index更新方法，减少冗余计算，提高效率。
   • 实验验证：通过实验验证算法在大规模图上的高效性。

有向图密集子图发现算法

1. [x, y]-core计算：
   • 定义：一个[x, y]-core是有向图中出度至少为x，入度至少为y的最大子图。
   • 迭代剥离：剥离出度或入度最小的顶点，直到剩余图满足[x, y]条件。
   • w诱导子图模型：定义边权重为其两端点度数乘积，通过剥离权重最小的边来找到密集子图。

2. w诱导子图计算：
   • 边权重定义：每条边的权重定义为其两端点的出度和入度的乘积。
   • w诱导子图：剥离权重最小的边，记录其诱导数，并更新相邻边的权重，直到图为空。
   • 时间复杂度：最坏情况下时间复杂度为O(t * m)，其中t是迭代次数，m是图中的边数。

实验结果

实验在12个大规模真实图数据集上进行，包括4个十亿规模的图。实验结果表明，本文提出的并行算法在无向图和有向图上的表现均显著优于现有的最先进算法。具体来说，在处理无向图时，所提出的算法在计算时间上比基准算法快了20倍；在处理有向图时，速度提升达到30倍。此外，实验数据还展示了新算法在大规模图数据上的出色扩展性，不仅减少了计算时间，还提高了结果的准确性。

上圖10展示了PBD、PXY和PWC这三种并行算法在WE和TW两个数据集上的可扩展性测试结果。实验中所有子图的采样方式与实验-4相同。由于在p>4时，PBD和PXY在TW数据集上因内存溢出而无法运行，因此我们在各个图上将参数设置为p=4，以比较这三种并行算法的可扩展性。图中可以看到，随着图中边数的增加，所有算法的时间开销也相应增加。这一结果验证了我们提出的算法在处理大规模图数据时的良好表现，能够有效应对图规模的增长

图八展示了不同数据集上DDS算法的效率。实验结果显示，PXY和PBD由于内存溢出无法在TW数据集上运行。与其他算法相比，PWC在所有数据集上的运行速度最快，最多比最先进的PXY算法快30倍。触及上边界的条形图表示相应的算法无法在105秒内完成。

结论

本文提出了一系列高效的并行算法，用于在大规模无向图和有向图中发现密集子图。通过引入共享内存模型的并行设计和w诱导子图模型，显著减少了计算过程中的冗余操作，提升了算法的效率和可扩展性。实验结果验证了所提算法在处理大规模图数据时的优越性能。未来的研究可以进一步优化这些算法，探索在异构计算环境（如GPU和CPU结合）中的应用。此外，可以研究动态图上的密集子图发现算法，以应对图结构随时间变化的情况。在应用方面，这些算法可广泛应用于社交网络中的社区检测和虚假用户识别、生物信息学中的基因调控网络分析、网络安全中的异常行为检测以及大规模图数据的可视化和查询优化。通过这些扩展，密集子图发现算法将会在更多的实际场景中发挥重要作用，为各个领域提供有力的数据分析工具。

论文地址:https://ieeexplore.ieee.org/document/10184843