PDFs that Calibre scrambles, as a clean reflowable EPUB.

friends, we give a sufficient condition. II. RELATED WORK

• Complexity (Section IV-B). Finding a largest LCC is NP-

hard even with equal tolerances in the plane and on the Community search: Community search identifies a cohe-

sphere; with the dimension as part of the input, it is not sive subgraph containing a query vertex, usually a connected

approximable within 1−ε k-core [1], [11] or k-truss [12]; a survey is given in [2]. n unless P = NP , and for each

fixed Attributed variants add conditions on attributes: ACQ [13] k ≥ 2 even deciding whether an LCC exists is NP-

complete; it is polynomial on a line. maximizes the keywords shared by all members, VAC [7]

• minimizes the largest pairwise attribute distance in a k-truss Algorithms (Section V). LatSweep fixes the smallest

tolerance (NP-hard, with a 2-approximation), and skyline community τ of the answer. Every member must then

satisfy search [14] returns the cohesive communities of a bipar- d ( x v , x q ) ≤ τ ≤ θ v , which turns the coupled

constraint into a sweep over survival intervals with a tite graph that none dominates on multi-dimensional edge

common threshold at each step (Fig. 2). The sweep attributes. (k, r)-cores [3] require all pairs of members to

yields BallCore-F and a greedy variant, which return only be similar within one threshold, and (k, P )-cores [15] ex-

LCCs; BallCore-R, a polynomial-time tend k-cores to heterogeneous information networks, where (1 , 2) -bicriteria

approximation whose diameter factor cannot be improved significant-attributed community search [16] maximizes the

in general metrics unless smallest significance of a member and FCS-HGNN [17] learns P = NP ; and an exact branch-

and-bound algorithm that refines upper bounds best-first to return communities that span several vertex types. In density

and, if stopped early, returns the best LCC found, if personalized group queries [18], members individually bound

any, with a proven bound on the optimum. A query- their number of friends within the group. These models

Here, positions are opinions in m under any norm ∥·∥. A R updates, in which only some vertices apply (1) at each step,

group H starts from xv(0) = xv; the graph and the tolerances Theorem 1(a) and the monotonicity of diam(t) still hold, and are fixed, interactions follow edges of G[H], and diam(t) = if every vertex updates at least once in every κ consecutive maxu,v∈H ∥xu(t) − xv(t)∥. steps, applying (b) to blocks of κ steps gives convergence

Bounded-confidence dynamics: In the network version of (cf. [42]). The loose rate bound in (b) serves only to establish

the Hegselmann–Krause (HK) model [9] with agent-specific geometric convergence.

bounds [10], vertex v averages the opinions of the neighbours Social-judgment dynamics: SJT adds noncommitment

it accepts: and rejection. Following Jager and Amblard [36], vertex v

X moves towards accepted neighbours, ignores noncommittal

x v (t + 1) = wvu (t) xu(t), (1) ones, and moves away from rejected ones:

u∈Av (t)∪{v}

x X ( t + 1) = x ( t ) + α x ( t ) − x ( t )

where v v vu u v A ( t ) = { u ∈ N ( v ) : ∥ x ( t ) − x ( t ) ∥ ≤ θ } , the

v H u v v

weights are non-negative with unit sum, and u∈Av (t) w vu ( t ) ≥ η > 0 for X u ∈ A v vu v β ( t ) ∪ { v } ; equal weights w ( t ) = 1 / ( | A ( t ) | + 1) − x ( t ) − x ( t ), (2)

vu u v

give η = 1/|H|. An interaction along (u, v) is accepted at u∈Rv(t)

 

time t if u ∈ Av(t). acc where A v ( t ) uses θ v, Rv(t) = {u ∈ NH (v) : ∥xu(t) − Lemma 1. rej If every x ( t + 1) is a convex combination of x ( t ) ∥ > θ}, and α , β ≥ 0 may vary with t, with

Notation: Let G = (V, E) be an undirected simple graph

with 1 k-cores: For S ⊆ V , the k-core [40] of G[S] is its n = | V | . For H ⊆ V , G [ H ] is the induced subgraph and

N unique maximal subgraph with minimum degree at least k, and H ( v ) the set of neighbours of v in G [ H ] . Each vertex has a

position C xk(S, q) denotes the component of this k-core that contains v ∈ X and a tolerance θ v > 0 ; we write diam( H ) =

max q, or the empty set if q is not in the k-core; peeling computes u,v ∈ H d ( x u , x v ) and θ min ( H ) = min w ∈ H θ w ; Table I lists

the main notation. it in O(|S| + |E(S)|) time [41], and we use the same notation

for peeling in a spanning subgraph of G. Throughout, we use

1 the k-core fact: every connected H ⊆ S with q ∈ H and

For a heterogeneous information network, G can be the homogeneous

graph induced by a meta-path, as for (k, P)-cores [15]. minimum degree at least k satisfies H ⊆ Ck(S, q).