Truss-based Why-not Community Search

In this paper, we investigate a new problem of truss-based why-not community search. Given a k-truss community C in a graph G and a why-not vertex w ∉ C, the goal is to insert the minimum number of new edges into G to ensure that w becomes part of the k-truss community. This problem has a wide range of applications, such as friends recommendation and transportation planning. We prove that the truss-based why-not community search problem is NP-hard and propose two efficient heuristic algorithms: the expansion-based algorithm and the simulation-based algorithm. Specifically, the expansion-based algorithm incrementally inserts the edges one by one, guided by a carefully designed edge goodness function that quantifies edge quality to ensure optimal selection. In contrast, the simulation-based algorithm firstly inserts a sufficient number of edges into G to immediately include w in a k-truss community and then removes redundant edges to minimize insertions. Furthermore, we implement a set of optimizations to further enhance the efficiency of both algorithms. Extensive experiments on real-world graphs demonstrate the efficiency and effectiveness of our proposed methods and optimizations.