Distributed Truss Computation in Dynamic Graphs

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\mathrm{-}\mathrm{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.