大规模动态图的k-最密集子图启发式近似发现算法研究OA

To address the issue that static densest subgraph mining algorithms often exhibit low efficiency when han-dling large scale dynamic graphs,this paper proposes a heu-ristic approximation algorithm.The algorithm approximates the densest k-subgraphs of the entire graph through four steps:partitioning the large-scale dynamic graph,construct-ing a partial set of the densest k-subgraphs,heuristically merging the subgraph sets,and finally extracting the dens-est k-subgraphs.This approach significantly reduces the computational time for large-scale dynamic graphs while si-multaneously improving the quality of the resulting sub-graphs.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 scalabil-ity and computational efficiency.Theoretical analysis dem-onstrates that the optimal density of the densest k-subgraphs extracted by the proposed algorithm reaches 0.9.To evalu-ate the performance of the algorithm,experiments were con-ducted on four billion-scale datasets:Friendster,Orkut,YouTube,and DBLP.The results indicate that the pro-posed algorithm outperforms static methods in both runtime efficiency and subgraph quality on large-scale dynamic graphs.