betaFeedback

WorksComputer Science

Community Search under Member-Specific Tolerances

Abstract

We study community search when each member has its own tolerance for differences in position, as when members of a group interact repeatedly and influence one another. 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. The bound is exactly the condition under which every interaction in a connected closed group stays accepted under bounded-confidence dynamics for every choice of positive weights. It also prevents rejection under social-judgment dynamics, whereas the pairwise condition and other 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 fixes the answer's smallest tolerance and turns the coupled bound into a best-first sweep over candidate thresholds, yielding an exact branch-and-bound algorithm, a (1,2)-bicriteria approximation and two feasible heuristics. Across eight graphs with up to 1.8 billion edges, six with synthetic positions and tolerances, the exact algorithm proves optimality on all but 9 of 3,700 efficiency queries; in a shared implementation on two large graphs, 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 of closed groups, LCC groups keep every accepted interaction under uneven influence, whereas 3-40% of pairwise-compatible groups lose some. On three location-based networks, tolerance-agnostic groups often place another member's home beyond a member's estimated travel radius. Enforcing every member's tolerance causes no measurable loss of co-visits relative to spatial communities of the same size. Relative to the larger pairwise-compatible groups, it can cause a size-adjusted loss.

Index Terms—Community search, cohesive subgraphs, opinion dynamics, approximation algorithms

Introduction

For a query vertex qq, community search identifies a cohesive subgraph containing qq [1, 2]. When vertices have positions, such as opinions, interest profiles or homes, existing models enforce compactness using a shared threshold [3, 4, 5] or by minimizing spread [6, 7]. However, a shared threshold cannot express how much variation each individual accepts: social judgment theory (SJT) [8] describes a personal latitude of acceptance whose width varies across individuals, just as users of location-based social networks differ in how far they are willing to travel.

We search for latitude-consistent communities (LCCs): connected subgraphs with minimum degree at least kk, containing qq, whose diameter in the position space is bounded by the smallest member tolerance. In deliberative settings such as a platform assembling a discussion panel on a contested topic, members adjust their positions as they influence one another over repeated rounds, so a group selected only for initial pairwise compatibility can lose acceptable exchanges. In Figure 1(a), every pair initially accepts each other, so the group meets the pairwise condition, yet a single round of equal-weight averaging ((1) in Section IV-A) separates uu and vv, whereas bounding the spread by the smallest tolerance preserves acceptance in the LCC of (c). With a common tolerance rr, a largest LCC is a maximum (k,r)(k,r)-core [3] containing qq. Member-specific tolerances complicate the search because adding a less tolerant member tightens the bound for every pair; whether two vertices can coexist depends on the rest of the group, preventing direct pruning under a fixed threshold. We take member tolerances as inputs, as community search takes attributes or query radii, and study what the bound guarantees and how to search under it.

Pairwise acceptance versus the smallest-tolerance bound

Figure 1. Pairwise acceptance versus the smallest-tolerance bound (k=3k = 3; grey uu and vv have tolerance 1, all others 2; in (c), non-members are faded; vertical offsets only aid legibility).

  • Model and guarantees (Sections III and IV-A). If tolerances are the radii of the latitudes of acceptance, every interaction in a closed LCC stays accepted under bounded-confidence dynamics with personal bounds [9, 10] and any positive weights, and the group converges to consensus. If they are the distances beyond which mem-

bers reject, no member of an LCC ever rejects another under SJT dynamics. Conversely, in every connected group that violates the bound, some positive weighting of the averaging makes a member refuse an interaction. Neither a slack of ε\varepsilon, nor exempting two members, nor the pairwise condition d(xu,xv)≤min⁡(θu,θv)d(x_u,x_v) \le\min(\theta_u,\theta_v) preserves the guarantees. For members who also listen to outside friends, we give a sufficient stability condition.

  • Complexity (Section IV-B). Finding a largest LCC is NP-hard even with equal tolerances in the plane and on the sphere. With the dimension as part of the input, it is not approximable within n1−εn^{1-\varepsilon} unless P = NP, and for each fixed k≥2k \ge2, even deciding whether an LCC exists is NP-complete. On a line, the problem is polynomial.

  • Algorithms (§ 5). LatSweep fixes the smallest tolerance τ\tau of the answer so that every member must satisfy d(xv,xq)≤τ≤θvd(x_v,x_q) \le\tau\le\theta_v, turning the coupled constraint into a sweep over survival intervals with a common threshold at each step (Figure 2). The sweep yields BallCore-F and a greedy variant, which return only LCCs; BallCore-R, a polynomial-time (1, 2)-bicriteria approximation whose diameter factor cannot be improved in general metrics unless P = NP; and an exact branch-and-bound algorithm that refines upper bounds best-first and, if stopped early, returns the best LCC found, if any, with a proven bound on the optimum. A query-independent index shrinks the search region of all but BallCore-R.

The LatSweep framework

Figure 2. The LatSweep framework: (a) survival intervals and the candidates S(τ)S(\tau) (dots) at two thresholds; (b) index, query pipeline and the bounds β(τ)\beta(\tau) that the sweep refines.

  • Experiments (§ 6). We ask how far exact search scales, how groups with and without the bound behave under repeated interaction, and what personal tolerances change on real positions. On eight graphs with up to 1.8 billion edges, six with synthetic positions and tolerances, the exact algorithm proves within microseconds that most queries without an LCC have none. It proves optimality on all but 9 of our 3,700 efficiency queries and, on those, returns an LCC of at least 0.689 times a proven upper bound. On two large graphs, with only the subproblem solver exchanged, it proves more queries than a reimplemented maximum-(k,r)(k,r)-core algorithm, a mixed-integer program and CP-SAT. In simulations of closed groups, LCC groups keep every accepted interaction, whereas groups that satisfy only the pairwise condition lose some when influence is uneven. On three location-based datasets, tolerance-agnostic groups often place another member’s home beyond a member’s radius; enforcing every member’s tolerance causes no measurable loss of co-visits relative to spatial communities of the same size, and it can cause a size-adjusted loss relative to the larger pairwise groups.

Our code and processing scripts are available at https://github.com/YangH-L/LACS; compared with the conference version, this report provides full proofs and an appendix of supplementary results.

Community search: Community search identifies a cohesive subgraph containing a query vertex, usually a connected kk-core [1, 11] or kk-truss [12]; a survey is given in [2]. Attributed variants add conditions on attributes. ACQ [13] maximizes the keywords shared by all members; VAC [7] minimizes the largest pairwise attribute distance in a kk-truss, which is NP-hard and admits a 2-approximation; and skyline community search [14] returns the cohesive communities of a bipartite graph that no other community dominates on multi-dimensional edge attributes. (k,r)(k,r)-cores [3] require all pairs of members to be similar within one threshold, and (k,P)(k,\mathcal{P})-cores [15] extend kk-cores to heterogeneous information networks, where significant-attributed community search [16] maximizes the smallest significance of a member and FCS-HGNN [17] learns to return communities that span several vertex types. In density personalized group queries [18], members individually bound their internal degree; in an LCC, group composition sets the distance bound for every pair. Signed-network models take positive and negative edges as observed [19, 20], and Liu et al. [21] cluster cognition-aware embeddings; an LCC keeps an explicit cohesion constraint and derives acceptance from positions and personal tolerances.

Spatial and geo-social groups: Spatial-aware community search (SAC) [6] returns the kk-core containing qq whose minimum covering circle is smallest. Radius-bounded kk-cores [4] must fit in a circle of given radius, and maximum co-located communities [5] keep all pairwise distances within a given threshold. Geo-social group queries [22, 23] select a group, near a rally point or within a query region, in which every member knows a given number of others, and skyline cohesive groups [24] trade social cohesion against the members’ travel cost to a meeting point within everyone’s reach. On road-social networks, cohesive group nearest neighbour queries [25, 26] pair a cohesive group with the meeting point that minimizes its travel distance, under one or several criteria, and multi-attributed community search [27] ranks cohesive groups by attributes with uncertain weights. Rather than imposing a shared spatial radius or objective, LCCs bound group spread by the least tolerant member through a hard metric constraint, analogous to how least-misery group recommendation scores groups by their least satisfied member [28, 29].

Opinion dynamics: Averaging models repeatedly update agents to weighted averages of their neighbours’ opinions [30], possibly with an anchor at their initial opinions [31]. Bounded-confidence models [9, 32] average only opinions within a confidence bound; with heterogeneous bounds, whether consensus arises depends on the bounds and the network [10, 33], and, for scalar opinions, the dynamics converge in finite time if the initial opinions span at most twice the smallest bound [34]. Opinions fixed outside the group act as constant signals, for example from radical groups or charismatic leaders [35]. Models based on SJT add noncommitment and rejection [36]; bounded-confidence models have been fitted to social traces [37], and individual users’ confidence intervals have been measured as the span of their neighbours’ opinions [38]. We use these dynamics as a group-selection criterion: the search returns groups with guarantees about subsequent interactions (Section IV), whereas the cited studies follow an initially given population.

Problem Definition

Member-specific tolerances: Social judgment theory [8] describes how people assess positions against a personal anchor. Nearby positions are assimilated within the latitude of acceptance; distant positions are contrasted within the latitude of rejection, with noncommitment between these regions. Their widths differ across individuals. We give each vertex vv a position xvx_v in a metric space (X,d)(\mathcal{X},d) and two radii 0<θvacc≤θvrej0<\theta_v^{\mathrm{acc}}\leq\theta_v^{\mathrm{rej}}: vertex vv accepts a position yy if d(xv,y)≤θvaccd(x_v,y)\leq\theta_v^{\mathrm{acc}}, rejects it if d(xv,y)>θvrejd(x_v,y)>\theta_v^{\mathrm{rej}}, and is noncommittal otherwise. The same search model applies to geographic positions. In meetups (§ 6), xvx_v is a user’s home and θv\theta_v estimates, from past visits, how far the user is willing to travel. Each member need only reach every other member’s home.

Notation: Let G=(V,E)G=(V,E) be an undirected simple graph with n=∣V∣n=|V|.1 For H⊆VH\subseteq V, G[H]G[H] is the induced subgraph and NH(v)N_H(v) the set of neighbours of vv in G[H]G[H]. Each vertex has a position xv∈Xx_v\in\mathcal{X} and a tolerance θv>0\theta_v>0; we write diam⁡(H)=max⁡u,v∈Hd(xu,xv)\operatorname{diam}(H)=\max_{u,v\in H}d(x_u,x_v) and θmin⁡(H)=min⁡w∈Hθw\theta_{\min}(H)=\min_{w\in H}\theta_w; Table 1 lists the main notation.

SymbolMeaning
G=(V,E),nG=(V,E), nsocial graph, n=∣V∣n=|V|
(X,d)(\mathcal{X},d)metric space of positions
q,kq,kquery vertex, minimum degree
xv,θvx_v,\theta_vposition and tolerance of vv
θvacc≤θvrej\theta_v^{\mathrm{acc}}\leq\theta_v^{\mathrm{rej}}radii of acceptance and of rejection
H,hH,hgroup, h=∣H∣h=|H|
G[H],NH(v)G[H],N_H(v)induced subgraph; neighbours of vv in it
diam⁡(H),θmin⁡(H)\operatorname{diam}(H),\theta_{\min}(H)largest distance and smallest tolerance in HH
OPT\mathrm{OPT}size of a largest LCC (0 if none)
xv(t),Av(t)x_v(t),A_v(t)position at step tt; neighbours accepted at tt
wvu(t)≥ηw_{vu}(t)\geq\etaaveraging weights, bounded below by η>0\eta>0
Ck(S,q)C_k(S,q)component with qq of the kk-core of G[S]G[S]
GθG_\thetasubgraph of GG on mutually accepted edges
ρv,Iv\rho_v,I_vd(xv,xq)d(x_v,x_q); survival interval of vv
RRquery region around qq
τ,Tq\tau,T_qthreshold; candidate thresholds
S(τ),C(τ)S(\tau),C(\tau)vertices of RR with τ∈Iv\tau\in I_v; Ck(S(τ),q)C_k(S(\tau),q)
OPTτ,β(τ)\mathrm{OPT}_\tau,\beta(\tau)optimum at threshold τ\tau and its upper bound
B,UBB,\mathrm{UB}best set found; proven upper bound on OPT\mathrm{OPT}

Table 1. NOTATION.

Definition 1 (Latitude-consistent community). For a query vertex qq and an integer k≥1k\geq1, we call a set H⊆VH\subseteq V a latitude-consistent community (LCC) when (i) q∈Hq\in H; (ii) G[H]G[H] is connected and has minimum degree at least kk; and (iii) diam⁡(H)≤θmin⁡(H)\operatorname{diam}(H)\leq\theta_{\min}(H).

Choosing θ=θacc\theta=\theta^{\mathrm{acc}} yields an LCCaccLCC^{\mathrm{acc}}, in which every member accepts every other member’s position; θ=θrej\theta=\theta^{\mathrm{rej}} yields the weaker LCCrejLCC^{\mathrm{rej}}, where no member rejects another.

Problem 1 (MaxLCC). For inputs GG, xx, θ\theta, qq and kk, return an LCC with the largest possible number of vertices. The decision problem LCC-Dec asks whether there exists an LCC containing at least ss vertices.

Why the minimum: Section IV shows that condition (iii) is exactly what keeps every interaction in a connected group accepted at all times, for all positive averaging weights (Proposition 2). In the worst case, it cannot be weakened even for equal weights: neither a slack of ε\varepsilon, nor exempting two members, nor the pairwise condition d(xu,xv)≤min⁡(θu,θv)d(x_u,x_v)\leq\min(\theta_u,\theta_v) preserves the guarantee (Proposition 1, Figure 1). In a normed space, pairwise acceptance is equivalent to every member accepting every weighted average of the members’ positions, which suffices while those positions stay fixed. Removing members can only decrease diam⁡(H)\operatorname{diam}(H) and increase θmin⁡(H)\theta_{\min}(H), so condition (iii) is hereditary. Yet the condition couples three members at a time: d(xu,xv)≤θwd(x_u,x_v)\leq\theta_w for all u,v,w∈Hu,v,w\in H. This dependence on other members prevents a fixed pairwise decomposition. For instance, uu and vv at distance 1 with tolerance 1 form a feasible pair, and so does each with a vertex ww midway between them with tolerance 1/21/2, yet {u,v,w}\{u,v,w\} violates (iii). With uniform tolerances θv=r\theta_v=r, condition (iii) becomes the pairwise constraint of (k,r)(k,r)-cores [3], with distance in place of similarity. MaxLCC then asks for a maximum (k,r)(k,r)-core containing qq. Pruning for (k,r)(k,r)-cores relies on this fixed pairwise structure, which LatSweep (§ 5) recovers by fixing the threshold.

When to require (iii): The guarantees in Section IV apply to closed groups interacting repeatedly under unknown, possibly uneven influence weights, such as platform-formed study groups, deliberative-poll panels, project teams [39] or online deliberation groups. For a one-off meetup with fixed positions, the pairwise condition already suffices and permits larger groups (§ 6-C and VI-D).

kk-cores: For S⊆VS\subseteq V, the kk-core [40] of G[S]G[S] is its unique maximal subgraph with minimum degree at least kk, and Ck(S,q)C_k(S,q) denotes the component of this kk-core that contains qq, or the empty set if qq is not in the kk-core; peeling computes it in O(∣S∣+∣E(S)∣)O(|S|+|E(S)|) time [41], and we use the same notation for peeling in a spanning subgraph of GG. Throughout, we use the kk-core fact: every connected H⊆SH\subseteq S with q∈Hq\in H and minimum degree at least kk satisfies H⊆Ck(S,q)H\subseteq C_k(S,q).

Theoretical Properties

The theory addresses two questions: which groups preserve acceptance under opinion dynamics (Section IV-A), and how difficult it is to find a largest such group or approximate its size (Section IV-B).

Guarantees under Opinion Dynamics

Here, positions are opinions in Rm\mathbb{R}^m under any norm ∥⋅∥\|\cdot\|. A group HH starts from xv(0)=xvx_v(0)=x_v; the graph and the tolerances are fixed, interactions follow edges of G[H]G[H], and diam⁡(t)=max⁡u,v∈H∥xu(t)−xv(t)∥\operatorname{diam}(t)=\max_{u,v\in H}\lVert x_u(t)-x_v(t)\rVert.

Bounded-confidence dynamics: In the network version of the Hegselmann–Krause (HK) model [9] with agent-specific bounds [10], vertex vv averages the opinions of the neighbours it accepts:

xv(t+1)=∑u∈Av(t)∪{v}wvu(t)xu(t),(1)x_v(t+1)=\sum_{u\in A_v(t)\cup\{v\}}w_{vu}(t)x_u(t), \tag*{(1)}

where Av(t)={u∈NH(v):∥xu(t)−xv(t)∥≤θv}A_v(t)=\{u\in N_H(v):\lVert x_u(t)-x_v(t)\rVert\leq\theta_v\}, the weights are non-negative with unit sum, and wvu(t)≥η>0w_{vu}(t)\geq\eta>0 for u∈Av(t)∪{v}u\in A_v(t)\cup\{v\}; equal weights wvu(t)=1/(∣Av(t)∣+1)w_{vu}(t)=1/(|A_v(t)|+1) give η=1/∣H∣\eta=1/|H|. An interaction along (u,v)(u,v) is accepted at time tt if u∈Av(t)u\in A_v(t).

Lemma 1. If every xv(t+1)x_v(t+1) is a convex combination of {xu(t):u∈H}\{x_u(t):u\in H\}, then diam⁡(t+1)≤diam⁡(t)\operatorname{diam}(t+1)\leq\operatorname{diam}(t), because, by convexity of the norm, a point set and its convex hull have the same diameter.

Theorem 1 (Consensus). Let HH be an LCCaccLCC^{\mathrm{acc}} with h=∣H∣≥2h=|H|\geq2 that evolves by (1) with θ=θacc\theta=\theta^{\mathrm{acc}}. Then for every t≥0t\geq0, (a) every interaction along every edge of G[H]G[H] is accepted, and (b) diam⁡(t)\operatorname{diam}(t) is non-increasing and

diam⁡(t)≤(1−hηh−1)⌊t/(h−1)⌋diam⁡(0),\operatorname{diam}(t)\leq\left(1-h\eta^{h-1}\right)^{\lfloor t/(h-1)\rfloor}\operatorname{diam}(0),

so all opinions converge to a common point. (c) With equal weights, the limit is the (deg⁡H(v)+1)(\deg_H(v)+1)-weighted average of the initial opinions.

Proof. (a) Each update (1) is a convex combination, so by Lemma 1, diam⁡(t)≤diam⁡(0)≤θmin⁡(H)≤θv\operatorname{diam}(t)\leq\operatorname{diam}(0)\leq\theta_{\min}(H)\leq\theta_v for all tt and vv; hence Av(t)=NH(v)A_v(t)=N_H(v).

(b) By (a), the update matrix W(t)W(t) is row-stochastic with entries at least η\eta on the diagonal and on the edges of G[H]G[H]. Since G[H]G[H] is connected, any two vertices are joined by a walk of exactly h−1h-1 steps when self-loops are allowed, so every entry of Π=W(t+h−2)⋯W(t)\Pi=W(t+h-2)\cdots W(t) is at least γ=ηh−1\gamma=\eta^{h-1}. For two rows a,ba,b of Π\Pi, let δ=12∑j∣aj−bj∣=1−∑jmin⁡(aj,bj)≤1−hγ\delta=\frac{1}{2}\sum_j|a_j-b_j|=1-\sum_j\min(a_j,b_j)\leq1-h\gamma; the vector ∑j(aj−bj)xj\sum_j(a_j-b_j)x_j is 00 if δ=0\delta=0 and otherwise δ\delta times a difference of two convex combinations of the xjx_j, so its norm is at most δ⋅diam⁡\delta\cdot\operatorname{diam}. Hence the diameter is multiplied by at most 1−hγ1-h\gamma every h−1h-1 steps. Because every later opinion remains in the convex hull of the opinions at time tt, the trajectories are Cauchy and share a common limit.

(c) With equal weights, W(t)≡WW(t)\equiv W is the random walk on G[H]G[H] with self-loops, whose stationary distribution πv∝deg⁡H(v)+1\pi_v\propto\deg_H(v)+1 satisfies π⊤x(t)=π⊤x(0)\pi^\top x(t)=\pi^\top x(0).

Condition (iii) fixes the accepted interactions, so the dynamics reduce to linear averaging on G[H]G[H] [30]. Connectivity then ensures convergence; the role of kk is structural cohesion. Consensus does not require condition (iii), although it suffices: heterogeneous bounded-confidence dynamics can reach consensus from much more dispersed configurations and remain only partly understood [10, 33]. Natural relaxations of (iii) do not guarantee consensus (Proposition 1). Under asynchronous updates, in which only some vertices apply (1) at each step, Theorem 1(a) and the monotonicity of diam⁡(t)\operatorname{diam}(t) still hold, and if every vertex updates at least once in every κ\kappa consecutive steps, applying (b) to blocks of κ\kappa steps gives convergence (cf. [42]). The loose rate bound in (b) serves only to establish geometric convergence.

Social-judgment dynamics: SJT adds noncommitment and rejection. Following Jager and Amblard [36], vertex vv moves towards accepted neighbours, ignores noncommittal ones, and moves away from rejected ones:

xv(t+1)=xv(t)+∑u∈Av(t)αvu(xu(t)−xv(t))−∑u∈Rv(t)βvu(xu(t)−xv(t)),(2)x_v(t+1)=x_v(t)+\sum_{u\in A_v(t)}\alpha_{vu}\bigl(x_u(t)-x_v(t)\bigr)-\sum_{u\in R_v(t)}\beta_{vu}\bigl(x_u(t)-x_v(t)\bigr), \tag*{(2)}

where Av(t)A_v(t) uses θvacc\theta_v^{\mathrm{acc}}, Rv(t)={u∈NH(v):∥xu(t)−xv(t)∥>θvrej}R_v(t)=\{u\in N_H(v):\lVert x_u(t)-x_v(t)\rVert>\theta_v^{\mathrm{rej}}\}, and αvu,βvu≥0\alpha_{vu},\beta_{vu}\geq0 may vary with tt, with ∑uαvu≤1\sum_u\alpha_{vu}\leq1; updates may be asynchronous.

Theorem 2 (No rejection). If an LCCrejLCC^{\mathrm{rej}} HH follows (2), then Rv(t)=∅R_v(t)=\varnothing for all v∈Hv\in H and t≥0t\geq0, and diam⁡(t)\operatorname{diam}(t) never increases; consensus need not occur.

Proof. Suppose diam⁡(t)≤θmin⁡(H)\operatorname{diam}(t)\leq\theta_{\min}(H), which holds at t=0t=0. Then every edge satisfies ∥xu(t)−xv(t)∥≤θv\lVert x_u(t)-x_v(t)\rVert\leq\theta_v, so Rv(t)=∅R_v(t)=\varnothing, and the update xv(t+1)=(1−∑uαvu)xv(t)+∑uαvuxu(t)x_v(t+1)=(1-\sum_u\alpha_{vu})x_v(t)+\sum_u\alpha_{vu}x_u(t) is a convex combination; Lemma 1 gives diam⁡(t+1)≤diam⁡(t)\operatorname{diam}(t+1)\leq\operatorname{diam}(t), and induction completes the proof. Finally, split K2k+2K_{2k+2} equally between positions 00 and 11 with θacc=1/2\theta^{\mathrm{acc}}=1/2 and θrej=1\theta^{\mathrm{rej}}=1: this LCCrejLCC^{\mathrm{rej}} has only noncommittal cross pairs and never moves. □

Proposition 1 (Tightness). Fix k≥1k\geq1, θ>0\theta>0 and ε>0\varepsilon>0.

(a) There is a connected group with minimum degree at least kk, diameter θ+ε\theta+\varepsilon and uniform tolerance θ\theta in which acceptance and consensus fail under (1); with θacc=θ/2\theta^{\mathrm{acc}}=\theta/2, θrej=θ\theta^{\mathrm{rej}}=\theta and β>0\beta>0, rejection occurs under (2) and the diameter grows.

(b) There is a connected group with minimum degree at least kk in which every pair satisfies d(xu,xv)≤min⁡(θu,θv)d(x_u,x_v)\leq\min(\theta_u,\theta_v) and every member ww but two satisfies diam⁡(H)≤θw\operatorname{diam}(H)\leq\theta_w, but in which acceptance and consensus fail under (1); with θacc=θrej=θ\theta^{\mathrm{acc}}=\theta^{\mathrm{rej}}=\theta and β>0\beta>0, rejection occurs under (2).

Proof. (a) Split K2k+2K_{2k+2} equally between positions 00 and θ+ε\theta+\varepsilon on a line. Under (1), no cross pair is accepted, so both halves stay where they are; under (2), every cross pair is rejected, and the first update pushes the halves apart.

(b) Let ℓ=max⁡(k,3)\ell=\max(k,3). Place cliques H0H_0 and H2H_2 of ℓ\ell vertices each at positions 00 and 22 with tolerance 22, and two adjacent vertices uu and vv at position 11 with tolerance 11, where uu is adjacent to all of H0H_0 and vv to all of H2H_2. Every pair is within the smaller of its two tolerances, every vertex has degree at least ℓ≥k\ell\geq k, and only uu and vv have tolerance below diam⁡(H)=2\operatorname{diam}(H)=2. With equal weights, one update of (1) moves H0H_0 to 1/(ℓ+2)1/(\ell+2), uu to 2/(ℓ+2)2/(\ell+2), vv to 2−2/(ℓ+2)2-2/(\ell+2) and H2H_2 to 2−1/(ℓ+1)2-1/(\ell+1). Then ∥xu−xv∥=2−4/(ℓ+2)>1\lVert x_u-x_v\rVert=2-4/(\ell+2)>1, so uu and vv no longer accept each other, and the vertices of H0∪{u}H_0\cup\{u\}, like those of H2∪{v}H_2\cup\{v\}, accept only one another. Each part therefore stays in the convex hull of its own positions at t=1t = 1, and the two hulls are more than 1 apart; by the argument of Theorem 1(b), each part converges to its own limit. With θacc=θrej\theta^{\mathrm{acc}} = \theta^{\mathrm{rej}} and αvu=1/(∣Av(t)∣+1)\alpha_{vu} = 1/(|A_v(t)| + 1), the first update of (2) coincides with that of (1), after which uu and vv reject each other.

Part (b), illustrated in Figure 1 for ℓ=3\ell= 3, explains the minimum in Definition 1: even with pairwise acceptance, exempting two members breaks the guarantees. A single member below the bound already breaks acceptance. Give H2H_2 one more vertex, and replace uu and vv by one vertex ww at position 1 with tolerance 1, adjacent to all of H0H_0 and to one vertex z∈H2z \in H_2; one update moves ww to 3/(ℓ+2)3/(\ell+ 2) and zz to (2ℓ+3)/(ℓ+2)(2\ell+ 3)/(\ell+ 2), which are 2ℓ/(ℓ+2)>12\ell/(\ell+ 2) > 1 apart. However, consensus survives a single exemption: every other member accepts all its neighbours at all times, so ww is a root of every interaction graph, and consensus follows [42].

The counterexamples in Proposition 1 motivate an exact characterization across static and dynamic regimes: whereas the pairwise condition suffices for every member to accept static compromises when positions remain fixed, condition (iii) is necessary and sufficient to protect a connected group against every positive weighting of (1).

Proposition 2 (Characterization). Let H⊆VH \subseteq V with ∣H∣≥2|H| \ge2 and θ=θacc\theta= \theta^{\mathrm{acc}}. (a) Every pair u,v∈Hu, v \in H satisfies ∥xu−xv∥≤min⁡(θu,θv)\lVert x_u - x_v \rVert\le\min(\theta_u, \theta_v) if and only if every member of HH accepts every point of conv⁡{xu:u∈H}\operatorname{conv}\{x_u : u \in H\}. (b) If G[H]G[H] is connected, then diam⁡(H)≤θmin⁡(H)\operatorname{diam}(H) \le\theta_{\min}(H) if and only if, for every η>0\eta> 0 and all weights admitted by (1), every interaction along every edge of G[H]G[H] is accepted at all times. Moreover, if diam⁡(H)>θmin⁡(H)\operatorname{diam}(H) > \theta_{\min}(H) and all these interactions are accepted at t=0t = 0, then for every sufficiently small η>0\eta> 0 some admitted weights make a member refuse, within 2∣H∣2|H| steps, an interaction that it accepted at t=0t = 0.

Proof. (a) For fixed vv, the function p↦∥p−xv∥p \mapsto\lVert p - x_v \rVert is convex, so its maximum over the convex hull is attained at one of the points xux_u. Hence vv accepts the whole hull if and only if ∥xu−xv∥≤θv\lVert x_u - x_v \rVert\le\theta_v for all u∈Hu \in H; requiring this for every vv gives the pairwise condition.

(b) The proof of Theorem 1(a) requires only that each update be a convex combination, so it applies to all admitted weights and establishes the forward direction. For the converse, assume diam⁡(H)>θmin⁡(H)\operatorname{diam}(H) > \theta_{\min}(H) and that every interaction along an edge of G[H]G[H] is accepted at t=0t = 0, since otherwise there is nothing to prove; let D=diam⁡(H)D = \operatorname{diam}(H) and 0<δ≤120 < \delta\le\frac{1}{2}. In a copy step along an edge (z,y)(z,y), member yy puts weight 1−δ1-\delta on zz and spreads δ\delta evenly over its other accepted neighbours and itself, while every other member puts weight 1−δ1-\delta on itself and spreads δ\delta evenly over its accepted neighbours, or keeps weight 1 if it accepts none. Every weight on an accepted neighbour or on the member itself is at least δ/∣H∣\delta/|H|, so these weights are admitted for every η≤δ/∣H∣\eta\le\delta/|H|, provided that yy still accepts zz; if it does not, an interaction accepted at t=0t = 0 has been refused. The same holds if any member refuses any neighbour during the steps below, so assume that this never happens. By Lemma 1, the diameter stays at most DD; hence in a copy step yy moves to within δD\delta D of the position of zz, and every other member moves by at most δD\delta D. Copying along a path p0,…,pLp_0,\ldots,p_L, that is, performing copy steps along (p0,p1),…,(pL−1,pL)(p_0,p_1),\ldots,(p_{L-1},p_L) in this order, therefore brings pLp_L to within LδDL\delta D of where p0p_0 started, and moves every member outside {p1,…,pL}\{p_1,\ldots,p_L\} by at most LδDL\delta D.

If some pair a,b∈Ha,b \in H has ∥xa−xb∥>θa\lVert x_a - x_b \rVert> \theta_a, then aa and bb are not adjacent. A shortest path from bb to aa, without its last vertex aa, ends at a neighbour yy of aa and has length 1≤L<∣H∣1 \le L < |H|. Copying along it brings yy to within LδDL\delta D of xbx_b, while aa moves by at most LδDL\delta D, so aa refuses yy at t=Lt = L once 2LδD<∥xa−xb∥−θa2L\delta D < \lVert x_a - x_b \rVert- \theta_a.

Otherwise the pairwise condition holds. Let θw=θmin⁡(H)\theta_w = \theta_{\min}(H) and ∥xu−xv∥=D\lVert x_u - x_v \rVert= D; then w∉{u,v}w \notin\{u,v\}, because ∥xw−xy∥≤θw<D\lVert x_w - x_y \rVert\le\theta_w < D for all y∈Hy \in H. There is a path from uu to ww that avoids vv, or one from vv to ww that avoids uu: if vv lies on every path from uu to ww, then every path from vv to ww continues inside the component of G[H]−vG[H] - v that contains ww, and uu is not in this component. Swapping uu and vv if necessary, copy along a path from uu to ww that avoids vv, and then along a shortest path from vv to ww without its last vertex ww; the latter ends at a neighbour yy of ww, possibly y=vy = v. After these T<2∣H∣T < 2|H| steps, ww is within TδDT\delta D of uu and vv within TδDT\delta D of ww, so ∥xw(T)−xy(T)∥≥(1−2Tδ)D>θw\lVert x_w(T) - x_y(T) \rVert\ge(1 - 2T\delta)D > \theta_w once 2TδD<D−θw2T\delta D < D - \theta_w: member ww refuses yy, which it accepted at t=0t = 0.

Part (b) is a worst-case statement over all weightings. Its converse requires weights that may be arbitrarily uneven: in the proof, each moving member puts almost all its weight on one neighbour. Under equal weights, a group that violates (iii) may or may not lose an accepted interaction (Proposition 1(b)). For instance, let u,w,vu,w,v form a triangle in GG, at positions 0, 1/21/2 and 1 on a line, with tolerances 1, 0.6 and 1: every pair satisfies the pairwise condition and (iii) fails, but with η=13\eta= \frac{1}{3} every update is the equal-weight one, so the group meets at its centroid after one step and no interaction is ever refused. The proof requires only a connected interaction graph, so (b) also holds when all members hear one another. With θacc=θrej\theta^{\mathrm{acc}} = \theta^{\mathrm{rej}}, the same steps are admitted by (2), where a refusal is a rejection, so (iii) is also exactly what rules out rejection under (2) for all coefficients; this needs θacc=θrej\theta^{\mathrm{acc}} = \theta^{\mathrm{rej}}, since, for instance, with θacc≡0.4\theta^{\mathrm{acc}} \equiv0.4 in the triangle above every pair is noncommittal and nobody ever moves. § 6-C measures how often other methods’ groups lose an accepted interaction under equal and uneven weights.

Open groups: When members average with accepted neighbours outside the group, condition (iii) alone no longer suffices; Proposition 3 supplies an additional sufficient condition.

Proposition 3 (Open groups). Let each v∈Hv \in H also interact with its outside neighbours Ov=NG(v)∖HO_v = N_G(v) \setminus H, whose positions xox_o stay fixed, and let every update move xvx_v to a convex combination, with non-negative weights that may vary with time and state, of xv(t)x_v(t) and the in-group and outside neighbours that vv accepts at time tt. Let Y0Y_0 be the set of outside positions accepted by some member at t=0t = 0, and K0=conv⁡({xv(0):v∈H}∪Y0)K_0 = \operatorname{conv}(\{x_v(0) : v \in H\} \cup Y_0). If (a) diam⁡(K0)≤θmin⁡(H)\operatorname{diam}(K_0) \le\theta_{\min}(H) and (b) ∥xo−p∥>θv\lVert x_o - p \rVert> \theta_v for all p∈K0p \in K_0, v∈Hv \in H and o∈Ovo \in O_v with xo∉Y0x_o \notin Y_0, then xv(t)∈K0x_v(t) \in K_0 for all vv and tt, and at every time each member accepts exactly the neighbours it accepted at t=0t = 0.

Proof. We prove by induction on tt that xu(t)∈K0x_u(t) \in K_0 for all u∈Hu \in H; the claim holds at t=0t = 0. Assume it holds at time tt and fix vv. If o∈Ovo \in O_v and xo∉Y0x_o \notin Y_0, then ∥xv(t)−xo∥>θv\lVert x_v(t) - x_o \rVert> \theta_v by (b), so vv does not accept oo; every other point that vv can average, namely xv(t)x_v(t), the positions xu(t)x_u(t) of its in-group neighbours and the outside positions in Y0Y_0, lies in the convex set K0K_0, so xv(t+1)∈K0x_v(t + 1) \in K_0. Any two points of K0K_0 are within diam⁡(K0)≤θmin⁡(H)≤θv\operatorname{diam}(K_0) \le\theta_{\min}(H) \le\theta_v, so at every time vv accepts all its in-group neighbours and all outside neighbours with positions in Y0Y_0, and no others; by the definition of Y0Y_0, these are exactly the neighbours it accepts at t=0t = 0. As a point set and its convex hull have the same diameter (Lemma 1), (a) can be checked on the finite set {xv(0)}v∈H∪Y0\{x_v(0)\}_{v \in H} \cup Y_0. The argument requires neither connectivity nor positive weights nor synchronous updates, but it does require fixed outside positions.

The fixed outside neighbours are the constant signals of Hegselmann and Krause [35]; what matters is the certificate. The condition of Mirtabatabaei and Bullo [33 Prop. 4.11], under which an isolated all-to-all group with scalar opinions reaches consensus if all members but one have bounds larger than its opinion range, permits one exemption but no outside neighbours, the reverse of Proposition 3; neither condition therefore implies the other. In our network model, two exemptions are too many by Proposition 1(b). Condition (a) of Proposition 3 alone does not suffice, even with equal weights, because members can begin to accept outside neighbours that none accepted at t=0t = 0 and drift apart, an instance of the indirect influence described in [35]. For example, let adjacent members aa and bb start at 00 and 12\frac{1}{2} with θ≡1\theta\equiv1, let aa have 2020 outside neighbours at 00, and bb have 1010 at 1920\frac{19}{20} and 1010 at 85\frac{8}{5}. Then diam⁡({xa,xb}∪Y0)=1920≤1\operatorname{diam}(\{x_a,x_b\} \cup Y_0) = \frac{19}{20} \le1, but (b) fails; under equal-weight HK, bb starts to accept the neighbours at 85\frac{8}{5} after one step, and at t=2t = 2 the two members are 5144>1\frac{51}{44} > 1 apart and refuse each other. The argument needs outside positions to stay fixed, and open groups need not reach consensus: if aa has 2020 outside neighbours at 00 and bb has 1010 at 0.950.95, with θ≡1\theta\equiv1 and members at 00 and 12\frac{1}{2}, the two members converge to 19460\frac{19}{460} and 399460\frac{399}{460} under equal weights, so the members’ diameter grows from 12\frac{1}{2} to 1923\frac{19}{23} while K0K_0 stays fixed. Section VI-C evaluates how often conditions (a) and (b) hold in real networks and how groups behave when external weights vary.

Complexity

We study LCC-DEC in Rm\mathbb{R}^m with the Euclidean norm and rational coordinates and tolerances; in parts (a), (b) and (f), mm is part of the input and we use the following embedding.

Lemma 2. Given a graph F=(U,EF)F = (U,E_F) with ∣U∣=n|U| = n, points yu∈{−1,0,1}my_u \in\{-1,0,1\}^m with m=O(n2)m = O(n^2) and an integer rr can be computed in polynomial time such that, for distinct u,w∈Uu,w \in U, ∥yu−yw∥≤r\lVert y_u - y_w \rVert\le r if and only if {u,w}∈EF\{u,w\} \in E_F.

Proof. Let F‾\overline{F} denote the complement of FF, and let Δ\Delta denote its maximum degree. Take the least positive integer jj satisfying $2j^2 \ge \Delta$, and put D=2j2D = 2j^2. For every edge {u,w}\{u,w\} in F‾\overline{F} ordered by u<wu < w, introduce a coordinate assigning yu=+1y_u = +1, $y_w = -1, and every other point the value 00. For each uu, introduce another D−deg⁡F‾(u)D-\deg_{\overline{F}}(u) private coordinates with value 11. This gives ∥yu∥2=D\lVert y_u \rVert^2 = D for every uu; distinct points can share a non-zero coordinate only when they are adjacent in F‾\overline{F}. Thus ∥yu−yw∥\lVert y_u-y_w\rVert is −1-1 when {u,w}∉EF\{u,w\} \notin E_F and 00 when {u,w}∈EF\{u,w\} \in E_F. Thus ∥yu−yw∥2\lVert y_u-y_w\rVert^2 takes value D+2D+2 in the former case and 2D2D in the latter, so the threshold r=2jr = 2j distinguishes them. □

Theorem 3 (Hardness). (a) For each fixed k≥1k \ge1, LCC-DEC is NPNP-complete. This holds even for complete GG, equal tolerances, and coordinates restricted to {−1,0,1}\{-1,0,1\}. (b) For every fixed ε∈(0,1)\varepsilon\in(0,1), unless P=NP\mathrm{P} = \mathrm{NP}, no polynomial-time algorithm can approximate MaxLCC to within a factor of n1−εn^{1-\varepsilon}. (c) The conclusions of (a) and (b) extend to general metrics supplied as distance matrices. (d) When m=1m = 1, MaxLCC can be solved in O(n2(n+∣E∣))O(n^2(n+|E|)) time. (e) For each fixed k≥1k \ge1 and m≥2m \ge2, LCC-DEC remains NPNP-complete, also on the sphere with chord distance, even with equal tolerances. (f) For each fixed k≥2k \ge2, deciding whether an LCC exists is NPNP-complete, even with equal tolerances, both for distances in {1,2}\{1,2\} and in Rm\mathbb{R}^m with mm part of the input. Hence, for each fixed k≥2k \ge2, unless P=NP\mathrm{P} = \mathrm{NP}, no polynomial-time algorithm returns an LCC for every input that has one; in particular, MaxLCC cannot be approximated within any factor.

Proof. Feasibility can be checked by comparing squared distances and squared tolerances using rational arithmetic, so membership in NP follows directly. (a) The reduction is from CLIQUE, which is NP-complete [43]. For an instance (F,c)(F,c), add a clique KK of k+1k+1 new vertices, including qq, and make every vertex of KK adjacent to every vertex of UU. Apply the embedding of Lemma 2 to this augmented graph, take GG to be complete, assign tolerance rr to every vertex, and set s=c+k+1s = c + k + 1. Any cc-clique QQ in FF gives the set Q∪KQ \cup K, whose pairwise distances are at most rr and whose minimum degree in GG is c+k≥kc + k \ge k. Conversely, every pair of vertices in an LCC has distance at most rr; by Lemma 2, these vertices form a clique in the augmented graph, and deleting KK leaves a clique in FF with at least cc vertices. (b) Embed FF itself by Lemma 2, with complete GG and tolerance rr. Checking all sets of at most k+1k+1 vertices in nO(k)n^{O(k)} time either finds a maximum clique, if its size ω\omega is at most kk, or shows ω>k\omega> k. In the latter case, apply a ρ\rho-approximation algorithm to each query q∈Uq \in U that lies in a (k+1)(k+1)-clique. If qq belongs to a maximum clique, the corresponding optimum equals ω\omega. Every LCC returned by the algorithm is a clique in FF, and the largest returned set therefore contains at least ω/ρ\omega/\rho vertices. This gives a polynomial-time approximation for CLIQUE within ρ\rho; taking ρ=n1−ε\rho= n^{1-\varepsilon} would imply P = NP [44].

(c) The embedding would give irrational distances, so we bypass it: set d(u,w)=1d(u,w)=1 if {u,w}\{u,w\} is an edge of the graph being embedded and d(u,w)=2d(u,w)=2 for every other pair u≠wu\ne w, and give every vertex tolerance 1. Any symmetric matrix with zero diagonal and off-diagonal entries in {1,2}\{1,2\} satisfies the triangle inequality, and the arguments of (a) and (b) apply unchanged.

(d) Take an optimal solution H∗H^* and define τ∗=θmin⁡(H∗)\tau^*=\theta_{\min}(H^*) and a∗=min⁡v∈H∗xva^*=\min_{v\in H^*}x_v. The inequality diam⁡(H∗)≤τ∗\operatorname{diam}(H^*)\le\tau^* places H∗H^* inside the window [a∗,a∗+τ∗][a^*,a^*+\tau^*]. For each pair (a,τ)∈{xu}×{θu}(a,\tau)\in\{x_u\}\times\{\theta_u\}, evaluate C(a,τ)=Ck(Sa,τ,q)C(a,\tau)=C_k(S_{a,\tau},q), where Sa,τ={v:θv≥τ, a≤xv≤a+τ}S_{a,\tau}=\{v:\theta_v\ge\tau,\ a\le x_v\le a+\tau\}. Every non-empty C(a,τ)C(a,\tau) is an LCC: its positions occupy a window of length τ\tau, and each tolerance is at least τ\tau. The kk-core fact gives H∗⊆C(a∗,τ∗)H^*\subseteq C(a^*,\tau^*), establishing optimality of the largest C(a,τ)C(a,\tau). The enumeration considers n2n^2 pairs and takes O(n+∣E∣)O(n+|E|) time for each.

(e) We reduce from 3-SAT [43] with variables x1,…,xνx_1,\ldots,x_\nu, ν≥2\nu\ge2, and clauses c1,…,cμc_1,\ldots,c_\mu. Let ti=i/(ν+1)t_i=i/(\nu+1) and pi=((1−ti2)/(1+ti2),2ti/(1+ti2))p_i=((1-t_i^2)/(1+t_i^2),2t_i/(1+t_i^2)), a rational point of the unit circle at angle ϕi=2arctan⁡ti∈(0,π/2)\phi_i=2\arctan t_i\in(0,\pi/2). Place a clique KK of k+1k+1 vertices, including qq, at the origin; for each ii, place kk copies of the literal xix_i at pip_i and kk copies of ¬xi\neg x_i at −pi-p_i; and place one vertex per clause at the origin. Every copy is adjacent to all of KK, and each clause vertex is adjacent to all copies of its literals. Copies of xix_i and ¬xi\neg x_i are at distance 2; every other pair is closer than r=2−1/(16(ν+1)2)r=2-1/(16(\nu+1)^2). Indeed, pairs involving the origin and pairs of copies of the same literal are at distance at most 1. Copies of literals of distinct variables xix_i and xjx_j are at distance 2sin⁡(α/2)2\sin(\alpha/2) or 2cos⁡(α/2)2\cos(\alpha/2), where α=∣ϕi−ϕj∣<π/2\alpha=|\phi_i-\phi_j|<\pi/2; both are at most 2cos⁡(δ/2)2\cos(\delta/2), where δ≤α\delta\le\alpha is the smallest difference between distinct angles ϕi\phi_i. Since the derivative of 2arctan⁡t2\arctan t is at least 1 on [0,1][0,1] and consecutive values tit_i differ by 1/(ν+1)1/(\nu+1), we have δ≥1/(ν+1)\delta\ge1/(\nu+1); with y=δ/2<1y=\delta/2<1 and cos⁡y≤1−y2/2+y4/24≤1−11y2/24\cos y\le1-y^2/2+y^4/24\le1-11y^2/24, this gives 2cos⁡(δ/2)≤2−11δ2/48<r2\cos(\delta/2)\le2-11\delta^2/48<r. With tolerance rr for every vertex, an LCC contains copies of at most one literal per variable, and therefore at most s=k+1+kν+μs=k+1+k\nu+\mu vertices. An LCC with ss vertices contains KK, all copies of one literal per variable, and every clause vertex; each clause vertex then needs kk neighbours, that is, a chosen literal, so the chosen literals satisfy the formula. Conversely, the true literals of a satisfying assignment, together with KK and all clause vertices, form an LCC with ss vertices. On the sphere with chord distance, put the copies on the equator and the other vertices at the north pole, at distance 2<r\sqrt{2}<r from every copy; the argument is unchanged. Padding the coordinates with zeros extends the planar construction to every fixed m≥2m\ge2.

(f) Membership in NP is as above. We reduce from Multi-Colored Clique: given a graph F=(U,EF)F=(U,E_F) whose vertex set is partitioned into classes U1,…,UmU_1,\ldots,U_m with m≥2m\ge2, decide whether some u1∈U1,…,um∈Umu_1\in U_1,\ldots,u_m\in U_m are pairwise adjacent. It is NP-complete, since an instance (F′,c)(F',c) of CLIQUE with c≥2c\ge2 reduces to it by taking Ui=V(F′)×{i}U_i=V(F')\times\{i\} for i≤ci\le c and joining (a,i)(a,i) and (b,j)(b,j) if and only if i≠ji\ne j and {a,b}∈E(F′)\{a,b\}\in E(F'). Add an original vertex q^\hat q and arrange the classes {q^},U1,…,Um\{\hat q\},U_1,\ldots,U_m on a ring, so that the ring neighbours of UiU_i are Ui−1U_{i-1} and Ui+1U_{i+1}, with U0=Um+1={q^}U_0=U_{m+1}=\{\hat q\}. Replace every original a∈U∪{q^}a\in U\cup\{\hat q\} by c−1c-1 copies, let qq be a copy of q^\hat q, and join two copies in GG if and only if their originals lie in ring-neighbouring classes. Call two originals compatible if they are equal, if one of them is q^\hat q, or if they lie in different classes and are adjacent in FF. Put copies of compatible originals at distance 1 and all other pairs at distance 2, with tolerance 1 for every vertex; for Euclidean distances, embed the compatibility graph on U∪{q^}U\cup\{\hat q\} by Lemma 2, put every copy at the point of its original, and give every vertex tolerance rr. In both cases, a set satisfies (iii) if and only if its members are copies of pairwise compatible originals. If u1,…,umu_1,\ldots,u_m form a multicolored clique, all copies of q^,u1,…,um\hat q,u_1,\ldots,u_m form an LCC: the subgraph they induce is connected, each of its vertices has 2(k−1)≥k2(k-1)\ge k neighbours in it, and their originals are pairwise compatible. Conversely, let HH be an LCC. Distinct originals in the same class are incompatible, so the members of HH among the copies of a class are copies of a single original. The neighbours in G[H]G[H] of a member therefore lie in its two ring-neighbouring classes, at most k−1k-1 in each, and minimum degree kk forces both of these classes to contribute members. Starting from qq, whose ring neighbours are U1U_1 and UmU_m, and following the ring, every class UiU_i contributes copies of some uiu_i; these originals are pairwise compatible and lie in different classes, so they form a multicolored clique. Finally, if a polynomial-time algorithm returned an LCC for every input that has one, checking whether its output is an LCC would decide existence in polynomial time. □

Parts (a) and (b) transfer the hardness of CLIQUE through Lemma 2, a simple instance of representing graphs by distances as in the study of sphericity [45], and (c) through distances in {1,2}\{1,2\}; (e) and (f) require new constructions. With uniform tolerances, (e) and (e) also show that the query version of the (k,r)(k,r)-core problem [3] is NP-hard under Euclidean distance, even in the plane, and by (f), for each fixed k≥2k\ge2, even deciding whether qq lies in any (k,r)(k,r)-core is NP-complete when the dimension is part of the input. The assumption that kk is fixed matters: if kk is part of the input, the construction of (a) with K={q}K=\{q\} and k=ck=c already makes existence NP-complete. Parts (b) and (f) motivate relaxing the diameter, but not the size, in Section V-B: by (f), for each fixed k≥2k\ge2 and unless P = NP, every polynomial-time algorithm that returns only LCCs, such as BallCore-F and the greedy variant, returns nothing on some inputs that have an LCC, whereas BallCore-R is empty only if no LCC exists. Part (b) is not subsumed by (f): it also holds for k=1k=1, and its proof gives the same bound even on inputs with an LCC that is easy to find, a (k+1)(k+1)-clique of FF containing qq.

Open cases: It remains open whether MaxLCC is hard to approximate in dimensions 2 and 3 and whether, for k≥2k\ge2, deciding the existence of an LCC is hard in fixed dimension; on the sphere with chord distance, as in our meetup data, only (e) applies. If GG is complete, Lemma 4 reduces MAXLCC to finding, for each candidate threshold, a maximum clique containing qq in a unit ball graph. This is polynomial in the plane [46], even with member-specific tolerances, so the hardness in (e) stems from the graph; in dimension 4 and above, it is NP-hard even for complete GG [47], while these results leave dimension 3 unresolved.

The LatSweep Framework

LatSweep makes the coupled constraint (iii) searchable by fixing the smallest tolerance τ\tau. Each value yields a fixed-threshold subproblem in a reduced region around qq (see Figure 2). The sweep yields four algorithms: BallCore-F and a greedy variant return only LCCs, BallCore-R is a polynomial-time (1,2)(1,2)-bicriteria approximation, and LatSweep-Exact (Exact) is exact and, if stopped early, returns the best LCC found, if any, with an upper bound on the optimum. For a fixed threshold, the subproblem is a search for a maximum (k,r)(k,r)-core containing qq [3], which we solve with known tools: peeling, filtering of conflicts (pairs farther apart than the threshold) and colouring bounds [48]. Survival intervals give each threshold its candidate set; these sets are not nested. Best-first refinement then allocates search across thresholds and supports early stopping with a certificate; a compatibility index reduces the search region. We write ρv=d(xv,xq)\rho_v=d(x_v,x_q) and let OPT be the size of a largest LCC, or 0 if none exists; all results hold in arbitrary metric spaces.

Survival Intervals and Candidate Reduction

Lemma 3 (Sound reductions). Let HH be an LCC and τ=θmin⁡(H)\tau=\theta_{\min}(H). (a) Every v∈Hv\in H satisfies ρv≤τ≤θv\rho_v\le\tau\le\theta_v, and hence ρv≤min⁡(θv,θq)\rho_v\le\min(\theta_v,\theta_q). (b) Let Gθ=(V,Eθ)G_\theta=(V,E_\theta) with Eθ={(u,v)∈E:d(xu,xv)≤min⁡(θu,θv)}E_\theta=\{(u,v)\in E:d(x_u,x_v)\le\min(\theta_u,\theta_v)\}. Then G[H]=Gθ[H]G[H]=G_\theta[H]; hence HH lies in the component of the kk-core of GθG_\theta that contains qq.

Proof. (a) As q∈Hq\in H, we have ρv≤diam⁡(H)≤θmin⁡(H)=τ≤θv\rho_v\le\operatorname{diam}(H)\le\theta_{\min}(H)=\tau\le\theta_v, and τ≤θq\tau\le\theta_q. (b) Every edge (u,v)(u,v) inside HH satisfies d(xu,xv)≤diam⁡(H)≤θmin⁡(H)≤min⁡(θu,θv)d(x_u,x_v)\le\operatorname{diam}(H)\le\theta_{\min}(H)\le\min(\theta_u,\theta_v); the kk-core fact applied to GθG_\theta completes the proof.

Lemma 3(a) assigns each vertex vv a survival interval Iv=[ρv,min⁡(θv,θq)]I_v=[\rho_v,\min(\theta_v,\theta_q)] for the smallest tolerance of an LCC containing it. A vertex with an empty interval, such as v4v_4 in Figure 2(a), cannot belong to an LCC. The core numbers of GθG_\theta form a compatibility index; it is independent of the query and is built once per tolerance assignment (say, for θacc\theta^{\mathrm{acc}} and for θrej\theta^{\mathrm{rej}}) in O(td∣E∣+n)O(t_d|E|+n) time, where tdt_d is the cost of one distance evaluation. For a query and a graph G′∈{G,Gθ}G'\in\{G,G_\theta\}, the query region RR is obtained by a traversal from qq along edges of G′G' that visits only vertices with a non-empty survival interval and core number at least kk in G′G'. By Lemma 3, every LCC lies in RR for either choice of G′G', and building RR inspects only RR and its neighbours; BallCore-R uses G′=GG'=G, and hence the core numbers of GG rather than the index, all other variants G′=GθG'=G_\theta.

Candidate thresholds: For τ>0\tau>0, let S(τ)={v∈R:τ∈Iv}S(\tau)=\{v\in R:\tau\in I_v\} and let C(τ)=Ck(S(τ),q)C(\tau)=C_k(S(\tau),q), peeled in G′G'. Let Tq={min⁡(θv,θq):v∈R}T_q=\{\min(\theta_v,\theta_q):v\in R\}, and let OPTτ\mathrm{OPT}_\tau be the largest size of a connected set H⊆S(τ)H\subseteq S(\tau) with q∈Hq\in H, minimum degree at least kk and diam⁡(H)≤τ\operatorname{diam}(H)\le\tau.

Lemma 4. OPT=max⁡τ∈TqOPTτ\mathrm{OPT}=\max_{\tau\in T_q}\mathrm{OPT}_\tau, and OPTτ≤∣C(τ)∣≤∣S(τ)∣\mathrm{OPT}_\tau\le|C(\tau)|\le|S(\tau)| for all τ\tau.

Proof. Every set counted in OPTτ\mathrm{OPT}_\tau has all tolerances at least τ≥diam⁡(H)\tau\ge\operatorname{diam}(H) and is therefore an LCC. Conversely, an optimal H∗H^* has τ∗=θmin⁡(H∗)≤θq\tau^*=\theta_{\min}(H^*)\le\theta_q, so τ∗∈Tq\tau^*\in T_q, and H∗⊆S(τ∗)H^*\subseteq S(\tau^*) by Lemma 3(a); thus H∗H^* is counted in OPTτ∗\mathrm{OPT}_{\tau^*}. The bound OPTτ≤∣C(τ)∣\mathrm{OPT}_\tau\le|C(\tau)| is the kk-core fact.

Best-first sweep: Algorithm 1 keeps an upper bound β(τ)\beta(\tau) on OPTτ\mathrm{OPT}_\tau for every threshold and repeatedly refines the threshold with the largest one, instead of increasing cost (see Figure 2(b)): the interval count ∣S(τ)∣|S(\tau)|, obtained for all thresholds by one sort of the interval end points; the size ∣C(τ)∣|C(\tau)| of the peeled set; for Exact, the bound that branch and bound computes at its root (Section V-C); and finally the search itself, which settles OPTτ\mathrm{OPT}_\tau. The root bound holds only for solutions larger than the incumbent BB, which suffices because BB never shrinks. By Lemma 4, no threshold can improve the incumbent once every remaining bound is at most ∣B∣|B|. Ordering by ∣S(τ)∣|S(\tau)| alone can prioritize expensive subproblems that have small optima; refining β(τ)\beta(\tau) instead focuses the search on promising thresholds (Section VI-B). Unlike with a uniform radius, S(τ)S(\tau) is not monotone in τ\tau: a larger τ\tau admits vertices farther from qq but drops those with θv<τ\theta_v<\tau; in Figure 2(a), from τ1\tau_1 to τ2\tau_2, S(τ)S(\tau) loses v1v_1 and gains v2v_2. The sort takes O(nqlog⁡nq)O(n_q\log n_q) time and one peeling O(nq+eq)O(n_q+e_q), where nq=∣R∣n_q=|R| and eq=∣E(R)∣e_q=|E(R)|.

BallCore: Feasible and Bicriteria Solutions

Feasible solutions: Variant F doubles the left end points of the survival intervals (λ=2\lambda=2 in Algorithm 1); it is fast but conservative, since it admits only vertices within τ/2\tau/2 of qq. The greedy variant avoids this restriction. It starts from C(τ)C(\tau), peeled in GθG_\theta, at each of the 20 thresholds with the largest ∣S(τ)∣|S(\tau)|. It repeatedly deletes the vertex other than qq with the

Algorithm 1 LatSweep
Require: $G$, $x$, $\theta$, query $q$, integer $k$, variant $\in \{F, R, \mathrm{Exact}\}$
1: $\lambda \leftarrow 2$ for F, else 1; $G' \leftarrow G$ for R, else $G_\theta$
2: $R \leftarrow$ query region in $G'$, with $\lambda\rho_v$ for $\rho_v \triangleright$ Lemma 3
3: $I_v \leftarrow [\lambda\rho_v,\min(\theta_v,\theta_q)]$ for $v \in R$
4: $T \leftarrow \{\min(\theta_v,\theta_q):v \in R\}$; $\beta(\tau) \leftarrow |S(\tau)|$ for $\tau \in T$
5: $B \leftarrow \varnothing$, or for Exact the larger of the BallCore-F and greedy results
6: while $T \ne \varnothing$ and $\max_{\tau \in T}\beta(\tau)>|B|$ do
7: $\tau \leftarrow$ a threshold in $T$ with the largest $\beta(\tau)$
8: if $\tau$ has not been peeled then
9: $C(\tau) \leftarrow C_k(S(\tau),q)$ in $G'$; $\beta(\tau) \leftarrow |C(\tau)|$
10: if the variant is F or R then
11: if $|C(\tau)|>|B|$ then $B \leftarrow C(\tau)$
12: remove $\tau$ from $T$
13: else if $\tau$ has no root bound yet then
14: $\beta(\tau) \leftarrow$ root bound of $C(\tau) \triangleright$ Section V-C
15: else
16: $H \leftarrow \operatorname{BRANCHANDBOUND}(C(\tau),\tau,|B|)$
17: if $|H|>|B|$ then $B \leftarrow H$
18: remove $\tau$ from $T \triangleright$ the threshold is settled
19: return $B$

Algorithm 1 stops only when every remaining threshold has ∣S(τ)∣≤∣B∣|S(\tau)| \le|B| and therefore cannot improve BB. □\square

The factor 2 is attained: place qq at 0 and kk vertices at each of −τ-\tau and +τ+\tau on a line, take GG complete, and give every vertex tolerance τ\tau. Then C(τ)C(\tau) contains all 2k+12k+1 vertices and has diameter 2τ2\tau, whereas an optimum consists of qq and the kk vertices on one side. It is also best possible in general metrics: with distances in {1,2}\{1,2\} as in Theorem 3(c), every set of diameter below 2 is a clique, so unless P = NP, no polynomial-time algorithm achieves size ratio n1−ϵn^{1-\epsilon} with diameter factor 2−δ2-\delta. BallCore-R relaxes condition (iii), so its output has no numerical guarantees of Section IV; a completed sweep returns at least OPT vertices within twice their smallest tolerance, and thus bounds OPT and certifies absence whenever B=∅B=\varnothing.

LatSweep-Exact

By Lemma 4, an optimal LCC is found by solving, at every τ∈Tq\tau\in T_q whose bound exceeds the incumbent, the fixed-threshold subproblem on C(τ)C(\tau): two vertices conflict if their distance exceeds τ\tau, and the goal is a largest conflict-free subset containing qq that is connected and has minimum degree at least kk. The exact variant peels in GθG_\theta, which is sparser and by Lemma 3(b) loses no solution, and initializes the incumbent with the BallCore-F and greedy solutions, which are feasible by Proposition 4.

Branch and bound: BRANCHANDBOUND⁡(C,τ,b)\operatorname{BRANCHANDBOUND}(C,\tau,b) returns a largest feasible subset of CC if it has more than bb vertices, and the empty set otherwise. A search node (M,P)(M,P) consists of selected vertices M⊇qM \supseteq q and undecided vertices PP, with no conflicts within MM or between MM and PP; the root has M={q}M=\{q\} and P=C(τ)∖{q}P=C(\tau)\setminus\{q\}, which satisfies this invariant because ρv≤τ\rho_v \le\tau for every v∈C(τ)v \in C(\tau). Let bb denote the size of the incumbent. Each node first applies rules (1) and (2) of Lemma 5 to reduce M∪PM \cup P. If no conflict remains in PP, then M∪PM \cup P is feasible and optimal for the subtree; otherwise, the node tests rule (3) and branches on a vertex p∈Pp \in P with the most conflicts in PP, either deleting pp or moving it to MM and deleting its conflicting partners from PP. Together, the two branches retain every solution in the subtree, and both maintain the invariant. The root bound used by Algorithm 1 is ∣M∣+c|M|+c at the root after rules (1) and (2), where c≤∣P∣c \le|P| is the colour count of rule (3); by Lemma 5, no feasible subset of C(τ)C(\tau) with more than bb vertices exceeds it. Rules (2) and (3) adapt the degree and colouring bounds of maximum-clique search [48].

Lemma 5 (Sound pruning). The rules below preserve every feasible solution with more than bb vertices in the current node’s subtree. (1) Delete edges joining conflicting vertices, peel G[M∪P]G[M \cup P] down to the component containing qq in its kk-core, and prune the node whenever this removes a vertex of MM. (2) Prune the node when ∣M∪P∣<b|M \cup P| < b. If this test fails, examine any vertex having fewer than bb conflict-free partners in M∪PM \cup P: delete it if it belongs to PP, or prune the node if it belongs to MM. Apply rules (1) and (2) alternately until both leave M∪PM \cup P unchanged. (3) Greedily colour the vertices of PP, in increasing order of their number of conflicts in PP, so that every colour class is a set of pairwise conflicting vertices; prune when ∣M∣|M| plus the colour count cc does not exceed bb.

Proof. Take any feasible HH satisfying ∣H∣>b|H| > b and M⊆H⊆M∪PM \subseteq H \subseteq M \cup P. (1) Since HH contains no conflicting pair, none of the deleted edges belongs to G[H]G[H]; the kk-core fact therefore ensures that HH remains after peeling. (2) Every v∈Hv \in H has the remaining ∣H∣−1≥b|H| - 1 \ge b vertices of HH as conflict-free partners, and all are contained in M∪PM \cup P. (3) H∖MH \setminus M is pairwise conflict-free, so it can contain at most one vertex from each colour class.

Colouring vertices with few conflicts first tends to use fewer colours than an arbitrary order [48] and gives a smaller additional speed-up in our experiments. Conflicts are stored as bitsets over C(τ)C(\tau), which takes O(∣C(τ)∣2)O(|C(\tau)|^2) time and space per threshold. The reductions shrink the region by orders of magnitude for most evaluated queries (§ 6). The remaining search is still exponential in the worst case, as expected from Theorem 3.

Time limits and certificates: Our implementation checks a time limit at every search node and does not search sets C(τ)C(\tau) with more than 3,000 vertices; such thresholds keep their bound, and root bounds are computed only for sets of up to 20,000 vertices, which Greedy also skips if larger. If Exact stops before every threshold is settled, one more pass outside the time limit, lasting at most 5 s or 10% of the limit, whichever is larger, tightens the bounds of the unsettled thresholds TT. Exact then returns the incumbent BB with UB=max⁡(∣B∣,max⁡τ∈Tβ(τ))≥OPT\mathrm{UB} = \max(|B|, \max_{\tau\in T} \beta(\tau)) \ge\mathrm{OPT}. Every answer is thus proven optimal (UB=∣B∣\mathrm{UB} = |B|, which includes proven empty answers), feasible with a gap ∣B∣/UB|B|/\mathrm{UB} (0<∣B∣<UB0 < |B| < \mathrm{UB}), or undecided (B=∅B = \varnothing and UB>0\mathrm{UB} > 0).

Experiments

The experiments ask how far exact search scales and where it stops (§ 6-B), how groups with and without the bound behave under uneven influence and outside ties (§ 6-C), and what personal tolerances change on real positions and what enforcing them costs (§ 6-D; two parliaments in § 6-E). Shares are compared in percentage points (pp); brackets denote 95% bootstrap confidence intervals (CIs). Between-method CIs resample queries 2,000 times with the two groups paired within each query. Groups may overlap across queries; the CIs therefore describe the sampled queries within each graph. Appendix A gives supplementary tables.

Setup

Graphs and positions: Gowalla and Brightkite [49] provide friendships and time-stamped check-ins, which we split by time into a training (70%), a validation (10%) and a test period (20%). We retain users with at least 10 training check-ins and the friendships between them. The home xvx_v of a user is the median check-in position in the user’s most frequent cell of about 25 km, and θv\theta_v is the median distance of the user’s training check-ins from home, at least 1 km. Distances are chord lengths between Earth-centred coordinates, within 0.1% of great-circle distances below 300 km. DBLP, YouTube, LiveJournal, Orkut and Friendster [50], together with Pokec [51], lack positions. For these SNAP graphs [52], we generate community-aligned positions. Label propagation [53] with a size cap forms groups of at most 1,000 vertices, whose members scatter with unit Gaussian spread in Rm\mathbb{R}^m around centres about eight times the within-group scale 2m\sqrt{2m} apart. Tolerances are θv=s2mexp⁡(σZv−σ2/2)\theta_v = s\sqrt{2m}\exp(\sigma Z_v - \sigma^2/2) with standard normal ZvZ_v and σ=0.4\sigma= 0.4. The scale ss is calibrated on 30 queries: it is the smallest value, on a grid refined by bisection, at which Exact (with a 5 s limit per query) finds LCCs with a median of at least 10 members. Where no value of the grid achieves this (YouTube, and Friendster on a coarser grid), we take the largest one. The calibrated ss ranges from 1.25 on Orkut to 3 on YouTube.

Queries and algorithms: Efficiency queries are drawn at random from the kk-core of GG (on synthetic positions, from groups of at least 20 members), 50 per setting. The default setting (k=3k = 3, all vertices and, on synthetic positions, m=16m = 16 and the calibrated scale) occurs in every parameter sweep on Gowalla, Brightkite, LiveJournal and Orkut. We pool its disjoint samples into 200 queries per graph, or 150 on Gowalla and Brightkite, which have no dimension sweep. The other four graphs use only the default setting, with 200 queries each. We run Exact (with a time limit of 60 s), the greedy variant (Greedy), BallCore-F and BallCore-R. The connected kk-core component of qq and the global (k,r)(k,r)-core, found by a heuristic search with the median tolerance as radius, serve as references. All algorithms we time are written in C++ (g++ 11.4, -O3 --march=native) and run single-threaded on an Intel Xeon Gold 6530 with 64 GB of memory; a two-pass loader converts Friendster’s edge list in 13 minutes. Query times exclude loading the graph, building the index and the bound pass after a time limit (§ 5-C), which took at most 4 μs on our efficiency queries.

Baselines: The baselines separate the effects of the LCC constraint, personal tolerances and structural cohesion; each dynamics or application analysis uses the relevant subset. The largest group satisfying the pairwise condition (pairwise) is also NP-hard to find: under equal tolerances, the pairwise condition coincides with (iii), so the proof of Theorem 3(a) applies. Our branch and bound solves it on a fixed conflict graph, in which uu and vv conflict if d(xu,xv)>min⁡(θu,θv)d(x_u,x_v) > \min(\theta_u,\theta_v), with a limit of 60 s (10 s in the heterogeneity sweep, where Exact keeps 60 s). Edge-accept is the kk-core on the edges accepted by both endpoints. Several baselines ignore tolerances. The (k,r)(k,r)-core at the LCC’s own threshold τ\tau is an oracle baseline, since τ\tau is known only after the search; the global (k,r)(k,r)-core uses the median tolerance instead. SAC [6], in its AppInc approximation, returns the connected kk-core containing qq in the smallest ball centred at qq that holds one, and size-matched SAC returns the kk-core in the smallest such ball whose kk-core has at least the LCC’s size, so its groups may be larger than the LCC. Finally, we use a random connected group of the LCC’s size and the kk-core component.

Efficiency

At the default setting, exact search is fast and proves its answers; once tolerances span several communities, it often cannot finish within the time limit.

Queries with and without an LCC: At the default setting, most queries without an LCC are settled before any search: the reductions in Lemma 3 eliminate every candidate for 74–100% of them, and Exact certifies absence in a median of at most 4.7 µs and a maximum of 0.81 s. Between 13% (Brightkite) and 57% (DBLP) of the queries have an LCC, and Table II reports these queries separately. On them, Exact takes a median of 0.07 ms (Brightkite) to 861 ms (Pokec), and it proves optimality on all but 4 queries on Pokec and 3 on Friendster, which reach the 60 s limit (column Unproven). As a reference, we extract qq’s kk-core component, which ignores positions and tolerances (median times in Table II). On the seven graphs where it ran alongside Exact, Exact is faster on 70% (Pokec) to 99% (Brightkite) of the default queries, and on 41–97% of those with an LCC. On Friendster, the extraction was timed in a separate run of the same code on the same queries (median 70.5 s). For queries with an LCC, Greedy finds one on 77–100%. On queries with a proven optimum, Greedy’s mean size relative to the optimum is 0.62–0.98, where a query counts as 0 when Greedy finds no LCC. On LiveJournal, Orkut and Pokec, BallCore-F finds an LCC for only 4–6% of queries that have one. BallCore-R is evaluated as an upper bound because its output need not be an LCC. On the four largest graphs, at most 3% of its non-empty outputs satisfy (iii), and its sets have a median size of 1.3–2.0 times the optimum; the global (k,r)(k,r)-core is never an LCC there.

Graph∣V∣|V|∣E∣|E|With LCCMedian (μ\mus)Medianp90UnprovenFindsSizekk-core (ms)
Gowalla56 K222 K16%0.30.26270100%0.982.2
Brightkite24 K108 K13%0.20.070.41095%0.951.1
DBLP317 K1.0 M57%0.90.145.4096%0.9422
YouTube1.1 M3.0 M23%2.331349093%0.9041
Pokec1.6 M22.3 M52%3.386121.6 s477%0.62373
LiveJournal4.0 M34.7 M50%3.46.01.9 s090%0.79630
Orkut3.1 M117.2 M55%4.72003.8 s084%0.681.6 s
Friendster65.6 M1.81 B55%0.43527.9 s389%0.7770.5 s

Table II. Exact and greedy at the default setting (k=3k = 3).

Unproven queries: Of the 3,700 queries across all graphs and settings, 1,352 have an LCC, and 9 of these remain unproven by Exact: 2 among the 2,900 parameter-sweep queries and 7 among the 800 queries on the other four graphs. For each of them, Exact still returns an LCC of at least 0.689 times a proven upper bound on OPT (§ 5-C): the ratio is 0.955 and 0.982 on LiveJournal and Orkut, and 0.689–0.939 on Pokec and Friendster. The unproven queries have 560–918 candidate vertices, and no efficiency query has more than 1,502, so the size caps of § 5-C never apply in this setting (Table XIV).

GraphSettingLCCUBLCC/UBCandidatesThresholdsNodes
Friendsterdefault1472120.69358722/25519,058
Friendsterdefault3053360.90756083/84263,320
Friendsterdefault3743980.93973869/78102,156
LiveJournal2×2\times scale5525780.95580334/3560,421
Orkut2×2\times scale7197320.982918154/85170,370
Pokecdefault1692450.68962277/83539,455
Pokecdefault1792460.72764573/79417,817
Pokecdefault1892530.747578323/484551,931
Pokecdefault3693940.936787379/539199,822

Table XIV. The nine efficiency queries that Exact leaves unproven within 60 s.

Scalability: On Friendster, with 65.6 million vertices and 1.8 billion edges, Exact proves 98.5% of the queries. It takes 1.9 s on average, with a median of 0.9 ms and a 90th percentile of 2.0 s. On the queries with an LCC, the median is 352 ms and its 90th percentile (p90 in Table II) is 7.9 s, whereas extracting qq’s kk-core component takes a median of 70.5 s. The hardest graph is Pokec (median 861 ms, p90 21.6 s for queries with an LCC). The graph GθG_{\theta} keeps 10–61% of the edges. The index is built once per tolerance assignment, in 5 ms (Brightkite) to 9.7 s (Orkut), and in 4.7 minutes on Friendster.

Abllation and parameters: On the 50 queries of the k=3k = 3 sample on LiveJournal and Orkut, Exact solves every query within the limit. Best-first order, conflict colouring and rule (3) each contribute, and rule (3) the most. Sweeping in non-increasing order of ∣S(τ)∣|S(\tau)| instead of best-first (count order) leaves 6% and 8% of these queries unproven; colouring in index order instead of by conflicts leaves one query (2%) each; and dropping rule (3) of Lemma 5 leaves 12% each. Without the index, the median query region on LiveJournal grows from 7 to 29 vertices and the median time from 0.07 to 0.48 ms. Without any reductions or pruning, every query processes qq’s entire kk-core component (2.7 and 3.0 million vertices), and 12% and 14% of the queries reach the limit. Across k∈{2,…,5}k \in\{2,\ldots,5\}, vertex samples of 25–100% and m∈{2,4,8,16,32}m \in\{2,4,8,16,32\} dimensions, the median time over all queries stays below 0.5 ms on LiveJournal and 19 ms on Orkut (below 96 and 525 ms over those with an LCC), and no query reaches the limit. The tolerance scale ss matters most. At half the calibrated ss, almost no LCC exists (0% and 4% of the queries). At twice and three times the calibrated ss, most queries have one (68–88%), and at twice the calibrated ss, Exact leaves one query unproven on each graph.

Solver comparison: We compare solvers for the fixed-threshold subproblem in a common Python framework that uses the count-order sweep and exchanges only this solver. Our branch and bound proves 96.5% of the 200 default queries per graph on LiveJournal and Orkut, against 72.5–90.5% for the other solvers (Table III, which also gives the shares among the queries with an LCC found by some solver). It also proves every query that any other solver proves, and all solvers agree on every proven optimum. Besides the sweep, the framework fixes the reductions, the cap on searched sets, the time limit of 60 s and the initial incumbent. The alternative solvers are our C++ reimplementation of AdvMax, the maximum (k,r)(k,r)-core algorithm of Zhang et al. [3], adapted to contain qq and run with its own and with a simple branching order; a mixed-integer program with flow-based connectivity, solved by HiGHS [54]; and the same model in CP-SAT [55]. All solvers, including a separate C++ copy of our branch and bound, run single-threaded inside this Python framework, so only relative times are meaningful; 150 of the queries also appear in Table II. On hard queries, which take our solver at least 100 ms and are proven by both solvers of a pair (12–28 per pair), the other solvers are slower by median factors of 5.7 to 175. On queries of 1–100 ms, the AdvMax implementations match our branch and bound (median ratios 0.93–1.05), and below 1 ms the others are about twice as fast, a difference of microseconds.

SolverProven LJProven Ork.Proven, LCC LJProven, LCC Ork.Slowdown LJSlowdown Ork.
Branch and bound (ours)96.596.592.693.911
AdvMax, simple branching90.580.580.066.15.77.2
AdvMax89.576.577.959.114.014.6
MILP (HiGHS)90.580.080.065.226.721.2
CP-SAT86.072.570.552.217545.0

Table III. Solvers in the count-order sweep: queries proven optimal (%) and median slowdown against ours on hard queries.

Against a single threshold: Once the index is built, sweeping personal tolerances costs no more per query than a single-threshold search in our engine. On the 200 queries of Table III, we compute the maximum (k,r)(k,r)-core containing qq. At the median tolerance, it times out on 71 queries on Orkut and 19 on LiveJournal, where best-first Exact proves all 200. At the LCC’s own threshold τ∗\tau^*, run on the 115 and 95 queries with an LCC, it times out on 37 and 16. For queries with an LCC, the sweep is faster on 92–94% of the queries on Orkut (median time ratios 0.065 and 0.135). On LiveJournal, where the sweep answers most of the 200 queries in under 1 ms, the two searches take similar times (median ratios 0.86–0.89, with a 1 ms floor). Only the sweep needs the index, and on LiveJournal its construction would dominate if amortized over 200 queries (Section A-F). A single threshold also ignores the personal tolerances in the candidate region, and the single-threshold answers satisfy (iii) on at most 4.2% of the queries.

Heterogeneity: Heterogeneous tolerances are what separate LCCs from (k,r)(k,r)-cores. With equal tolerances (σ=0\sigma= 0), the LCC coincides with the (k,r)(k,r)-core at the same threshold on all 220 queries of LiveJournal and Orkut on which Exact and the exact (k,r)(k,r)-core and pairwise searches all finish. Exact then has a single threshold to sweep; in count order, it reaches its limit on 0.5% (LiveJournal) and 45% (Orkut) of the 200 queries per graph, against 14% and 26.5% at σ=0.2\sigma= 0.2 and 4% and 7% at the default σ=0.4\sigma= 0.4 (Table X); the copy of our solver in Table III leaves 3.5% unproven there. From σ=0.2\sigma= 0.2 on, (k,r)(k,r)-cores at the LCC’s threshold satisfy (iii) on at most 9% of the queries, and 12–65% of their members face another member beyond their own tolerance.

σ\sigmaWith LCC LWith LCC OExact limit LExact limit O(k,r)(k,r)-core at τ\tau: (iii) holds L(k,r)(k,r)-core at τ\tau: (iii) holds O(k,r)(k,r)-core at τ\tau: Members L(k,r)(k,r)-core at τ\tau: Members O(k,r)(k,r)-core at τ\tau: Size/LCC L(k,r)(k,r)-core at τ\tau: Size/LCC OPairwise (iii) holds LPairwise (iii) holds OGlobal (k,r)(k,r) Members LGlobal (k,r)(k,r) Members O
0.076.585.50.545.0100.0100.0001.001.00100.0100.000
0.270.074.514.026.58.64.712231.251.504.10.62738
0.4 (default)47.557.54.07.04.20.031431.802.195.62.34044
0.639.044.00.53.02.61.143522.542.937.13.14547
0.830.533.00.00.01.60.049612.723.879.02.74749
1.021.027.50.00.02.41.855653.504.2111.16.94948

Table X. Heterogeneity sweep on LiveJournal (L) and Orkut (O), count-order sweep.

Tolerances that span communities enlarge the search: Once tolerances let LCCs span several communities, the candidate regions grow by up to two orders of magnitude. The calibrated scales of § 6-A were chosen to yield LCCs with a median of at least 10 members. Here we consider tolerances of cc times the median distance between friends; since most friends lie in different communities, c≥0.75c \ge0.75 (Orkut) or c≥1c \ge1 (LiveJournal) lets LCCs span several communities. On Orkut, the queries with an LCC have a median of 8,360 candidate vertices at c=0.75c = 0.75 and 210,146 at c=1c = 1, whereas no efficiency query has more than 1,502;

on LiveJournal at c=1c = 1, the median is 1,218 (Section A-E). In these settings, Exact reaches the time limit on 35–99% of the queries with an LCC, and 0–1.7% stop at a cap. The bounds are then looser: the median ratio of the returned solution to the bound is 0.03–7.6%. At c=1c = 1, Exact proves only 64% (LiveJournal) and 20% (Orkut) of these queries, and for c=0.5,0.75,1,1.5c = 0.5, 0.75, 1, 1.5 and 2, 100%, 100%, 64%, 15% and 3% on LiveJournal and 100%, 51%, 20%, 3% and 0.6% on Orkut (Table XI). At the calibrated scale, drawing the queries from the whole kk-core rather than from groups of at least 20 members still leaves no query unproven. Larger caps and time limits do not close the gap (§ 5-C). We test them at c=1c = 1 on both graphs and at c=0.75c = 0.75 on Orkut: raising the cap on searched sets to 20,000 or 50,000, or the root-bound cap to 100,000, changes the proven share by at most +1.1 pp; letting Greedy use all thresholds lowers it by up to 3.3 pp; and a limit of 300 s proves only 0–9% of the remaining queries (Table XII).

GraphSettingLCCProven (%)Limit (%)Size cap (%)Solution/bound (%)
LiveJournalc=0.5c = 0.5153100.00.00.0–
LiveJournalc=0.75c = 0.75153100.00.00.0–
LiveJournalc=1c = 115364.135.30.70.33
LiveJournalc=1.5c = 1.515015.384.00.70.04
LiveJournalc=2c = 21193.495.01.70.03
Orkutc=0.5c = 0.5177100.00.00.0–
Orkutc=0.75c = 0.7517750.848.01.10.91
Orkutc=1c = 117719.879.70.60.18
Orkutc=1.5c = 1.51613.196.30.60.40
Orkutc=2c = 21770.699.40.07.6
LiveJournalqq from the kk-core91100.00.00.0–
Orkutqq from the kk-core92100.00.00.0–
LiveJournalmixing μ=0.1\mu= 0.180100.00.00.0–
LiveJournalmixing μ=0.2\mu= 0.268100.00.00.0–
LiveJournalmixing μ=0.4\mu= 0.442100.00.00.0–
Orkutmixing μ=0.1\mu= 0.1103100.00.00.0–
Orkutmixing μ=0.2\mu= 0.283100.00.00.0–
Orkutmixing μ=0.4\mu= 0.451100.00.00.0–

Table XI. Synthetic settings: scale, query sampling and community mixing.

Setting (LCC)C0cap 20,000cap 50,000root 100,000Greedy all τ\tau300 s: proven / unproven under C0
LiveJournal c=1c = 1 (153)64.164.164.164.160.85 / 55
Orkut c=0.75c = 0.75 (177)50.851.452.050.848.61 / 87
Orkut c=1c = 1 (177)19.820.320.319.819.80 / 142

Table XII. Proven share (%) of the queries with an LCC when one cap or the time limit changes (200 queries per setting).

Dynamics on Returned Groups

In closed groups, the bound keeps every accepted interaction, whereas groups without it, including pairwise groups, lose some under uneven influence. Outside ties make groups of every method lose interactions, LCC groups less often on Gowalla and Brightkite. We run the dynamics of Section IV on the groups that each method returns for queries with an LCC. These are a random 1,000 of the meetup queries of § 6-D on Gowalla, all 462 on Brightkite, and the 95 and 115 default queries of Table III on LiveJournal and Orkut; for pairwise, we also include the 3, 2, 12 and 14 groups of queries without an LCC. Interactions follow the edges of G[H]G[H] for at most 300 steps. We test whether any initially accepted interaction is later refused. In addition to equal-weight HK (1), the variants in Table IV draw each member’s weights from a Dirichlet distribution with α=0.1\alpha= 0.1, which concentrates them on a few neighbours, or let random adjacent pairs move towards each other (Deffuant–Weisbuch gossip [32]). Randomized variants run 10 times, and a group counts as losing an interaction if any run does. These variants serve as stress tests between equal weights and the weights in the proof of Proposition 2(b), which put almost all of a member’s weight on one neighbour.

MethodEqual GEqual BEqual LEqual OConcentrated GConcentrated BConcentrated LConcentrated OGossip GGossip BGossip LGossip O
LCC (Exact)000000000000
Pairwise000040333240171137
(k,r)(k,r)-core at τ\tau151713414491973440646985
Size-matched SAC58125256899839406386

Table IV. Groups (%) that lose an interaction accepted at the start, on G[H]G[H] (G, B, L, O: Gowalla, Brightkite, LiveJournal, Orkut).

Closed groups: No group satisfying (iii) loses an accepted interaction in 83,594 group–variant pairs across 11 variants, including complete interaction graphs, as Theorem 1 predicts. Under SJT dynamics (2), none of 15,392 shows a new rejection. The zero counts check the implementation against the theorem; the other rows of Table IV compare groups without its guarantee. Even with equal weights, groups found without tolerances lose accepted interactions: 4–17% of the (k,r)(k,r)-cores at τ\tau do. With uneven influence, this happens much more often (34–98%). With equal weights, pairwise groups never lose an accepted interaction, although 62–98% violate (iii) and fall outside Theorem 1. Under gossip, 3–17% lose one, as do 32–40% under concentrated weights. When a pairwise group loses an interaction, usually a single pair is affected: the median share of refused interactions is at most 0.3%. On Gowalla and Brightkite with concentrated weights, refusal occurs mostly in the first step, and acceptance resumes in about 99% of cases. Refusals start mostly at the least tolerant members, whom the LCC tends to leave out. In 73% and 94% of the refusals, the refuser is among the three least tolerant members. The LCC of the same query excludes the refuser, the refused member or both in 84% and 82% of them, while these pairwise groups have a median of 22.5 and 5 members outside the LCC (Section A-B). Consensus is about as frequent in these groups as in LCC groups. Per run rather than per group, pairwise groups lose an interaction in 1–5% of the runs under gossip and 5–13% under concentrated weights, against 23–67% and 32–90% for (k,r)(k,r)-cores at τ\tau and size-matched SAC groups. If the tolerances that drive the dynamics deviate from those used in the search by a factor exp⁡(0.3Z)\exp(0.3Z) with standard normal ZZ, 0–3.5% of the LCC groups lose an interaction, against 0.9–4.1% of the pairwise groups and 25–38% of the (k,r)(k,r)-cores at τ\tau.

LCC or pairwise: The LCC bound trades group size for robustness to uneven influence. Pairwise groups are at least as large by definition, since every LCC satisfies the pairwise condition. Where both are proven optimal (Table VIII), the pairwise group is larger for 60%, 61%, 93% and 97% of the queries on Gowalla, Brightkite, LiveJournal and Orkut, with a median per-query size ratio of 1.08–1.52. In exchange, LCC groups lose no accepted interaction in Table IV, whereas pairwise groups do under uneven influence. This is the distinction drawn in Section III: the pairwise condition suffices when positions remain fixed (Proposition 2(a)), as in a one-off meetup, whereas for groups that interact repeatedly with unknown weights, only (iii) guarantees acceptance for every weighting.

GraphQueriesLarger (%)Size ratioConcentrated AnyConcentrated Per runGossip AnyGossip Per runFollow one AnyFollow one Per run
Gowalla2,46960.41.0840.413.216.65.16.91.9
Brightkite46260.81.0933.48.110.62.97.81.5
LiveJournal8793.11.3331.84.82.80.80.00.0
Orkut10297.11.5239.57.87.01.70.80.2

Table VIII. LCC AGAINST PAIRWISE GROUPS: SIZES, AND PAIRWISE GROUPS (%) THAT LOSE AN ACCEPTED INTERACTION ON G[H]G[H].

Open groups: We add outside influence to test the closed-group assumption. Each accepted outside friend gets weight ww, against weight 1 for the member itself and for each accepted group neighbour. On Gowalla and Brightkite, LCC groups lose an interaction less often than both size-matched SAC groups (by 3.6–16.9 pp) and pairwise groups (by 2–7 pp) at every w>0w > 0, but not on Congress (Section VI-E); on the synthetic graphs, where accepted outside friends lie in the same community, no LCC group loses one even at w=1w = 1. When members average with accepted outside neighbours at fixed positions, Proposition 3 preserves acceptance under conditions (a) and (b), but only 4.6% and 2.6% of LCC groups on these datasets meet them, mainly because accepted outside friends extend the hull K0K_0 of Proposition 3 beyond θmin⁡\theta_{\min}. Already at w=0.01w = 0.01, 34% and 23% of the LCC groups lose an interaction accepted at the start, and at w=1w = 1, 65% and 62% do; no group that satisfies the conditions ever does. The loss is small and occurs early: it starts at a median step of 1 and affects a median 0.4–12% of the initially accepted interactions (Table XIX). Consensus is rare for open groups of every method (at most 5.3%).

GowallaBrightkiteCongress
ww0.010.110.010.110.010.11obs.
Groups that lose an interaction (%)34.148.465.222.537.762.10080.698.2
lost share (median, %)4.08.511.00.411.810.8––2.15.3
first loss (median step)111111––21
Largest final cluster (mean, %)23.517.716.824.018.018.871.611.85.23.9
Largest cluster, LCC − size-matched SAC (pp)−1.0+0.8+0.9−1.4+0.4+0.3−4.7−1.5−0.3−0.4
95% CI[−1.7,−0.3][0.4,1.2][0.5,1.2][−2.4,−0.3][−0.0,0.9][−0.1,0.7][−6.4,−3.1][−2.3,−0.8][−0.4,−0.1][−0.5,−0.3]

Table XIX. Open LCC groups: losses and final opinion clusters.

Meetups: What Member-Specific Tolerances Change

On real positions, we ask what member-specific tolerances change and what enforcing them costs. Groups found without tolerances often leave a member’s home beyond another member’s travel radius, while enforcing every member’s tolerance causes no measurable loss of co-visits relative to spatial communities of the same size. Here θv\theta_v is a travel radius. A meetup needs only the pairwise condition of Section III, which (iii) strengthens, so these data do not test the dynamics of Section IV. We replicate the Gowalla and Brightkite application on the Yelp Open Dataset [56]. We keep the users with at least 10 reviews up to 2017 whose home lies in one of 11 metropolitan areas, and the friendships between users of the same area (66,412 users, 293,785 friendships). As for check-ins, a user’s home is the median position of the reviewed businesses in the user’s most frequent cell of about 25 km, and θv\theta_v is the median distance of the reviewed businesses from home, at least 1 km. Two users co-visit if they check in at the same venue on the same day (Gowalla, Brightkite) or review the same business in the test year 2019 (Yelp; 2018 serves for validation). Homes, tolerances and design choices use only the training and validation periods, except the Yelp time split, chosen by the share of all friend pairs that co-visit in the test period (3.9%, above a minimum of 0.5%), which involves no method’s groups; the validation-period share (6.8%) gives the same split, and a second split ending in 2018 gives the same interpretation (Section A-I). Every test-active user in the kk-core is a query, with k=3k = 3: 15,829, 5,260 and 10,363 queries, of which 2,469, 462 and 5,010 have an LCC. Yelp produces much larger LCCs, with a median of 370 members against 16 and 10, and Exact proves 94.8% of its queries within 60 s. An

LCC differs from a kk-core only where tolerances are narrow relative to the spread of positions, as travel radii are: when we placed Yelp users at the mean category profile of their reviewed businesses, with tolerances defined in the same way, 99.9% of the friend pairs accepted each other and the LCC was almost the whole kk-core (median size ratio 0.998).

T**olerance violations: Groups found without tolerances leave many members with another member’s home beyond their estimated travel radius. In groups of at most 3,000 members on Gowalla, Brightkite and Yelp, only 7%, 2% and 27% of the members of SAC groups have every other member’s home within their radius; the shares are 29%, 42% and 42% for global (k,r)(k,r)-cores and 65%, 72% and 84% for (k,r)(k,r)-cores at τ\tau. All members of LCC and pairwise groups do, by construction. Condition (iii) is stricter: on the Gowalla queries with an LCC, it holds for 39% of the pairwise groups, 57% of the (k,r)(k,r)-cores at τ\tau and 33% of the size-matched SAC groups, which are larger (median 22, 27 and 22 members, against 16).

Co-visits: Enforcing every member’s tolerance causes no measurable loss of co-visits relative to spatial communities of the same size on Gowalla, Brightkite and Yelp. Where both groups exist, LCC groups have a higher raw share of co-visiting member pairs than size-matched SAC on all three datasets, mainly owing to size (Figure 3 and Table XV). We control for size in two ways, developed on Gowalla and Brightkite and replicated on Yelp: (a) on the 610, 108 and 2,387 queries where SAC and LCC groups have equal size but different members, and (b) by regressing the difference on the log ratio of the two sizes. Against size-matched SAC, we count a difference only when both CIs exclude 0, and no dataset meets this test: both CIs contain 0 on Gowalla and Brightkite, and on Yelp, the CI of (a) contains 0 while that of (b) lies just above it, with an intercept of +0.04 pp. On Gowalla, Brightkite and Yelp, the CIs of (a) and (b) exclude losses of more than about 0.25, 0.5 and 0.01 pp, respectively, while 8.4%, 5.7% and 1.7% of the member pairs in LCC groups co-visit. A second measure, the share of members who co-visit with anyone in the group (Figure 3, right), favours LCC groups at equal size on Brightkite and Yelp, but not on Gowalla. Against (k,r)(k,r)-cores at τ\tau, LCC groups are ahead at equal size only on Yelp (+0.08 pp [0.04, 0.11] in pair rate, by (b)). Across k∈{2,…,5}k \in\{2,\ldots,5\} and tolerances at the 70th and 90th percentiles (on Yelp, 2,000 queries per setting), the raw differences against size-matched SAC and (k,r)(k,r)-cores at τ\tau retain their sign on all

Figure 3. LCC minus size-matched SAC in co-visit shares (pp, 95% CIs): raw, at equal size with other members (a), and size-adjusted (b, for pairs only).

GowallaBrightkiteYelp
Pairs, raw+0.75 [0.50,0.99]+0.56 [0.15,1.01]+0.14 [0.11,0.18]
(a) same size+0.44 [−0.15,1.02]+0.74 [−0.28,1.74]+0.03 [−0.01,0.08]
(b) adjusted+0.01 [−0.24,0.24]−0.05 [−0.49,0.47]+0.04 [0.00,0.08]
Members, raw−1.35 [−1.83,−0.87]+0.12 [−0.84,1.08]+1.03 [0.84,1.22]
(a) same size−0.30 [−1.52,0.99]+2.86 [0.96,4.79]+0.84 [0.61,1.06]
Queries, all / (a)2,469 / 610462 / 1085,010 / 2,387

Table XV. The values of Fig. 3 (pp, 95% bootstrap CIs).

three datasets (on Gowalla and Brightkite, as unpaired means). Within tolerance-agnostic groups, whether members who can reach everyone co-visit more depends on the dataset and the baseline once eccentricity and activity are controlled for.

Against pairwise groups: Relative to the pairwise condition, enforcing (iii) costs co-visits on Gowalla by a size-adjusted estimate that extrapolates, since size cannot be held fixed here. On Gowalla and Brightkite, raw differences favour LCC groups: the two groups are identical for 38% of the queries, and on the 60% and 61% where the pairwise group is larger, its member pairs co-visit less often (LCC minus pairwise +1.49 pp [1.08, 1.95] and +1.77 pp [1.12, 2.50]). The size-adjusted difference (b) is nevertheless −0.85 pp [−1.35, −0.37] on Gowalla, −0.29 pp [−0.69, 0.11] on Brightkite and −0.05 pp [−0.12, 0.02] on Yelp, whose CIs exclude 0 at k=4k = 4 (−0.31 pp) and with 90th-percentile tolerances (−0.13 pp); as equal-size groups are almost always identical (Gowalla, Brightkite) or rare (36 of 4,951 Yelp queries), (b) extrapolates here (Section A-A).

Yelp as a weaker test of travel radii: On Yelp, whether friends co-visit in the validation year is unrelated to the distance between their homes (Spearman −0.009 [−0.026, 0.008], against −0.152 on Gowalla), so the interpretation of θv\theta_v as a travel radius is weaker there than for check-ins, although adding the pair’s tighter tolerance to a distance-only model of friends’ co-visits still lowers the held-out log loss (by 0.0029 [0.0020, 0.0039] per pair).

An empty LCC: The absence of an LCC usually reflects a constraint already imposed by accepted friendship edges. An LCC is absent for most queries (84.4%, 91.2% and 51.7% on Gowalla, Brightkite and Yelp). For 95%, 97% and 86% of these queries, even the kk-core of qq’s component restricted to friendships whose two ends accept each other is empty, so qq has no kk connected friends who accept one another. Only 1.8%, 0.6% and 4.4% of them have pairwise groups but no LCC (Table XVII). An empty answer thus usually tells a user that qq lacks such friends. Only a smaller kk or wider tolerances could change this, and even tripling every tolerance gives an LCC to only 22%, 16% and 50% of these queries. Conversely, shrinking every tolerance by 20% keeps an LCC for 80%, 80% and 87% of the queries that have one, at a median 82%, 89% and 69% of its size (Table XVIII). On Gowalla and Brightkite, an empty LCC is informative: SAC groups co-visit more when an LCC exists, by +4.1 pp [3.4, 4.9] and +3.1 pp [1.9, 4.5] in a regression on log size, and global (k,r)(k,r)-cores show the same direction (+0.74 pp [0.09, 1.42] and +1.12 pp [−0.35, 2.51] without size adjustment). On Yelp, the raw difference is a size effect: SAC groups are much larger when the LCC is empty (median 742 against 75 members), and controlling for log size reverses the raw difference (+2.09 pp) to −0.25 pp [−0.39, −0.11]. Descriptively, the Yelp difference is positive for SAC groups of up to 20 members (+2.3 and +0.9 pp) and close to zero for larger ones, and for global (k,r)(k,r)-cores it remains positive after the control (+0.08 pp [0.01, 0.16]); the share of SAC members who co-visit with anyone in the group points in different directions (raw: +0.8 and +5.4 pp on Gowalla and Brightkite, −3.9-3.9 pp on Yelp, where it stays negative after the control). On two datasets out of three, an empty answer thus marks queries lacking a cohesive group satisfying (iii), for which groups found without tolerances also tend to meet less.

DataQueriesNo LCCABCU70th90thNo LCCABCU
Gowalla15,82913,360 (84.4%)95.03.21.8015.035.654.785.111.83.10
Brightkite5,2604,798 (91.2%)96.72.60.6010.033.360.881.714.33.90
Yelp10,3635,353 (51.7%)86.37.84.41.523.549.726.167.415.99.67.1
Congress47218 (3.8%)1422012/1816/18–––––

Table XVII. QUERIES WITHOUT AN LCC (k=3k = 3) BY CAUSE, AND WITH RAISED TOLERANCES.

ssLCC (%)Proven (%)SizeABCUKept (%)Gained (%)Share (%)vs. s=1s = 1 (pp)
\multicolumn{12}{l}{Gowalla (15,829 queries)}
0.57.9100.0914,204244129050.7 (0.58)–11.12+3.73 [3.15,4.40]
0.6710.5100.01013,617392159067.3 (0.67)–9.44+1.86 [1.52,2.26]
0.812.5100.01113,237424194080.0 (0.82)–8.84+1.30 [1.03,1.59]
115.6100.01612,6914232460––8.42–
1.2519.3100.02211,9425572700–4.47.33−1.29 [−1.57,−1.03]
1.522.7100.02711,4315522520–8.46.67−2.18 [−2.51,−1.87]
227.3100.04010,6575832740–13.85.93−3.09 [−3.50,−2.69]
333.9100.0539,6835632240–21.65.13−3.84 [−4.28,−3.41]
\multicolumn{12}{l}{Brightkite (5,260 queries)}
0.54.5100.084,970486051.1 (0.78)–8.58+1.18 [0.34,2.13]
0.675.9100.084,8497722067.5 (0.80)–7.56+0.68 [0.18,1.21]
0.87.1100.084,76210621080.3 (0.89)–6.44+0.24 [−0.08,0.59]
18.8100.0104,640127310––5.67–
1.2511.0100.0124,473146620–2.44.32−1.35 [−1.91,−0.85]
1.512.9100.0134,326172850–4.53.60−2.11 [−2.74,−1.52]
217.1100.0164,088175950–9.23.15−3.19 [−4.18,−2.32]
323.5100.0243,746186920–16.12.52−3.75 [−4.80,−2.79]
\multicolumn{12}{l}{Yelp (2,000 queries)}
0.529.799.9144.51,2827941461.6 (0.32)–2.53+1.07 [0.90,1.26]
0.6736.799.72171,11796381576.1 (0.52)–2.26+0.71 [0.59,0.84]
0.842.299.52711,02074511187.4 (0.69)–1.97+0.39 [0.28,0.49]
148.295.7379700684813––1.70–
1.2553.888.9477792783421–10.71.59−0.25 [−0.32,−0.18]
1.558.187.1549692883127–19.21.44−0.43 [−0.52,−0.35]
265.084.9679572713424–32.51.19−0.70 [−0.82,−0.60]
374.284.0824402673315–50.20.98−0.88 [−1.01,−0.76]

Table XVIII. TOLERANCE SCALING: EVERY TOLERANCE MULTIPLIED BY ss.

Figure 4. Groups for one Congress query (k=3k = 3).

Positions from Votes: Two Parliaments

Opinion positions are rarely observed alongside a network. We illustrate the method using the 474 members of the 117th U.S. Congress, then repeat the main analyses on the European Parliament. Positions are the first dimension of DW-NOMINATE [57], [58], estimated from roll-call votes; θv\theta_v is the median distance from vv to the sponsors of the bills that vv co-sponsored from January 2021 to February 8, 2022 [59] (median 0.145, floor 0.02, which no member reaches); and GG joins members who retweeted, quoted, replied to or mentioned each other on Twitter between February 9 and June 9, 2022 [60], [61] (10,188 edges). Positions derive from votes and tolerances from co-sponsorship, rather than measured attitudes. With strong party discipline in Congress, the results concern only this setting. Tolerances do filter: 42.7% of the adjacent pairs accept each other, an LCC exists for 96.2% of the 472 queries, and its median size is 12% of that of qq’s kk-core component.

Premise test: The premise test asks whether co-sponsorship tolerances predict Twitter interactions beyond ideological distance. They do not. In a logistic model of whether uu interacted with vv, with sender and receiver effects, a spline in the distance, and indicators of the same party, state and chamber, the coefficient of 1[d(xu,xv)≤θu]1[d(x_u,x_v) \leq\theta_u] is −0.044-0.044 (one-sided permutation p=0.92p = 0.92, permuting tolerances within party and chamber), and it does not improve the held-out log loss. Members with wider co-sponsorship radii interact over wider ranges (Spearman 0.71 [0.65, 0.76]; 0.63 [0.56, 0.68] controlling for party, chamber and centrality), but the cutoff at θu\theta_u adds nothing beyond distance and fixed effects, so this tolerance estimate is not validated on Twitter. A possible explanation, which we do not test, is the adversarial nature of some replies and mentions; Luan et al. [38] find more cross-ideological exchanges in reply ties than follows. Of the other tolerance variants, only 90th-percentile tolerances yield a significantly positive coefficient (0.32, p=0.001p = 0.001).

Static violations and dynamics: Groups found without tolerances often contain members who face someone beyond their own tolerance (391 of the 454 size-matched SAC groups; 4.9%, 8.2% and 56.7% of the members of (k,r)(k,r)-cores at τ\tau, size-matched SAC groups and global (k,r)(k,r)-cores; Table V); pairwise groups contain none by definition, but only 0.7% of them satisfy (iii). Table V also gives the groups satisfying (iii) and the member pairs with at least one refusal. In closed dynamics, no LCC group loses an interaction accepted at the start, as Theorem 1 predicts. Pairwise groups never do under equal weights or under weights proportional to the observed Twitter interactions, but 26–47% do under concentrated weights, gossip, and updates that follow one random accepted neighbour, as do 33–49% of the size-matched SAC groups and (k,r)(k,r)-cores at τ\tau; global (k,r)(k,r)-cores lose an interaction in 33% of the cases even under equal weights. No LCC group satisfies the conditions of Proposition 3; in open dynamics, none loses an interaction for w≤0.1w \leq0.1, but 22%, 41% and 81% do at w=0.2,0.5w = 0.2, 0.5 and 11, and 98% with observed weights. Unlike on Gowalla and Brightkite, LCC groups here lose an interaction more often than size-matched SAC groups at every w≥0.2w \geq0.2 (22% against 11% at w=0.2w = 0.2), and more often than pairwise groups at w=0.2w = 0.2 and 0.5. Because the premise test fails, these results illustrate simulated dynamics on real ideological positions; they do not establish how legislators respond to one another. Fig. 4 shows a median-sized query: of the 391 of 454 queries (86%) whose size-matched SAC group has a member facing another beyond its interval, the one whose LCC size is nearest the median (ties: lowest id); it illustrates Table V.

Co-sponsorship: In the test period (June 10, 2022 to January 3, 2023), the share of member pairs who co-sponsor a bill is not measurably higher in LCC groups than in size-matched SAC groups: +0.39 pp [−0.13, 0.92] raw, −0.30 pp [−1.03, 0.43] at equal size with other members, and +0.36 pp [−0.16, 0.91] size-adjusted; as about two thirds of the member pairs and 99.9% of the members of LCC groups co-sponsor with each other, this measure discriminates poorly.

A second parliament: On the European Parliament of 2014–16 [62] (roll-call positions, tolerances from earlier retweets), the premise test is again negative (−0.07-0.07, p=0.78p = 0.78);

Method(iii) holdsMembersPairs
LCC (Exact, Greedy, BallCore-F)10000
Pairwise0.700
(k,r)(k,r)-core at τ\tau15.64.91.3
Size-matched SAC2.28.21.5
SAC87.114.314.2
Global (k,r)(k,r)-core1.756.719.1
BallCore-R0.949.612.9
Random, kk-core, edge-accept010071.6–77.4

Table V. Tolerance violations in Congress groups (k=3k = 3, 472 queries).

only 90th-percentile tolerances give a positive coefficient (0.42, p=0.001p = 0.001, no held-out gain), a hint that acceptance may reach beyond the median distance. In size-matched SAC groups, 21% of the members face someone beyond their tolerance, and 21–52% of the groups lose an initially accepted interaction under unequal influence; no LCC group does.

Conclusion

Bounding group diameter by the smallest member tolerance connects community search to persistent acceptance: closed LCC groups preserve acceptance under bounded-confidence dynamics with any positive weights and avoid rejection under SJT dynamics, whereas the pairwise condition and other natural relaxations lose these guarantees. Finding a largest LCC is NP-hard even in the plane. LatSweep reduces the search to subproblems with a common threshold, refines their bounds best-first, and returns certificates of optimality or absence, or a bound on the remaining gap. Its exact variant answers most evaluated queries faster than extracting qq’s kk-core component, handles graphs with 1.8 billion edges, and returns an LCC of at least 0.689 times a proven upper bound on the efficiency queries stopped early. On real positions, groups found without tolerances often place a member’s home beyond another member’s travel radius, while enforcing every member’s tolerance causes no measurable loss of co-visits relative to spatial communities of the same size.

The guarantee is for closed groups: with outside ties, acceptance can be lost early for many groups, and once tolerances span several communities, exact search exceeds our 60 s budget on many queries (Sections VI-B and VI-C). LCCs are candidate groups, not verdicts on individuals; tolerances estimated from check-ins or reviews are noisy and should not be used to label or exclude individuals. Whether tolerances estimated from behaviour predict who interacts in opinion settings remains open; in two parliaments, median-based tolerances did not predict interaction beyond ideological distance (Section VI-E). Other open questions include learning task-specific tolerances from longitudinal traces, maintaining LCCs as graphs evolve, and approximating MAXLCC in fixed dimension.

Supplementary Results

This appendix provides supplementary tables for Section VI. The tables retain the runs reported in the main text; any change in sample or sweep order is stated explicitly.

Dynamics: All Variants and Methods

Tables VI and VII extend Table IV to all variants and methods, with the same abbreviations G, B, L and O; <1 marks shares above 0 and below 1%, and – marks runs not performed (edge-accept was not run on LiveJournal and Orkut). A group is counted in the SJT rows when it shows a new rejection. The last column of Table VI counts simulated LCC groups per variant, out of 1,000, 462, 95 and 115. Complete-graph and multi-run variants skip groups above a size cap (see Variants). Other methods have lower coverage because their larger groups are skipped more often (for gossip on Orkut, 37 of 115 (k,r)(k,r)-cores at τ\tau). For each method, the last row of both tables reports its groups under equal-weight HK on G[H]G[H]. The groups are those of Table IV: on Gowalla and Brightkite, 1,000 and 462 meetup queries with an LCC and 300 sampled queries without one, and on LiveJournal and Orkut, 200 default queries; the LCC, Greedy, (k,r)(k,r)-cores at τ\tau, size-matched SAC and random groups exist only for queries with an LCC, whereas the other methods may also return groups for queries without an LCC. BallCore-F returns subsets satisfying (iii), and no BallCore-F group loses an interaction in a closed variant. We omit the kk-core component because almost all its groups exceed 5,000 members, the largest group size we simulate.

Variants: HK (1) runs with equal weights, also for 3,000 steps with a stopping rule 10610^{6} times stricter, or with weights drawn in each run from a Dirichlet distribution with α=1\alpha= 1 or α=0.1\alpha= 0.1. In follow one neighbour, each move moves halfway towards one accepted neighbour drawn at random in each step; in gossip [32], a random edge interacts, and each end that accepts the other moves 0.3 of their distance towards it, for 100 rounds of ∣E(H)∣|E(H)| such steps (50 rounds on complete graphs). SJT (2) uses equal weights, θvacc=0.5 θv\theta_v^{acc}=0.5\,\theta_v, θvrej=θv\theta_v^{rej}=\theta_v and β=0.05\beta= 0.05; there we report new rejections, the event that Theorem 2 excludes. Randomized variants run 10 times (gossip on complete graphs 5 times), and a group counts if any run loses an interaction. On complete interaction graphs, every member hears every other; these variants run on groups of at most 1,000 members (equal weights, SJT, open), 300 (random weights, follow) or 100 (gossip), and the randomized variants on G[H]G[H] on groups of at most 2,000 members. The last three blocks test sensitivity to departures from the assumptions in Section IV. In open groups, members also average with the outside neighbours they accept, which stay fixed, with the same weight as accepted members (w=1w = 1 in Section VI-C; at most 200 outside neighbours per member, sampled at random); stubborn outsiders pull each member with weight λ\lambda towards the fixed mean of all its outside neighbours, near or far; with tolerance noise, the dynamics use θvexp⁡(νZv)\theta_v \exp(\nu Z_v) with standard normal ZvZ_v, whereas the groups were found with θv\theta_v.

Observations: In closed variants, no group returned by a method guaranteeing (iii) (LCC, Greedy) loses an interaction; a tenfold longer run leaves every entry unchanged. BallCore-R, whose sets need not satisfy (iii), loses interactions under uneven influence in up to 76% of its groups on G[H]G[H]. On complete interaction graphs, pairwise groups also lose interactions under uneven influence (up to 30%), and the (k,r)(k,r)-cores at τ\tau already under equal weights (18–54%). With stubborn outsiders, at least 77% of the groups of every method lose an interaction on the meetup graphs, whose outside friends lie in all directions; on the synthetic graphs at λ=0.01\lambda= 0.01, about 1% of the LCC groups do, against 52–68% of the (k,r)(k,r)-cores at τ\tau. Up to ν=0.2\nu= 0.2, tolerance noise barely affects LCC and pairwise groups (below 1%), while 16–39% of (k,r)(k,r)-cores at τ\tau lose an interaction.

Variant(k,r)(k,r)-core at τ\tau G(k,r)(k,r)-core at τ\tau B(k,r)(k,r)-core at τ\tau L(k,r)(k,r)-core at τ\tau OGlobal (k,r)(k,r)-core GGlobal (k,r)(k,r)-core BGlobal (k,r)(k,r)-core LGlobal (k,r)(k,r)-core OSAC GSAC BSAC LSAC OSize-matched SAC GSize-matched SAC BSize-matched SAC LSize-matched SAC ORandom GRandom BRandom LRandom O
Closed group, interactions on G[H]G[H]
HK, equal weights15174136033761832135812372700
HK, equal, 3,000 steps15174136033761832135812372700
HK, random weights, α=1\alpha= 12635436877815377264322422129385955452126
HK, random weights, α=0.1\alpha= 0.14144919786899999415678845256899864537569
Follow one neighbour3339587882817386304526413535486755451524
Gossip (DW)3440698583828193324738553940638657473931
SJT, new rejection2531929875719999284761832131859790899897
Closed group, complete interaction graph
HK, equal weights1823335459503956153113258141534534022
HK, random weights, α=1\alpha= 11831376962684376184017421728296565612937
HK, random weights, α=0.1\alpha= 0.12945899579879799315174833747889874688184
Follow one neighbour3643708977867896304440584548638867613939
Gossip (DW)2742547873817484284334534146508066613330
SJT, new rejection24299210071759999234467851930939778789397
Assumptions violated
Open group, G[H]G[H]75804128484596174411737951449370<1
Open group, complete73813355808739575872143170801544604623
Stubborn outsiders, λ=0.01\lambda= 0.01969952689799647692972429959938458077129
Stubborn outsiders, λ=0.05\lambda= 0.059810083909910097979799596095100798289864835
Stubborn outsiders, λ=0.1\lambda= 0.199100969799100991009899808499100959791888070
Tolerance noise, ν=0.1\nu= 0.11722163265581520173341091361044320<1
Tolerance noise, ν=0.2\nu= 0.2232721397065243420378121519914483703
Tolerance noise, ν=0.3\nu= 0.328352538747331402639101623291523514212
Groups (HK, equal, G[H]G[H])1,000462951159944281501621,2437451531781,000462951151,00046295115

Table VII. As Table VI: methods that ignore tolerances.

LCC or pairwise: Table VIII provides the results for the paragraph “LCC or pairwise” of § 6-C. It counts queries for which both LCC and pairwise groups exist and are proven optimal, the share where the pairwise group is strictly larger, and the median pairwise-to-LCC size ratio across these queries. The other columns give the pairwise groups (%) that lose an interaction accepted at the start, for the groups of Table IV: in any of 10 runs, as in Table IV, and on average per run; no LCC group ever does. Pairwise groups are strictly larger than LCCs for most queries, and under uneven influence they lose an accepted interaction in a few of their runs: on average 5–13% of the runs under concentrated weights, 1–5% under gossip, and at most 2% when each member follows one neighbour. On Gowalla and Brightkite, the pairwise group is the LCC itself for 938 of the 978 and 177 of the 181 queries on which the two have the same size (the paired co-visit difference on these is +0.14 pp [−0.03, 0.36] and 0.00 pp), and on the 1,491 and 281 queries on which it is larger (median 52 against 34 and 17 against 12 members), the LCC’s pair rate is higher by +1.49 pp [1.08, 1.95] and +1.77 pp [1.12, 2.50]. The size-adjusted difference (b) of § 6-D, a linear regression of the difference on the log size ratio, gives intercepts of −0.85 pp [−1.35, −0.37] and −0.29 pp [−0.69, 0.11]. The relation is far from linear: on Gowalla, the mean difference is +0.14 pp for log size ratios in [0, 0.25), +1.2 and +0.8 pp in [0.25, 0.5) and [0.5, 1), and +7.6 and +27 pp for the 67 and 32 queries with log ratios in [1, 2) and above 2, which set the slope; without the latter 99 queries, the intercept is +0.10 pp. On Brightkite, the intercept stays negative without the queries of log ratio at least 1 (−0.38 pp). The fitted line also misses the equal-size queries for size-matched SAC groups (+0.01 against +0.19 pp on Gowalla, −0.05 against +0.30 pp on Brightkite), so (b) is a coarse adjustment for every baseline, and with pairwise groups, whose equal-size groups are almost all the LCC itself, it rests on extrapolation. On Yelp, the pairwise group has the LCC’s size for only 36 of the 4,951 queries where both searches return a group (median 443 against 365 members; about 10% of the pairwise groups are not proven maximal within the limit or the cap on searched sets, so their sizes are lower bounds), so we compare them by the size-adjusted difference (b): −0.05 pp [−0.12, 0.02] at the default setting, −0.31 pp at k=4k = 4 and −0.13 pp with tolerances at the 90th percentile (both CIs below 0), and CIs containing 0 at k=2k = 2, k=5k = 5 and the 70th percentile.

Refusals in Pairwise Groups

Table IX examines the refusals behind the column of concentrated weights in Table IV on Gowalla and Brightkite. For the queries with an LCC, we replayed every run of the pairwise and LCC groups of that column with the same random streams and an instrumented copy of the simulator that records, for each directed interaction (vv accepts uu) accepted at the start, the first step at which it is refused; the replay reproduces the stored results of every group and run exactly, and no LCC group ever refuses an interaction. The table counts refused interactions over all runs; a refuser counts as the least tolerant member if its tolerance equals the group’s minimum (ties included), and as one of the three least tolerant if it is the least tolerant or its average rank from the least tolerant is at most 3 (tied members share their average rank).

GowallaBrightkite
Pairwise groups with a refusal402 of 1,000153 of 462
Refused interactions, all runs2,200592
Initial d/θvd/\theta_v, median [quartiles]0.55 [0.36, 0.73]0.55 [0.28, 0.77]
Initial d/θv≥0.9d/\theta_v \geq0.9 (%)8.911.8
Step of refusal, median11
Largest d/θvd/\theta_v, median1.081.10
Still refused at the end (%)1.21.0
Refuser is the least tolerant member (%)45.373.3
Refuser among the three least tolerant (%)72.993.9
Refuser outside the LCC (%)69.171.1
Refuser or refused outside the LCC (%)83.782.4
Pairwise members outside the LCC, median22.55

Table IX. REFUSED INTERACTIONS IN PAIRWISE GROUPS UNDER CONCENTRATED WEIGHTS (d=d(vx,vu)d = d(v_x,v_u); vv REFUSES uu).

At the start, refused interactions are not close to tolerance (median d/θvd/\theta_v of 0.55, and at least 0.9 for only 9% and 12%). Refusal occurs mostly at the first step. During the run, the largest distance excess over θv\theta_v has a median of 8% and 10%; by the end, all but about 1% are accepted again. The refuser is one of the three least tolerant members of the group in 73% and 94% of the refused interactions and is (or ties for) the least tolerant one in 45% and 73%; the least tolerant member is the one that bounds the diameter in (iii). In 84% and 82% of the refused interactions, the LCC of the same query excludes the refuser, the refused member or both, while the pairwise groups with a refusal have a median of 22.5 and 5 members outside the LCC. These refusals use simulated influence weights. Closed Congress dynamics with weights proportional to observed interactions produce no loss in any pairwise group (Section VI-E).

Figure 5 shows a median-sized case: among the 250 Gowalla groups of at most 80 members with a refusal, the group whose size is nearest the median of 33 (ties: lowest query), its first run with a refusal, and its earliest refused interaction. Positions are shown relative to the group centroid. Member uu (θu=15.3\theta_u = 15.3 km, outside the LCC) puts 99.8% of its weight on one neighbour, also outside the LCC, and moves 2.0 km in the first step; its distance to vv (θv=2.86\theta_v = 2.86 km, the second least tolerant of the 33 members, in the LCC of 27 members) grows from 0.50 to 1.004θv1.004 \theta_v and is back within θv\theta_v from the second step on. For the same query and run index, every adjacent pair in the LCC remains within 0.76 times its smaller tolerance.

Figure 5. A refusal in a Gowalla pairwise group: (a) homes and first moves; (b) worst adjacent pair per step.

Heterogeneity of Tolerances

Table X provides further results for the paragraph on heterogeneity in Section VI-B. It uses 200 default queries per setting and the count-order sweep (Exact 60 s, the other searches 10 s). For each σ\sigma, it gives the queries (%) with an LCC and those reaching the 60 s limit, out of all; for the other methods, columns (iii) holds, Members and Size/LCC give the groups (%) satisfying (iii), the mean share (%) of members who face another member beyond their own tolerance, and the median size relative to the LCC where both exist; Global (k,r)(k,r) is the heuristic (k,r)(k,r)-core search with the median tolerance. With equal tolerances, every (k,r)(k,r)-core at τ\tau and every pairwise group satisfies (iii), and their median size equals the LCC’s; Exact reaches the limit on 45% of the Orkut queries there, the setting in which the LCC is a maximum (k,r)(k,r)-core. As σ\sigma grows, fewer queries have an LCC, and the (k,r)(k,r)-cores at τ\tau grow to 1.25–4.21 times the LCC’s size (median) while at most 9% of them satisfy (iii). The reported time-limit shares use the count-order sweep; the best-first sweep is used in tbl:II.

Synthetic Robustness

Table XI provides further results for the paragraph on the tolerance scale and the proven share in Section VI-B, with 200 queries per setting and a 60 s limit. Column LCC counts the queries with an LCC; the next columns give shares (%) of these queries: proven, reaching the limit, and stopped at the cap on searched sets; the last column gives, for the queries reaching the limit, the median ratio (%) of the returned LCC to the proven upper bound. Here the mean tolerance is cc times the median distance between friends (106.9 on LiveJournal and 126 on Orkut, mostly between communities), without calibration on Exact; c=0.5c = 0.5 already corresponds to scales ss of 9.4 and 11.1, against the calibrated 1.5 and 1.25. We also draw queries uniformly from the whole kk-core instead of from groups of at least 20 members, and move a share μ\mu of the vertices to a random community. Where tolerances reach the scale between communities (c≥0.75c \ge0.75 on Orkut, c≥1c \ge1 on LiveJournal), 35–99% of the queries with an LCC reach the time limit and the bounds for these queries are loose; in the other settings, Exact proves every query.

Caps and Time Limit at the Scale between Communities

Table XII varies one parameter of Section V-C at a time on the three settings of Table XI where Exact starts to time out, with the same instances and queries: the cap on searched sets (default 3,000), the cap on the root bound (default 20,000), the number of thresholds Greedy tries for the initial incumbent (default 20), and, for the queries left unproven at the default (C0), a time limit of 300 s instead of 60 s. Raising a cap changes the proven share by at most +1.1 pp (two queries on Orkut at c=0.75c = 0.75); with a larger cap on searched sets, the queries that stopped at that cap under C0 (0.6–1.1%) reach the time limit instead. Letting Greedy try all thresholds lowers the share by 3.3 and 2.3 pp on LiveJournal at c=1c = 1 and Orkut at c=0.75c = 0.75, because the longer initial phase consumes part of the limit. Under a 300 s limit, Exact proves 5 of 55, 1 of 87 and 0 of 142 queries. Across configurations, the median returned-LCC-to-bound ratio remains 0.18–1.3%. Every configuration returns the same optimum wherever it proves one, in agreement with Table XI; the queries with an LCC have a median of 1,218 (LiveJournal), 8,360 and 210,146 (Orkut, c=0.75c = 0.75 and 1) candidate vertices, and each engine process uses at most 2.7 GB.

Sweep against a Single Threshold

Table XIII runs our engine on one threshold only, as a maximum (k,r)(k,r)-core search containing qq without personal tolerances, at the median tolerance of all vertices (the radius of the global baseline) and at the threshold τ∗\tau^* of the optimal LCC, which the single-threshold search does not know in advance; the latter is run only on queries with an LCC. Time ratios are computed per query with an LCC, flooring both times at 1 ms; the last column reports the share of these queries for which the sweep is faster. Query times exclude index construction, which the single-threshold search does not use. The index is built once per process; in this run it took 5.7 s on LiveJournal and 14.3 s on Orkut (a slower run than the 9.7 s of Section VI-B). On LiveJournal, where the sweep answers most queries in under 1 ms, amortizing this cost over 200 queries would raise the median ratio to about 39. The non-empty single-threshold answers satisfy (iii) on 0% of the queries at the median tolerance and on 4.2% (LiveJournal) and 0% (Orkut) at τ∗\tau^*.

GraphSearchProven non-emptyProven emptyLimitTime (ms)MedianSweep faster (%)
LiveJournalSweep (Exact)9510500.13––
LiveJournal(k,r)(k,r)-core at median θ\theta13150192.10.8955
LiveJournal(k,r)(k,r)-core at τ∗\tau^* (95 queries)79–166.20.8656
OrkutSweep (Exact)1158503.2––
Orkut(k,r)(k,r)-core at median θ\theta9633719590.06592
Orkut(k,r)(k,r)-core at τ∗\tau^* (115 queries)78–372,5860.13594

Table XIII. The sweep and single-threshold (k,r)(k,r)-core searches on the 200 default queries of Table III (60 s limit).

Unproven Efficiency Queries

Table XIV lists the unproven queries of Section VI-B, with the size of the returned LCC, the proven upper bound UB, their ratio (truncated), the candidate vertices (those with a non-empty survival interval), the thresholds evaluated out of all, and the branch-and-bound nodes. Every candidate set C(τ)C(\tau) is a subset of the candidate vertices, of which these queries have at most 918 and no efficiency query has more than 1,502, so the size caps of Section V-C never apply; the search explores 60,421–551,931 nodes without settling all thresholds. The bound pass after the limit, which query times exclude, takes at most 4 µs on these queries; on all other efficiency queries, it does not run.

Meetups

Table XV gives the values plotted in Figure 3: LCC minus size-matched SAC where both exist, in the share of member pairs that co-visit and of members who co-visit with anyone in the group: raw, on queries where SAC returns a group of the LCC’s size with other members (a), and as the intercept of a regression on the log size ratio (b).

Yelp on a Second Time Split

The split of Section VI-D (training up to 2017, validation 2018, test 2019) was chosen from the co-visit rate of all friend pairs in the test period; the validation-period rate (6.82%) and the number of validation-active users in the 3-core (12,351) lead to the same split. As a robustness check, we rebuilt the dataset on a split that ends before 2019 (training up to 2016, validation 2017, test 2018): 52,527 users, 246,633 friendships, 9,343 queries, of which 4,416 have an LCC (median 323 members; θv\theta_v median 4.07 km). Table XVI repeats the comparison with size-matched SAC groups on both splits; the two splits have different users, homes and graphs, so they are not paired. In pair rate, both splits give the same picture: the raw LCC advantage does not persist at equal size, as (a) and (b) do not both exclude 0. Against (k,r)(k,r)-cores at τ\tau, the size-adjusted difference (b) on the second split is +0.16 pp [0.12, 0.21] in pair rate and +0.71 pp [0.42, 1.01] in member rate.

Queries without an LCC and Tolerance Scaling

Table XVII provides the classification for the paragraph on empty LCCs in Section VI-D. At the median tolerance and on all queries, a query without an LCC is in class A if the kk-core of qq’s component restricted to friendships whose ends accept each other is empty, in B if it is not but no pairwise group exists, in C if a pairwise group exists but no LCC, and in U if the LCC or a pairwise search is not proven; columns A–U give shares (%) of the queries without an LCC (Congress: counts). The next two columns give the share of these queries that gain an LCC when every tolerance is the 70th or 90th percentile of the user’s distances, and the last five the share of queries without an LCC at the 90th percentile and its classes; raised tolerances use the 2,000 sampled queries of the parameter study, and on Congress the two columns count all 18 queries without an LCC. Raising tolerances to the 90th percentile gives an LCC to 605 of 1,698, 606 of 1,822 and 515 of 1,036 sampled queries without one. Queries of classes B and C almost all gain an LCC at the 90th percentile (B: 45 of 45, 50 of 51 and 67 of 68; C: 41 of 41, 8 of 8 and 47 of 48 on Gowalla, Brightkite and Yelp), but only 31–43% of class A do (519 of 1,612, 548 of 1,763 and 390 of 907). Newly obtained LCCs have median sizes of 21.5, 13 and 280 members at the 70th percentile, and 103, 42 and 522 at the 90th. On Yelp, 22 of 243 and 106 of 515 are not proven optimal, making their sizes lower bounds. Table XVIII provides the full tolerance-scaling results for the same paragraph, on the same queries at every ss (Yelp: 2,000 sampled queries) with Exact limited to 60 s. It gives the queries (%) with an LCC, the queries (%) proven within the limit, the median LCC size, and the queries without an LCC by class (Table XVII). For s<1s < 1, column Kept gives the share (%) of the queries with an LCC at s=1s = 1 that keep one, with the median size ratio of the kept LCCs in parentheses; for s>1s > 1, column Gained gives the share of the queries without an LCC at s=1s = 1 that gain one. The last two columns report the mean co-visiting share of member pairs in LCC groups and its difference from s=1s = 1, for queries with an LCC at both scales (pp, 95% bootstrap CI). Whenever both solutions are proven, increasing ss never shrinks an LCC (7 Yelp cases cannot be checked because a solution remains unproven). Larger tolerances give more and larger LCCs whose pairs co-visit less, and smaller ones fewer and smaller LCCs whose pairs co-visit more; all paired differences exclude 0 except on Brightkite at s=0.8s = 0.8. Class A dominates queries without an LCC at every ss. Shrinking tolerances also protects against noisy estimates: with tolerance noise ν=0.3\nu= 0.3 in equal-weight HK on G[H]G[H] (10 runs; a separate run on all LCC groups, with different random draws from those in Table VI), 1.17% [0.82, 1.68] of the Gowalla and 3.68% [2.31, 5.81] of the Brightkite LCC groups at s=1s = 1 lose an interaction accepted at the start, against 0% [0, 0.19] and 1.08% [0.42, 2.74] at s=0.8s = 0.8 (Wilson intervals; without noise, none does).

SplitMeasureRaw(a) Same size(b) Intercept
precovid (test 2019)member pairs+0.14 [0.11, 0.18]+0.03 [−0.01, 0.08]+0.04 [0.00, 0.08]
precovid (test 2019)members+1.03 [0.84, 1.22]+0.84 [0.61, 1.06]+0.91 [0.73, 1.10]
shift2018 (test 2018)member pairs+0.19 [0.15, 0.24]−0.01 [−0.06, 0.04]+0.04 [−0.01, 0.09]
shift2018 (test 2018)members+1.55 [1.37, 1.74]+0.98 [0.73, 1.22]+1.27 [1.07, 1.48]

Table XVI. YELP, LCC MINUS SIZE-MATCHED SAC (PP, 95% BOOTSTRAP CIS) ON THE TWO TIME SPLITS.

Open Groups at Group Level

Table XIX covers the LCC groups of Table VI on Gowalla and Brightkite and the 454 LCC groups on Congress, when each accepted outside friend has weight ww or, on Congress, a weight proportional to the observed interactions (obs.). It gives the lost share of the interactions accepted at the start, in groups that lose one, and the largest final opinion cluster, by single linkage at 10−310^{-3} of the initial diameter after at most 300 steps (closed groups: 99.7–100%); its last rows give LCC minus size-matched SAC in this cluster (closed groups: +1.6, +1.7 and 0 pp). Interaction loss and group-wide convergence are separate outcomes: open groups lose only a small share of interactions, usually early. Except on Congress at w=0.01w = 0.01, open groups also fail to reach a common opinion whether or not they lose an interaction: members stay spread between the outside friends they average with, and the largest final cluster holds a minority of the members of LCC groups that lose no interaction as well (22–35% on Gowalla and Brightkite), and on Congress at w=0.1w = 0.1, where no LCC group loses an interaction, only 11.8%. Pairwise groups, size-matched SAC groups and (k,r)(k,r)-cores at τ\tau also have largest final clusters of 15–28%. Paired differences relative to size-matched SAC vary in sign, so open LCC groups have no consistent group-level advantage.

VariantLCC (Exact) GLCC (Exact) BLCC (Exact) LLCC (Exact) OGreedy GGreedy BGreedy LGreedy OBallCore-R GBallCore-R BBallCore-R LBallCore-R OPairwise GPairwise BPairwise LPairwise OEdge-accept GEdge-accept BEdge-accept LEdge-accept OLCC groups GLCC groups BLCC groups LLCC groups OG/B/L/O
Closed group, interactions on G[H]G[H]
HK, equal weights00000000<100000006763––1,000/462/95/115
HK, equal, 3,000 steps00000000<100000006763––1,000/462/95/115
HK, random weights, α=1\alpha= 1000000001970<11<1007877––1,000/462/95/115
HK, random weights, α=0.1\alpha= 0.10000000062566476403332408585––1,000/462/95/115
Follow one neighbour000000004531312780<18180––1,000/462/95/115
Gossip (DW)00000000543828581711378282––1,000/462/95/115
SJT, new rejection0000000029154982<100<17473––1,000/462/95/115
Closed group, complete interaction graph
HK, equal weights00000000<100000005762––1,000/462/95/115
HK, random weights, α=1\alpha= 100000000022000005773––931/462/95/115
HK, random weights, α=0.1\alpha= 0.100000000293911121323547685––931/462/95/115
Follow one neighbour000000005146103330171<17282––931/462/95/115
Gossip (DW)00000000474474327216176672––907/462/63/71
SJT, new rejection0000000016176587<10027072––1,000/462/95/115
Assumptions violated
Open group, G[H]G[H]6562006363007470007267008385––1,000/462/95/115
Open group, complete6157005757006762006560007886––1,000/462/95/115
Stubborn outsiders, λ=0.01\lambda= 0.0191941<190941193973293970297100––1,000/462/95/115
Stubborn outsiders, λ=0.05\lambda= 0.05989949339899392698100734698100653899100––1,000/462/95/115
Stubborn outsiders, λ=0.1\lambda= 0.199100917198100886899100938499100938099100––1,000/462/95/115
Tolerance noise, ν=0.1\nu= 0.100000000310000007069––1,000/462/95/115
Tolerance noise, ν=0.2\nu= 0.20<100<1000165<130<1007373––1,000/462/95/115
Tolerance noise, ν=0.3\nu= 0.323032401312161234<127675––1,000/462/95/115
Groups (HK, equal, G[H]G[H])1,0004629511588744783931,0044671071301,0034641071291,011471––

Table VI. Groups (%) that lose an interaction accepted at the start in all 21 variants: methods that use tolerances.

AI-generated content acknowledgement

We used Anthropic Claude Opus 5.5 to debug and test code, and OpenAI GPT-6 Astra to polish the manuscript.

References

References

  1. [1]M. Sozio and A. Gionis, “The community-search problem and how to plan a successful cocktail party,” in KDD, 2010, pp. 939–948.DOI
  2. [2]Y. Fang, X. Huang, L. Qin, Y. Zhang, W. Zhang, R. Cheng, and X. Lin, “A survey of community search over big graphs,” The VLDB Journal, vol. 29, no. 1, pp. 353–392, 2020.arxiv.org/abs/1904.12539
  3. [3]F. Zhang, Y. Zhang, L. Qin, W. Zhang, and X. Lin, “When engagement meets similarity: Efficient (k, r)-core computation on social networks,” PVLDB, vol. 10, no. 10, pp. 998–1009, 2017.
  4. [4]K. Wang, X. Cao, X. Lin, W. Zhang, and L. Qin, “Efficient computing of radius-bounded k-cores,” in ICDE, 2018, pp. 233–244.DOI
  5. [5]L. Chen, C. Liu, R. Zhou, J. Li, X. Yang, and B. Wang, “Maximum co-located community search in large scale social networks,” PVLDB, vol. 11, no. 10, pp. 1233–1246, 2018.DOI
  6. [6]Y. Fang, R. Cheng, X. Li, S. Luo, and J. Hu, “Effective community search over large spatial graphs,” PVLDB, vol. 10, no. 6, pp. 709–720, 2017.DOI
  7. [7]Q. Liu, Y. Zhu, M. Zhao, X. Huang, J. Xu, and Y. Gao, “VAC: Vertex-centric attributed community search,” in ICDE, 2020, pp. 937–948.DOI
  8. [8]M. Sherif and C. I. Hovland, Social Judgment: Assimilation and Contrast Effects in Communication and Attitude Change. Yale University Press, 1961.
  9. [9]R. Hegselmann and U. Krause, “Opinion dynamics and bounded confidence: Models, analysis and simulation,” J. Artif. Soc. Soc. Simul., vol. 5, no. 3, 2002.
  10. [10]J. Lorenz, “Heterogeneous bounds of confidence: Meet, discuss and find consensus!” Complexity, vol. 15, no. 4, pp. 43–52, 2010.DOI
  11. [11]W. Cui, Y. Xiao, H. Wang, and W. Wang, “Local search of communities in large graphs,” in SIGMOD, 2014, pp. 991–1002.DOI
  12. [12]X. Huang, H. Cheng, L. Qin, W. Tian, and J. X. Yu, “Querying k-truss community in large and dynamic graphs,” in SIGMOD, 2014, pp. 1311–1322.DOI
  13. [13]Y. Fang, R. Cheng, S. Luo, and J. Hu, “Effective community search for large attributed graphs,” PVLDB, vol. 9, no. 12, pp. 1223–1244, 2016.DOI
  14. [14]F. Guo, X. Luo, S. Xu, H. Gao, Y. Liu, H. Shen, and X. Cheng, “Skyline community search over edge-attributed bipartite graphs,” in DASFAA, ser. LNCS, vol. 16536. Springer, 2026, pp. 367–383.arxiv.org/abs/2401.12895
  15. [15]Y. Fang, Y. Yang, W. Zhang, X. Lin, and X. Cao, “Effective and efficient community search over large heterogeneous information networks,” PVLDB, vol. 13, no. 6, pp. 854–867, 2020.DOI
  16. [16]Y. Liu, F. Guo, B. Xu, P. Bao, H. Shen, and X. Cheng, “SACH: Significant-attributed community search in heterogeneous information networks,” in ICDE, 2024, pp. 3283–3296.DOI
  17. [17]G. Chen, F. Guo, Y. Wang, Y. Liu, P. Yu, H. Shen, and X. Cheng, “FCS-HGNN: Flexible multi-type community search in heterogeneous information networks,” in CIKM, 2024, pp. 207–217.DOI
  18. [18]C.-Y. Shen, S.-H. Ko, G.-S. Lee, W.-C. Lee, and D.-N. Yang, “Density personalized group query,” PVLDB, vol. 16, no. 4, pp. 615–628, 2022.DOI
  19. [19]F. Bonchi, E. Galimberti, A. Gionis, B. Ordozgoiti, and G. Ruffo, “Discovering polarized communities in signed networks,” in CIKM, 2019, pp. 961–970.arxiv.org/abs/1910.02438
  20. [20]B. Ordozgoiti, A. Matakos, and A. Gionis, “Finding large balanced subgraphs in signed networks,” in WWW, 2020, pp. 1378–1388.arxiv.org/abs/2002.00775
  21. [21]Y. Liu, F. Guo, H. Shen, and X. Cheng, “Rethinking community consistency in heterogeneous networks,” in CIKM, 2026, pp. 3293–3304.DOI
  22. [22]D.-N. Yang, C.-Y. Shen, W.-C. Lee, and M.-S. Chen, “One social-spatial group query for location-based social networks,” in KDD, 2012, pp. 949–957.DOI
  23. [23]Q. Zhu, H. Hu, C. Xu, J. Xu, and W.-C. Lee, “Geo-social group queries with minimum acquaintance constraints,” The VLDB Journal, vol. 26, no. 5, pp. 709–727, 2017.DOI
  24. [24]Q. Li, Y. Zhu, and J. X. Yu, “Skyline cohesive group queries in large road-social networks,” in ICDE, 2020, pp. 397–408.DOI
  25. [25]F. Guo, Y. Yuan, G. Wang, L. Chen, X. Lian, and Z. Wang, “Cohesive group nearest neighbor queries over road-social networks,” in ICDE, 2019, pp. 434–445.DOI
  26. [26]———, “Cohesive group nearest neighbor queries over road-social networks under multi-criteria,” IEEE Trans. Knowl. Data Eng., vol. 33, no. 11, pp. 3520–3536, 2021.DOI
  27. [27]F. Guo, Y. Yuan, G. Wang, X. Zhao, and H. Sun, “Multi-attributed community search in road-social networks,” in ICDE, 2021, pp. 109–120.DOI
  28. [28]S. Amer-Yahia, S. Basu Roy, A. Chawla, G. Das, and C. Yu, “Group recommendation: Semantics and efficiency,” PVLDB, vol. 2, no. 1, pp. 754–765, 2009.
  29. [29]S. Basu Roy, L. V. S. Lakshmanan, and R. Liu, “From group recommendations to group formation,” in SIGMOD, 2015, pp. 1603–1616.arxiv.org/abs/1503.03753
  30. [30]M. H. DeGroot, “Reaching a consensus,” J. Am. Stat. Assoc., vol. 69, no. 345, pp. 118–121, 1974.DOI
  31. [31]N. E. Friedkin and E. C. Johnsen, “Social influence and opinions,” J. Math. Sociol., vol. 15, no. 3–4, pp. 193–206, 1990.DOI
  32. [32]G. Deffuant, D. Neau, F. Amblard, and G. Weisbuch, “Mixing beliefs among interacting agents,” Advances in Complex Systems, vol. 3, no. 1–4, pp. 87–98, 2000.DOI
  33. [33]A. Mirtabatabaei and F. Bullo, “Opinion dynamics in heterogeneous networks: Convergence conjectures and theorems,” SIAM J. Control Optim., vol. 50, no. 5, pp. 2763–2785, 2012.arxiv.org/abs/1103.2829
  34. [34]W. Su, Y. Gu, S. Wang, and Y. Yu, “Partial convergence of heterogeneous Hegselmann-Krause opinion dynamics,” Sci. China Technol. Sci., vol. 60, no. 9, pp. 1433–1438, 2017.DOI
  35. [35]R. Hegselmann and U. Krause, “Opinion dynamics under the influence of radical groups, charismatic leaders, and other constant signals: A simple unifying model,” Netw. Heterog. Media, vol. 10, no. 3, pp. 477–509, 2015.DOI
  36. [36]W. Jager and F. Amblard, “Uniformity, bipolarization and pluriformity captured as generic stylized behavior with an agent-based simulation model of attitude change,” Comput. Math. Organ. Theory, vol. 10, no. 4, pp. 295–303, 2005.DOI
  37. [37]C. Monti, G. De Francisci Morales, and F. Bonchi, “Learning opinion dynamics from social traces,” in KDD, 2020, pp. 764–773.
  38. [38]Y. Luan, C. Ancona, C. Bernardo, V. Pansanella, F. Lo Iudice, G. Rossetti, F. Vasca, X. Wu, and C. Altafini, “Quantifying opinion homophily in online social networks: A bounded confidence perspective,” arXiv:2604.23157, 2026.arxiv.org/abs/2604.23157
  39. [39]T. Lappas, K. Liu, and E. Terzi, “Finding a team of experts in social networks,” in KDD, 2009, pp. 467–476.DOI
  40. [40]S. B. Seidman, “Network structure and minimum degree,” Social Networks, vol. 5, no. 3, pp. 269–287, 1983.DOI
  41. [41]V. Batagelj and M. Zaveršnik, “An O(m) algorithm for cores decomposition of networks,” arXiv:cs/0310049, 2003.arxiv.org/abs/cs/0310049
  42. [42]L. Moreau, “Stability of multiagent systems with time-dependent communication links,” IEEE Trans. Autom. Control, vol. 50, no. 2, pp. 169–182, 2005.DOI
  43. [43]R. M. Karp, “Reducibility among combinatorial problems,” in Complexity of Computer Computations. Plenum Press, 1972, pp. 85–103.
  44. [44]D. Zuckerman, “Linear degree extractors and the inapproximability of max clique and chromatic number,” Theory of Computing, vol. 3, pp. 103–128, 2007.
  45. [45]H. Maehara, “Space graphs and sphericity,” Discrete Applied Mathematics, vol. 7, no. 1, pp. 55–64, 1984.DOI
  46. [46]B. N. Clark, C. J. Colbourn, and D. S. Johnson, “Unit disk graphs,” Discrete Mathematics, vol. 86, no. 1–3, pp. 165–177, 1990.
  47. [47]M. Bonamy, É. Bonnet, N. Bousquet, P. Charbit, P. Giannopoulos, E. J. Kim, P. R. Pęczarski, F. Sikora, and S. Thomassé, “ETPAS and subexponential algorithm for maximum clique on disk and unit ball graphs,” J. ACM, vol. 68, no. 2, 2021, article 9.
  48. [48]E. Tomita and T. Seki, “An efficient branch-and-bound algorithm for finding a maximum clique,” in DMTCS, ser. LNCS, vol. 2731. Springer, 2003, pp. 278–289.DOI
  49. [49]E. Cho, S. A. Myers, and J. Leskovec, “Friendship and mobility: User movement in location-based social networks,” in KDD, 2011, pp. 1082–1090.
  50. [50]J. Yang and J. Leskovec, “Defining and evaluating network communities based on ground-truth,” in ICDM, 2012, pp. 745–754.
  51. [51]L. Takac and M. Zabovsky, “Data analysis in public social networks,” in Proc. Int. Scientific Conf. & Int. Workshop Present Day Trends of Innovations, Łomża, Poland, May 2012.
  52. [52]J. Leskovec and A. Krevl, “SNAP Datasets: Stanford large network dataset collection,” http://snap.stanford.edu/data/, Jun. 2014.
  53. [53]U. N. Raghavan, R. Albert, and S. Kumara, “Near linear time algorithm to detect community structures in large-scale networks,” Physical Review E, vol. 76, no. 3, p. 036106, 2007.DOI
  54. [54]Q. Huangfu and J. A. J. Hall, “Parallelizing the dual revised simplex method,” Math. Program. Comput., vol. 10, no. 1, pp. 119–142, 2018.
  55. [55]Google, “OR-Tools, version 9.15, with the CP-SAT solver,” https://developers.google.com/optimization/, 2026.
  56. [56]Yelp, “Yelp Open Dataset,” https://www.yelp.com/dataset, 2022, accessed 2026.
  57. [57]K. T. Poole and H. Rosenthal, Ideology and Congress, 2nd ed. New Brunswick, NJ: Transaction Publishers, 2007.
  58. [58]J. B. Lewis, K. Poole, H. Rosenthal, A. Boche, A. Rudkin, and L. Sonnet, “Voteview: Congressional Roll-Call Votes Database,” https://voteview.com/, 2026.
  59. [59]U.S. Government Publishing Office, “Bill status (BILLSTATUS) bulk data, 117th Congress,” https://www.govinfo.gov/bulkdata/BILLSTATUS, 2026, accessed Oct. 2026.
  60. [60]C. G. Fink, N. Omodt, S. Zinnecker, and G. Sprint, “A Congressional Twitter network dataset quantifying pairwise probability of influence,” Data Brief, vol. 50, 2023, Art. no. 109521.DOI
  61. [61]C. G. Fink, K. Fullin, G. Gutierrez, N. Omodt, S. Zinnecker, G. Sprint, and S. McCulloch, “A centrality measure for quantifying spread on weighted, directed networks,” Physica A, vol. 626, 2023, Art. no. 129083.
  62. [62]D. Cherepanlokski, A. Karpf, I. Mozetič, and M. Grčar, “Cohesion and coalition formation in the European Parliament: Roll-call votes and Twitter activities,” PLoS ONE, vol. 11, no. 11, 2016, Art. no. e0166586; data: CLARIN.SI 11356/1071.

Paper details

vlnc:W_2x8hgu5n
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents