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: 10503
Venue: VLDB
Year: 2012
Pagerank: 0.00014568714
Overall Rank: 1,029 | 92.86%
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.00011311977
2,043	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	9.6970812e-05
2,516	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB	8.6114467e-05
3,369	Online Density Bursting Subgraph Detection from Temporal Graphs	2019	VLDB	7.1656755e-05
4,147	Scaling Up k-Clique Densest Subgraph Detection	2023	SIGMOD	6.4060893e-05
4,266	Efficient k-Clique Listing: An Edge-Oriented Branching Strategy	2024	SIGMOD	6.3006582e-05
4,984	Efficient Maximum k-Defective Clique Computation with Improved Time Complexity	2023	SIGMOD	5.7811667e-05
5,274	A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery	2022	SIGMOD	5.5919087e-05
5,709	Maximum k-Plex Computation: Theory and Practice	2024	SIGMOD	5.3622436e-05
6,882	Theoretically and Practically Efficient Parallel Nucleus Decomposition	2022	VLDB	4.8923998e-05
7,806	RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs	2021	VLDB	4.6421951e-05
9,396	Efficient Maximum s-Bundle Search via Local Vertex Connectivity	2025	SIGMOD	4.3399748e-05
9,409	A Counting-based Approach for Efficient k-Clique Densest Subgraph Discovery	2024	SIGMOD	4.3399748e-05
9,557	An Efficient and Exact Algorithm for Locally h-Clique Densest Subgraph Discovery	2024	SIGMOD	4.3212967e-05
10,072	Efficient and Scalable Directed Densest Subgraph Discovery	2026	SIGMOD	4.1905499e-05
10,526	Faster and Efficient Density Decomposition via Proportional Response with Exponential Momentum	2025	SIGMOD	4.1905499e-05
10,689	Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory	2025	VLDB	4.1905499e-05
11,413	Densest Subgraph Discovery on Large Graphs: Applications, Challenges, and Techniques	2022	VLDB	4.1905499e-05
11,968	ALID: Scalable Dominant Cluster Detection	2015	VLDB	4.1905499e-05
12,135	Message From The Vldb 2012 General Program Chair	2012	VLDB	4.1905499e-05
13,389	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.00065421423
182	Mining Frequent Patterns without Candidate Generation	2000	SIGMOD	0.00036955562
969	TwitterMonitor: Trend Detection over the Twitter Stream	2010	SIGMOD	0.00014927789
1,204	Efficient Diversity-Aware Search	2011	SIGMOD	0.00013316893
1,803	Incremental Clustering for Mining in a Data Warehousing Environment	1998	VLDB	0.00010481475
2,374	Seeking Stable Clusters in the Blogosphere	2007	VLDB	8.9402142e-05
3,485	CSV: Visualizing and Mining Cohesive Subgraphs	2008	SIGMOD	7.0470365e-05
8,552	What's on the Grapevine ?	2009	SIGMOD	4.4893996e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
734	Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis	2013	VLDB	0.00017419528
10,134	A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs	2026	SIGMOD	4.1905499e-05
3,323	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	7.2170169e-05
10,500	Integral Densest Subgraph Search on Directed Graphs	2025	SIGMOD	4.1905499e-05
645	Densest Subgraph in Streaming and MapReduce	2012	VLDB	0.00018727714
4,341	Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs	2020	SIGMOD	6.268429e-05
10,062	Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings	2026	SIGMOD	4.1905499e-05
10,072	Efficient and Scalable Directed Densest Subgraph Discovery	2026	SIGMOD	4.1905499e-05
4,092	On Dense Pattern Mining in Graph Streams [Extended Abstract]	2010	VLDB	6.4525563e-05
7,305	Real Time Discovery of Dense Clusters in Highly Dynamic Graphs: Identifying Real World Events in Highly Dynamic Environments	2012	VLDB	4.7627067e-05