Computer Science ›› 2026, Vol. 53 ›› Issue (6): 320-331.doi: 10.11896/jsjkx.250400076

• Database & Big Data & Data Science • Previous Articles     Next Articles

Top-k Core-based Edge Structural Diversity Search in Temporal Graphs

ZHAN Chenting, ZHOU Junfeng, DU Ming   

  1. School of Computer Science and Technology,Donghua University,Shanghai 201620,China
  • Received:2025-04-15 Revised:2025-06-22 Online:2026-06-15 Published:2026-06-09
  • About author:ZHAN Chenting,born in 2000,postgraduate,is a member of CCF(No.Z3419G).Her main research interest is query processing techniques on large-scale graph data.
    ZHOU Junfeng,born in 1977,Ph.D,professor,Ph.D supervisor,is a member of CCF(No.16083M).His main research interests include information retrieval technology,semi structured data,query processing and optimization of graphic data.
  • Supported by:
    National Natural Science Foundation of China(62372101).

Abstract: Temporal graphs provide an effective framework for modeling time-varying interactions in dynamic networks,yet computing edge structural diversity efficiently remains a significant challenge.This study investigates the top-k edge core-based structural diversity search problem on temporal graphs and develops a multi-level optimization strategy.Previous methods lack core structure awareness and require full-graph traversal,leading to inefficiency.To address this,a t-core-based edge diversity metric is defined,which quantifies structural diversity by counting the number of t-core connected components in each edge ego-network.Two upper-bound pruning algorithms are designed:LUBP uses node degree distribution to estimate a loose upper bound for rapid candidate selection,while SUBP applies coreness information to build a tighter bound that further reduced the search space.Furthermore,the t-SUBP algorithm is proposed to restrict computation to high-coreness subgraphs(e.g.,(t+2)-core),avoiding unnecessary processing in low-coreness areas.Experiments on seven real-world datasets show that the proposed algorithms achieves up to an 8-fold improvement in efficiency compared to baseline methods,while maintaining good scalability with increasing graph size.

Key words: Temporal graphs, t-core, Edge structural diversity, Pruning optimization, Top-k queries

CLC Number: 

  • TP311
