| As a fundamental graph problem,community search is applied in various areas,e.g.,social networks,the world wide web,and biology.Community search aims to find a subgraph that has a given query vertex and dense internal structure.Considering limit budget and volume,a common requirement from real applications is to return a community with bounded size while most existing solutions do not constrain community size.Recent studies on size-constrained community search still face some critical issues,e.g.,the existence of better cohesiveness objective,some queries return empty results and inefficiency on partial queries.Thus,in this paper,we study the size-constrained truss community search(STCS).Given a graph G,a query vertex q,and size constraint [l,h],the STCS problem aims to find a subgraph containing q with the largest min-trussness among all connected subgraphs having at least l and at most h vertices.We prove the STCS problem is NP-hard and APX-hard unless P=NP.An effective heuristic is proposed to quickly find a high-quality initial result.Then,a branch-and-bound exact algorithm is introduced to find the exact result,with novel optimization techniques,e.g.,budget-cost based bounding and branching strategies.Integrating the heuristic and branch-and-bound algorithms,we further design a time-depending algorithm,which can find the optimal result with a good trade-off between time and quality.Extensive experiments verify that the community quality returned by our algorithm is better and our algorithm is faster by up to 5 orders of magnitude,compared with the state-of-the-art. |
