Truss Decomposition in Massive Networks

Abstract

The k-truss is a type of cohesive subgraphs proposed recently for the study of networks. While the problem of computing most cohesive subgraphs is NP-hard, there exists a polynomial time algorithm for computing k-truss. Compared with k-core which is also efficient to compute, k-truss represents the "core" of a k-core that keeps the key information of, while filtering out less important information from, the k-core. However, existing algorithms for computing k-truss are inefficient for handling today's massive networks. We first improve the existing in-memory algorithm for computing k-truss in networks of moderate size. Then, we propose two I/O-efficient algorithms to handle massive networks that cannot fit in main memory. Our experiments on real datasets verify the efficiency of our algorithms and the value of k-truss.

VLDB2012

References in corpus (3)

• New Model of Internet Topology Using k-shell Decomposition
• MEDUSA - New Model of Internet Topology Using k-shell Decomposition
• An O(m) Algorithm for Cores Decomposition of Networks

Cited by in corpus (5)

• Interplay Between Hierarchy and Centrality in Complex Networks
• Keyword Aware Influential Community Search in Large Attributed Graphs
• Finding the Hierarchy of Dense Subgraphs using Nucleus Decompositions
• Critical Edge Identification: A K-Truss Based Model
• On Rich Clubs of Path-Based Centralities in Networks