Introduction
In network science, real-world graphs such as social networks or citation maps are typically sparse on a global scale but contain local "pockets" of extreme density. Traditional graph mining often focuses on the Densest Subgraph Problem, which seeks to identify one or a few optimally dense sets. However, this approach frequently falls into the "massive subgraph trap," where metrics favor a single giant, moderately dense subgraph over numerous small, extremely dense ones. Furthermore, many practical applications—including community detection, spam identification, and gene discovery—require high coverage, meaning the identification of many distinct dense groups rather than just the single best one.
This paper introduces RTRExtractor, an efficient algorithm designed to find a large collection of disjoint, high-density subgraphs that cover a significant portion of a network. By shifting the focus to "regularly triangle-rich" (RTR) families, the authors provide a scalable solution capable of processing graphs with hundreds of millions of edges in minutes.
Methodology: The RTRExtractor Framework
The core of the proposed approach is the mathematical framework of Regularly Triangle-Rich (RTR) sets. A set is considered RTR if its vertices have similar degrees and it contains a high density of triangles (3-node cliques). Triangles serve as a much more powerful signal for community structure than simple edge density because they are significantly harder to form by chance in sparse graphs.
RTRExtractor operates through an iterative extraction process:
- Triangle-Based Cleaning: The algorithm first removes "bad" edges that participate in too few triangles relative to the degrees of their endpoints. This sparsification step highlights dense cores.
- Seeded Extraction: It selects the lowest-degree vertex in the remaining graph as a "seed" and examines its neighborhood.
- Two-Hop Expansion: A key innovation is the "radius 2" approach. Instead of just taking immediate neighbors, the algorithm examines the two-hop neighborhood, adding vertices that form a high number of triangles with the initial neighborhood. This prevents the accidental splitting of a single dense cluster.
- Iteration: Once a dense set is identified, it is removed from the graph, and the process repeats until the graph is exhausted.
Experimental Results
The authors evaluated RTRExtractor on 11 diverse real-world datasets, including Orkut (117M edges), LiveJournal, and DBLP.
High Coverage and Density
A primary metric for the algorithm's success is its ability to cover a large portion of the graph with high-density subgraphs. On the Orkut social network, RTRExtractor covered 24% of the vertices with subgraphs having an edge density of at least 0.5. In contrast, competing methods like Louvain or $k$-truss covered less than 10% at the same density level.
Furthermore, the algorithm maintains exceptional density across the extracted subsets. In the DBLP citation network, the mean edge density of the output sets was 1.0, indicating that the algorithm primarily identifies cliques.
Scalability and Semantic Meaning
RTRExtractor is remarkably fast, processing the Orkut graph (over 100 million edges) in approximately 16 minutes on a standard laptop. This efficiency is achieved through a space-complexity of $O(m)$ by storing triangle counts on edges and recomputing specific triangles only when necessary.
Beyond quantitative metrics, the extracted subgraphs carry significant semantic meaning. In a case study of the DBLP network, the algorithm automatically grouped papers into highly specific sub-topics, such as "Spatial Joins" or "Object-Oriented Programming Traits," without prior knowledge of metadata like paper titles or venues.
Conclusion and Future Work
RTRExtractor demonstrates that focusing on triangle-rich sets and utilizing a two-hop expansion strategy allows for the efficient discovery of dense subgraph families with high coverage. While the current implementation produces a "flat" collection of disjoint sets, future work may extend the algorithm to capture the hierarchical nature of real-world communities. Additionally, the triangle-based cleaning step shows promise as a general-purpose graph sparsification tool for broader machine learning tasks.
Summary updated