2014/12/30 by Heng Wang, Wang, Heng, Da Zheng +6
Computer Science · Physics and Astronomy · #Advanced Clustering Algorithms Research #Complex Network Analysis Techniques #FOS: Computer and information sciences #FOS: Physical sciences #Opinion Dynamics and Social Influence #Physics and Society (physics.soc-ph) #Social and Information Networks (cs.SI) #cs.SI #physics.soc-ph
paper · pdf · doi:10.48550/arxiv.1412.8576
published in SDM-Networks 2015
openalex publication_date 2014/12/30 · arxiv created 2015/02/13 · arxiv updated 2015/02/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A canonical problem in graph mining is the detection of dense communities. This problem is exacerbated for a graph with a large order and size -- the number of vertices and edges -- as many community detection algorithms scale poorly. In this work we propose a novel framework for detecting active communities that consist of the most active vertices in massive graphs. The framework is applicable to graphs having billions of vertices and hundreds of billions of edges. Our framework utilizes a parallelizable trimming algorithm based on a locality statistic to filter out inactive vertices, and then clusters the remaining active vertices via spectral decomposition on their similarity matrix. We demonstrate the validity of our method with synthetic Stochastic Block Model graphs, using Adjusted Rand Index as the performance metric. We further demonstrate its practicality and efficiency on a most recent real-world Hyperlink Web graph consisting of over 3.5 billion vertices and 128 billion edges.