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

Xin Sun, Xin Huang, Zitan Sun, Di Jin

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

Abstract

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)
Pages1754-1763
Number of pages10
ISBN (Electronic)9781450384469
DOIs
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
https://www.cikm2021.org/
https://dl.acm.org/doi/proceedings/10.1145/3459637

Publication series

NameInternational Conference on Information and Knowledge Management, Proceedings

Conference

Conference30th ACM International Conference on Information and Knowledge Management, CIKM 2021
Country/TerritoryAustralia
CityGold Coast, Queensland
Period1/11/215/11/21
Internet address

Scopus Subject Areas

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

User-Defined Keywords

  • edge insertions
  • k-truss
  • subgraph maximization

Fingerprint

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