Dense Subgraph Maintenance under Streaming Edge Weight Updates for Real-time Story Identification

Summary: Maintaining dense subgraphs under streaming edge-weight updates for real-time story identification. DYN DENS exploits tight bounds on edge-update impact to density, outperforming naive baselines with validation on large real and synthetic data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10502
Venue: VLDB
Year: 2012
Pagerank: 0.00014582849
Overall Rank: 1,029 | 92.85%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,570	KClist++: A Simple Algorithm for Finding k-Clique Densest Subgraphs in Large Graphs	2020	VLDB	0.00011322927
2,039	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	9.7061003e-05
2,512	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB	8.6196023e-05
3,367	Online Density Bursting Subgraph Detection from Temporal Graphs	2019	VLDB	7.1725806e-05
4,145	Scaling Up k-Clique Densest Subgraph Detection	2023	SIGMOD	6.4122551e-05
4,270	Efficient k-Clique Listing: An Edge-Oriented Branching Strategy	2024	SIGMOD	6.3067205e-05
4,984	Efficient Maximum k-Defective Clique Computation with Improved Time Complexity	2023	SIGMOD	5.7867286e-05
5,265	A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery	2022	SIGMOD	5.5972878e-05
5,696	Maximum k-Plex Computation: Theory and Practice	2024	SIGMOD	5.3673968e-05
6,880	Theoretically and Practically Efficient Parallel Nucleus Decomposition	2022	VLDB	4.8970985e-05
7,804	RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs	2021	VLDB	4.6466513e-05
9,390	Efficient Maximum s-Bundle Search via Local Vertex Connectivity	2025	SIGMOD	4.3441378e-05
9,403	A Counting-based Approach for Efficient k-Clique Densest Subgraph Discovery	2024	SIGMOD	4.3441378e-05
9,557	An Efficient and Exact Algorithm for Locally h-Clique Densest Subgraph Discovery	2024	SIGMOD	4.3254416e-05
10,072	Efficient and Scalable Directed Densest Subgraph Discovery	2026	SIGMOD	4.1945683e-05
10,517	Faster and Efficient Density Decomposition via Proportional Response with Exponential Momentum	2025	SIGMOD	4.1945683e-05
10,681	Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory	2025	VLDB	4.1945683e-05
11,410	Densest Subgraph Discovery on Large Graphs: Applications, Challenges, and Techniques	2022	VLDB	4.1945683e-05
11,960	ALID: Scalable Dominant Cluster Detection	2015	VLDB	4.1945683e-05
12,127	Message From The Vldb 2012 General Program Chair	2012	VLDB	4.1945683e-05
13,376	StoryPivot: Comparing and Contrasting Story Evolution	2015	SIGMOD	-

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
57	Discovering Large Dense Subgraphs in Massive Graphs	2005	VLDB	0.00065491112
181	Mining Frequent Patterns without Candidate Generation	2000	SIGMOD	0.00036992674
969	TwitterMonitor: Trend Detection over the Twitter Stream	2010	SIGMOD	0.00014942212
1,208	Efficient Diversity-Aware Search	2011	SIGMOD	0.00013275712
1,816	Incremental Clustering for Mining in a Data Warehousing Environment	1998	VLDB	0.0001045313
2,374	Seeking Stable Clusters in the Blogosphere	2007	VLDB	8.9452874e-05
3,480	CSV: Visualizing and Mining Cohesive Subgraphs	2008	SIGMOD	7.0538737e-05
8,555	What's on the Grapevine ?	2009	SIGMOD	4.4937074e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
738	Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis	2013	VLDB	0.00017435236
10,134	A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs	2026	SIGMOD	4.1945683e-05
3,321	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	7.223972e-05
10,490	Integral Densest Subgraph Search on Directed Graphs	2025	SIGMOD	4.1945683e-05
644	Densest Subgraph in Streaming and MapReduce	2012	VLDB	0.00018748988
4,344	Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs	2020	SIGMOD	6.2744553e-05
10,062	Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings	2026	SIGMOD	4.1945683e-05
10,072	Efficient and Scalable Directed Densest Subgraph Discovery	2026	SIGMOD	4.1945683e-05
4,089	On Dense Pattern Mining in Graph Streams [Extended Abstract]	2010	VLDB	6.4587806e-05
7,308	Real Time Discovery of Dense Clusters in Highly Dynamic Graphs: Identifying Real World Events in Highly Dynamic Environments	2012	VLDB	4.7672834e-05