Distributed Truss Computation in Dynamic Graphs  

作　　者：Ziwei Mo Qi Luo Dongxiao Yu Hao Sheng Jiguo Yu Xiuzhen Cheng 

机构地区：[1]School of Computer Science and Technology,Shandong University,Qingdao 266200,China [2]State Key Laboratory of Software Development Environment,School of Computer Science and Engineering and the Beijing Advanced Innovation Center for Big Data and Brain Computing,Beihang University,Beijing 100191,China [3]Big Data Institute,Qilu University of Technology(Shandong Academy of Sciences),Jinan 250353,China

出　　处：《Tsinghua Science and Technology》2023年第5期873-887,共15页清华大学学报（自然科学版（英文版）

基　　金：supported in part by the National Key Research and Development Program of China(No.2020YFB1005900);in part by National Natural Science Foundation of China(No.62122042);in part by Shandong University Multidisciplinary Research and Innovation Team of Young Scholars(No.2020QNQT017)。

摘　　要：Large-scale graphs usually exhibit global sparsity with local cohesiveness,and mining the representative cohesive subgraphs is a fundamental problem in graph analysis.The k-truss is one of the most commonly studied cohesive subgraphs,in which each edge is formed in at least k 2 triangles.A critical issue in mining a k-truss lies in the computation of the trussness of each edge,which is the maximum value of k that an edge can be in a k-truss.Existing works mostly focus on truss computation in static graphs by sequential models.However,the graphs are constantly changing dynamically in the real world.We study distributed truss computation in dynamic graphs in this paper.In particular,we compute the trussness of edges based on the local nature of the k-truss in a synchronized node-centric distributed model.Iteratively decomposing the trussness of edges by relying only on local topological information is possible with the proposed distributed decomposition algorithm.Moreover,the distributed maintenance algorithm only needs to update a small amount of dynamic information to complete the computation.Extensive experiments have been conducted to show the scalability and efficiency of the proposed algorithm.

关 键 词：distributed algorithm dynamic graph graph mining cohesive subgraph k-truss 

分 类 号：O15[理学—数学]