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 , community search identifies a cohesive subgraph containing [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 , containing , 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 and , whereas bounding the spread by the smallest tolerance preserves acceptance in the LCC of (c). With a common tolerance , a largest LCC is a maximum -core [3] containing . 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.

Figure 1. Pairwise acceptance versus the smallest-tolerance bound (; grey and 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 , nor exempting two members, nor the pairwise condition 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 unless P = NP, and for each fixed , even deciding whether an LCC exists is NP-complete. On a line, the problem is polynomial.
Algorithms (§ 5). LatSweep fixes the smallest tolerance of the answer so that every member must satisfy , 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.

Figure 2. The LatSweep framework: (a) survival intervals and the candidates (dots) at two thresholds; (b) index, query pipeline and the bounds 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--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.
Related Work
Community search: Community search identifies a cohesive subgraph containing a query vertex, usually a connected -core [1, 11] or -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 -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. -cores [3] require all pairs of members to be similar within one threshold, and -cores [15] extend -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 -core containing whose minimum covering circle is smallest. Radius-bounded -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 a position in a metric space and two radii : vertex accepts a position if , rejects it if , and is noncommittal otherwise. The same search model applies to geographic positions. In meetups (§ 6), is a user’s home and estimates, from past visits, how far the user is willing to travel. Each member need only reach every other member’s home.
Notation: Let be an undirected simple graph with .1 For , is the induced subgraph and the set of neighbours of in . Each vertex has a position and a tolerance ; we write and ; Table 1 lists the main notation.
| Symbol | Meaning |
| social graph, | |
| metric space of positions | |
| query vertex, minimum degree | |
| position and tolerance of | |
| radii of acceptance and of rejection | |
| group, | |
| induced subgraph; neighbours of in it | |
| largest distance and smallest tolerance in | |
| size of a largest LCC (0 if none) | |
| position at step ; neighbours accepted at | |
| averaging weights, bounded below by | |
| component with of the -core of | |
| subgraph of on mutually accepted edges | |
| ; survival interval of | |
| query region around | |
| threshold; candidate thresholds | |
| vertices of with ; | |
| optimum at threshold and its upper bound | |
| best set found; proven upper bound on |
Table 1. NOTATION.
Definition 1 (Latitude-consistent community). For a query vertex and an integer , we call a set a latitude-consistent community (LCC) when (i) ; (ii) is connected and has minimum degree at least ; and (iii) .
Choosing yields an , in which every member accepts every other member’s position; yields the weaker , where no member rejects another.
Problem 1 (MaxLCC). For inputs , , , and , return an LCC with the largest possible number of vertices. The decision problem LCC-Dec asks whether there exists an LCC containing at least 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 , nor exempting two members, nor the pairwise condition 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 and increase , so condition (iii) is hereditary. Yet the condition couples three members at a time: for all . This dependence on other members prevents a fixed pairwise decomposition. For instance, and at distance 1 with tolerance 1 form a feasible pair, and so does each with a vertex midway between them with tolerance , yet violates (iii). With uniform tolerances , condition (iii) becomes the pairwise constraint of -cores [3], with distance in place of similarity. MaxLCC then asks for a maximum -core containing . Pruning for -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).
-cores: For , the -core [40] of is its unique maximal subgraph with minimum degree at least , and denotes the component of this -core that contains , or the empty set if is not in the -core; peeling computes it in time [41], and we use the same notation for peeling in a spanning subgraph of . Throughout, we use the -core fact: every connected with and minimum degree at least satisfies .
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 under any norm . A group starts from ; the graph and the tolerances are fixed, interactions follow edges of , and .
Bounded-confidence dynamics: In the network version of the Hegselmann–Krause (HK) model [9] with agent-specific bounds [10], vertex averages the opinions of the neighbours it accepts:
where , the weights are non-negative with unit sum, and for ; equal weights give . An interaction along is accepted at time if .
Lemma 1. If every is a convex combination of , then , because, by convexity of the norm, a point set and its convex hull have the same diameter.
Theorem 1 (Consensus). Let be an with that evolves by (1) with . Then for every , (a) every interaction along every edge of is accepted, and (b) is non-increasing and
so all opinions converge to a common point. (c) With equal weights, the limit is the -weighted average of the initial opinions.
Proof. (a) Each update (1) is a convex combination, so by Lemma 1, for all and ; hence .
(b) By (a), the update matrix is row-stochastic with entries at least on the diagonal and on the edges of . Since is connected, any two vertices are joined by a walk of exactly steps when self-loops are allowed, so every entry of is at least . For two rows of , let ; the vector is if and otherwise times a difference of two convex combinations of the , so its norm is at most . Hence the diameter is multiplied by at most every steps. Because every later opinion remains in the convex hull of the opinions at time , the trajectories are Cauchy and share a common limit.
(c) With equal weights, is the random walk on with self-loops, whose stationary distribution satisfies .
Condition (iii) fixes the accepted interactions, so the dynamics reduce to linear averaging on [30]. Connectivity then ensures convergence; the role of 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 still hold, and if every vertex updates at least once in every consecutive steps, applying (b) to blocks of 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 moves towards accepted neighbours, ignores noncommittal ones, and moves away from rejected ones:
where uses , , and may vary with , with ; updates may be asynchronous.
Theorem 2 (No rejection). If an follows (2), then for all and , and never increases; consensus need not occur.
Proof. Suppose , which holds at . Then every edge satisfies , so , and the update is a convex combination; Lemma 1 gives , and induction completes the proof. Finally, split equally between positions and with and : this has only noncommittal cross pairs and never moves. □
Proposition 1 (Tightness). Fix , and .
(a) There is a connected group with minimum degree at least , diameter and uniform tolerance in which acceptance and consensus fail under (1); with , and , rejection occurs under (2) and the diameter grows.
(b) There is a connected group with minimum degree at least in which every pair satisfies and every member but two satisfies , but in which acceptance and consensus fail under (1); with and , rejection occurs under (2).
Proof. (a) Split equally between positions and 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 . Place cliques and of vertices each at positions and with tolerance , and two adjacent vertices and at position with tolerance , where is adjacent to all of and to all of . Every pair is within the smaller of its two tolerances, every vertex has degree at least , and only and have tolerance below . With equal weights, one update of (1) moves to , to , to and to . Then , so and no longer accept each other, and the vertices of , like those of , accept only one another. Each part therefore stays in the convex hull of its own positions at , and the two hulls are more than 1 apart; by the argument of Theorem 1(b), each part converges to its own limit. With and , the first update of (2) coincides with that of (1), after which and reject each other.
Part (b), illustrated in Figure 1 for , 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 one more vertex, and replace and by one vertex at position 1 with tolerance 1, adjacent to all of and to one vertex ; one update moves to and to , which are apart. However, consensus survives a single exemption: every other member accepts all its neighbours at all times, so 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 with and . (a) Every pair satisfies if and only if every member of accepts every point of . (b) If is connected, then if and only if, for every and all weights admitted by (1), every interaction along every edge of is accepted at all times. Moreover, if and all these interactions are accepted at , then for every sufficiently small some admitted weights make a member refuse, within steps, an interaction that it accepted at .
Proof. (a) For fixed , the function is convex, so its maximum over the convex hull is attained at one of the points . Hence accepts the whole hull if and only if for all ; requiring this for every 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 and that every interaction along an edge of is accepted at , since otherwise there is nothing to prove; let and . In a copy step along an edge , member puts weight on and spreads evenly over its other accepted neighbours and itself, while every other member puts weight on itself and spreads 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 , so these weights are admitted for every , provided that still accepts ; if it does not, an interaction accepted at 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 ; hence in a copy step moves to within of the position of , and every other member moves by at most . Copying along a path , that is, performing copy steps along in this order, therefore brings to within of where started, and moves every member outside by at most .
If some pair has , then and are not adjacent. A shortest path from to , without its last vertex , ends at a neighbour of and has length . Copying along it brings to within of , while moves by at most , so refuses at once .
Otherwise the pairwise condition holds. Let and ; then , because for all . There is a path from to that avoids , or one from to that avoids : if lies on every path from to , then every path from to continues inside the component of that contains , and is not in this component. Swapping and if necessary, copy along a path from to that avoids , and then along a shortest path from to without its last vertex ; the latter ends at a neighbour of , possibly . After these steps, is within of and within of , so once : member refuses , which it accepted at .
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 form a triangle in , at positions 0, and 1 on a line, with tolerances 1, 0.6 and 1: every pair satisfies the pairwise condition and (iii) fails, but with 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 , 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 , since, for instance, with 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 also interact with its outside neighbours , whose positions stay fixed, and let every update move to a convex combination, with non-negative weights that may vary with time and state, of and the in-group and outside neighbours that accepts at time . Let be the set of outside positions accepted by some member at , and . If (a) and (b) for all , and with , then for all and , and at every time each member accepts exactly the neighbours it accepted at .
Proof. We prove by induction on that for all ; the claim holds at . Assume it holds at time and fix . If and , then by (b), so does not accept ; every other point that can average, namely , the positions of its in-group neighbours and the outside positions in , lies in the convex set , so . Any two points of are within , so at every time accepts all its in-group neighbours and all outside neighbours with positions in , and no others; by the definition of , these are exactly the neighbours it accepts at . As a point set and its convex hull have the same diameter (Lemma 1), (a) can be checked on the finite set . 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 and drift apart, an instance of the indirect influence described in [35]. For example, let adjacent members and start at and with , let have outside neighbours at , and have at and at . Then , but (b) fails; under equal-weight HK, starts to accept the neighbours at after one step, and at the two members are apart and refuse each other. The argument needs outside positions to stay fixed, and open groups need not reach consensus: if has outside neighbours at and has at , with and members at and , the two members converge to and under equal weights, so the members’ diameter grows from to while 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 with the Euclidean norm and rational coordinates and tolerances; in parts (a), (b) and (f), is part of the input and we use the following embedding.
Lemma 2. Given a graph with , points with and an integer can be computed in polynomial time such that, for distinct , if and only if .
Proof. Let denote the complement of , and let denote its maximum degree. Take the least positive integer satisfying $2j^2 \ge \Delta$, and put . For every edge in ordered by , introduce a coordinate assigning , $y_w = -1, and every other point the value . For each , introduce another private coordinates with value . This gives for every ; distinct points can share a non-zero coordinate only when they are adjacent in . Thus is when and when . Thus takes value in the former case and in the latter, so the threshold distinguishes them. □
Theorem 3 (Hardness). (a) For each fixed , LCC-DEC is -complete. This holds even for complete , equal tolerances, and coordinates restricted to . (b) For every fixed , unless , no polynomial-time algorithm can approximate MaxLCC to within a factor of . (c) The conclusions of (a) and (b) extend to general metrics supplied as distance matrices. (d) When , MaxLCC can be solved in time. (e) For each fixed and , LCC-DEC remains -complete, also on the sphere with chord distance, even with equal tolerances. (f) For each fixed , deciding whether an LCC exists is -complete, even with equal tolerances, both for distances in and in with part of the input. Hence, for each fixed , unless , 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 , add a clique of new vertices, including , and make every vertex of adjacent to every vertex of . Apply the embedding of Lemma 2 to this augmented graph, take to be complete, assign tolerance to every vertex, and set . Any -clique in gives the set , whose pairwise distances are at most and whose minimum degree in is . Conversely, every pair of vertices in an LCC has distance at most ; by Lemma 2, these vertices form a clique in the augmented graph, and deleting leaves a clique in with at least vertices. (b) Embed itself by Lemma 2, with complete and tolerance . Checking all sets of at most vertices in time either finds a maximum clique, if its size is at most , or shows . In the latter case, apply a -approximation algorithm to each query that lies in a -clique. If belongs to a maximum clique, the corresponding optimum equals . Every LCC returned by the algorithm is a clique in , and the largest returned set therefore contains at least vertices. This gives a polynomial-time approximation for CLIQUE within ; taking would imply P = NP [44].
(c) The embedding would give irrational distances, so we bypass it: set if is an edge of the graph being embedded and for every other pair , and give every vertex tolerance 1. Any symmetric matrix with zero diagonal and off-diagonal entries in satisfies the triangle inequality, and the arguments of (a) and (b) apply unchanged.
(d) Take an optimal solution and define and . The inequality places inside the window . For each pair , evaluate , where . Every non-empty is an LCC: its positions occupy a window of length , and each tolerance is at least . The -core fact gives , establishing optimality of the largest . The enumeration considers pairs and takes time for each.
(e) We reduce from 3-SAT [43] with variables , , and clauses . Let and , a rational point of the unit circle at angle . Place a clique of vertices, including , at the origin; for each , place copies of the literal at and copies of at ; and place one vertex per clause at the origin. Every copy is adjacent to all of , and each clause vertex is adjacent to all copies of its literals. Copies of and are at distance 2; every other pair is closer than . 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 and are at distance or , where ; both are at most , where is the smallest difference between distinct angles . Since the derivative of is at least 1 on and consecutive values differ by , we have ; with and , this gives . With tolerance for every vertex, an LCC contains copies of at most one literal per variable, and therefore at most vertices. An LCC with vertices contains , all copies of one literal per variable, and every clause vertex; each clause vertex then needs neighbours, that is, a chosen literal, so the chosen literals satisfy the formula. Conversely, the true literals of a satisfying assignment, together with and all clause vertices, form an LCC with vertices. On the sphere with chord distance, put the copies on the equator and the other vertices at the north pole, at distance from every copy; the argument is unchanged. Padding the coordinates with zeros extends the planar construction to every fixed .
(f) Membership in NP is as above. We reduce from Multi-Colored Clique: given a graph whose vertex set is partitioned into classes with , decide whether some are pairwise adjacent. It is NP-complete, since an instance of CLIQUE with reduces to it by taking for and joining and if and only if and . Add an original vertex and arrange the classes on a ring, so that the ring neighbours of are and , with . Replace every original by copies, let be a copy of , and join two copies in if and only if their originals lie in ring-neighbouring classes. Call two originals compatible if they are equal, if one of them is , or if they lie in different classes and are adjacent in . 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 by Lemma 2, put every copy at the point of its original, and give every vertex tolerance . In both cases, a set satisfies (iii) if and only if its members are copies of pairwise compatible originals. If form a multicolored clique, all copies of form an LCC: the subgraph they induce is connected, each of its vertices has neighbours in it, and their originals are pairwise compatible. Conversely, let be an LCC. Distinct originals in the same class are incompatible, so the members of among the copies of a class are copies of a single original. The neighbours in of a member therefore lie in its two ring-neighbouring classes, at most in each, and minimum degree forces both of these classes to contribute members. Starting from , whose ring neighbours are and , and following the ring, every class contributes copies of some ; 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 ; (e) and (f) require new constructions. With uniform tolerances, (e) and (e) also show that the query version of the -core problem [3] is NP-hard under Euclidean distance, even in the plane, and by (f), for each fixed , even deciding whether lies in any -core is NP-complete when the dimension is part of the input. The assumption that is fixed matters: if is part of the input, the construction of (a) with and 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 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 , and its proof gives the same bound even on inputs with an LCC that is easy to find, a -clique of containing .
Open cases: It remains open whether MaxLCC is hard to approximate in dimensions 2 and 3 and whether, for , 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 is complete, Lemma 4 reduces MAXLCC to finding, for each candidate threshold, a maximum clique containing 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 [47], while these results leave dimension 3 unresolved.
The LatSweep Framework
LatSweep makes the coupled constraint (iii) searchable by fixing the smallest tolerance . Each value yields a fixed-threshold subproblem in a reduced region around (see Figure 2). The sweep yields four algorithms: BallCore-F and a greedy variant return only LCCs, BallCore-R is a polynomial-time -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 -core containing [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 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 be an LCC and . (a) Every satisfies , and hence . (b) Let with . Then ; hence lies in the component of the -core of that contains .
Proof. (a) As , we have , and . (b) Every edge inside satisfies ; the -core fact applied to completes the proof.
Lemma 3(a) assigns each vertex a survival interval for the smallest tolerance of an LCC containing it. A vertex with an empty interval, such as in Figure 2(a), cannot belong to an LCC. The core numbers of form a compatibility index; it is independent of the query and is built once per tolerance assignment (say, for and for ) in time, where is the cost of one distance evaluation. For a query and a graph , the query region is obtained by a traversal from along edges of that visits only vertices with a non-empty survival interval and core number at least in . By Lemma 3, every LCC lies in for either choice of , and building inspects only and its neighbours; BallCore-R uses , and hence the core numbers of rather than the index, all other variants .
Candidate thresholds: For , let and let , peeled in . Let , and let be the largest size of a connected set with , minimum degree at least and .
Lemma 4. , and for all .
Proof. Every set counted in has all tolerances at least and is therefore an LCC. Conversely, an optimal has , so , and by Lemma 3(a); thus is counted in . The bound is the -core fact.
Best-first sweep: Algorithm 1 keeps an upper bound on for every threshold and repeatedly refines the threshold with the largest one, instead of increasing cost (see Figure 2(b)): the interval count , obtained for all thresholds by one sort of the interval end points; the size 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 . The root bound holds only for solutions larger than the incumbent , which suffices because never shrinks. By Lemma 4, no threshold can improve the incumbent once every remaining bound is at most . Ordering by alone can prioritize expensive subproblems that have small optima; refining instead focuses the search on promising thresholds (Section VI-B). Unlike with a uniform radius, is not monotone in : a larger admits vertices farther from but drops those with ; in Figure 2(a), from to , loses and gains . The sort takes time and one peeling , where and .
BallCore: Feasible and Bicriteria Solutions
Feasible solutions: Variant F doubles the left end points of the survival intervals ( in Algorithm 1); it is fast but conservative, since it admits only vertices within of . The greedy variant avoids this restriction. It starts from , peeled in , at each of the 20 thresholds with the largest . It repeatedly deletes the vertex other than 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 and therefore cannot improve .
The factor 2 is attained: place at 0 and vertices at each of and on a line, take complete, and give every vertex tolerance . Then contains all vertices and has diameter , whereas an optimum consists of and the vertices on one side. It is also best possible in general metrics: with distances in 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 with diameter factor . 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 .
LatSweep-Exact
By Lemma 4, an optimal LCC is found by solving, at every whose bound exceeds the incumbent, the fixed-threshold subproblem on : two vertices conflict if their distance exceeds , and the goal is a largest conflict-free subset containing that is connected and has minimum degree at least . The exact variant peels in , 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: returns a largest feasible subset of if it has more than vertices, and the empty set otherwise. A search node consists of selected vertices and undecided vertices , with no conflicts within or between and ; the root has and , which satisfies this invariant because for every . Let denote the size of the incumbent. Each node first applies rules (1) and (2) of Lemma 5 to reduce . If no conflict remains in , then is feasible and optimal for the subtree; otherwise, the node tests rule (3) and branches on a vertex with the most conflicts in , either deleting or moving it to and deleting its conflicting partners from . Together, the two branches retain every solution in the subtree, and both maintain the invariant. The root bound used by Algorithm 1 is at the root after rules (1) and (2), where is the colour count of rule (3); by Lemma 5, no feasible subset of with more than 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 vertices in the current node’s subtree. (1) Delete edges joining conflicting vertices, peel down to the component containing in its -core, and prune the node whenever this removes a vertex of . (2) Prune the node when . If this test fails, examine any vertex having fewer than conflict-free partners in : delete it if it belongs to , or prune the node if it belongs to . Apply rules (1) and (2) alternately until both leave unchanged. (3) Greedily colour the vertices of , in increasing order of their number of conflicts in , so that every colour class is a set of pairwise conflicting vertices; prune when plus the colour count does not exceed .
Proof. Take any feasible satisfying and . (1) Since contains no conflicting pair, none of the deleted edges belongs to ; the -core fact therefore ensures that remains after peeling. (2) Every has the remaining vertices of as conflict-free partners, and all are contained in . (3) 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 , which takes 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 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 . Exact then returns the incumbent with . Every answer is thus proven optimal (, which includes proven empty answers), feasible with a gap (), or undecided ( and ).
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 of a user is the median check-in position in the user’s most frequent cell of about 25 km, and 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 around centres about eight times the within-group scale apart. Tolerances are with standard normal and . The scale 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 ranges from 1.25 on Orkut to 3 on YouTube.
Queries and algorithms: Efficiency queries are drawn at random from the -core of (on synthetic positions, from groups of at least 20 members), 50 per setting. The default setting (, all vertices and, on synthetic positions, 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 -core component of and the global -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 and conflict if , with a limit of 60 s (10 s in the heterogeneity sweep, where Exact keeps 60 s). Edge-accept is the -core on the edges accepted by both endpoints. Several baselines ignore tolerances. The -core at the LCC’s own threshold is an oracle baseline, since is known only after the search; the global -core uses the median tolerance instead. SAC [6], in its AppInc approximation, returns the connected -core containing in the smallest ball centred at that holds one, and size-matched SAC returns the -core in the smallest such ball whose -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 -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 ’s -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 -core is never an LCC there.
| Graph | With LCC | Median (s) | Median | p90 | Unproven | Finds | Size | -core (ms) | ||
| Gowalla | 56 K | 222 K | 16% | 0.3 | 0.26 | 27 | 0 | 100% | 0.98 | 2.2 |
| Brightkite | 24 K | 108 K | 13% | 0.2 | 0.07 | 0.41 | 0 | 95% | 0.95 | 1.1 |
| DBLP | 317 K | 1.0 M | 57% | 0.9 | 0.14 | 5.4 | 0 | 96% | 0.94 | 22 |
| YouTube | 1.1 M | 3.0 M | 23% | 2.3 | 31 | 349 | 0 | 93% | 0.90 | 41 |
| Pokec | 1.6 M | 22.3 M | 52% | 3.3 | 861 | 21.6 s | 4 | 77% | 0.62 | 373 |
| LiveJournal | 4.0 M | 34.7 M | 50% | 3.4 | 6.0 | 1.9 s | 0 | 90% | 0.79 | 630 |
| Orkut | 3.1 M | 117.2 M | 55% | 4.7 | 200 | 3.8 s | 0 | 84% | 0.68 | 1.6 s |
| Friendster | 65.6 M | 1.81 B | 55% | 0.4 | 352 | 7.9 s | 3 | 89% | 0.77 | 70.5 s |
Table II. Exact and greedy at the default setting ().
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).
| Graph | Setting | LCC | UB | LCC/UB | Candidates | Thresholds | Nodes |
| Friendster | default | 147 | 212 | 0.693 | 587 | 22/25 | 519,058 |
| Friendster | default | 305 | 336 | 0.907 | 560 | 83/84 | 263,320 |
| Friendster | default | 374 | 398 | 0.939 | 738 | 69/78 | 102,156 |
| LiveJournal | scale | 552 | 578 | 0.955 | 803 | 34/35 | 60,421 |
| Orkut | scale | 719 | 732 | 0.982 | 918 | 154/851 | 70,370 |
| Pokec | default | 169 | 245 | 0.689 | 622 | 77/83 | 539,455 |
| Pokec | default | 179 | 246 | 0.727 | 645 | 73/79 | 417,817 |
| Pokec | default | 189 | 253 | 0.747 | 578 | 323/484 | 551,931 |
| Pokec | default | 369 | 394 | 0.936 | 787 | 379/539 | 199,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 ’s -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 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 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 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 ’s entire -core component (2.7 and 3.0 million vertices), and 12% and 14% of the queries reach the limit. Across , vertex samples of 25–100% and 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 matters most. At half the calibrated , almost no LCC exists (0% and 4% of the queries). At twice and three times the calibrated , most queries have one (68–88%), and at twice the calibrated , 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 -core algorithm of Zhang et al. [3], adapted to contain 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.
| Solver | Proven LJ | Proven Ork. | Proven, LCC LJ | Proven, LCC Ork. | Slowdown LJ | Slowdown Ork. |
| Branch and bound (ours) | 96.5 | 96.5 | 92.6 | 93.9 | 1 | 1 |
| AdvMax, simple branching | 90.5 | 80.5 | 80.0 | 66.1 | 5.7 | 7.2 |
| AdvMax | 89.5 | 76.5 | 77.9 | 59.1 | 14.0 | 14.6 |
| MILP (HiGHS) | 90.5 | 80.0 | 80.0 | 65.2 | 26.7 | 21.2 |
| CP-SAT | 86.0 | 72.5 | 70.5 | 52.2 | 175 | 45.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 -core containing . 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 , 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 -cores. With equal tolerances (), the LCC coincides with the -core at the same threshold on all 220 queries of LiveJournal and Orkut on which Exact and the exact -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 and 4% and 7% at the default (Table X); the copy of our solver in Table III leaves 3.5% unproven there. From on, -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.
| With LCC L | With LCC O | Exact limit L | Exact limit O | -core at : (iii) holds L | -core at : (iii) holds O | -core at : Members L | -core at : Members O | -core at : Size/LCC L | -core at : Size/LCC O | Pairwise (iii) holds L | Pairwise (iii) holds O | Global Members L | Global Members O | |
| 0.0 | 76.5 | 85.5 | 0.5 | 45.0 | 100.0 | 100.0 | 0 | 0 | 1.00 | 1.00 | 100.0 | 100.0 | 0 | 0 |
| 0.2 | 70.0 | 74.5 | 14.0 | 26.5 | 8.6 | 4.7 | 12 | 23 | 1.25 | 1.50 | 4.1 | 0.6 | 27 | 38 |
| 0.4 (default) | 47.5 | 57.5 | 4.0 | 7.0 | 4.2 | 0.0 | 31 | 43 | 1.80 | 2.19 | 5.6 | 2.3 | 40 | 44 |
| 0.6 | 39.0 | 44.0 | 0.5 | 3.0 | 2.6 | 1.1 | 43 | 52 | 2.54 | 2.93 | 7.1 | 3.1 | 45 | 47 |
| 0.8 | 30.5 | 33.0 | 0.0 | 0.0 | 1.6 | 0.0 | 49 | 61 | 2.72 | 3.87 | 9.0 | 2.7 | 47 | 49 |
| 1.0 | 21.0 | 27.5 | 0.0 | 0.0 | 2.4 | 1.8 | 55 | 65 | 3.50 | 4.21 | 11.1 | 6.9 | 49 | 48 |
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 times the median distance between friends; since most friends lie in different communities, (Orkut) or (LiveJournal) lets LCCs span several communities. On Orkut, the queries with an LCC have a median of 8,360 candidate vertices at and 210,146 at , whereas no efficiency query has more than 1,502;
on LiveJournal at , 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 , Exact proves only 64% (LiveJournal) and 20% (Orkut) of these queries, and for 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 -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 on both graphs and at 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).
| Graph | Setting | LCC | Proven (%) | Limit (%) | Size cap (%) | Solution/bound (%) |
| LiveJournal | 153 | 100.0 | 0.0 | 0.0 | – | |
| LiveJournal | 153 | 100.0 | 0.0 | 0.0 | – | |
| LiveJournal | 153 | 64.1 | 35.3 | 0.7 | 0.33 | |
| LiveJournal | 150 | 15.3 | 84.0 | 0.7 | 0.04 | |
| LiveJournal | 119 | 3.4 | 95.0 | 1.7 | 0.03 | |
| Orkut | 177 | 100.0 | 0.0 | 0.0 | – | |
| Orkut | 177 | 50.8 | 48.0 | 1.1 | 0.91 | |
| Orkut | 177 | 19.8 | 79.7 | 0.6 | 0.18 | |
| Orkut | 161 | 3.1 | 96.3 | 0.6 | 0.40 | |
| Orkut | 177 | 0.6 | 99.4 | 0.0 | 7.6 | |
| LiveJournal | from the -core | 91 | 100.0 | 0.0 | 0.0 | – |
| Orkut | from the -core | 92 | 100.0 | 0.0 | 0.0 | – |
| LiveJournal | mixing | 80 | 100.0 | 0.0 | 0.0 | – |
| LiveJournal | mixing | 68 | 100.0 | 0.0 | 0.0 | – |
| LiveJournal | mixing | 42 | 100.0 | 0.0 | 0.0 | – |
| Orkut | mixing | 103 | 100.0 | 0.0 | 0.0 | – |
| Orkut | mixing | 83 | 100.0 | 0.0 | 0.0 | – |
| Orkut | mixing | 51 | 100.0 | 0.0 | 0.0 | – |
Table XI. Synthetic settings: scale, query sampling and community mixing.
| Setting (LCC) | C0 | cap 20,000 | cap 50,000 | root 100,000 | Greedy all | 300 s: proven / unproven under C0 |
| LiveJournal (153) | 64.1 | 64.1 | 64.1 | 64.1 | 60.8 | 5 / 55 |
| Orkut (177) | 50.8 | 51.4 | 52.0 | 50.8 | 48.6 | 1 / 87 |
| Orkut (177) | 19.8 | 20.3 | 20.3 | 19.8 | 19.8 | 0 / 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 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 , 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.
| Method | Equal G | Equal B | Equal L | Equal O | Concentrated G | Concentrated B | Concentrated L | Concentrated O | Gossip G | Gossip B | Gossip L | Gossip O |
| LCC (Exact) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| Pairwise | 0 | 0 | 0 | 0 | 40 | 33 | 32 | 40 | 17 | 11 | 3 | 7 |
| -core at | 15 | 17 | 13 | 41 | 44 | 91 | 97 | 34 | 40 | 64 | 69 | 85 |
| Size-matched SAC | 5 | 8 | 1 | 2 | 52 | 56 | 89 | 98 | 39 | 40 | 63 | 86 |
Table IV. Groups (%) that lose an interaction accepted at the start, on (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 -cores at 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 -cores at and size-matched SAC groups. If the tolerances that drive the dynamics deviate from those used in the search by a factor with standard normal , 0–3.5% of the LCC groups lose an interaction, against 0.9–4.1% of the pairwise groups and 25–38% of the -cores at .
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.
| Graph | Queries | Larger (%) | Size ratio | Concentrated Any | Concentrated Per run | Gossip Any | Gossip Per run | Follow one Any | Follow one Per run |
| Gowalla | 2,469 | 60.4 | 1.08 | 40.4 | 13.2 | 16.6 | 5.1 | 6.9 | 1.9 |
| Brightkite | 462 | 60.8 | 1.09 | 33.4 | 8.1 | 10.6 | 2.9 | 7.8 | 1.5 |
| LiveJournal | 87 | 93.1 | 1.33 | 31.8 | 4.8 | 2.8 | 0.8 | 0.0 | 0.0 |
| Orkut | 102 | 97.1 | 1.52 | 39.5 | 7.8 | 7.0 | 1.7 | 0.8 | 0.2 |
Table VIII. LCC AGAINST PAIRWISE GROUPS: SIZES, AND PAIRWISE GROUPS (%) THAT LOSE AN ACCEPTED INTERACTION ON .
Open groups: We add outside influence to test the closed-group assumption. Each accepted outside friend gets weight , 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 , 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 . 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 of Proposition 3 beyond . Already at , 34% and 23% of the LCC groups lose an interaction accepted at the start, and at , 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%).
| Gowalla | Brightkite | Congress | ||||||||
| 0.01 | 0.1 | 1 | 0.01 | 0.1 | 1 | 0.01 | 0.1 | 1 | obs. | |
| Groups that lose an interaction (%) | 34.1 | 48.4 | 65.2 | 22.5 | 37.7 | 62.1 | 0 | 0 | 80.6 | 98.2 |
| lost share (median, %) | 4.0 | 8.5 | 11.0 | 0.4 | 11.8 | 10.8 | – | – | 2.1 | 5.3 |
| first loss (median step) | 1 | 1 | 1 | 1 | 1 | 1 | – | – | 2 | 1 |
| Largest final cluster (mean, %) | 23.5 | 17.7 | 16.8 | 24.0 | 18.0 | 18.8 | 71.6 | 11.8 | 5.2 | 3.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 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 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 -core is a query, with : 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 -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 -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 -cores and 65%, 72% and 84% for -cores at . 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 -cores at 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 -cores at , LCC groups are ahead at equal size only on Yelp (+0.08 pp [0.04, 0.11] in pair rate, by (b)). Across and tolerances at the 70th and 90th percentiles (on Yelp, 2,000 queries per setting), the raw differences against size-matched SAC and -cores at 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).
| Gowalla | Brightkite | Yelp | |
| 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 / 610 | 462 / 108 | 5,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 (−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 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 -core of ’s component restricted to friendships whose two ends accept each other is empty, so has no 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 lacks such friends. Only a smaller 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 -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 -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, 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.
| Data | Queries | No LCC | A | B | C | U | 70th | 90th | No LCC | A | B | C | U |
| Gowalla | 15,829 | 13,360 (84.4%) | 95.0 | 3.2 | 1.8 | 0 | 15.0 | 35.6 | 54.7 | 85.1 | 11.8 | 3.1 | 0 |
| Brightkite | 5,260 | 4,798 (91.2%) | 96.7 | 2.6 | 0.6 | 0 | 10.0 | 33.3 | 60.8 | 81.7 | 14.3 | 3.9 | 0 |
| Yelp | 10,363 | 5,353 (51.7%) | 86.3 | 7.8 | 4.4 | 1.5 | 23.5 | 49.7 | 26.1 | 67.4 | 15.9 | 9.6 | 7.1 |
| Congress | 472 | 18 (3.8%) | 14 | 2 | 2 | 0 | 12/18 | 16/18 | – | – | – | – | – |
Table XVII. QUERIES WITHOUT AN LCC () BY CAUSE, AND WITH RAISED TOLERANCES.
| LCC (%) | Proven (%) | Size | A | B | C | U | Kept (%) | Gained (%) | Share (%) | vs. (pp) | |
| \multicolumn{12}{l}{Gowalla (15,829 queries)} | |||||||||||
| 0.5 | 7.9 | 100.0 | 9 | 14,204 | 244 | 129 | 0 | 50.7 (0.58) | – | 11.12 | +3.73 [3.15,4.40] |
| 0.67 | 10.5 | 100.0 | 10 | 13,617 | 392 | 159 | 0 | 67.3 (0.67) | – | 9.44 | +1.86 [1.52,2.26] |
| 0.8 | 12.5 | 100.0 | 11 | 13,237 | 424 | 194 | 0 | 80.0 (0.82) | – | 8.84 | +1.30 [1.03,1.59] |
| 1 | 15.6 | 100.0 | 16 | 12,691 | 423 | 246 | 0 | – | – | 8.42 | – |
| 1.25 | 19.3 | 100.0 | 22 | 11,942 | 557 | 270 | 0 | – | 4.4 | 7.33 | −1.29 [−1.57,−1.03] |
| 1.5 | 22.7 | 100.0 | 27 | 11,431 | 552 | 252 | 0 | – | 8.4 | 6.67 | −2.18 [−2.51,−1.87] |
| 2 | 27.3 | 100.0 | 40 | 10,657 | 583 | 274 | 0 | – | 13.8 | 5.93 | −3.09 [−3.50,−2.69] |
| 3 | 33.9 | 100.0 | 53 | 9,683 | 563 | 224 | 0 | – | 21.6 | 5.13 | −3.84 [−4.28,−3.41] |
| \multicolumn{12}{l}{Brightkite (5,260 queries)} | |||||||||||
| 0.5 | 4.5 | 100.0 | 8 | 4,970 | 48 | 6 | 0 | 51.1 (0.78) | – | 8.58 | +1.18 [0.34,2.13] |
| 0.67 | 5.9 | 100.0 | 8 | 4,849 | 77 | 22 | 0 | 67.5 (0.80) | – | 7.56 | +0.68 [0.18,1.21] |
| 0.8 | 7.1 | 100.0 | 8 | 4,762 | 106 | 21 | 0 | 80.3 (0.89) | – | 6.44 | +0.24 [−0.08,0.59] |
| 1 | 8.8 | 100.0 | 10 | 4,640 | 127 | 31 | 0 | – | – | 5.67 | – |
| 1.25 | 11.0 | 100.0 | 12 | 4,473 | 146 | 62 | 0 | – | 2.4 | 4.32 | −1.35 [−1.91,−0.85] |
| 1.5 | 12.9 | 100.0 | 13 | 4,326 | 172 | 85 | 0 | – | 4.5 | 3.60 | −2.11 [−2.74,−1.52] |
| 2 | 17.1 | 100.0 | 16 | 4,088 | 175 | 95 | 0 | – | 9.2 | 3.15 | −3.19 [−4.18,−2.32] |
| 3 | 23.5 | 100.0 | 24 | 3,746 | 186 | 92 | 0 | – | 16.1 | 2.52 | −3.75 [−4.80,−2.79] |
| \multicolumn{12}{l}{Yelp (2,000 queries)} | |||||||||||
| 0.5 | 29.7 | 99.9 | 144.5 | 1,282 | 79 | 41 | 4 | 61.6 (0.32) | – | 2.53 | +1.07 [0.90,1.26] |
| 0.67 | 36.7 | 99.7 | 217 | 1,117 | 96 | 38 | 15 | 76.1 (0.52) | – | 2.26 | +0.71 [0.59,0.84] |
| 0.8 | 42.2 | 99.5 | 271 | 1,020 | 74 | 51 | 11 | 87.4 (0.69) | – | 1.97 | +0.39 [0.28,0.49] |
| 1 | 48.2 | 95.7 | 379 | 700 | 68 | 48 | 13 | – | – | 1.70 | – |
| 1.25 | 53.8 | 88.9 | 477 | 792 | 78 | 34 | 21 | – | 10.7 | 1.59 | −0.25 [−0.32,−0.18] |
| 1.5 | 58.1 | 87.1 | 549 | 692 | 88 | 31 | 27 | – | 19.2 | 1.44 | −0.43 [−0.52,−0.35] |
| 2 | 65.0 | 84.9 | 679 | 572 | 71 | 34 | 24 | – | 32.5 | 1.19 | −0.70 [−0.82,−0.60] |
| 3 | 74.2 | 84.0 | 824 | 402 | 67 | 33 | 15 | – | 50.2 | 0.98 | −0.88 [−1.01,−0.76] |
Table XVIII. TOLERANCE SCALING: EVERY TOLERANCE MULTIPLIED BY .
Figure 4. Groups for one Congress query ().
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; is the median distance from to the sponsors of the bills that co-sponsored from January 2021 to February 8, 2022 [59] (median 0.145, floor 0.02, which no member reaches); and 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 ’s -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 interacted with , with sender and receiver effects, a spline in the distance, and indicators of the same party, state and chamber, the coefficient of is (one-sided permutation , 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 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, ).
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 -cores at , size-matched SAC groups and global -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 -cores at ; global -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 , but 22%, 41% and 81% do at and , 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 (22% against 11% at ), and more often than pairwise groups at 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 (, );
| Method | (iii) holds | Members | Pairs |
| LCC (Exact, Greedy, BallCore-F) | 100 | 0 | 0 |
| Pairwise | 0.7 | 0 | 0 |
| -core at | 15.6 | 4.9 | 1.3 |
| Size-matched SAC | 2.2 | 8.2 | 1.5 |
| SAC | 87.1 | 14.3 | 14.2 |
| Global -core | 1.7 | 56.7 | 19.1 |
| BallCore-R | 0.9 | 49.6 | 12.9 |
| Random, -core, edge-accept | 0 | 100 | 71.6–77.4 |
Table V. Tolerance violations in Congress groups (, 472 queries).
only 90th-percentile tolerances give a positive coefficient (0.42, , 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 ’s -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 -cores at ). For each method, the last row of both tables reports its groups under equal-weight HK on . 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, -cores at , 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 -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 times stricter, or with weights drawn in each run from a Dirichlet distribution with or . 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 such steps (50 rounds on complete graphs). SJT (2) uses equal weights, , and ; 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 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 ( in Section VI-C; at most 200 outside neighbours per member, sampled at random); stubborn outsiders pull each member with weight towards the fixed mean of all its outside neighbours, near or far; with tolerance noise, the dynamics use with standard normal , whereas the groups were found with .
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 . On complete interaction graphs, pairwise groups also lose interactions under uneven influence (up to 30%), and the -cores at 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 , about 1% of the LCC groups do, against 52–68% of the -cores at . Up to , tolerance noise barely affects LCC and pairwise groups (below 1%), while 16–39% of -cores at lose an interaction.
| Variant | -core at G | -core at B | -core at L | -core at O | Global -core G | Global -core B | Global -core L | Global -core O | SAC G | SAC B | SAC L | SAC O | Size-matched SAC G | Size-matched SAC B | Size-matched SAC L | Size-matched SAC O | Random G | Random B | Random L | Random O |
| Closed group, interactions on | ||||||||||||||||||||
| HK, equal weights | 15 | 17 | 4 | 13 | 60 | 33 | 7 | 6 | 18 | 32 | 1 | 3 | 5 | 8 | 1 | 2 | 37 | 27 | 0 | 0 |
| HK, equal, 3,000 steps | 15 | 17 | 4 | 13 | 60 | 33 | 7 | 6 | 18 | 32 | 1 | 3 | 5 | 8 | 1 | 2 | 37 | 27 | 0 | 0 |
| HK, random weights, | 26 | 35 | 43 | 68 | 77 | 81 | 53 | 77 | 26 | 43 | 22 | 42 | 21 | 29 | 38 | 59 | 55 | 45 | 21 | 26 |
| HK, random weights, | 41 | 44 | 91 | 97 | 86 | 89 | 99 | 99 | 41 | 56 | 78 | 84 | 52 | 56 | 89 | 98 | 64 | 53 | 75 | 69 |
| Follow one neighbour | 33 | 39 | 58 | 78 | 82 | 81 | 73 | 86 | 30 | 45 | 26 | 41 | 35 | 35 | 48 | 67 | 55 | 45 | 15 | 24 |
| Gossip (DW) | 34 | 40 | 69 | 85 | 83 | 82 | 81 | 93 | 32 | 47 | 38 | 55 | 39 | 40 | 63 | 86 | 57 | 47 | 39 | 31 |
| SJT, new rejection | 25 | 31 | 92 | 98 | 75 | 71 | 99 | 99 | 28 | 47 | 61 | 83 | 21 | 31 | 85 | 97 | 90 | 89 | 98 | 97 |
| Closed group, complete interaction graph | ||||||||||||||||||||
| HK, equal weights | 18 | 23 | 33 | 54 | 59 | 50 | 39 | 56 | 15 | 31 | 13 | 25 | 8 | 14 | 15 | 34 | 53 | 40 | 2 | 2 |
| HK, random weights, | 18 | 31 | 37 | 69 | 62 | 68 | 43 | 76 | 18 | 40 | 17 | 42 | 17 | 28 | 29 | 65 | 65 | 61 | 29 | 37 |
| HK, random weights, | 29 | 45 | 89 | 95 | 79 | 87 | 97 | 99 | 31 | 51 | 74 | 83 | 37 | 47 | 88 | 98 | 74 | 68 | 81 | 84 |
| Follow one neighbour | 36 | 43 | 70 | 89 | 77 | 86 | 78 | 96 | 30 | 44 | 40 | 58 | 45 | 48 | 63 | 88 | 67 | 61 | 39 | 39 |
| Gossip (DW) | 27 | 42 | 54 | 78 | 73 | 81 | 74 | 84 | 28 | 43 | 34 | 53 | 41 | 46 | 50 | 80 | 66 | 61 | 33 | 30 |
| SJT, new rejection | 24 | 29 | 92 | 100 | 71 | 75 | 99 | 99 | 23 | 44 | 67 | 85 | 19 | 30 | 93 | 97 | 78 | 78 | 93 | 97 |
| Assumptions violated | ||||||||||||||||||||
| Open group, | 75 | 80 | 4 | 12 | 84 | 84 | 5 | 9 | 61 | 74 | 4 | 11 | 73 | 79 | 5 | 14 | 49 | 37 | 0 | <1 |
| Open group, complete | 73 | 81 | 33 | 55 | 80 | 87 | 39 | 57 | 58 | 72 | 14 | 31 | 70 | 80 | 15 | 44 | 60 | 46 | 2 | 3 |
| Stubborn outsiders, | 96 | 99 | 52 | 68 | 97 | 99 | 64 | 76 | 92 | 97 | 24 | 29 | 95 | 99 | 38 | 45 | 80 | 77 | 12 | 9 |
| Stubborn outsiders, | 98 | 100 | 83 | 90 | 99 | 100 | 97 | 97 | 97 | 99 | 59 | 60 | 95 | 100 | 79 | 82 | 89 | 86 | 48 | 35 |
| Stubborn outsiders, | 99 | 100 | 96 | 97 | 99 | 100 | 99 | 100 | 98 | 99 | 80 | 84 | 99 | 100 | 95 | 97 | 91 | 88 | 80 | 70 |
| Tolerance noise, | 17 | 22 | 16 | 32 | 65 | 58 | 15 | 20 | 17 | 33 | 4 | 10 | 9 | 13 | 6 | 10 | 44 | 32 | 0 | <1 |
| Tolerance noise, | 23 | 27 | 21 | 39 | 70 | 65 | 24 | 34 | 20 | 37 | 8 | 12 | 15 | 19 | 9 | 14 | 48 | 37 | 0 | 3 |
| Tolerance noise, | 28 | 35 | 25 | 38 | 74 | 73 | 31 | 40 | 26 | 39 | 10 | 16 | 23 | 29 | 15 | 23 | 51 | 42 | 1 | 2 |
| Groups (HK, equal, ) | 1,000 | 462 | 95 | 115 | 994 | 428 | 150 | 162 | 1,243 | 745 | 153 | 178 | 1,000 | 462 | 95 | 115 | 1,000 | 462 | 95 | 115 |
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 and −0.13 pp with tolerances at the 90th percentile (both CIs below 0), and CIs containing 0 at , 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 ( accepts ) 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).
| Gowalla | Brightkite | |
| Pairwise groups with a refusal | 402 of 1,000 | 153 of 462 |
| Refused interactions, all runs | 2,200 | 592 |
| Initial , median [quartiles] | 0.55 [0.36, 0.73] | 0.55 [0.28, 0.77] |
| Initial (%) | 8.9 | 11.8 |
| Step of refusal, median | 1 | 1 |
| Largest , median | 1.08 | 1.10 |
| Still refused at the end (%) | 1.2 | 1.0 |
| Refuser is the least tolerant member (%) | 45.3 | 73.3 |
| Refuser among the three least tolerant (%) | 72.9 | 93.9 |
| Refuser outside the LCC (%) | 69.1 | 71.1 |
| Refuser or refused outside the LCC (%) | 83.7 | 82.4 |
| Pairwise members outside the LCC, median | 22.5 | 5 |
Table IX. REFUSED INTERACTIONS IN PAIRWISE GROUPS UNDER CONCENTRATED WEIGHTS (; REFUSES ).
At the start, refused interactions are not close to tolerance (median 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 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 ( 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 ( km, the second least tolerant of the 33 members, in the LCC of 27 members) grows from 0.50 to and is back within 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 , 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 is the heuristic -core search with the median tolerance. With equal tolerances, every -core at 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 -core. As grows, fewer queries have an LCC, and the -cores at 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 times the median distance between friends (106.9 on LiveJournal and 126 on Orkut, mostly between communities), without calibration on Exact; already corresponds to scales of 9.4 and 11.1, against the calibrated 1.5 and 1.25. We also draw queries uniformly from the whole -core instead of from groups of at least 20 members, and move a share of the vertices to a random community. Where tolerances reach the scale between communities ( on Orkut, 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 ); 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 and Orkut at , 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, 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 -core search containing without personal tolerances, at the median tolerance of all vertices (the radius of the global baseline) and at the threshold 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 .
| Graph | Search | Proven non-empty | Proven empty | Limit | Time (ms) | Median | Sweep faster (%) |
| LiveJournal | Sweep (Exact) | 95 | 105 | 0 | 0.13 | – | – |
| LiveJournal | -core at median | 131 | 50 | 19 | 2.1 | 0.89 | 55 |
| LiveJournal | -core at (95 queries) | 79 | – | 16 | 6.2 | 0.86 | 56 |
| Orkut | Sweep (Exact) | 115 | 85 | 0 | 3.2 | – | – |
| Orkut | -core at median | 96 | 33 | 71 | 959 | 0.065 | 92 |
| Orkut | -core at (115 queries) | 78 | – | 37 | 2,586 | 0.135 | 94 |
Table XIII. The sweep and single-threshold -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 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; 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 -cores at , 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 -core of ’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 (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 , column Kept gives the share (%) of the queries with an LCC at that keep one, with the median size ratio of the kept LCCs in parentheses; for , column Gained gives the share of the queries without an LCC at that gain one. The last two columns report the mean co-visiting share of member pairs in LCC groups and its difference from , for queries with an LCC at both scales (pp, 95% bootstrap CI). Whenever both solutions are proven, increasing 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 . Class A dominates queries without an LCC at every . Shrinking tolerances also protects against noisy estimates: with tolerance noise in equal-weight HK on (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 lose an interaction accepted at the start, against 0% [0, 0.19] and 1.08% [0.42, 2.74] at (Wilson intervals; without noise, none does).
| Split | Measure | Raw | (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 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 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 , 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 , where no LCC group loses an interaction, only 11.8%. Pairwise groups, size-matched SAC groups and -cores at 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.
| Variant | LCC (Exact) G | LCC (Exact) B | LCC (Exact) L | LCC (Exact) O | Greedy G | Greedy B | Greedy L | Greedy O | BallCore-R G | BallCore-R B | BallCore-R L | BallCore-R O | Pairwise G | Pairwise B | Pairwise L | Pairwise O | Edge-accept G | Edge-accept B | Edge-accept L | Edge-accept O | LCC groups G | LCC groups B | LCC groups L | LCC groups O | G/B/L/O |
| Closed group, interactions on | |||||||||||||||||||||||||
| HK, equal weights | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | <1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 67 | 63 | – | – | 1,000/462/95/115 | ||||
| HK, equal, 3,000 steps | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | <1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 67 | 63 | – | – | 1,000/462/95/115 | ||||
| HK, random weights, | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 19 | 7 | 0 | <1 | 1 | <1 | 0 | 0 | 78 | 77 | – | – | 1,000/462/95/115 | ||||
| HK, random weights, | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 62 | 56 | 64 | 76 | 40 | 33 | 32 | 40 | 85 | 85 | – | – | 1,000/462/95/115 | ||||
| Follow one neighbour | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 45 | 31 | 3 | 12 | 7 | 8 | 0 | <1 | 81 | 80 | – | – | 1,000/462/95/115 | ||||
| Gossip (DW) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 54 | 38 | 28 | 58 | 17 | 11 | 3 | 7 | 82 | 82 | – | – | 1,000/462/95/115 | ||||
| SJT, new rejection | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 29 | 15 | 49 | 82 | <1 | 0 | 0 | <1 | 74 | 73 | – | – | 1,000/462/95/115 | ||||
| Closed group, complete interaction graph | |||||||||||||||||||||||||
| HK, equal weights | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | <1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 57 | 62 | – | – | 1,000/462/95/115 | ||||
| HK, random weights, | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 2 | 2 | 0 | 0 | 0 | 0 | 0 | 57 | 73 | – | – | 931/462/95/115 | ||||
| HK, random weights, | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 29 | 39 | 11 | 12 | 13 | 23 | 5 | 4 | 76 | 85 | – | – | 931/462/95/115 | ||||
| Follow one neighbour | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 51 | 46 | 10 | 33 | 30 | 17 | 1 | <1 | 72 | 82 | – | – | 931/462/95/115 | ||||
| Gossip (DW) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 47 | 44 | 7 | 43 | 27 | 21 | 6 | 17 | 66 | 72 | – | – | 907/462/63/71 | ||||
| SJT, new rejection | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 16 | 17 | 65 | 87 | <1 | 0 | 0 | 2 | 70 | 72 | – | – | 1,000/462/95/115 | ||||
| Assumptions violated | |||||||||||||||||||||||||
| Open group, | 65 | 62 | 0 | 0 | 63 | 63 | 0 | 0 | 74 | 70 | 0 | 0 | 72 | 67 | 0 | 0 | 83 | 85 | – | – | 1,000/462/95/115 | ||||
| Open group, complete | 61 | 57 | 0 | 0 | 57 | 57 | 0 | 0 | 67 | 62 | 0 | 0 | 65 | 60 | 0 | 0 | 78 | 86 | – | – | 1,000/462/95/115 | ||||
| Stubborn outsiders, | 91 | 94 | 1 | <1 | 90 | 94 | 1 | 1 | 93 | 97 | 3 | 2 | 93 | 97 | 0 | 2 | 97 | 100 | – | – | 1,000/462/95/115 | ||||
| Stubborn outsiders, | 98 | 99 | 49 | 33 | 98 | 99 | 39 | 26 | 98 | 100 | 73 | 46 | 98 | 100 | 65 | 38 | 99 | 100 | – | – | 1,000/462/95/115 | ||||
| Stubborn outsiders, | 99 | 100 | 91 | 71 | 98 | 100 | 88 | 68 | 99 | 100 | 93 | 84 | 99 | 100 | 93 | 80 | 99 | 100 | – | – | 1,000/462/95/115 | ||||
| Tolerance noise, | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 70 | 69 | – | – | 1,000/462/95/115 | ||||
| Tolerance noise, | 0 | <1 | 0 | 0 | <1 | 0 | 0 | 0 | 16 | 5 | <1 | 3 | 0 | <1 | 0 | 0 | 73 | 73 | – | – | 1,000/462/95/115 | ||||
| Tolerance noise, | 2 | 3 | 0 | 3 | 2 | 4 | 0 | 1 | 31 | 21 | 6 | 12 | 3 | 4 | <1 | 2 | 76 | 75 | – | – | 1,000/462/95/115 | ||||
| Groups (HK, equal, ) | 1,000 | 462 | 95 | 115 | 887 | 447 | 83 | 93 | 1,004 | 467 | 107 | 130 | 1,003 | 464 | 107 | 129 | 1,011 | 471 | – | – |
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]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]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]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]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]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]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]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]M. Sherif and C. I. Hovland, Social Judgment: Assimilation and Contrast Effects in Communication and Attitude Change. Yale University Press, 1961.
- [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]J. Lorenz, “Heterogeneous bounds of confidence: Meet, discuss and find consensus!” Complexity, vol. 15, no. 4, pp. 43–52, 2010.DOI
- [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]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]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]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]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]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]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]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]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]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]Y. Liu, F. Guo, H. Shen, and X. Cheng, “Rethinking community consistency in heterogeneous networks,” in CIKM, 2026, pp. 3293–3304.DOI
- [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]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]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]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]———, “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]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]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]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]M. H. DeGroot, “Reaching a consensus,” J. Am. Stat. Assoc., vol. 69, no. 345, pp. 118–121, 1974.DOI
- [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]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]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]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]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]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]C. Monti, G. De Francisci Morales, and F. Bonchi, “Learning opinion dynamics from social traces,” in KDD, 2020, pp. 764–773.
- [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]T. Lappas, K. Liu, and E. Terzi, “Finding a team of experts in social networks,” in KDD, 2009, pp. 467–476.DOI
- [40]S. B. Seidman, “Network structure and minimum degree,” Social Networks, vol. 5, no. 3, pp. 269–287, 1983.DOI
- [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]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]R. M. Karp, “Reducibility among combinatorial problems,” in Complexity of Computer Computations. Plenum Press, 1972, pp. 85–103.
- [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]H. Maehara, “Space graphs and sphericity,” Discrete Applied Mathematics, vol. 7, no. 1, pp. 55–64, 1984.DOI
- [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]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]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]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]J. Yang and J. Leskovec, “Defining and evaluating network communities based on ground-truth,” in ICDM, 2012, pp. 745–754.
- [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]J. Leskovec and A. Krevl, “SNAP Datasets: Stanford large network dataset collection,” http://snap.stanford.edu/data/, Jun. 2014.
- [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]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]Google, “OR-Tools, version 9.15, with the CP-SAT solver,” https://developers.google.com/optimization/, 2026.
- [56]Yelp, “Yelp Open Dataset,” https://www.yelp.com/dataset, 2022, accessed 2026.
- [57]K. T. Poole and H. Rosenthal, Ideology and Congress, 2nd ed. New Brunswick, NJ: Transaction Publishers, 2007.
- [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]U.S. Government Publishing Office, “Bill status (BILLSTATUS) bulk data, 117th Congress,” https://www.govinfo.gov/bulkdata/BILLSTATUS, 2026, accessed Oct. 2026.
- [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]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]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.


