KDCS: Achieving Efficient and Privacy-Preserving (k,d-Truss Community Search for Social Networks

Community search is essential in social network analysis, with the (k,d)-truss model offering a robust framework to identify densely connected subgraphs that contain a query vertex and meet both k-truss and distance constraints. Despite the increasing reliance on cloud servers for processing large social network graph data, privacy concerns remain unaddressed. To fill this gap, we propose a novel privacy-preserving (k,d)-truss community search (KDCS) scheme based on weighted community graphs. Specifically, to enhance search efficiency, we introduce a k-truss-G (KTG) tree to index communities for efficient queries. Firstly, we develop a boundary vertex encoding mechanism for the social distance matrix. Then, we design a KTG tree construction algorithm and a (k,d)-truss community search algorithm based on the concept of segmentation and assembly. To ensure data security, we propose a secure community distance calculation (SCDC) algorithm, which utilizes mutually orthogonal matrices to preserve the privacy of the social distance matrix while accurately calculating the social distance. Furthermore, improved symmetric homomorphic encryption (iSHE) and matrix encryption are utilized to safeguard both dataset privacy and query privacy effectively. In addition, rigorous security analysis demonstrates that the proposed KDCS scheme is indeed privacy-preserving. Finally, extensive comparative experiments with real social network datasets show that KDCS exhibits outstanding performance at every stage, underscoring its practical significance.