2020/08/18 by Aritra Konar, Konar, Aritra, Nicholas D. Sidiropoulos +1
Computer Science · #Advanced Database Systems and Queries #Data Management and Algorithms #Data Mining Algorithms and Applications #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.2.1 #G.2.2 #Machine Learning (cs.LG) #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.2008.07996
openalex publication_date 2020/08/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Mining dense subgraphs is an important primitive across a spectrum of\ngraph-mining tasks. In this work, we formally establish that two recurring\ncharacteristics of real-world graphs, namely heavy-tailed degree distributions\nand large clustering coefficients, imply the existence of substantially large\nvertex neighborhoods with high edge-density. This observation suggests a very\nsimple approach for extracting large quasi-cliques: simply scan the vertex\nneighborhoods, compute the clustering coefficient of each vertex, and output\nthe best such subgraph. The implementation of such a method requires counting\nthe triangles in a graph, which is a well-studied problem in graph mining. When\nempirically tested across a number of real-world graphs, this approach reveals\na surprise: vertex neighborhoods include maximal cliques of non-trivial sizes,\nand the density of the best neighborhood often compares favorably to subgraphs\nproduced by dedicated algorithms for maximizing subgraph density. For graphs\nwith small clustering coefficients, we demonstrate that small vertex\nneighborhoods can be refined using a local-search method to ``grow'' larger\ncliques and near-cliques. Our results indicate that contrary to worst-case\ntheoretical results, mining cliques and quasi-cliques of non-trivial sizes from\nreal-world graphs is often not a difficult problem, and provides motivation for\nfurther work geared towards a better explanation of these empirical successes.\n