Adaptive Truss Maximization on Large Graphs: A Minimum Cut Approach

Zitan Sun, Xin Huang*, Chengzhi Piao, Cheng Long, Jianliang Xu

*Corresponding author for this work

Research output: Contribution to conferenceConference paperpeer-review


A cohesive subgraph of k-truss requires that each edge has at least (k − 2) triangles, which has wide applications of modeling social communities and complex network visualization. Recently, the study of truss maximization has gained attention, which aims to enlarge k-truss most by inserting b new edges into a graph G. However, existing maximization methods suffer from a stiff strategy of complete truss conversion, that is either converting the whole (k−1)-truss component to k-truss or converting no edge to k-truss without using any budget. To tackle this bottleneck, we develop a novel partial conversion strategy to explore more insertion plans.

Based on partial conversion strategy, we revisit the problem of truss maximization in this paper and propose adaptive solutions by achieving more new k-truss edges. Specifically, we first decompose all (k−1)-truss into a series of disjoint components via the triangle connectivity, where each component’s conversion is independent to each other. Then, for each (k−1)- truss component, we explore possible insertion plans of partial conversions. An intuitive method is to randomly insert a budget no more than b new edges and check the expected profit of new k-truss edges. Obviously, this method is inefficient due to a large search space of edge insertions and many times of expensive k-truss verification. To improve it, we propose a new minimum-cut based approach, which converts a subgraph of (k−1)-truss component into a flow graph with weighted edges and finds a key of maximum-flow answer corresponding to a k-truss conversion plan with the minimum budget consumption. Next, we develop a new dynamic programming framework to find the best way to allocate the budget b to all components. We design two fast dynamic programming algorithms and analyze the complexities theoretically. In addition, we explore the case of a large given budget b and extend our techniques to handle the conversion of (k−h)-truss into k-truss for 2 ≤ h ≤ k −2. Extensive experiment results demonstrate the superiority of our algorithms against the state-of-the-art methods.
Original languageEnglish
Publication statusPublished - May 2024
Event40th IEEE International Conference on Data Engineering, ICDE 2024 - Kinepolis Jaarbeurs theater, Utrecht, Netherlands
Duration: 13 May 202417 May 2024 (Link to conference's schedule ) (Conference's website)


Conference40th IEEE International Conference on Data Engineering, ICDE 2024
OtherThe annual IEEE International Conference on Data Engineering (ICDE) is one of the premier conferences in data and information engineering and addresses research issues on designing, building, managing, and evaluating advanced data intensive systems and applications. It is a leading forum for researchers, practitioners, developers, and users to explore cutting-edge ideas and to exchange techniques, tools, and experiences.

Each year, ICDE attracts over 500 researchers and practitioners from the academia, industry and government from across the world. The audience includes leading data scientists and professors, entrepreneurs, developers, talented young researchers/students and other thought leaders from major vendors and academia.

This year ICDE will take place in Utrecht. It is the fourth largest city in the Netherlands, located right in the middle of the country, and is a major transportation hub. The historical part of the city features many buildings dating back in the middle ages. It has been the religious centre of the Netherlands since the 8th century and the most important city. It had been the country's cultural centre, until the 16th century when it was surpassed by Amsterdam. Today, it hosts the second-highest number of cultural events in the country. It is home to Utrecht University, the largest university in the Netherlands, that is ranked internationally in the 66th position by the Times Higher Education University Rankings.
Internet address

User-Defined Keywords

  • k-truss
  • graph enhancement
  • minimum cut
  • maximization
  • dynamic


Dive into the research topics of 'Adaptive Truss Maximization on Large Graphs: A Minimum Cut Approach'. Together they form a unique fingerprint.

Cite this