Efficient Community Search Based on Relaxed k-Truss Index

Communities are prevalent in large graphs such as social networks, protein networks, etc. Community search aims to find a cohesive subgraph that contains the query nodes. Existing community search algorithms often adopt community models to find target communities, and k-truss model is a popularly used one that provides structural constraints. However, the structural constraints presented by k-truss is so tight that the searching algorithm often can not find the target communities. There always exist some subgraphs that may not conform to k-truss structure but do have cohesive characteristics to meet users' personalized requirements. Moreover, the k-truss based community search algorithms can not meet users' real-time demands on large graphs. To address the above problems, this paper proposes the relaxed k-truss community search problem for the first time. Then we construct a relaxed k-truss index, which can help to find cohesive communities in linear time and provide flexible searching for nested communities. We also design an index maintenance algorithm to dynamically update the index. Furthermore, a community search algorithm based on the relaxed k-truss index is presented. Extensive experimental results on real datasets prove the effectiveness and efficiency of our model and algorithms.