KDDAug, 2020
从顶点邻居中挖掘具有质量保证的大型拟团
Mining Large Quasi-cliques with Quality Guarantees from Vertex Neighborhoods
Aritra Konar, Nicholas D. Sidiropoulos
TL;DR本文探讨了通过扫描顶点邻域，计算每个顶点的聚类系数并输出最佳子图来提取大的准簇的简单方法，证明了现实世界图的两个重要特征意味着存在具有高边密度的大型顶点邻域。这种方法的实现需要对图中的三角形进行计数，这在图挖掘中是一个被深入研究的问题。经过实际测试，该方法揭示了一个惊人的事实：顶点邻域包括中等大小的极大团，而最佳邻域的密度往往比用于最大化子图密度的专用算法产生的子图优越。对于聚类系数较小的图，我们证明可以使用局部搜索方法来 “增长” 更大的团和准团。与最坏情况理论结果相反，从实际图中挖掘中等大小的团和准团通常不是一个困难问题，并且激励了进一步研究这些实证成功的更好解释。