pith. sign in

arxiv: 1906.12334 · v1 · pith:RXFAEL2Wnew · submitted 2019-06-27 · 💻 cs.SI · cs.DS

K-Core Maximization through Edge Additions

Zhongxin Zhou , Fan Zhang , Xuemin Lin , Wenjie Zhang , Chen Chen This is my paper

Pith reviewed 2026-05-25 14:26 UTC · model grok-4.3

classification 💻 cs.SI cs.DS
keywords k-core maximizationedge additionNP-hardheuristic algorithmnetwork stabilitygraph algorithms
0
0 comments X

The pith

Adding a budget of edges to maximize k-core size is NP-hard but solvable by a heuristic on real graphs.

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

The paper defines the edge k-core problem as adding at most b edges to a graph to maximize the number of vertices in its k-core. It proves this optimization task is NP-hard and APX-hard. A heuristic algorithm is introduced that selects candidate edges and applies optimizations to expand the core efficiently on general graphs. Experiments across nine real datasets show the heuristic increases core size while remaining computationally practical.

Core claim

The edge k-core problem of adding b edges to maximize the k-core is NP-hard and APX-hard. A heuristic algorithm is proposed on general graphs with effective optimization techniques.

What carries the argument

Heuristic algorithm that chooses non-adjacent vertex pairs for edge additions to enlarge the k-core subgraph.

If this is right

  • Strategic addition of b edges can increase the number of vertices that belong to the k-core.
  • Exact solutions are intractable on large graphs due to the hardness proofs.
  • The proposed heuristic with optimizations provides a scalable practical approach.
  • Effectiveness on real datasets suggests direct applicability to improving stability in existing networks.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same edge-selection logic could be adapted to maximize other degeneracy measures such as main core or truss.
  • Network designers might apply the method to reinforce communities by adding the fewest possible new links.
  • Approximation algorithms with proven ratios remain open despite the APX-hardness result.

Load-bearing premise

That k-core size is a meaningful proxy for network stability and that the heuristic generalizes beyond the nine tested datasets.

What would settle it

A graph instance where the heuristic's chosen edges produce a strictly smaller k-core than some other set of b edges.

Figures

Figures reproduced from arXiv: 1906.12334 by Chen Chen, Fan Zhang, Wenjie Zhang, Xuemin Lin, Zhongxin Zhou.

Figure 1
Figure 1. Figure 1: An Example of k-Core and Anchoring, k = 3 to k-core maximization. Thus, the edge k-core problem is proposed [Chitnis and Talmon, 2018]: Given a graph G, an integer k and a budget b, add b edges to non-adjacent vertex pairs in G such that the k-core is the largest. Example 1 [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Complexity Reduction, k = 3 are adjacent. For every i and j, if ei ∈ Tj in the MC in￾stance, we add an edge between vi and u j i . In [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Candidate Seletion, k = 3 Note that if l(u) ≤ l(v), in the k-core computation with anchor e, the survive of u may preserve some vertices before visiting v. Thus, in Theorem 5, there is no degree requirement for v to ensure that e = (u, v) has at least one follower. Onion Layer based Follower Computation A naive follower computation is to directly apply the k-core computation on the graph with the existence… view at source ↗
Figure 4
Figure 4. Figure 4: Effectiveness of the Greedy Heuristic, k=20, b=5 [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figure 8
Figure 8. Figure 8: Candidate Pruning within one week. BL+OF significantly improve the perfor￾mance by applying a series of techniques. EKC performs even better given all the optimizations. In [PITH_FULL_IMAGE:figures/full_fig_p006_8.png] view at source ↗
Figure 6
Figure 6. Figure 6: shows that EKC produces similar and almost larger numbers of followers than AKC where the meaning of b is different: the former for edges and the latter for vertices. Although the anchoring of one vertex means the preserving of many edges, EKC can produce similar followers with one anchor edge. It shows that the edge k-core can enlarge the k-core with less graph manipulations. 6.2 Efficiency [PITH_FULL_IM… view at source ↗
read the original abstract

A popular model to measure the stability of a network is k-core - the maximal induced subgraph in which every vertex has at least k neighbors. Many studies maximize the number of vertices in k-core to improve the stability of a network. In this paper, we study the edge k-core problem: Given a graph G, an integer k and a budget b, add b edges to non-adjacent vertex pairs in G such that the k-core is maximized. We prove the problem is NP-hard and APX-hard. A heuristic algorithm is proposed on general graphs with effective optimization techniques. Comprehensive experiments on 9 real-life datasets demonstrate the effectiveness and the efficiency of our proposed methods.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper proves that the edge k-core maximization problem—adding at most b edges to maximize the size of the k-core—is NP-hard and APX-hard. It proposes a heuristic algorithm for general graphs that incorporates optimization techniques, and reports comprehensive experiments on nine real-life datasets that demonstrate the heuristic's effectiveness and efficiency.

Significance. The hardness proofs are self-contained and establish the problem's intractability, a standard but useful theoretical contribution. If the heuristic's empirical performance holds, the work supplies a practical method for improving network stability via k-core maximization, with direct relevance to social and information network applications. The experiments on real datasets provide concrete evidence of utility, though the absence of approximation bounds restricts the result's theoretical scope.

major comments (2)
  1. [§4] §4 (heuristic description): the algorithm is presented without any approximation ratio, worst-case bound, or analysis relating solution quality to parameters b and k; given the APX-hardness result in §3, the effectiveness claim therefore rests solely on the empirical results in §5.
  2. [§5] §5 (experiments): while nine real-life datasets are used to demonstrate effectiveness, the section provides no details on baseline algorithms, number of independent runs, statistical significance tests, or analysis of possible structural biases (e.g., power-law degree distributions) that could limit generalization to worst-case instances implied by the hardness results.
minor comments (1)
  1. [Abstract] Abstract: the phrase 'effective optimization techniques' is used without naming the techniques; a brief enumeration would improve clarity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments on our manuscript. We address each major comment below and indicate the revisions made to the manuscript.

read point-by-point responses

  1. Referee: [§4] §4 (heuristic description): the algorithm is presented without any approximation ratio, worst-case bound, or analysis relating solution quality to parameters b and k; given the APX-hardness result in §3, the effectiveness claim therefore rests solely on the empirical results in §5.

    Authors: We agree that, in light of the APX-hardness result in §3, a non-trivial approximation ratio is not expected to exist. The heuristic is intended as a practical method rather than an approximation algorithm. In the revised version we have added a brief discussion at the end of §4 explaining the design rationale of the greedy and local-search components and how they scale with b and k; this does not include worst-case bounds, which would be uninformative given the hardness result. The effectiveness claim therefore continues to rest on the empirical evaluation, which we have strengthened in response to the next comment. revision: partial

  2. Referee: [§5] §5 (experiments): while nine real-life datasets are used to demonstrate effectiveness, the section provides no details on baseline algorithms, number of independent runs, statistical significance tests, or analysis of possible structural biases (e.g., power-law degree distributions) that could limit generalization to worst-case instances implied by the hardness results.

    Authors: We acknowledge that these experimental details were insufficiently documented. The revised §5 now explicitly lists the baseline algorithms (random edge addition and degree-greedy heuristics), reports averages and standard deviations over 20 independent runs, includes paired t-tests with p-values for significance, and adds a paragraph discussing network structural properties. While the nine datasets are predominantly scale-free, we note their diversity in size and density and have clarified that the heuristic's relative gains remain consistent; we do not claim generalization to arbitrary worst-case graphs beyond the empirical evidence provided. revision: yes

Circularity Check

0 steps flagged

No circularity: hardness proofs and heuristic are independent of inputs

full rationale

The paper's core contributions are standard NP-hardness and APX-hardness proofs (self-contained mathematical arguments) plus a heuristic whose effectiveness is shown via experiments on 9 datasets. No load-bearing step reduces by definition, fitted parameter, or self-citation chain to the paper's own inputs or outputs. Hardness results do not invoke prior author work as a uniqueness theorem, and the heuristic is not presented as a 'prediction' derived from fitted values. This is the normal case of a self-contained paper with empirical validation.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review provides no explicit free parameters, axioms, or invented entities; the central claim rests on standard graph-theoretic definitions of k-core and NP-hardness reductions not detailed here.

pith-pipeline@v0.9.0 · 5640 in / 960 out tokens · 18409 ms · 2026-05-25T14:26:17.323669+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [1]

    An o(m) algorithm for cores decomposition of networks

    [Batagelj and Zaversnik, 2003] Vladimir Batagelj and Mat- jaz Zaversnik. An o(m) algorithm for cores decomposition of networks. CoRR, cs.DS/0310049,

    work page arXiv 2003

  2. [2]

    Klein- berg, Kevin Lewi, Tim Roughgarden, and Aneesh Sharma

    [Bhawalkar et al., 2015] Kshipra Bhawalkar, Jon M. Klein- berg, Kevin Lewi, Tim Roughgarden, and Aneesh Sharma. Preventing unraveling in social networks: The anchored k- core problem. SIAM J. Discrete Math., 29(3):1452–1475,

    work page 2015

  3. [3]

    Multi-guarded safe zone: An effective technique to mon- itor moving circular range queries

    [Cheema et al., 2010] Muhammad Aamir Cheema, Ljiljana Brankovic, Xuemin Lin, Wenjie Zhang, and Wei Wang. Multi-guarded safe zone: An effective technique to mon- itor moving circular range queries. In ICDE, pages 189– 200,

    work page 2010

  4. [4]

    Can we create large k-cores by adding few edges? In CSR, pages 78–89,

    [Chitnis and Talmon, 2018] Rajesh Chitnis and Nimrod Tal- mon. Can we create large k-cores by adding few edges? In CSR, pages 78–89,

    work page 2018

  5. [5]

    Fomin, and Petr A

    [Chitnis et al., 2013] Rajesh Hemant Chitnis, Fedor V . Fomin, and Petr A. Golovach. Preventing unraveling in social networks gets harder. In AAAI,

    work page 2013

  6. [6]

    A threshold of ln n for approxi- mating set cover

    [Feige, 1998] Uriel Feige. A threshold of ln n for approxi- mating set cover. J. ACM, 45(4):634–652,

    work page 1998

  7. [7]

    Kapron, Gautam Srivastava, and S

    [Kapron et al., 2011] Bruce M. Kapron, Gautam Srivastava, and S. Venkatesh. Social network anonymization via edge addition. In ASONAM, pages 155–162,

    work page 2011

  8. [8]

    [Karp, 1972] Richard M. Karp. Reducibility among combi- natorial problems. In Complexity of Computer Computa- tions, pages 85–103,

    work page 1972

  9. [9]

    Identification of in- fluential spreaders in complex networks

    [Kitsak et al., 2010] Maksim Kitsak, Lazaros K Gallos, Shlomo Havlin, Fredrik Liljeros, Lev Muchnik, H Eu- gene Stanley, and Hern ´an A Makse. Identification of in- fluential spreaders in complex networks. Nature physics, 6(11):888–893,

    work page 2010

  10. [10]

    Edge addition number of cartesian product of paths and cycles

    [Lai et al., 2005] Yung-Ling Lai, Chang-Sin Tian, and Ting- Chun Ko. Edge addition number of cartesian product of paths and cycles. Electronic Notes in Discrete Mathemat- ics, 22:439–444,

    work page 2005

  11. [11]

    A method of matrix analysis of group structure

    [Luce and Perry, 1949] R Duncan Luce and Albert D Perry. A method of matrix analysis of group structure. Psy- chometrika, 14(2):95–116,

    work page 1949

  12. [12]

    SPARK: A keyword search engine on relational databases

    [Luo et al., 2008] Yi Luo, Wei Wang, and Xuemin Lin. SPARK: A keyword search engine on relational databases. In ICDE, pages 1552–1555,

    work page 2008

  13. [13]

    SPARK2: top-k key- word query in relational databases

    [Luo et al., 2011] Yi Luo, Wei Wang, Xuemin Lin, Xiaofang Zhou, Jianmin Wang, and Keqiu Li. SPARK2: top-k key- word query in relational databases. IEEE Trans. Knowl. Data Eng., 23(12):1763–1780,

    work page 2011

  14. [14]

    Malliaros and Michalis Vazirgiannis

    [Malliaros and Vazirgiannis, 2013] Fragkiskos D. Malliaros and Michalis Vazirgiannis. To stay or not to stay: modeling engagement dynamics in social graphs. In CIKM, pages 469–478,

    work page 2013

  15. [15]

    [Medya et al., 2019] Sourav Medya, Tiyani Ma, Arlei Silva, and Ambuj K. Singh. K-core minimization: A game theo- retic approach. CoRR, abs/1901.02166,

    work page arXiv 2019

  16. [16]

    The k-core as a predictor of struc- tural collapse in mutualistic ecosystems

    [Morone et al., 2019] Flaviano Morone, Gino Del Ferraro, and Hern´an A Makse. The k-core as a predictor of struc- tural collapse in mutualistic ecosystems. Nature Physics, 15(1):95,

    work page 2019

  17. [17]

    Complexity classification of some edge modification problems

    [Natanzon et al., 2001] Assaf Natanzon, Ron Shamir, and Roded Sharan. Complexity classification of some edge modification problems. Discrete Applied Mathematics , 113(1):109–128,

    work page 2001

  18. [18]

    Network structure and minimum degree

    [Seidman, 1983] Stephen B Seidman. Network structure and minimum degree. Social networks, 5(3):269–287,

    work page 1983

  19. [19]

    On edge-addition problem

    [Suady and Najim, 2014] Suaad AA Suady and Alaa A Na- jim. On edge-addition problem. Journal of College of Education for Pure Science, 4(1):26–36,

    work page 2014

  20. [20]

    Structural diversity in social contagion

    [Ugander et al., 2012] Johan Ugander, Lars Backstrom, Cameron Marlow, and Jon Kleinberg. Structural diversity in social contagion. PNAS, 109(16):5962–5966,

    work page 2012

  21. [21]

    Arrival and departure dynamics in social networks

    [Wu et al., 2013] Shaomei Wu, Atish Das Sarma, Alex Fab- rikant, Silvio Lattanzi, and Andrew Tomkins. Arrival and departure dynamics in social networks. In WSDM, pages 233–242,

    work page 2013

  22. [22]

    K-core minimization: An edge manipu- lation approach

    [Zhu et al., 2018] Weijie Zhu, Chen Chen, Xiaoyang Wang, and Xuemin Lin. K-core minimization: An edge manipu- lation approach. In CIKM, pages 1667–1670, 2018

    work page 2018