K-Truss Decomposition of Large Networks on a Single Consumer-Grade Machine

k-truss decomposition of a graph is a method to discover cohesive subgraphs and to study the hierarchical structure among them. The existing algorithms for computing k-truss of today's massive networks mainly focus on reducing the runtime using parallel computation on a powerful multi-core server. Our focus, by contrast, is to investigate the feasibility of computing the k-truss on a single consumer-grade machine within a reasonable amount of time. We engineer two efficient k-truss decomposition algorithms: the edge-peeling algorithm proposed by J. Wang and J. Cheng and the asynchronous h-index-updating algorithm proposed by A. E. Sariyuce, C. Seshadhri, and A. Pinar. We reduce their memory usage significantly by optimizing the underlying data structures and by using WebGraph, an efficient framework for graph compression. With our optimized implementation, we show that we can efficiently compute k-truss decomposition of large networks (e.g., a graph with 1.2 billion edges) on a single consumer-grade machine.