Budget-constrained Truss Maximization over Large Graphs: A Component-based Approach

Xin Sun, Xin Huang, Zitan Sun, Di Jin*

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

4 Citations (Scopus)


Cohesive substructure identification is one fundamental task of graph analytics. Recently, a useful problem of dense subgraph maximization has attracted significant attentions, which aims at enlarging a dense subgraph pattern using a few new edge insertions, e.g., k-core maximization. As a more cohesive subgraph of k-core, k-truss requires that each edge has at least k-2 triangles within this subgraph. However, the problem of k-truss maximization has not been studied yet. In this paper, we motivate and formulate a new problem of budget-constrained k-truss maximization. Given a budget of b edges and an integer k≥2, the problem is to find and insert b new edges into a graph G such that the resulted k-truss of G is maximized. We theoretically prove the NP-hardness of k-truss maximization problem. To efficiently tackle it, we analyze non-submodular property of k-truss newcomers function and develop non-conventional heuristic strategies for edge insertions. We first identify high-quality candidate edges with regard to (k-1)-light subgraphs and propose a greedy algorithm using per-edge insertion. Besides further improving the efficiency by pruning disqualified candidate edges, we finally develop a component-based dynamic programming algorithm for enlarging k-truss mostly, which makes a balance of budget assignment and inserts multiple edges simultaneously into all (k-1)-light components. Extensive experiments on nine real-world graphs demonstrate the efficiency and effectiveness of our proposed methods.

Original languageEnglish
Title of host publicationCIKM 2021 - Proceedings of the 30th ACM International Conference on Information and Knowledge Management
PublisherAssociation for Computing Machinery (ACM)
Number of pages10
ISBN (Electronic)9781450384469
Publication statusPublished - 26 Oct 2021
Event30th ACM International Conference on Information and Knowledge Management, CIKM 2021 - Virtual, Online, Gold Coast, Queensland, Australia
Duration: 1 Nov 20215 Nov 2021

Publication series

NameInternational Conference on Information and Knowledge Management, Proceedings


Conference30th ACM International Conference on Information and Knowledge Management, CIKM 2021
CityGold Coast, Queensland
Internet address

Scopus Subject Areas

  • Business, Management and Accounting(all)
  • Decision Sciences(all)

User-Defined Keywords

  • edge insertions
  • k-truss
  • subgraph maximization


Dive into the research topics of 'Budget-constrained Truss Maximization over Large Graphs: A Component-based Approach'. Together they form a unique fingerprint.

Cite this