Please use this identifier to cite or link to this item:
|Title:||On triangulation-based dense neighborhood graph discovery||Authors:||Wang, N.
|Issue Date:||2010||Citation:||Wang, N.,Zhang, J.,Tan, K.-L.,Tung, A.K.H. (2010). On triangulation-based dense neighborhood graph discovery. Proceedings of the VLDB Endowment 4 (2) : 58-68. ScholarBank@NUS Repository.||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.||Source Title:||Proceedings of the VLDB Endowment||URI:||http://scholarbank.nus.edu.sg/handle/10635/39504||ISSN:||21508097|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Oct 28, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.