This is the authors' abstract. We don't add key points for this paper.
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 graphG, a query vertexq, and size constraint$[l,h]$, the STCS problem aims to find a subgraph containingqwith the largest min-support among all connected subgraphs having at leastland at mosthvertices. 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.
Answers are grounded in this paper and cite their sources.
No takes yet. Share an insight, caveat, or question.
Zhang et al. (2023) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: