Title: Local Algorithms for Hierarchical Dense Subgraph Discovery,
Abstract: Finding the dense regions of a graph and relations among them is a
fundamental problem in network analysis. Core and truss decompositions reveal
dense subgraphs with hierarchical relations. The incremental nature of
algorithms for computing these decompositions and the need for global
information at each step of the algorithm hinders scalable parallelization and
approximations since the densest regions are not revealed until the end. In a
previous work, Lu et al. proposed to iteratively compute the $h$-indices of
neighbor vertex degrees to obtain the core numbers and prove that the
convergence is obtained after a finite number of iterations. This work
generalizes the iterative $h$-index computation for truss decomposition as well
as nucleus decomposition which leverages higher-order structures to generalize
core and truss decompositions. In addition, we prove convergence bounds on the
number of iterations. We present a framework of local algorithms to obtain the
core, truss, and nucleus decompositions. Our algorithms are local, parallel,
offer high scalability, and enable approximations to explore time and quality
trade-offs. Our shared-memory implementation verifies the efficiency,
scalability, and effectiveness of our local algorithms on real-world networks.