Size-Constrained Community Search on Large Networks: An Effective and Efficient Solution
Fan Zhang, Haicheng Guo, Dian Ouyang, Shiyu Yang, Xuemin Lin, Zhihong Tian
Abstract
As a fundamental graph problem, community search is applied in various areas, e.g., social networks, the world wide web, and biology. A common requirement from real applications is to return a community with a bounded size while most existing solutions do not constrain community size. Recent studies on size-constrained community search still have some critical issues, e.g., the existence of a better cohesiveness objective, some queries returning empty results, and inefficiency on partial queries. Thus, in this paper, we study the size-constrained truss community search (STCS). Given a graph <inline-formula><tex-math notation="LaTeX">$G$</tex-math></inline-formula> , a query vertex <inline-formula><tex-math notation="LaTeX">$q$</tex-math></inline-formula> , and size constraint <inline-formula><tex-math notation="LaTeX">$[l,h]$</tex-math></inline-formula> , the STCS problem aims to find a subgraph containing <inline-formula><tex-math notation="LaTeX">$q$</tex-math></inline-formula> with the largest min-support among all connected subgraphs having at least <inline-formula><tex-math notation="LaTeX">$l$</tex-math></inline-formula> and at most <inline-formula><tex-math notation="LaTeX">$h$</tex-math></inline-formula> 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 algorithm is introduced to find the exact result, with novel optimizations, e.g., budget-cost-based bounding and branching strategies. 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.