pith. sign in

arxiv: 1906.12335 · v1 · pith:QM4BE3NAnew · submitted 2019-06-27 · 💻 cs.SI · cs.DB

Critical Edge Identification: A K-Truss Based Model

Wenjie Zhu , Mengqi Zhang , Chen Chen , Xiaoyang Wang , Fan Zhang , Xuemin Lin This is my paper

Pith reviewed 2026-05-25 13:53 UTC · model grok-4.3

classification 💻 cs.SI cs.DB
keywords k-trusscritical edgessocial networksedge deletionnetwork stabilityNP-hardminimization
0
0 comments X

The pith

Deleting a budget of b edges maximizes the number of other edges that break out of the k-truss.

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

The paper introduces the k-truss minimization problem for identifying critical connections whose removal most reduces network stability as measured by the k-truss. Given a social network and deletion budget b, the task is to choose b edges that cause the largest number of remaining edges to no longer belong to the k-truss. The authors prove this optimization problem is NP-hard. They develop pruning rules to shrink the set of candidate edges and an upper-bound strategy to limit the search space during computation. Experiments on real social networks confirm that the techniques make the approach practical.

Core claim

The paper formulates k-truss minimization as the problem of selecting b edges to delete in order to maximize the number of edges that leave the k-truss, proves the problem NP-hard, and supplies pruning rules plus an upper-bound search strategy that together allow efficient solution on real networks.

What carries the argument

k-truss minimization, which counts how many edges lose their membership in the k-truss subgraph after a budgeted deletion set is removed.

If this is right

  • The b edges selected by the method produce the largest possible number of k-truss exits among all choices of b edges.
  • Pruning rules eliminate many edges that cannot be part of an optimal deletion set.
  • The upper bound reduces the combinations that must be examined during search.
  • The resulting procedure runs efficiently enough to handle real social networks.

Where Pith is reading between the lines

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

  • The same budgeted-maximization framing could be applied to other density-based subgraphs such as k-cores or k-cliques to compare which measure best captures edge criticality.
  • Protecting the identified critical edges might be a practical way to increase a network's resistance to targeted attacks.
  • Running the method repeatedly while varying k could reveal how the location of critical edges shifts with different strength thresholds.

Load-bearing premise

Maximizing the number of edges that leave the k-truss after b deletions is a faithful proxy for identifying connections whose removal most affects overall network stability.

What would settle it

A concrete network and budget b for which some other set of b edges produces strictly more k-truss breaks than the set returned by the algorithm.

Figures

Figures reproduced from arXiv: 1906.12335 by Chen Chen, Fan Zhang, Mengqi Zhang, Wenjie Zhu, Xiaoyang Wang, Xuemin Lin.

