Pith. sign in

REVIEW 3 major objections 6 minor 31 references

Fast Algorithms for Intimate-Core Group Search in Weighted Graphs

T0 review · 3 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read By starting from a small weighted tree that connects the query nodes and expanding it locally, LEKS finds intimate-core groups with smaller total edge weight than the prior ICG-M method while running significantly faster on large…

desk verdict New local-seeding heuristic for intimate-core group search shows consistent empirical gains over the previous state of the art, but the evaluation is under-powered and the protection mechanism is under-specified. read the letter →

arxiv 1908.11788 v1 pith:FOD3XVKS submitted 2019-08-30 cs.SI cs.DB

Longxu Sun , Xin Huang , Rong-Hua Li , Jianliang Xu This is my paper · ORCID
classification cs.SIcs.DB MSC 05C8568R10
keywords communitysearchk-coreweightedgraphslocalexplorationcoredecompositionintimate-coregroupgraphalgorithms
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Intimate-core group search asks for the connected k-core containing a given set of query nodes that has the smallest total edge weight. Prior state-of-the-art methods start from the maximal connected k-core and peel nodes away, which is slow when that core is large. This paper presents LEKS, a local-exploration framework that connects the query nodes with a low-weight tree, expands the tree level by level until it encloses a connected k-core, and then refines that candidate with the existing ICG-M deletion routine. On three real weighted networks, LEKS-tree and LEKS-path return groups with smaller group weights than ICG-M while running significantly faster, with LEKS-path the fastest in most cases. The message is that a query-centric local start can dominate a global start for this NP-hard problem, at least empirically.

What carries the argument

The central object is the intimate-core group, a connected k-core containing all query nodes with minimum total edge weight, a problem known to be NP-hard. The mechanism that carries the argument is a three-phase pipeline: (1) tree generation, which uses Dijkstra shortest paths and a Prim minimum spanning tree (or a path-based variant) to build a small-weighted tree spanning the queries; (2) tree-to-graph expansion, which grows the tree level by level until the induced subgraph contains a connected k-core; (3) refinement with the ICG-M bulk-deletion routine, guarded by a protection mechanism that preserves query nodes and their required neighbors so the k-core does not collapse. The k-core index, which stores the coreness of every node and is built offline by core decomposition, lets each phase test k-core membership quickly.

What would settle it

Construct a weighted graph with two connected k-cores containing the same query nodes: one reachable only through a heavy edge and another slightly larger but composed of light edges. If LEKS's local expansion locks onto the first core and returns a higher group weight than ICG-M starting from the maximal core, the paper's claim of uniformly better quality fails; running both algorithms on this graph decides it.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that the quality and speed of intimate-core search are decided before refinement begins: a small, query-centric candidate subgraph yields better answers than the maximal connected k-core. LEKS builds that candidate in three phases: it first computes shortest paths among query nodes and merges them into a spanning tree (Algorithm 3) or a path-based tree (Algorithm 4); it then expands the tree level by level through the k-core until the induced subgraph contains a connected k-core; finally it applies ICG-M's bulk node removal. The experiments report lower group weights for both LEKS variants than ICG-M across k values from 2 to 8 and query-set sizes from 1 to 7 on wiki-vote, Flickr, and DBLP, plus running-time reductions, with the path variant fastest in most cases. The DBLP case study is the concrete illustration: for authors Huan Liu, Xia Hu, and Jiliang Tang at k=4, LEKS-path returns a 5-node, 10-edge 4-core of weight 1.6, whereas ICG-M returns a 12-node subgraph of weight 16.7.

Load-bearing premise

The load-bearing premise is that a small tree expanded locally around the query nodes yields a candidate subgraph that, after refinement, is at least as good as, and typically much smaller than, the maximal connected k-core; the paper supports this only empirically on three datasets and gives no worst-case guarantee.

Editorial extensions

If this is right

  • Community search on large weighted graphs becomes interactive: because the initial candidate is local, LEKS can return an intimate group without ever materializing the maximal k-core.
  • The returned groups are more intimate under the edge-weight semantics, since lower group weight means tighter relationships; this matters for co-authorship, communication, and collaboration networks.
  • The offline k-core index makes repeated queries cheap, amortizing the core-decomposition cost over many online queries on the same graph.
  • The protection mechanism keeps the answer feasible during refinement, since query nodes and their required neighbors cannot be deleted by the peeling process.
  • LEKS-path offers a practical speed-quality tradeoff: it matches LEKS-tree in group weight while running fastest in most reported cases.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same tree-then-expand pattern could be transplanted to other dense-subgraph community models, such as k-truss or clique-percolation search, where the baseline currently starts from the global maximal structure.
  • A natural stress test is to run both algorithms on a broader set of graphs, including networks with skewed weight distributions or bridge-like heavy edges, to see whether LEKS ever returns a heavier group than ICG-M or produces a candidate as large as the maximal core.
  • The protection of query nodes connects LEKS to the anchored-k-core literature; formalizing the minimal set of nodes that must be protected for a query set would turn an empirical safeguard into a provable invariant.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. This paper addresses the intimate-core group search problem: given an undirected weighted graph, a set of query nodes Q, and an integer k, find a connected k-core containing Q with minimum total edge weight. The problem is NP-hard, so the paper follows the heuristic line of Zheng et al. [29], which starts from the maximal connected k-core and greedily deletes high-weight nodes (ICG-M). The proposed LEKS framework changes the starting point: it first builds a query-connecting tree (either an all-pairs shortest-path spanning tree or a sequential path-based tree), expands this tree level by level until a connected k-core containing Q is obtained, and then applies the ICG-M refinement on this smaller candidate graph. A protection mechanism is proposed to prevent removal of query nodes with degree exactly k. Experiments on wiki-vote, Flickr, and DBLP compare LEKS-tree and LEKS-path against ICG-M for k in {2,4,6,8} and |Q| in {1,...,7}, reporting lower group weights and lower running times, plus a DBLP case study.

Significance. If the empirical claim is correct, LEKS is a practically useful contribution: it provides a simple and natural way to shrink the initial candidate for a well-known NP-hard community-search problem, and the reported gains on three networks are substantial. The paper is clearly written and contains a reasonable algorithmic framework, complexity analyses for the tree-generation phases, and a concrete case study. The strengths are the local-exploration idea, the two tree-construction variants, and the attempt to protect critical query nodes. However, the central comparative claim is supported only by average curves without statistical tests or error bars, on three datasets and without released code, so the significance remains conditional. The lack of any worst-case or average-case analysis of the expansion phase is acceptable for a heuristic paper only if the experimental evidence is thorough, which is not currently the case.

major comments (3)
  1. [Section 4.4 / Algorithm 5 / Section 5, Exp-1] The central premise that locally expanding a shortest-path tree yields a candidate GQ whose ICG-M refinement has lower group weight than refining the maximal connected k-core is not supported by any analysis. Section 4.4 explicitly concedes that GQ can equal the maximal connected k-core in the worst case, and even when GQ is a proper subgraph, the greedy deletion procedure could in principle find a heavier local optimum from the smaller set because GQ may exclude low-weight k-cores that connect queries through nodes outside the BFS layers. Because this premise is the basis for the paper's quality claim, it needs either formal support or a much stronger empirical justification than the three averaged curves currently provide.
  2. [Section 5] The experimental evaluation is not sufficient to support the claim that LEKS 'always' finds smaller weights and is 'always' faster. Figures 5-8 report averages over 100 random query sets on three networks, with no error bars, standard deviations, or paired significance tests, and no code or random seeds are provided. On heavy-tailed network data, a small number of query sets could drive the reported mean differences, so the reader cannot verify that the advantage is systematic. The manuscript should add per-query distributions or significance tests, additional datasets, and a reproducibility statement.
  3. [Section 4.5] The protection mechanism is not auditable from the manuscript. Algorithm 2's refinement step is simply 'Apply ICG-M [29] on graph GQ', and the description of protecting query nodes with degree exactly k and their neighbors appears only in prose, without pseudocode or a precise modification of the ICG-M removal procedure. It is also unclear why the protection covers only the degree-exactly-k case, since a query node with degree > k could also be removed or collapsed during bulk deletion. The authors should specify the exact protected set and how the ICG-M subroutine is altered.
minor comments (6)
  1. [Section 4.3] The complexity analysis of Algorithm 3 does not match its pseudocode: the loop over all pairs (q1,q2) in Q implies O(|Q|^2) shortest-path computations, while the text claims a single-source implementation in O(|Q| mk log nk). Please clarify which implementation is actually used.
  2. [Section 5, Datasets] Reference [15] is a SIGMOD paper on truss decomposition, not a dataset repository; the statement 'All datasets are publicly available from [15]' should point to the actual data source.
  3. [Section 5, Exp-1] The sentence 'ICG-M can find answers quickly for k=4, which achieves similar performance with LEKS methods' is vague; no separate k=4 results are highlighted.
  4. [Figure 6 caption] 'Efficiency' is a typo; it should be 'Efficiency'.
  5. [Section 4.5] The phrase 'As pointed by [3,27,28]' has a grammar issue; it should be 'As pointed out by [3,27,28]'.
  6. [Section 4.4, after Algorithm 5] The statement 'GQ in practice is always much smaller than it' is an empirical assertion that would benefit from a quantitative report of candidate sizes for all datasets.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation found; only minor, non-load-bearing self-citation to the authors' prior ICG-M baseline.

full rationale

The paper's derivation chain is self-contained rather than circular. LEKS builds on standard shortest-path and core-decomposition primitives, and its final refinement explicitly calls the published ICG-M heuristic as a subroutine on the locally expanded candidate. The claimed advantage is an empirical comparison against that external baseline on three real networks; no parameter is fitted and then relabeled as a prediction, and no output quantity is defined in terms of its own result. The only self-citation is the use of the authors' prior work [29] as the baseline and refinement routine; that citation is not load-bearing in a circular sense because ICG-M is a published, externally falsifiable algorithm whose behavior is independent of this paper's candidate-generation phase. Exp-3's smaller initial candidate is partly by construction, since GQ is a subgraph of the maximal connected k-core, but the final group weights and runtimes are produced by the same refinement procedure and are not entailed by that containment. Absence of approximation guarantees, error bars, and released code weakens the empirical support, but that is a correctness and evidence concern, not circularity. Score 2 reflects only the minor self-citation.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper introduces no new free parameters fitted to data; k and Q are user inputs. The main assumptions are standard algorithm correctness for k-core decomposition and Dijkstra, plus two ad hoc heuristics: the local-expansion seed tree and the protection rule. These heuristics are the unproven load-bearing components of the method.

assumptions (5)
  • domain assumption Edge weights are positive (or at least non-negative), so Dijkstra's shortest path algorithm applies.
    Stated in Example 3.6: 'Each edge has a positive weight.' This is required for the shortest-path computations in Algorithms 3 and 4.
  • standard math The standard k-core decomposition algorithm correctly computes coreness values.
    Algorithm 1 relies on the classic O(m) core decomposition by Batagelj and Zaversnik, treated as a black box.
  • domain assumption The ICG-M refinement heuristic from Zheng et al. [29] maintains a connected k-core containing query nodes while removing nodes.
    LEKS's refinement phase (Algorithm 2, line 3) calls ICG-M as a subroutine. The correctness of the final output depends on this inherited property.
  • ad hoc to paper Protecting a query node q with degree exactly k and all of q's neighbors is sufficient to prevent q from being removed from the k-core.
    Section 4.5 states the protection rule without proof. It is a heuristic borrowed from anchored k-core ideas and may be incomplete for cascading failures.
  • ad hoc to paper A shortest-path tree connecting query nodes, plus BFS expansion up to the first depth that yields a connected k-core, produces a candidate subgraph that leads to a high-quality intimate-core group.
    This is the central heuristic premise of the LEKS framework (Section 4.2). It is validated only empirically and has no theoretical guarantee.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fast Algorithms for Intimate-Core Group Search in Weighted Graphs." pith.science (2026). https://pith.science/paper/FOD3XVKS

@misc{pith2026190811788,
  author       = {Pith},
  title        = {Pith review of: Fast Algorithms for Intimate-Core Group Search in Weighted Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FOD3XVKS}},
  note         = {Machine review of arXiv:1908.11788}
}
abstract

Community search that finds query-dependent communities has been studied on various kinds of graphs. As one instance of community search, intimate-core group search over a weighted graph is to find a connected $k$-core containing all query nodes with the smallest group weight. However, existing state-of-the-art methods start from the maximal $k$-core to refine an answer, which is practically inefficient for large networks. In this paper, we develop an efficient framework, called local exploration k-core search (LEKS), to find intimate-core groups in graphs. We propose a small-weighted spanning tree to connect query nodes, and then expand the tree level by level to a connected $k$-core, which is finally refined as an intimate-core group. We also design a protection mechanism for critical nodes to avoid the collapsed $k$-core. Extensive experiments on real-life networks validate the effectiveness and efficiency of our methods.

Figures

Figures reproduced from arXiv: 1908.11788 by the authors.

