Research on heuristic approximation algorithm of the densest k-subgraph discovery in large-scale dynamic graphs

Abstract

To address the issue that static densest subgraph mining algorithms often exhibit low efficiency when handling large scale dynamic graphs, this paper proposes a heuristic approximation algorithm. The algorithm approximates the densest k-subgraphs of the entire graph through four steps: partitioning the large-scale dynamic graph, constructing a partial set of the densest k-subgraphs, heuristically merging the subgraph sets, and finally extracting the densest k-subgraphs. This approach significantly reduces the computational time for large-scale dynamic graphs while simultaneously improving the quality of the resulting subgraphs. This algorithm is applicable to various definitions of “density” and can accommodate diverse requirements on the number of edges. When integrated with existing static densest subgraph detection algorithms, it achieves scalability and computational efficiency. Theoretical analysis demonstrates that the optimal density of the densest k-subgraphs extracted by the proposed algorithm reaches 0.9. To evaluate the performance of the algorithm, experiments were conducted on four billion-scale datasets: Friendster, Orkut, YouTube, and DBLP. The results indicate that the proposed algorithm outperforms static methods in both runtime efficiency and subgraph quality on large-scale dynamic graphs.

Keywords

the densest k-subgraph / features / heuristic approximation algorithm / optimal density

References

[1] Bao Q, Wu Z, Chen J M, et al. Comprehensive assessment of traffic operation risk based on vehicle trajectory prediction and macro-micro indicator aggregation for road segments approaching intersections[J]. Journal of Southeast University (Natural Science Edition), 2025, 55(1): 230-238. (in Chinese)

[2] LU H X, XU H Y, LIU S C, et al. Design of an intelligent online street view big data analysis system: A case study on sky view factor extraction[J]. Journal of Southeast University (Natural Science Edition), 2025, 55(1): 290-296. (in Chinese)

[3] LIU L, JIANG L Y, ZHANG B L. Multi-radar deployment based on improved simulated annealing with optimal neighborhood search[J]. Journal of Southeast University (Natural Science Edition), 2024, 54(5): 1322-1329. (in Chinese)

[4] DAS SARMA A, Deshpande A, Kannan R. Finding dense subgraphs in G(n,1/2)[C]// 7th International Workshop on Approximation and Online Algorithms. Copenhagen, Denmark, 2009, 5893: 98.

[5] FOX J, NGUYEN T, SCOTT A, et al. Induced subgraph density. Ⅱ. Sparse and dense sets in cographs[J]. European Journal of Combinatorics, 2025, 124: 104075.

[6] XU X J, LIU H Y, LÜ X W, et al. An efficient and exact algorithm for locally h-clique densest subgraph discovery[J]. Proceedings of the ACM on Management of Data, 2024, 2(6): 1-26.

[7] HOSSEINZADEH M M. Dense subgraphs in biological networks[C]// 46th International Conference on Current Trends in Theory and Practice of Informatics (SOFSEM). Limassol, Cyprus, 2020, 12011: 711-719.

[8] TU S J, STANKOVIC A, NEUMANN S, et al. Optirefine: Densest subgraphs and maximum cuts with k refinements[J]. Data Mining and Knowledge Discovery, 2025, 39(6): 82.

[9] CALUDE C S, DINNEEN M J, HUA R. Quantum solutions for densest k-subgraph problems[J]. Journal of Membrane Computing, 2020, 2(1): 26-41.

[10] LU Q H, SIDIROPOULOS N D, KONAR A. Densest k-subgraph mining via a provably tight relaxation[J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2025, 39(12): 12291-12299.

[11] KHANNA Y, LOUIS A. Planted models for the densest k-subgraph problem[C]// 40th Conference on Foundations of Software Technology and Theoretical Computer Science-FSTTCS. India, 2020, 182: 27.

[12] BONCHI F, GARCÍA-SORIANO D, MIYAUCHI A, et al. Finding densest k-connected subgraphs[J]. Discrete Applied Mathematics, 2021, 305: 34-47.

[13] Das Sarma A, Deshpande A, Kannan R. Finding dense subgraphs in G(n, 1/2)[C]// Approximation and Online Algorithms. Berlin, Germany: Springer, 2010: 98-103.

[14] CHEN T Y, MIYAUCHI A, TSOURAKAKIS C E. Q-DISCO: Query-centric densest subgraphs in networks with opinion information[C]// Proceedings of the Eighteenth ACM International Conference on Web Search and Data Mining. Hannover, Germany, 2025: 194-203.

[15] LANCIANO T, MIYAUCHI A, FAZZONE A, et al. A survey on the densest subgraph problem and its variants[J]. ACM Computing Surveys, 2024, 56(8): 1-40.

[16] DONDI R, HOSSEINZADEH M M, MAURI G, et al. Top-k overlapping densest subgraphs: Approximation algorithms and computational complexity[J]. Journal of Combinatorial Optimization, 2021, 41(1): 80-104.

[17] DONDI R, HOSSEINZADEH M M, GUZZI P H. A novel algorithm for finding top-k weighted overlapping densest connected subgraphs in dual networks[J]. Applied Network Science, 2021, 6(1): 40.

[18] MEGHERBI W, HADDAD M, SEBA H. DeepDense: Enabling node embedding to dense subgraph mining[J]. Expert Systems with Applications, 2024, 238: 121816.

[19] MA C H, FANG Y X, CHENG R, et al. A convex-programming approach for efficient directed densest subgraph discovery[C]// Proceedings of the 2022 International Conference on Management of Data. Philadelphia, PA, USA, 2022: 845-859.

[20] MA C H, FANG Y X, CHENG R, et al. Efficient directed densest subgraph discovery[J]. Sigmod Record, 2021, 50(1): 33-40.

[21] KOANA T, KOMUSIEWICZ C, SOMMER F. Computing dense and sparse subgraphs of weakly closed graphs[J]. Algorithmica, 2023, 85(7): 2156-2187.

[22] MA C H, FANG Y X, CHENG R, et al. On directed densest subgraph discovery[J]. ACM Transactions on Database Systems, 2021, 46(4): 13.

[23] DONDI R, HERMELIN D. Computing the k densest subgraphs of a graph[J]. Information Processing Letters, 2023, 179: 106316.

[24] XU Y C, MA C H, FANG Y X, et al. Efficient and effective algorithms for densest subgraph discovery and maintenance[J]. The VLDB Journal, 2024, 33(5): 1427-1452.

[25] BASU S, PAUL-PENA D, QIAN K, et al. Covering a graph with dense subgraph families, via triangle-rich sets[C]// Proceedings of the 33rd ACM International Conference on Information and Knowledge Management. Boise, ID, USA, 2024: 109-119.

[26] LESKOVEC J, SOSIC R. SNAP: A general-purpose network analysis and graph-mining library[J]. ACM Transactions on Intelligent Systems and Technology, 2016, 8(1): 1-20.

Funding

National Natural Science Foundation of China(62172443)