高效最小k-桁架搜索：一种基于分解的方法

《IEEE Transactions on Knowledge and Data Engineering》：Efficient Minimum k -Truss Search: A Decomposition-Based Approach

　　

摘要：

凝聚子图挖掘已被广泛研究，并在许多图挖掘应用中得到应用，如链接农场识别、社区检测和产品推荐等。在各种凝聚子图结构中，k-truss 结构因其基于三角形的强结构凝聚力而特别值得注意。然而，传统的 k-truss 问题旨在找到具有最大顶点数的 k-truss，这在实践中通常非常庞大且复杂。为了充分利用 k-truss 的优势，我们提出了一个称为最小 k-truss 问题的新方法，该方法旨在找到具有最小顶点数的 k-truss，其中 k≥2 是一个正整数。我们首先正式证明了该问题的 NP 难度。然后，我们设计了一个基于顶点枚举和启发式方法的基线算法 MTEnum 来计算上界。尽管如此，MTEnum 仍然面临实际效率问题，这可能是由于 k-truss 缺乏遗传性质。为了解决这个问题，我们开发了一个基于分解的新框架 DSA，该框架将问题优雅地转化为一系列基于称为基于边的 s-plex (s-eplex）的新凝聚子图模型的问题。利用 s-eplex 的遗传性质，我们为重新构建的问题设计了一个带有几种定制技术的分支定界算法。大量实验证明了我们研究问题的有效性以及我们提出的算法 DSA 的高效性。特别是，DSA 的运行速度比基线算法 MTEnum 快了五个数量级。