On Triangulation-based Dense Neighborhood Graph Discovery

Summary: Introduces DN-graphs, dense subgraphs defined jointly by size and minimum pairwise interaction. Iterative, triangle-scanning triangulation algorithms approximate their discovery without materializing triangles, enabling pay-as-you-go mining with small memory—even in semi-streaming settings. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h5cfd2fbd92edd49c
Venue: VLDB
Year: 2011
Pagerank: 0.00022949287
Overall Rank: 255 | 98.30%
DOI: 10.14778/1921071.1921073

Incoming Non-self Citations Over Time

Authors

1. Nan Wang (National University of Singapore)
2. Jingbo Zhang (National University of Singapore)
3. Kian-Lee Tan (National University of Singapore)
4. Anthony K. H. Tung (National University of Singapore)

BibTeX Citation

@article{wang_vldb11,
        title = {{On Triangulation-based Dense Neighborhood Graph Discovery}},
        author = {Wang, Nan and Zhang, Jingbo and Tan, Kian-Lee and Tung, Anthony K. H.},
        journal = {PVLDB},
        series = {{VLDB} '11},
        volume = {4},
        number = {2},
        pages = {58--69},
        doi = {10.14778/1921071.1921073},
        url = {https://doi.org/10.14778/1921071.1921073},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
96	Truss Decomposition in Massive Networks	2012	VLDB	0.00034261728
182	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00026383593
274	Online Search of Overlapping Communities	2013	SIGMOD	0.00022499515
580	Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis	2013	VLDB	0.00016057466
599	Massive Graph Triangulation	2013	SIGMOD	0.00015700433
970	Influential Community Search in Large Networks	2015	VLDB	0.00012749284
1,198	KClist++: A Simple Algorithm for Finding k-Clique Densest Subgraphs in Large Graphs	2020	VLDB	0.00011541919
1,860	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD	9.4720431e-05
2,110	Maximum Co-located Community Search in Large Scale Social Networks	2018	VLDB	9.0222862e-05
2,470	Efficient Structural Graph Clustering: An Index-Based Approach	2018	VLDB	8.4015437e-05
2,705	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD	8.0936619e-05
2,815	SCAN++: Efficient Algorithm for Finding Clusters, Hubs and Outliers on Large-scale Graphs	2015	VLDB	7.9544959e-05
3,145	Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity	2015	SIGMOD	7.5828479e-05
3,396	Scaling Up k-Clique Densest Subgraph Detection	2023	SIGMOD	7.3277458e-05
4,567	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD	6.5173666e-05
6,226	I/O Efficient ECC Graph Decomposition via Graph Reduction	2016	VLDB	5.8266364e-05
7,557	HERO: A Hierarchical Set Partitioning and Join Framework for Speeding up the Set Intersection Over Graphs	2024	SIGMOD	5.4795245e-05
7,752	RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs	2021	VLDB	5.4440674e-05
8,935	On Asymptotic Cost of Triangle Listing in Random Graphs	2017	PODS	5.2361195e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
130	Discovering Large Dense Subgraphs in Massive Graphs	2005	VLDB	0.0003029792
3,903	CSV: Visualizing and Mining Cohesive Subgraphs	2008	SIGMOD	6.9150978e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,966	Densest Subgraph Discovery on Large Graphs: Applications, Challenges, and Techniques	2022	VLDB
2	6,078	Maximal D-truss Search in Dynamic Directed Graphs	2023	VLDB
3	10,636	Efficient and Scalable Directed Densest Subgraph Discovery	2026	SIGMOD
4	10,879	Efficient Locally h-Clique Densest Subgraph Discovery via Divide-and-Conquer	2026	VLDB
5	11,383	Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory	2025	VLDB
6	10,499	Bound-Tightened Densest Subgraph Discovery on GPU	2026	SIGMOD
7	11,284	In-depth Analysis of Densest Subgraph Discovery in a Unified Framework	2025	VLDB
8	3,778	Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs	2020	SIGMOD
9	2,005	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB
10	1,995	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB