Mining dense subgraphs is an important primitive across a spectrum of
graph-mining tasks. In this work, we formally establish that two recurring
characteristics of real-world graphs, namely heavy-tailed degree distributions
and large clustering coefficients, imply the existence of substantially large
vertex neighborhoods with high edge-density. This observation suggests a very
simple approach for extracting large quasi-cliques: simply scan the vertex
neighborhoods, compute the clustering coefficient of each vertex, and output
the best such subgraph. The implementation of such a method requires counting
the triangles in a graph, which is a well-studied problem in graph mining. When
empirically tested across a number of real-world graphs, this approach reveals
a surprise: vertex neighborhoods include maximal cliques of non-trivial sizes,
and the density of the best neighborhood often compares favorably to subgraphs
produced by dedicated algorithms for maximizing subgraph density. For graphs
with small clustering coefficients, we demonstrate that small vertex
neighborhoods can be refined using a local-search method to ``grow'' larger
cliques and near-cliques. Our results indicate that contrary to worst-case
theoretical results, mining cliques and quasi-cliques of non-trivial sizes from
real-world graphs is often not a difficult problem, and provides motivation for
further work geared towards a better explanation of these empirical successes.

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