|Table of Contents|

[1] HAN Tao, TIAN Yuxi, ZHAO Jianwei, WANG Senzhang, et al. Research on heuristic approximation algorithm of the densest k-subgraph discovery in large-scale dynamic graphs [J]. Journal of Southeast University (English Edition), 2026, 42 (1): 74-79. [doi:10.3969/j.issn.1003-7985.2026.01.007]
Copy

Research on heuristic approximation algorithm of the densest k-subgraph discovery in large-scale dynamic graphs()
大规模动态图的k-最密集子图启发式近似发现算法研究

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:
42
Issue:
2026 1
Page:
74-79
Research Field:
Computer Science and Engineering
Publishing date:
2026-03-20

Info

Title:
Research on heuristic approximation algorithm of the densest k-subgraph discovery in large-scale dynamic graphs
大规模动态图的k-最密集子图启发式近似发现算法研究
Author(s):
HAN Tao1, TIAN Yuxi1, ZHAO Jianwei1, WANG Senzhang2
1.National Center for Public Credit and Geospatial Information, Beijing 100059, China
2.School of Computer Science and Engineering, Central South University, Changsha 410083, China
韩涛1, 田玉玺1, 赵建伟1, 王森章2
1.国家公共信用和地理空间信息中心, 北京 100059
2.中南大学计算机学院, 长沙 410083
Keywords:
the densest k-subgraph;  features;  heuristic approximation algorithm;  optimal density
k-最密集子图;  密集特征;  启发式近似算法;  最优密度
PACS:
TP311
DOI:
10.3969/j.issn.1003-7985.2026.01.007
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.
为了解决静态最密集子图挖掘算法处理大规模动态图效率较低问题,本文提出了一个启发式近似算法。该算法通过切分大规模动态图、构建部分k-最密集子图集、启发式合并子图集、挖掘k-最密集子图4个步骤近似计算整体图的k-最密集子图,大大减少大规模动态图的计算时间,同时提升结果子图质量。此算法适用于多种“密度”定义和不同边数要求,与现有静态最密集子图检测算法相结合实现算法的可扩展性和计算高效性。理论分析证明该算法提取的k-最密集子图的最优密度达到0.9。为了评估所提算法的性能,在4个十亿节点的数据集Friendster、Orkut、YouTube、DBLP上进行实验,结果表明所提算法在大规模和动态图上的运行时间、子图质量均优于静态方法。

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]SARMA A DAS, 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.

Memo

Memo:
Received: 2025-04-17; Revised: 2025-10-14.
Biography: HAN Tao (1984—), female, doctor, senior engineer, hantao@creditchina.gov.cn.
Foundation item: The National Natural Science Foundation of China (No.62172443).
Citation: HAN Tao, TIAN Yuxi, ZHAO Jianwei, et al. Research on heuristic approximation algorithm of the densest k-subgraph discovery in large-scale dynamic graphs[J]. Journal of Southeast University (English Edition), 2026, 42(1): 74-79. DOI: 10. 3969/j. issn. 1003-7985. 2026. 01. 007.
Last Update: 2026-03-20