Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/39504
Title: On triangulation-based dense neighborhood graph discovery
Authors: Wang, N.
Zhang, J.
Tan, K.-L. 
Tung, A.K.H. 
Issue Date: 2010
Source: 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.

Page view(s)

46
checked on Dec 8, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.