Please use this identifier to cite or link to this item:
DC FieldValue
dc.titleOn triangulation-based dense neighborhood graph discovery
dc.contributor.authorWang, N.
dc.contributor.authorZhang, J.
dc.contributor.authorTan, K.-L.
dc.contributor.authorTung, A.K.H.
dc.identifier.citationWang, 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.
dc.description.abstractThis 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.
dc.contributor.departmentCOMPUTER SCIENCE
dc.description.sourcetitleProceedings of the VLDB Endowment
Appears in Collections:Staff Publications

Show simple item record
Files in This Item:
There are no files associated with this item.

Page view(s)

checked on Dec 2, 2019

Google ScholarTM


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