Effective Structurally Similar Community Search in Large Temporal Graphs

A temporal graph is an undirected graph where each edge is associated with a timestamp representing the interaction time. As a fundamental problem in graph analysis, community search (CS) in temporal graphs has received tremendous research attention. Existing CS works on temporal graphs typically focus on identifying cohesive subgraphs (e.g., k -cores) within a specific time window. However, they overlook the specific roles of vertices (e.g., core, hub) and fail to capture their dynamic evolution over time. In this paper, we introduce a novel community model, called temporal structurally similar community (TSC), which models the communities in temporal graphs by explicitly considering the evolution of vertex roles across different time windows. Based on the TSC, we develop fast online and index-based algorithms that support efficient TSC queries over arbitrary time windows. Extensive experiments on real-world datasets demonstrate the effectiveness of the TSC model in revealing meaningful communities and the high efficiency of our proposed algorithms.