Efficient Size-Constrained Community Search over Directed Graphs
摘要
Community search over directed graphs is a fundamental graph problem, with applications in various areas such as social network analysis, financial fraud detection, and biology. A common requirement in real applications is to return a community with a constrained size. However, most existing studies primarily focus on the cohesiveness of the community and ignore the constraint on community size. Therefore, this paper investigates the problem of searching \((k_c,k_f)\) -truss community with a size constraint over directed graphs (denoted by SCTC), which aims to find a subgraph that satisfies \(csup \ge k_c\) and \(fsup \ge k_f\) among all connected subgraphs that contain the query vertex q and have at least l and at most h vertices, where q, l, h, \(k_c\) , and \(k_f\) are specified by the query. We develop an exact solution for SCTC search by exploiting the properties of \((k_c,k_f)\) -truss subgraphs. The approach first identifies the maximal \((k_c,k_f)\) -truss subgraph to narrow the search space, and then performs a refinement search within it to efficiently support the SCTC search. We investigate two search strategies, expansion and peeling. The expansion strategy guides the search order using a score function and optimizes the search strategy based on clique, while the peeling strategy designs a level-based mechanism to remove low-support edges one level at a time iteratively. Extensive experimental results on real-world datasets show that our proposed algorithm improves both the quality of the resulting community and the search efficiency.