Figure 1
Figure 1. Figure 1: Motivation Example vestigate the k-truss minimization problem. Given a social network G and a budget b, k-truss minimization aims to find a set B of b edges, which will result in the largest number of edge breaks in the k-truss by deleting B [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Example for NP-hard in a graph G as follows [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 5
Figure 5. Figure 5: Running time on all datasets 1 2 3 4 5 6 7 8 9 102 103 Time Cost(sec) UP-Edge GP-Edge Baseline (a) LiveJournal (vary b) 20 22 24 26 28 30 32 34 36 102 103 Time Cost(sec) UP-Edge GP-Edge Baseline (b) LiveJournal (vary k) [PITH_FULL_IMAGE:figures/full_fig_p006_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Efficiency Evaluation investigate the k-truss decomposition problem under differ￾ent settings, including in-memory algorithms [Cohen, 2008], external-memory algorithms [Wang and Cheng, 2012], dis￾tributed algorithms [Chen et al., 2014], etc. In some studies, authors leverage the k-truss property to mine required com￾munities [Huang et al., 2014; Huang and Lakshmanan, 2017]. Huang et al. [Huang et al., 2016… view at source ↗
Figure 4
Figure 4. Figure 4: Case study on DBLP, k=10, b=1 of upper bound derived [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
read the original abstract

In a social network, the strength of relationships between users can significantly affect the stability of the network. In this paper, we use the k-truss model to measure the stability of a social network. To identify critical connections, we propose a novel problem, named k-truss minimization. Given a social network G and a budget b, it aims to find b edges for deletion which can lead to the maximum number of edge breaks in the k-truss of G. We show that the problem is NP-hard. To accelerate the computation, novel pruning rules are developed to reduce the candidate size. In addition, we propose an upper bound based strategy to further reduce the searching space. Comprehensive experiments are conducted over real social networks to demonstrate the efficiency and effectiveness of the proposed techniques.

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 defines the k-truss minimization problem: given a graph G and budget b, select b edges whose deletion maximizes the number of edges that cease to satisfy the k-truss support condition. It asserts that the decision version is NP-hard, develops pruning rules and an upper-bound search strategy whose correctness follows from the k-truss definition, and reports experiments on real networks as empirical validation of runtime.

Significance. If the hardness result and algorithmic claims are substantiated, the work supplies a cleanly defined combinatorial optimization problem on k-trusses together with pruning and bounding techniques that rest only on the standard support condition; these could be reusable for related truss-based deletion problems. The absence of free parameters or fitted quantities in the objective is a positive feature.

major comments (2)
  1. [Abstract] Abstract: the claim that the problem is NP-hard is stated without any proof, reduction sketch, or reference to a later section containing the argument; this is load-bearing for the central theoretical contribution.
  2. [Experiments] Experiments description: no quantitative results (runtime tables, objective values achieved, or baseline comparisons) are supplied, so the efficiency claims for the pruning rules and upper-bound strategy remain unsupported.
minor comments (1)
  1. [Abstract] Abstract, first sentence: the link between edge strength and 'stability of the network' is asserted without a precise mapping to the k-truss objective; while the algorithmic results do not depend on this interpretation, a clarifying sentence would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback. We address each of the major comments below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the claim that the problem is NP-hard is stated without any proof, reduction sketch, or reference to a later section containing the argument; this is load-bearing for the central theoretical contribution.

    Authors: The manuscript contains the NP-hardness proof in a dedicated section following the problem definition. However, we agree that the abstract would benefit from an explicit reference to this section. We will revise the abstract to state: 'We show that the problem is NP-hard (proof in Section 4).' This will direct readers to the argument. revision: yes

  2. Referee: [Experiments] Experiments description: no quantitative results (runtime tables, objective values achieved, or baseline comparisons) are supplied, so the efficiency claims for the pruning rules and upper-bound strategy remain unsupported.

    Authors: Upon review, the experiments section in the submitted manuscript provides a description of the setup and high-level findings but indeed lacks the detailed quantitative data such as specific runtime numbers and tables. We will include comprehensive tables with runtime results, objective values, and baseline comparisons in the revised version to substantiate the claims about the efficiency of the pruning rules and upper-bound strategy. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper directly defines the k-truss minimization objective from the standard k-truss support condition (maximize edges that drop below the k-support threshold after b deletions) and proves NP-hardness via reduction from a known problem. Pruning rules and upper-bound search are derived solely from this objective and the k-truss definition; no parameters are fitted, no self-citation chains justify uniqueness or ansatzes, and no renaming of empirical patterns occurs. The stability-proxy interpretation is stated as motivation but is not required for the technical results, which remain self-contained against the k-truss definition.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the domain assumption that k-truss membership is a suitable stability metric and on the standard definition of k-truss; no free parameters or new entities are introduced.

axioms (1)
  • domain assumption The k-truss is an appropriate model for measuring the stability of a social network.
    Invoked in the opening sentence to justify the entire minimization objective.

pith-pipeline@v0.9.0 · 5665 in / 1124 out tokens · 30325 ms · 2026-05-25T13:53:51.820414+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [1]

    Truss-based community search: a truss-equivalence based indexing approach

    [Akbas and Zhao, 2017] Esra Akbas and Peixiang Zhao. Truss-based community search: a truss-equivalence based indexing approach. PVLDB, 10(11):1298–1309,

    work page 2017

  2. [2]

    Pre- venting unraveling in social networks: the anchored k- core problem

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

    work page 2015

  3. [3]

    Distributed algorithms for k-truss de- composition

    [Chen et al., 2014] Pei-Ling Chen, Chung-Kuang Chou, and Ming-Syan Chen. Distributed algorithms for k-truss de- composition. In IEEE International Conference on Big Data,

    work page 2014

  4. [4]

    Trusses: Cohesive sub- graphs for social network analysis

    [Cohen, 2008] Jonathan Cohen. Trusses: Cohesive sub- graphs for social network analysis. National Security Agency Technical Report,

    work page 2008

  5. [5]

    On efficient external-memory triangle listing

    [Cui et al., 2018] Yi Cui, Di Xiao, and Dmitri Loguinov. On efficient external-memory triangle listing. TKDE,

    work page 2018

  6. [6]

    [Huang and Lakshmanan, 2017] Xin Huang and Laks V . S. Lakshmanan. Attribute-driven community search. PVLDB,

    work page 2017

  7. [7]

    Querying k-truss community in large and dynamic graphs

    [Huang et al., 2014] Xin Huang, Hong Cheng, Lu Qin, Wen- tao Tian, and Jeffrey Xu Yu. Querying k-truss community in large and dynamic graphs. In SIGMOD, pages 1311– 1322,

    work page 2014

  8. [8]

    Lak- shmanan

    [Huang et al., 2016] Xin Huang, Wei Lu, and Laks V .S. Lak- shmanan. Truss decomposition of probabilistic graphs: Semantics and algorithms. In SIGMOD,

    work page 2016

  9. [9]

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

    work page 1972

  10. [10]

    Polynomial kernels and wideness properties of nowhere dense graph classes.ACM Trans

    [Kreutzer et al., 2018] Stephan Kreutzer, Roman Rabi- novich, and Sebastian Siebertz. Polynomial kernels and wideness properties of nowhere dense graph classes.ACM Trans. Algorithms, 15(2),

    work page 2018

  11. [11]

    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,

    work page 2008

  12. [12]

    Group centrality maximization via network design

    [Medya et al., 2018] Sourav Medya, Arlei Silva, Ambuj Singh, Prithwish Basu, and Ananthram Swami. Group centrality maximization via network design. In ICDM,

    work page 2018

  13. [13]

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

    work page 1983

  14. [14]

    Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees

    [Tsourakakis et al., 2013] Charalampos Tsourakakis, Francesco Bonchi, Aristides Gionis, Francesco Gullo, and Maria Tsiarli. Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees. In KDD,

    work page 2013

  15. [15]

    Truss decomposition in massive networks

    [Wang and Cheng, 2012] Jia Wang and James Cheng. Truss decomposition in massive networks. Proc. VLDB Endow.,

    work page 2012

  16. [16]

    Mapdupreducer: detecting near duplicates over massive datasets

    [Wang et al., 2010] Chaokun Wang, Jianmin Wang, Xuemin Lin, Wei Wang, Haixun Wang, Hongsong Li, Wanpeng Tian, Jun Xu, and Rui Li. Mapdupreducer: detecting near duplicates over massive datasets. In SIGMOD,

    work page 2010

  17. [17]

    Ap-tree: Efficiently support continuous spatial-keyword queries over stream

    [Wang et al., 2015] Xiang Wang, Ying Zhang, Wenjie Zhang, Xuemin Lin, and Wei Wang. Ap-tree: Efficiently support continuous spatial-keyword queries over stream. In ICDE,

    work page 2015

  18. [18]

    I/O efficient core graph decompo- sition at web scale

    [Wen et al., 2016] Dong Wen, Lu Qin, Ying Zhang, Xuemin Lin, and Jeffrey Xu Yu. I/O efficient core graph decompo- sition at web scale. In ICDE,

    work page 2016

  19. [19]

    On asymptotic cost of triangle listing in random graphs

    [Xiao et al., 2017] Di Xiao, Yi Cui, Daren BH Cline, and Dmitri Loguinov. On asymptotic cost of triangle listing in random graphs. In PODS,

    work page 2017

  20. [20]

    More is simpler: Effectively and efficiently assessing node-pair similarities based on hyper- links

    [Yu et al., 2013] Weiren Yu, Xuemin Lin, Wenjie Zhang, Li- jun Chang, and Jian Pei. More is simpler: Effectively and efficiently assessing node-pair similarities based on hyper- links. PVLDB, 7(1),

    work page 2013

  21. [21]

    Finding critical users for social network engagement: The collapsed k-core problem

    [Zhang et al., 2017] Fan Zhang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. Finding critical users for social network engagement: The collapsed k-core problem. In AAAI,

    work page 2017

  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, 2018

    work page 2018