[1]HOLME P.Modern temporal network theory:A colloquium[J].European Physical Journal B,2015,88(9):1-30.
[2]LIU P,BENSON A,CHARIKAR M.Sampling methods forcounting temporal motifs [C]//Proceedings of the 12th ACM International Conference on Web Search and Data Mining(WSDM).ACM,2019:294-302.
[3]LI Y,ZOU L,ÖZSU M T,et al.Time constrained continuoussubgraph search over streaming graphs [C]//Proceedings of the 35th IEEE International Conference on Data Engineering(ICDE).IEEE,2019:1082-1093.
[4]WU H,CHENG J,HUANG S,et al.Path problems in temporal graphs [J].Proceedings of the VLDB Endowment,2014,7(9):721-732.
[5]YUAN Y,LIAN X,WANG G,et al.Constrained shortest path query in a large time-dependent graph [J].Proceedings of the VLDB Endowment,2019,12(10):1058-1070.
[6]TANG J,MUSOLESI M,MASCOLO C,et al.Temporal dis-tance metrics for social network analysis [C]//Proceedings of the 2nd ACM Workshop on Online Social Networks.ACM,2009:31-36.
[7]DALY E M,HAAHR M.Social network analysis for routing in disconnected delay-tolerant MANETs [C]//Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing(MobiHoc).ACM,2007:32-40.
[8]HOLME P,SARAMÄKI J.Temporal networks [J].PhysicsReports,2012,519(3):97-125.
[9]UGANDER J,BACKSTROM L,MARLOW C,et al.Structural diversity in social contagion [J].Proceedings of the National Academy of Sciences,2012,109(16):5962-5966.
[10]FANG Z,ZHOU X,TANG J,et al.Modeling paying behavior in game social networks [C]//Proceedings of the 23rd ACM International Conference on Information and Knowledge Management(CIKM).ACM,2014:411-420.
[11]MA H.On measuring social friend interest similarities in recommender systems [C]//Proceedings of the 37th ACM SIGIR International Conference on Research and Development in Information Retrieval(SIGIR).ACM,2014:465-474.
[12]HUANG X,CHENG H,LI R H,et al.Top-k structural diversity search in large networks [J].Proceedings of the VLDB Endowment,2013,6(13):1618-1629.
[13]CHANG L,ZHANG C,LIN X,et al.Scalable top-k structural diversity search [C]//Proceedings of the 33rd IEEE International Conference on Data Engineering(ICDE).IEEE,2017:95-98.
[14]DONG Y,JOHNSON R A,XU J,et al.Structural diversity and homophily:A study across more than one hundred big networks [C]//Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD).ACM,2017:807-816.
[15]ZHANG Q,LI R H,YANG Q,et al.Efficient top-k edge structural diversity search [C]//Proceedings of the 36th IEEE International Conference on Data Engineering(ICDE).IEEE,2020:205-216.
[16]FEI R,WAN Y,HU B,et al.Deep core node information embedding on networks with missing edges for community detection [J].Information Sciences,2025,707:122039.
[17]CHOUMANE A,AWADA A,HARKOUS A.Core expansion:A new community detection algorithm based on neighborhood overlap [J].Social Network Analysis and Mining,2020,10(1):1-15.
[18]MALVESTIO I,CARDILLO A,MASUDA N.Interplay be-tween k-core and community structure in complex networks [J].Scientific Reports,2020,10:14702.
[19]FEI R,WAN Y,HU B,et al.A novel network core structure extraction algorithm utilized variational autoencoder for community detection [J].Expert Systems with Applications,2023,222:119775.
[20]WU Y,ZHAO J,SUN R,et al.Efficient personalized influential community search in large networks [J].Data Science and Engineering,2021,6(2):153-167.
[21]ZHANG W,SHANG R,JIAO L.Large-scale community detection based on core node and layer-by-layer label propagation [J].Information Sciences,2023,621:1-18.
[22]YANG J,ZHONG M,ZHU Y,et al.Scalable time-range k-core query on temporal graphs [J].Proceedings of the VLDB Endowment,2023,16(5):1163-1175.
[23]LIU Y,YAN B,ZHAO B,et al.Efficient size-prescribed k-core search [C]//Proceedings of the 2023 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mi-ning(ASONAM).ACM,2024:271-275.
[24]TIAN A,ZHOU A,WANG Y,et al.Efficient index for temporal core queries over bipartite graphs [J].Proceedings of the VLDB Endowment,2024,17(11):2813-2825.
[25]ZHANG Y,YU J X,ZHANG Y,et al.Maintaining top-t cores in dynamic graphs [J].IEEE Transactions on Knowledge and Data Engineering,2024,36(9):4766-4780.
[26]AKOGLU L,TONG H,KOUTRA D.Graph-based anomaly de-tection and description:A survey [J].Data Mining and Know-ledge Discovery,2015,29(3):626-688.
[27]SAFDARI H,DE BACCO C.Community detection and anomaly prediction in dynamic networks [J].Communications Physics,2024,7:397.
[28]LIU Y,PAN S,WANG Y G,et al.Anomaly detection in dyna-mic graphs via transformer [J].IEEE Transactions on Know-ledge and Data Engineering,2023,35(12):12081-12094.
[29]MORONE F,MAKSE H A.Influence maximization in complex networks through optimal percolation [J].Nature,2015,524(7563):65-68.
[30]LIQING Q,JINFENG Y,WEI J,et al.A k-shell decomposition based heuristic algorithm for influence maximization in social networks [C]//Proceedings of the 10th International Confe-rence on Genetic and Evolutionary Computing.Springer,2019:711-722.
[31]WU H,CHENG J,HUANG S,et al.Core decomposition in large temporal graphs [C]//Proceedings of 2015 IEEE International Conference on Big Data.IEEE,2015:649-658.
[32]GALIMBERTI E,BARRAT A,BONCHI F,et al.Span-core decomposition for temporal networks:algorithms and applications [J].ACM Transactions on Knowledge Discovery from Data,2020,14(4):41.
[33]PARANJAPE A,BENSON A R,LESKOVEC J.Motifs in tem-poral networks [C]//Proceedings of the Tenth ACM International Conference on Web Search and Data Mining.ACM,2017:601-610.
[34]CHEN X,WANG K,LIN X,et al.Efficiently answering reachability and path queries on temporal bipartite graphs [J].Proceedings of the VLDB Endowment,2021,14(10):1845-1858.
[1] LI Gui,CHEN Sheng-hong,LI Zheng-yu,HAN Zi-yang and SUN Ping. Recommendation Algorithm with User Temporal Preference Fusion [J]. Computer Science, 2014, 41(Z6): 394-399.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!