Figure 1
Figure 1. An example of intimate-core group search in graph [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. LEKS framework for intimate-core group search [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Tree construction for query nodes v1, v2, v5. Example 4.2 [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Tree-to-graph expansion Example 4.4 [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]
Figure 5
Figure 5. Figure 5: Effectiveness evaluation by varying k 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 2 4 6 8 time (seconds) k ICG-M LEKS-tree LEKS-path 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 2 4 6 8 time (seconds) k ICG-M LEKS-tree LEKS-path 0 200 400 600 800 1000 1200 2 4 6 8 time (seconds) k ICG-M LEKS-tre…
Figure 6
Figure 6. Figure 6: Efficiency evaluation by varying k protection mechanism for query nodes can also be used for k-core maintenance in the phrase of tree-to-graph expansion. 5 EXPERIMENTS In this section, we experimentally evaluate the performance of our proposed algorithms. All al￾gorith…
Figure 7
Figure 7. Figure 7: Effectiveness evaluation by varying |Q| 0 0.2 0.4 0.6 0.8 1 1.2 1 2 3 4 5 6 7 time (seconds) |Q| ICG-M LEKS-tree LEKS-path 0 0.5 1 1.5 2 1 2 3 4 5 6 7 time (seconds) |Q| ICG-M LEKS-tree LEKS-path 0 200 400 600 800 1000 1200 1 2 3 4 5 6 7 time (seconds) |Q| ICG-M LEKS-t…
Figure 8
Figure 8. Figure 8: Efficiency evaluation by varying |Q| Exp-2: Varying |Q| [PITH_FULL_IMAGE:figures/full_fig_p012_8.png]
Figure 9
Figure 9. Figure 9: The size and weight of intimate-groups varied by #ite [PITH_FULL_IMAGE:figures/full_fig_p013_9.png]
Figure 10
Figure 10. Figure 10: Case study of intimate-core group search on the DBLP [PITH_FULL_IMAGE:figures/full_fig_p013_10.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 28 canonical work pages

  1. [29]

    Dong Zheng, Jianquan Liu, Rong-Hua Li, Cigdem Aslay, Yi-Cheng Chen, and Xin Huang. 2017. Querying intimate- core groups in weighted graphs. In IEEE International Conference on Semantic Computing . 156–163

    work page 2017

  2. [1]

    Nicola Barbieri, Francesco Bonchi, Edoardo Galimberti, and France sco Gullo. 2015. Efficient and effective community search. DMKD 29, 5 (2015), 1406–1433

    work page 2015

  3. [2]

    Vladimir Batagelj and Matjaz Zaversnik. 2003. An O (m) algorith m for cores decomposition of networks. arXiv preprint cs/0310049 (2003)

    arXiv 2003

  4. [3]

    Kshipra Bhawalkar, Jon Kleinberg, Kevin Lewi, Tim Roughgarden, and Aneesh Sharma. 2015. Preventing unraveling in social networks: the anchored k-core problem. SIAM Journal on Discrete Mathematics 29, 3 (2015), 1452–1475

    work page 2015

  5. [4]

    Fei Bi, Lijun Chang, Xuemin Lin, and Wenjie Zhang. 2018. An optimal and p rogressive approach to online search of top-k influential communities. PVLDB 11, 9 (2018), 1056–1068

    work page 2018

  6. [5]

    Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Cliffor d Stein. 2009. Introduction to algorithms

    work page 2009

  7. [6]

    Wanyun Cui, Yanghua Xiao, Haixun Wang, and Wei Wang. 2014. Local se arch of communities in large graphs. In SIGMOD. 991–1002

    work page 2014

  8. [7]

    Dongsheng Duan, Yuhua Li, Yanan Jin, and Zhengding Lu. 2009. Community m ining on dynamic weighted directed graphs. In ACM international workshop on Complex networks meet inform ation & knowledge management . 11–18

    work page 2009

Show all 31 references
  1. [8]

    Yixiang Fang, Reynold Cheng, Yankai Chen, Siqiang Luo, and Jiafeng Hu. 20 17. Effective and efficient attributed community search. VLDBJ 26, 6 (2017), 803–828

    2017

  2. [9]

    Yixiang Fang, Reynold Cheng, Siqiang Luo, and Jiafeng Hu. 2016. Effectiv e community search for large attributed graphs. PVLDB 9, 12 (2016), 1233–1244

    2016

  3. [10]

    Yixiang Fang, Xin Huang, Lu Qin, Ying Zhang, Wenjie Zhang, Reynold Cheng, a nd Xuemin Lin. 2019. A Survey of Community Search Over Big Graphs. arXiv preprint arXiv:1904.12539 (2019)

    2019 arXiv

  4. [11]

    Xin Huang, Hong Cheng, Lu Qin, Wentao Tian, and Jeffrey Xu Yu. 2014. Qu erying k-truss community in large and dynamic graphs. In SIGMOD. 1311–1322

    2014

  5. [12]

    Xin Huang and Laks VS Lakshmanan. 2017. Attribute-driven commu nity search. PVLDB 10, 9 (2017), 949–960

    2017

  6. [13]

    Xin Huang, Laks VS Lakshmanan, and Jianliang Xu. 2019. Community Search over Big Graphs . Morgan & Claypool Publishers

    2019

  7. [14]

    Xin Huang, Laks VS Lakshmanan, Jeffrey Xu Yu, and Hong Cheng. 2015 . Approximate closest community search in networks. PVLDB 9, 4 (2015), 276–287

    2015

  8. [15]

    Xin Huang, Wei Lu, and Laks VS Lakshmanan. 2016. Truss decompo sition of probabilistic graphs: Semantics and algorithms. In SIGMOD. 77–90

    2016

  9. [16]

    Rong-Hua Li, Lu Qin, Jeffrey Xu Yu, and Rui Mao. 2015. Influential co mmunity search in large networks. PVLDB 8, 5 (2015), 509–520

    2015

  10. [17]

    Sourav Medya, Tiyani Ma, Arlei Silva, and Ambuj Singh. 2019. K- Core Minimization: A Game Theoretic Approach. arXiv preprint arXiv:1901.02166 (2019)

    2019 arXiv

  11. [18]

    Mark EJ Newman. 2001. Scientific collaboration networks. II. S hortest paths, weighted networks, and centrality. Physical review E 64, 1 (2001), 016132

    2001

  12. [19]

    Mark EJ Newman. 2004. Analysis of weighted networks. Physical review E 70, 5 (2004), 056131

    2004

  13. [20]

    Tore Opsahl, Filip Agneessens, and John Skvoretz. 2010. Node centrality in weighted networks: Generalizing degree and shortest paths. Social networks 32, 3 (2010), 245–251

    2010

  14. [21]

    Natali Ruchansky, Francesco Bonchi, David García-Soriano, Fra ncesco Gullo, and Nicolas Kourtellis. 2015. The mini- mum wiener connector problem. In SIGMOD. 1587–1602

    2015

  15. [22]

    Ahmet Erdem Saríyüce, Buğra Gedik, Gabriela Jacques-Silva , Kun-Lung Wu, and Ümit V Çatalyürek. 2013. Streaming algorithms for k-core decomposition. PVLDB 6, 6 (2013), 433–444

    2013

  16. [23]

    Mauro Sozio and Aristides Gionis. 2010. The community-search pro blem and how to plan a successful cocktail party. In KDD. 939–948

    2010

  17. [24]

    Jia Wang and James Cheng. 2012. Truss decomposition in massive net works. PVLDB 5, 9 (2012), 812–823

    2012

  18. [25]

    Long Yuan, Lu Qin, Xuemin Lin, Lijun Chang, and Wenjie Zhang. 2016. Diver sified top-k clique search. VLDBJ 25, 2 (2016), 171–196. , Vol. 1, No. 1, Article . Publication date: September 2019. Fast Algorithms for Intimate-Core Group Search in Weighted Graphs 15

    2016

  19. [26]

    Long Yuan, Lu Qin, Wenjie Zhang, Lijun Chang, and Jianye Yang. 2017. Inde x-based densest clique percolation community search in networks. ICDE 30, 5 (2017), 922–935

    2017

  20. [27]

    Fan Zhang, Wenjie Zhang, Ying Zhang, Lu Qin, and Xuemin Lin. 2017. OLAK: an efficient algorithm to prevent unraveling in social networks. PVLDB 10, 6 (2017), 649–660

    2017

  21. [28]

    Fan Zhang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. 2017. Finding cr itical users for social network engagement: The collapsed k-core problem. In AAAI

    2017

  22. [30]

    Zibin Zheng, Fanghua Ye, Rong-Hua Li, Guohui Ling, and Tan Jin. 2017. Finding weighted k-truss communities in large networks. Information Sciences 417 (2017), 344–360

    2017

  23. [31]

    Weijie Zhu, Chen Chen, Xiaoyang Wang, and Xuemin Lin. 2018. K-core M inimization: An Edge Manipulation Ap- proach. In CIKM. 1667–1670. , Vol. 1, No. 1, Article . Publication date: September 2019

    2018

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.