{"id":"76cc27eb-59a3-4365-964e-23b39f44a7bb","arxiv_id":"1908.11612","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new h-index based structural diversity score built from discriminative cores, with an efficient top-k search algorithm and experiments on four public social networks.","lead":"This paper proposes a parameter-free way to rank people by how many distinct social groups they belong to, removing the need to choose a group-size threshold. It introduces discriminative cores and an h-index style score, plus a fast top-k search algorithm, and tests it on four large social networks.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Definition 3.5 and Algorithm 2 disagree on what a discriminative core is, so the h(v) scores reported by the paper are not well-defined.","rationale":"The paper's central contribution is a parameter-free score h(v) built on an allegedly well-defined notion of discriminative core. The reader identified that Definition 3.5 and Algorithm 2 diverge, and my re-derivation confirms this. I constructed a concrete ego-network where Algorithm 2 discards a coreness-2 component because it touches a coreness-3 vertex, while the literal Definition 3.5, under the natural maximality reading, admits a coreness-2 discriminative core that includes some coreness-3 vertices. The resulting diversity vectors and h(v) scores differ, so the paper's experiments and top-k claims are computed for an object that is not formally defined. The issue is not an internal error in Algorithm 2; the algorithm is fully specified. The gap is that the algorithm's notion is never formalized, and the proof of Lemma 5.5 also silently assumes disjointness of discriminative cores, which the literal definition does not guarantee. This is a load-bearing concern because the score, the search problem, and the upper bound all depend on the meaning of discriminative core. It is correctable by revising Definition 3.5 to state that a discriminative core is a connected component of the subgraph induced by vertices of exactly coreness t with no edge to higher coreness, or by proving that Algorithm 2 follows from a revised definition. Given that the proposed algorithm and upper-bound framework are otherwise plausible and the flaw is definitional rather than computational, a conditional acceptance remains the appropriate verdict.","tokens_in":12836,"tokens_out":18209,"duration_ms":178911,"concrete_test":"Run Algorithm 2 on the 6-vertex ego-network G0: vertices {b,p,q,r} form a K4, vertices {a,c,d} form a triangle, and edge (a,b) connects them. Record C(v) and h(v) from Algorithm 2. Then independently enumerate all maximal connected subgraphs H of G0 satisfying the literal condition of Definition 3.5 (no subgraph H'⊆H with φ(H')>φ(H)) and compute C(v) and h(v) from that enumeration. If the two vectors differ—as expected, Algorithm 2 gives cv(2)=0,cv(3)=1 and h(v)=1, while the literal definition gives cv(2)=1,cv(3)=1 and h(v)=2—then Definition 3.5 must be revised to match Algorithm 2, or Algorithm 2's notion must be adopted as the intended definition. A second check is to verify the disjointness assumption in Lemma 5.5's proof by testing whether two maximal literal discriminative cores can overlap and reduce the number of distinct vertices below x*·(x*+1).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central quantity h(v) is defined through discriminative cores (Definition 3.5), but Algorithm 2 imposes an extra condition not stated there: a connected component at coreness t is counted only if it has no edge to any vertex of higher coreness (Algorithm 2, lines 16–17). Under the natural reading of Definition 3.5—maximal among connected subgraphs H with no subgraph H'⊆H satisfying φ(H')>φ(H)—the two notions diverge. Consider an ego-network consisting of a K4 clique and a triangle attached to one K4 vertex by a single edge. The subgraph induced by the triangle plus three of the four K4 vertices has minimum degree 2 and contains no subgraph of coreness 3; adding the fourth K4 vertex creates the K4 and violates the condition. Hence this 6-vertex graph is a maximal coreness-2 discriminative core under the literal Definition 3.5, even though it contains vertices of global coreness 3. Algorithm 2, however, sees the coreness-2 triangle and the edge to a coreness-3 vertex, sets Flag=false, and counts no coreness-2 core at all. The diversity vectors differ: Algorithm 2 yields cv(2)=0, cv(3)=1, so h(v)=1; the literal Definition 3.5 yields cv(2)=1, cv(3)=1, so h(v)=2. The paper never proves that Algorithm 2 implements Definition 3.5, and the assertion in Section 4.2 that a discriminative core of coreness t 'will be only formed by vertices with coreness exactly t' is a further unstated restriction. Moreover, Lemma 5.5's proof counts x*·(x*+1) distinct vertices across x* cores; under the literal definition, maximal cores can overlap, so this counting step is unjustified unless disjointness is proved. Since every experimental and algorithmic result is computed with Algorithm 2, the reported scores are for a model that is never formally defined. This is correctable by rewriting Definition 3.5 or proving Algorithm 2 implements it, but it is load-bearing: the parameter-free score, the top-k statement, and the upper bound all presuppose a unique notion of discriminative core.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript addresses the top-k structural diversity search problem, where the structural diversity of a vertex is the multiplicity of distinct social contexts in its ego-network. Existing models based on t-sized components, t-core, or t-brace require a user-specified parameter t. The paper proposes a parameter-free model: a discriminative core (Definition 3.5) is a maximal connected subgraph H with no subgraph H' ⊆ H of higher coreness φ(H') > φ(H); the diversity vector C(v) counts discriminative cores by their coreness in GN(v), and the diversity score h(v) is the largest r such that at least r discriminative cores have coreness at least r (Definition 3.6). The paper gives a baseline algorithm (Algorithms 1-3), an upper bound bh(v) (Lemma 5.5), and a top-k search framework (Algorithm 4) with claimed O(ρm) time and O(m) space. Experiments on Gowalla, Youtube, LiveJournal, and Orkut compare efficiency with the baseline and t-core, demonstrate parameter sensitivity of t-core, and evaluate effectiveness using an independent cascade simulation.","tokens_in":13206,"tokens_out":12861,"duration_ms":111256,"significance":"Assuming the formal model is repaired, the paper's parameter-free formulation is a useful contribution to structural diversity search: it removes the t parameter while preserving the ability to distinguish social contexts of different strengths, and the h-index combination of count and strength is natural. The upper-bound pruning scheme and its O(ρm) analysis are valuable, and the use of an external influence-propagation simulation for effectiveness is a strength. However, the paper's central quantity h(v) is not well-defined as written, because the formal definition of discriminative core and the algorithm used to compute it describe different objects; this issue affects the correctness of all reported scores and of the pruning bound. The paper also has a gap in the proof of Lemma 5.5 regarding vertex-disjointness of discriminative cores. With a revised definition and a completed proof, the contribution would be solid.","major_comments":[{"comment":"Definition 3.5 and Algorithm 2 define different objects. Under the literal reading of Definition 3.5, an ego-network consisting of a K4 on {a,b,c,d} and a triangle on {x,y,z} with a single edge (a,x) has a coreness-2 discriminative core induced by {a,b,c,x,y,z}: this subgraph has minimum degree 2, contains no subgraph of coreness 3, and is maximal connected with that property, since adding d creates the K4. Algorithm 2, however, assigns coreness 3 to a and coreness 2 to x,y,z; when BFS explores the coreness-2 component x,y,z it sees the edge to a, sets Flag=false, and reports cv(2)=0. The resulting diversity vector differs from Definition 3.6 (cv(2)=1 under the definition), and hence h(v) differs. The assertion in Section 4.2 that a coreness-t discriminative core 'will be only formed by the vertices with the coreness of exactly t' is an additional restriction that is not entailed by Definition 3.5, and the paper does not prove that Algorithm 2 implements Definition 3.5. This must be fixed by either revising Definition 3.5 to the operational characterization (connected component of equal-coreness vertices with no edge to higher coreness) and stating maximality with respect to inclusion, or by changing Algorithm 2 and Lemma 5.5 to match Definition 3.5.","section":"Definition 3.5, Section 4.2, Algorithm 2"},{"comment":"The proof of Lemma 5.5 assumes that the x* discriminative cores with coreness at least x* have disjoint vertex sets, so that their combined size is at least x*·(x*+1). Under Definition 3.5 this disjointness does not hold: discriminative cores of different coreness can overlap (in the example above, the coreness-2 core and the K4 share vertex a). The inequality |{u∈N(v): φ_GN(v)(u)≥x*}| ≥ x*(x*+1) is therefore not established, and the upper bound bh(v) may be invalid for the defined score. If the authors adopt the operational definition that makes Algorithm 2 correct, cores of different coreness are disjoint by construction because each vertex has a unique coreness, but this property and its use in the proof must be stated explicitly.","section":"Lemma 5.5"},{"comment":"Definition 3.5 also admits coreness-0 discriminative cores: a single vertex in GN(v) with no incident edges is a maximal connected subgraph with no subgraph of higher coreness. Definition 3.6 and Algorithm 2, however, only count cores with coreness at least 1. The paper should exclude coreness-0 cores in the definition (for instance by requiring φ(H)≥1) or explicitly justify why they are not part of the diversity vector.","section":"Definition 3.5 / Definition 3.6"}],"minor_comments":[{"comment":"The variable written as 'Flaд' in Algorithm 2 (lines 8, 17, 18) uses a non-ASCII character and should be 'Flag'.","section":"Algorithm 2"},{"comment":"The sentence 'in Fig. 2(c), h-core is 5 times faster than baseline on Youtube' is inconsistent with the figure, where panel (c) is LiveJournal; please correct the dataset/figure reference.","section":"Section 6.1"},{"comment":"The text says 'We vary t={2,3,4}' but then reports that '4-core and 5-core win none'; please align the reported set of t values with the results in Fig. 5(b).","section":"Section 6.3"},{"comment":"The proof of Lemma 5.1 is omitted and deferred to [12]; because the lemma is short and central, including its proof would make the paper self-contained.","section":"Lemma 5.1"},{"comment":"In Algorithm 3 the variable h(v) is used both as an accumulator and as the returned score; renaming the accumulator would avoid confusion.","section":"Algorithm 3"},{"comment":"The abstract says 'novel notation of discriminative core'; this should be 'novel notion'.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":"I believe the paper is revisable: the operational definition in Algorithm 2 is natural and the experiments appear reproducible under it. The main risk is whether the authors can make the formal definition and proofs consistent without changing the claimed results."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this paper has a good idea and a real definitional hole that makes its central score ambiguous. The new bit is the discriminative core, a parameter-free way to decompose an ego-network into social contexts, plus an h-index style score that balances the number and strength of contexts. The top-k pruning bound (Lemma 5.5) is genuinely clever, and the experiments on four SNAP graphs show the h-core algorithm runs much faster than the baseline and lands in the same ballpark as the old t-core method. If the model is made precise, this is a useful tool for social-contagion applications.\n\nThe problem is that Definition 3.5 does not match Algorithm 2. Definition 3.5 calls a subgraph a discriminative core if it is a maximal connected subgraph with no subgraph of higher coreness. Algorithm 2, however, only counts a component at coreness t if it is formed by vertices with coreness exactly t and has no edge to any vertex of coreness greater than t. Those are not the same object. The paper itself slips in the extra restriction in Section 4.2 when it says a discriminative core of coreness t 'will be only formed by the vertices with the coreness of exactly t,' but that condition is absent from the formal definition. The stress-test's K4-plus-triangle example makes the gap concrete: under the literal definition, a coreness-2 component can touch a coreness-3 vertex without containing any coreness-3 subgraph, so it should count; Algorithm 2 discards it. The reported h(v) scores are therefore computed under an unstated interpretation, and the paper never proves the algorithm implements the stated definition.\n\nThis also weakens Lemma 5.5's proof. The upper-bound argument multiplies x* by (x*+1) to count distinct vertices across x* discriminative cores. That only works if the cores are disjoint, which is true under Algorithm 2 but not under Definition 3.5, where maximal cores can overlap. So the proof depends on the same missing restriction.\n\nMinor issue: the effectiveness experiments report averages without error bars, which is easy to fix.\n\nThe whole thing is correctable by rewriting Definition 3.5 to match the algorithm (for example, a maximal connected subgraph with coreness exactly t and no edge to any vertex of higher coreness) or by proving Algorithm 2 implements the intended definition. As written, the central quantity is ambiguous, so I wouldn't cite it yet. But the idea is solid and the algorithm is plausible under the intended model. This deserves a serious referee, with a clear request to fix the definition before publication.","headline":"A genuinely useful parameter-free ranking idea, but the paper's own definition of discriminative core disagrees with the algorithm, so the scores it reports are for a model that is never formally defined.","tokens_in":13786,"tokens_out":3607,"would_cite":false,"duration_ms":33899,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that structural diversity becomes a parameter-free property when each ego-network is decomposed into discriminative cores and scored by the h-index, with a top-k search algorithm that runs in O(ρm) time.","keywords":["structural diversity","discriminative core","h-index","ego-network","top-k search","core decomposition","social contagion","parameter-free"],"falsifier":"Construct a small graph where a coreness-2 triangle is attached by one edge to a coreness-3 clique, then compute h(v) for the central vertex twice: once by enumerating discriminative cores according to Definition 3.5 and once by running Algorithm 2. If the two scores differ, the central quantity is not uniquely defined.","tokens_in":12635,"feed_emoji":"🌐","tokens_out":5048,"duration_ms":44183,"temperature":0.7,"pith_summary":"This paper proposes a parameter-free measure of structural diversity: instead of counting t-cores for a user-supplied threshold, it decomposes each vertex's ego-network into discriminative cores, which are maximal connected subgraphs that cannot be split into denser subgraphs, and then applies the h-index to the counts of these cores by coreness. The resulting score h(v) is claimed to capture both how many social contexts surround a vertex and how strongly each is connected, without requiring a global parameter. The paper further claims that the top-k vertices under this score can be found quickly, with an upper bound derived from global coreness that prunes most candidate vertices, giving an O(ρm) algorithm. A sympathetic reader would care because existing t-core-based structural diversity is shown to be highly sensitive to the chosen threshold, making rankings unstable, while this model is designed to be stable and personalized by construction.","feed_headline":"New score ranks social contexts with no tuning parameter","feed_subtitle":"Discriminative cores plus h-index capture how many distinct worlds surround each vertex, and top-k search stays fast.","key_machinery":"The load-bearing objects are discriminative cores and the h-index-based score. A discriminative core is a maximal connected subgraph H of an ego-network with the property that no subgraph H' ⊆ H has coreness φ(H') > φ(H); the paper treats each such core as one distinct social context whose coreness indicates its strength. The score h(v) is then the largest h such that at least h discriminative cores in the ego-network have coreness at least h. The efficiency argument rests on Corollary 5.4 and Lemma 5.5, which bound the coreness any neighbor u can have inside v's ego-network by min{φ_G(v), φ_G(u) − 1}, yielding a cheap upper bound b_h(v) used to prune the top-k search.","core_discovery":"The central claim is that social contexts inside a vertex's ego-network can be identified automatically as discriminative cores: each is a maximal connected subgraph whose coreness is strictly higher than any proper subgraph inside it. Counting these cores at each coreness level gives a diversity vector C(v), and the h-index-style score h(v) = max{r : sum_{r' ≥ r} c_v(r') ≥ r} is the proposed structural diversity score. The paper asserts that this score is parameter-free, reflects both the number and the strength of social contexts, and that Algorithm 4 returns the top-k vertices in O(ρm) time using the upper bound of Lemma 5.5.","pith_inferences":["A natural next test is to compare rankings produced by the formal Definition 3.5 against those produced by Algorithm 2: on graphs where a coreness-2 component is attached to a higher-coreness vertex, the two rules disagree, so the paper's score is not uniquely defined until that gap is closed.","If the discriminative-core model is adopted, it could be reused as a preprocessing step for community search or influence maximization, since it yields a hierarchy of contexts at all coreness levels without a tunable threshold.","The model implicitly assigns each vertex a personalized set of thresholds, namely the coreness values of its own discriminative cores, which suggests an extension to dynamic graphs where a global t would otherwise need periodic re-tuning."],"forward_implications":["If discriminative cores are accepted, structural diversity scores become directly comparable across vertices without choosing a threshold t, so rankings no longer swing with an arbitrary parameter.","The top-k algorithm computes exact scores only for vertices whose upper bound exceeds the current k-th score, shrinking the search space to a small fraction of the graph; the paper reports this space drops below one tenth of the vertex set on large networks.","The h-index scoring treats a few strong contexts as comparable to many weak ones, so vertices with very different social structures can be ranked by a single number that balances quantity and strength.","The O(ρm) bound means the method stays practical on million-edge graphs whenever arboricity is small, matching the complexity of standard subgraph-listing routines."],"supporting_citations":[{"why":"Supplies the O(m) core decomposition algorithm used by Algorithm 1 and repeated on each ego-network.","marker":"[2]"},{"why":"Provides the h-index concept that the diversity score adapts to coreness counts.","marker":"[11]"},{"why":"Defines the t-core based structural diversity model that this paper replaces and compares against, and is the source of Lemma 5.1's proof.","marker":"[12]"},{"why":"Establishes structural diversity as a predictor of social contagion, motivating the whole search problem.","marker":"[25]"},{"why":"Supplies the arboricity bound used in the O(ρm) complexity claim.","marker":"[7]"}],"fun_headline_variants":["Structural diversity search drops the tuning knob","Find top-k diverse vertices with zero parameters","Discriminative cores replace t in structural diversity","New parameter-free score for graph diversity search","H-index meets core theory for context-rich ranking"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the formal definition of a discriminative core and the algorithmic rule used to count them describe the same object; if a connected component can contain a denser subgraph yet touch a vertex of higher coreness, the definition says it counts while the algorithm says it does not, so the score is not well-defined without an added condition.","fun_headline_variants_meta":{"raw":{"variants":["Structural diversity search drops the tuning knob","Find top-k diverse vertices with zero parameters","Discriminative cores replace t in structural diversity","New parameter-free score for graph diversity search","H-index meets core theory for context-rich ranking"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000231,"raw_usage":{"total_tokens":1420,"prompt_tokens":811,"completion_tokens":609,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":427,"completion_tokens_details":{"reasoning_tokens":542}},"tokens_in":427,"tokens_out":609,"duration_ms":5457,"temperature":1.0,"reasoning_tokens":542,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:11:29.579389+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a small graph where a coreness-2 triangle is attached by one edge to a coreness-3 clique, then compute h(v) for the central vertex twice: once by enumerating discriminative cores according to Definition 3.5 and once by running Algorithm 2. If the two scores differ, the central quantity is not uniquely defined.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the h-index concept that the diversity score adapts to coreness counts."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the t-core based structural diversity model that this paper replaces and compares against, and is the source of Lemma 5.1's proof."},{"cited_title":"Ugander, L","cited_arxiv_id":null,"evidence_quote":"Establishes structural diversity as a predictor of social contagion, motivating the whole search problem."}],"review_version":1}