On triangulation-based dense neighborhood graph discovery

Abstract

This paper introduces a new definition of dense subgraph pattern, the DN-graph. DN-graph considers both the size of the substructure and the minimum level of interactions between any pair of the vertices. Themining ofDN-graphs inherits the difficulty of finding clique, the fully-connected subgraphs. We thus opt for approximately locating theDN-graphs using the state-of-the-art graph triangulation methods. Our solution consists of a family of algorithms, each of which targets a different problem setting. These algorithms are iterative, and utilize repeated scans through the triangles in the graph to approximately locate the DN-graphs. Each scan on the graph triangles improves the results. Since the triangles are not physically materialized, the algorithms have small memory footprint. With our solution, the users can adopt a "pay as you go" approach. They have the flexibility to terminate the mining process once they are satisfied with the quality of the results. As a result, our algorithms can cope with semi-streaming environment where the graph edges cannot fit into main memory. Results of extensive performance study confirmed our claims. © 2010 VLDB Endowment.