# Community Search under Member-Specific Tolerances

DevFeed: [Community Search under Member-Specific Tolerances](<https://devfeed.tech/articles/community-search-under-member-specific-tolerances-118119.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.05951>)

Author: Yanghao Liu, Fangda Guo, Yuxuan Zhang, Xueqi Cheng

Published: 2026-11-05T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Databases](<https://devfeed.tech/sources/arxiv-databases.md>)

Topics: [graph theory](<https://devfeed.tech/topics/graph-theory.md>), [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [Distributed Systems & Parallel Computing](<https://devfeed.tech/topics/distributed-systems-parallel-computing.md>)

Tags: [acceptance](<https://devfeed.tech/tags/acceptance.md>), [algorithm](<https://devfeed.tech/tags/algorithm.md>), [approximation](<https://devfeed.tech/tags/approximation.md>), [communities](<https://devfeed.tech/tags/communities.md>), [community](<https://devfeed.tech/tags/community.md>), [confidence](<https://devfeed.tech/tags/confidence.md>), [core](<https://devfeed.tech/tags/core.md>), [cs-cc](<https://devfeed.tech/tags/cs-cc.md>), [cs-db](<https://devfeed.tech/tags/cs-db.md>), [cs-si](<https://devfeed.tech/tags/cs-si.md>), [diameter](<https://devfeed.tech/tags/diameter.md>), [dimension](<https://devfeed.tech/tags/dimension.md>), [efficiency](<https://devfeed.tech/tags/efficiency.md>), [graphs](<https://devfeed.tech/tags/graphs.md>), [groups](<https://devfeed.tech/tags/groups.md>), [homes](<https://devfeed.tech/tags/homes.md>), [influence](<https://devfeed.tech/tags/influence.md>), [location](<https://devfeed.tech/tags/location.md>), [location-based](<https://devfeed.tech/tags/location-based.md>), [networks](<https://devfeed.tech/tags/networks.md>), [np](<https://devfeed.tech/tags/np.md>), [np-hard](<https://devfeed.tech/tags/np-hard.md>), [search](<https://devfeed.tech/tags/search.md>)

## AI overview

A latitude-consistent community (LCC) is a connected group containing a query vertex, with minimum degree at least k and diameter no greater than the smallest tolerance among its members. In a closed group, this bound exactly characterizes persistent acceptance of all interactions under bounded-confidence dynamics with arbitrary positive weights, and prevents rejection under social-judgment dynamics; natural relaxations guarantee neither. Finding a maximum LCC is NP-hard even in the plane, while existence is NP-complete for fixed k >= 2 in unbounded dimension. LatSweep uses a sweep over the smallest tolerance to produce two feasible heuristics, a (1,2)-bicriteria approximation and an exact branch-and-bound solver. Across eight graphs, the solver proved optimality on all but 9 of 3,700 efficiency queries and outperformed the listed comparison methods in queries proved. The reported applications also find that outside ties can invalidate the guarantee, and tolerance-agnostic groups in two location networks often exceed members' estimated travel radii; enforcing tolerances showed no detected co-visit loss against same-size spatial communities.

## Source excerpt

arXiv:2611.05951v1 Announce Type: cross Abstract: We study community search when each vertex has its own tolerance for differences in position. For positions such as opinions or homes, a latitude-consistent community (LCC) contains the query vertex, is connected, has minimum degree at least k, and bounds its diameter by the smallest member tolerance. Motivated by social judgment theory, the bound exactly characterizes persistent acceptance of every interaction in a closed group under bounded-confidence dynamics with arbitrary positive weights. It also prevents rejection under social-judgment dynamics, whereas natural relaxations preserve neither guarantee. Finding a maximum LCC is NP-hard even in the plane, and with unbounded dimension, deciding whether an LCC exists is NP-complete for every fixed k >= 2. LatSweep turns the coupled bound into a sweep over the smallest tolerance, yielding two feasible heuristics, a (1,2)-bicriteria approximation and an exact branch-and-bound algorithm. Across eight graphs with up to 1.8 billion edges, the exact algorithm proves optimality on all but 9 of 3,700 efficiency queries and usually certifies absence within microseconds when no LCC exists. Its branch-and-bound solver proves more queries than a reimplemented maximum-(k,r)-core algorithm, a mixed-integer program and CP-SAT. In simulations, uneven influence disrupts initially accepted interactions in pairwise groups. Outside ties invalidate the guarantee for many real groups. On two location-based networks, tolerance-agnostic groups often place another member's home beyond a member's estimated travel radius; comparisons with spatial communities of the same size detect no co-visit loss from enforcing every member's tolerance.