计算机科学 ›› 2021, Vol. 48 ›› Issue (10): 152-159.doi: 10.11896/jsjkx.201100005
穆聪聪, 王一舒, 袁野, 乔百友, 马玉亮
MU Cong-cong, WANG Yi-shu, YUAN Ye, QIAO Bai-you, MA Yu-liang
摘要: 稠密子图的查询是图分析领域的重要研究问题之一,在社交用户相关性分析、Web中社群分析等方面都有着广泛的应用。目前,关于稠密子图查询的研究工作主要基于静态图。而在实际应用中,时序信息会对稠密子图查询产生重要的影响,使得图拓扑结构随时间序列不断发生变化,包含的信息量也不断增加,使得已有的针对静态图的查找方法不再适用于时序图。因此,如何高效地在时序图上查找稠密子图仍然是一个挑战。为了解决上述挑战,首先规范化地定义了基于时序图的稠密子图查找问题;然后,根据图的拓扑结构和包含时间标签的边之间的相似度,提出一种基于阈值的近似查找算法DTS-base。为了加快算法的收敛速度,提出了一个基于快速计算最大相似度时间片的优化算法DTS-opt。最后,通过在真实数据集上的实验,证明了所提算法的高效性和可扩展性。
中图分类号:
[1]FRATKIN E,NAUGHTON B T,BRUTLAG D L,et al.Motifcut:regulatory motifs finding with maximum density subgraphs[J].Bioinformatics,2006,22(14):150-157. [2]RAVI K,PRABHAKAR R,SRIDHAR R,et al.Trawling the web for emerging cyber-communities[J].Computer Networks,1999,31(11-16):1481-1493. [3]SOZIO M,GIONIS A.The community-search problem and how to plan a successful cocktail party [C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining (KDD).Washington,DC,USA,2010:939-948. [4]CHENG J,KE Y,CHU S,et al.Efficient core decomposition in massive networks[C]//Proceedings of the 27th International Conference on Data Engineering.Hannover,Germany,2011:51-62. [5]UNO T.An efficient algorithm for solving pseudo clique enu-meration problem[J].Algorithmica,2010,56(1):3-16. [6]CHENG J,KE Y,FU W C,et al.Finding maximal cliques in massive networks by h*-graph [C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data.Indianapolis,Indiana,USA,2010:447-458. [7]TSOURAKAKIS C.The k-clique densest subgraph problem[C]//Proceedings of the 24th International Conference on World Wide Web.Florence,Italy,2015:1122-1132. [8]ABELLO J,RESENDE M G C,SUDARSKY S.Massive quasi-clique detection [C]//Theoretical Informatics,5th Latin American Symposium.Cancun,Mexico,2002:598-612. [9]MITZENMACHER M,PACHOCKI J,PENG R,et al.Scalable large near-clique detection in large-scale networks via sampling [C]//Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Sydney,NSW,Australia,2015:815-824. [10]LI R H,QIN L,YU J X,et al.Influential community search in large networks[J].Proceedings of the VLDB Endowment,2015,8(5):509-520. [11]MA S,HU R J,WANG L,et al.Fast Computation of Dense Temporal Subgraphs [C]//Proceeding of the 33rd IEEE International Conference on Data Engineering.San Diego,CA,USA,2017:361-372. [12]YANG Y,YAN D,WU H H,et al.Diversified Temporal Subgraph Pattern Mining [C]//Proceeding of the 22nd ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining.New York,USA,2016:1965-1974. [13]TSOURAKAKIS C,BONCHI F,GIONIS A,et al.Denser than the densest subgraph:extracting optimal quasi-cliques with qua-lity guarantees [C]//Proceeding of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Chicago,IL,USA,2013:104-112. [14]GOLDBERG A V.Finding a maximum density subgraph[D].Berkeley:University of California,1984. [15]CHARIKAR M.Greedy approximation algorithms for findingdense components in a Graph[C]//Proceeding of the Approximation Algorithms for Combinatorial Optimization,Third International Workshop.Saarbrücken,Germany,2000:84-95. [16]YANG Y J,GAO H,LI J Z.Survey on querying and mining algorithms on dynamic graphs[J].Intelligent Computer and Application,2013,3(4):24-27. [17]SARMA A D,LALL A,NANONGKAI D,et al.Dense sub-graphs on dynamic networks [C]//Proceeding of the Distributed Computing-26th International Symposium.Salvador,Brazil,2012:151-165. [18]ANGEL A,KOUDAS N,SARKAS N,et al.Dense subgraphmaintenance under streaming edge weight updates for real-time story identification[J].The VLDB Journal,2014,23(2):175-199. [19]VALARI E,KONTAKI M,PAPADOPOULOS A N.Discoveryof top-k dense subgraphs in dynamic graph collections [C]//Proceeding of the Scientific and Statistical Database Management-24th International Conference.Chania,Crete,Greece,2012:213-230. [20]WU H,HUANG Y,CHENG J,et al.Efficient processing ofreachability and time-based path queries in a temporal graph [C]//Proceedings of the 32nd International Conference on Data Engineering.Helsinki,Finland,2016:145-156. [21]SEMERTZIDIS K,PITOURA E,TERZI E,et al.Finding la-sting dense subgraphs[J].Data Mining and Knowledge Disco-very,2019,33(5):1417-1445. [22]LI Y,LIU J S,ZHAO H Q,et al.Research on Sustained Cohesive Subgraph Search Algorithm in Large Temporal Graphs[J].Computer Engineering and Applications,2021,4:1-11. |
[1] | 王金明,王远方. 基于Twitter Storm平台并行挖掘最稠密子图 Parallel Mining of Densest Subgraph Based on Twitter Storm 计算机科学, 2014, 41(1): 274-278. |
|