论文阅读-无需验证的高效局部最密子图发现方法

摘要

在大规模图中寻找密集子图是一项基础的图挖掘任务，具有许多应用。局部最密子图（LDS）的概念最近被提出，用于识别复盖大图不同区域的多个密集子图。LDS 是其局部区域中密度最高的子图。当前最先进的算法通过迭代计算最密子图并将其从图中删除，然后通过代价高昂的最大流计算来验证每个候选项。尽管有先进的剪枝技术，但验证步骤仍然耗时，特别是对于较大的 k 值。在本文中，我们设计了无验证方法来提高寻找前 k 个 LDS 的效率。我们提出了分治算法 LDS-DC 和优化算法 LDS-Opt，它们在不构建整个层次结构的情况下高效地识别前 k 个 LDS。实证研究表明，LDS-Opt 在所有 k 值上都优于现有方法，改进幅度达到几个数量级。

引言

在大规模图中寻找密集子图是一项基础的图挖掘任务。由于现实世界的图通常是全局稀疏的，密集子图通常表示图中的语义重要区域。密集子图挖掘已被应用于许多领域，如社交网络中的社区检测、社交媒体中的故事识别、网页图中的垃圾链接检测以及生物图中的调控基序发现。

局部最密子图（LDS）的概念

在实际应用中，仅仅找到一个最密子图往往不足以满足需求，因为这个子图只复盖了大图的一个区域。为了解决这个问题，Qin 等人提出了局部最密子图（LDS）的概念，其目的是在大图中找到多个分佈于不同区域的密集子图。

一个图是 λ-紧凑的，如果它满足以下两个条件：

1. 它是连通的。
2. 从中移除任何顶点子集 S 及其相关的边后，至少会移除 λ×∣S∣ 条边。

一个子图是图 G 的最大 λ-紧凑子图，如果它是 λ-紧凑的最大子图。局部最密子图（LDS）是当 λ 等于子图密度时的最大 λ-紧凑子图。

这样，LDS能够有效地识别大图中不同区域的多个密集子图，从而更全面地反映图的结构特徵。

现有方法的效率问题

计算密度最高的前 k 个局部最密子图（LDS）的最先进算法是LDS方法，其时间复杂度为

O ( m 2 n log ⁡ 2 n ) O(m^2 n \log^2 n) O(m2nlog2n)

基本思想是迭代地计算最密子图，并将其从图中删除；随着图的不断缩小，计算出的最密子图不一定是输入图 G 中最密的。所有计算出的最密子图的连通组件是LDS的候选项。对于每个候选子图 g，需要验证它是否确实是LDS。

在这个过程中，定义了一个函数
F ( λ ) F(λ) F(λ)

用于最大化
∣ E ( S ) ∣ − λ ∣ S ∣ ∣E(S)∣−λ∣S∣ ∣E(S)∣−λ∣S∣
其中 E(S) 表示图 G中两端点都在顶点集 S 中的边集。通过计算这个函数，可以找到最密子图的候选项。

可以通过网络流算法来计算。

然而，这种方法存在效率问题。随着图规模的增加和迭代次数的增加，计算时间会显着增长，因此需要更高效的算法来处理大规模图数据。

提出的无验证方法

本文提出了无需验证的方法来高效计算前 k 个 LDS。我们基于以下观察：所有可能 λ 值的最大 λ-紧凑子图集合形成一个层次结构，LDS 只是该层次结构中的叶子。因此，我们提出了一种分治算法 LDS-DC 以及一种优化算法 LDS-Opt，以便在不构建整个层次结构的情况下高效地识别前 k 个 LDS。实证研究表明，LDS-DC 在较大 k 值时（例如 k ≥ 20）运行速度比 LDS 快，但在较小 k 值时可能被 LDS 超过。为了解决 LDS-DC 在小 k 值时的低效问题，我们进一步提出了优化方法 LDS-Opt，该方法在所有 k 值下都优于 LDS-DC。

具体算法

LDS-DC 算法

LDS-DC 算法是一种分治算法，旨在通过分而治之的策略高效地计算最大 λ-紧凑子图。其核心思想是递归地分割图并计算局部密集子图，然后合并结果。

1. 初始化：将整个图作为输入，设定初始参数。
2. 分割：根据密度值 λ 将图分割为若干子图。
3. 递归计算：对每个子图递归调用 LDS-DC 算法，直至达到最小子图。
4. 合并结果：将递归计算的结果合并，形成最终的局部最密子图。

LDS-Opt 算法

LDS-Opt 算法在 LDS-DC 算法的基础上进行优化，旨在提高小 k 值时的计算效率。其主要优化策略包括：

1. 剪枝技术：在递归计算过程中，移除不可能属于 LDS 的顶点，减少计算量。
2. 局部优化：在每个子图中，优先计算密度最高的子图，以减少递归深度。
3. 动态调整参数：根据当前图的密度和结构，动态调整算法参数，以达到最优性能。

实验结果

我们在多个真实图上进行了广泛的实证研究，结果表明，LDS-Opt 在所有 k 值上都优于现有方法，尤其是在大 k 值情况下，改进幅度达到几个数量级。具体实验结果如下：

1. 对比方法：我们将 LDS-Opt 与现有的 LDS 算法进行了对比。

2. 实验图集：选择了多个具有代表性的真实图进行实验，包括社交网络图、网页图和生物图。

3. 性能指标：主要比较了计算时间和内存使用量。

4. 结果分析：LDS-Opt 在所有实验图上均表现出更高的效率，特别是在大 k 值情况下，计算时间显着减少。

   

   上图展示了在侦测所有LDSEs (即k = ∞) 时，在十个不同数据集，三种不同方法的效率，分别是LDS、LDS-DC 和LDS-Opt

这张图表展示了在十个不同数据集中，LDS、LDS-DC和LDS-Opt方法在侦测小k值 (k ≤ 20) 时的效率表现。

这张图表展示了在六个不同数据集中，LDS、LDS-DC和LDS-Opt方法在侦测所有LDSEs (k = ∞) 且随图规模变化时的效率表现。

结论

本文提出的无验证方法，通过定义新的问题、设计高效的算法以及引入优化技术，解决了在大规模图中高效发现局部最密子图（LDS）的问题。我们的研究在图数据挖掘中具有重要意义，并为相关研究提供了新的思路和方法。

具体来说，我们提出的LDS-DC和LDS-Opt算法，显着提高了发现局部最密子图的效率，并且在实验中表现出色，优于现有的LDS方法，特别是在处理较大的k值时。我们的方法避免了传统方法中昂贵的验证步骤，从而大幅减少了计算时间。

未来的研究方向可以包括以下几个方面：

1. 算法优化：进一步优化算法，以应对更大规模的图数据集，并提高算法的可扩展性。
2. 应用扩展：探索我们的方法在不同领域中的应用，例如社交网络分析、生物信息学和网络安全等。
3. 理论分析：深入分析算法的理论性能，探索其在不同图结构下的行为。

总结来说，本文的研究不仅提供了一种高效发现局部最密子图的方法，还为未来的研究开辟了新的方向，具有广泛的应用前景和深远的影响。

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