Efficient Triangle-Connected Truss Community Search In Dynamic Graphs

Download PDF

Abstract

Community search studies the retrieval of certain community structures containing query vertices, which has received lots of attention recently. 𝑘-truss is a fundamental community structure where each edge is contained in at least 𝑘 − 2 triangles. Triangle-connected 𝑘-truss community (𝑘-TTC) is a widely-used variant of 𝑘-truss, which is a maximal 𝑘-truss where edges can reach each other via a series of edge-adjacent triangles. Although existing works have provided indexes and query algorithms for 𝑘-TTC search, the cohesiveness of a 𝑘-TTC (diameter upper bound) has not been theoretically analyzed and the triangle connectivity has not been efficiently captured. Thus, we revisit the 𝑘-TTC search problem in dynamic graphs, aiming to achieve a deeper understanding of 𝑘-TTC. First, we prove that the diameter of a 𝑘-TTC with 𝑛 vertices is bounded by ⌊ 2𝑛 ⌋. 𝑘+1 Then, we encapsulate triangle connectivity with two novel concepts, partial class and truss-precedence, based on which we build our compact index, EquiTree, to support the efficient 𝑘-TTC search. We also provide efficient index construction and maintenance algorithms for the dynamic change of graphs. Compared with the state-of-the-art methods, our extensive experiments show that EquiTree can boost search efficiency up to two orders of magnitude at a small cost of index construction and maintenance.