Theoretically and Practically Efficient Parallel Nucleus Decomposition (Abstract)
Jessica Shi, Laxman Dhulipala, Julian Shun · 2023
Discovering dense substructures in graphs is a fundamental topic in graph mining, and has been studied across many areas including computational biology, spam and fraud-detection, and large-scale network analysis. Recently, Sariyuce et al. introduced the nucleus decomposition problem, which generalizes the influential notions of k-cores and k-trusses to k-(r,s) nucleii, and can better capture higher-order structures. Informally, a k-(r,s) nucleus is the maximal induced subgraph such that every r-clique in the subgraph is contained in at least k s-cliques. The goal of the (r, s) nucleus decomposition problem is to identify for each r-clique in the graph, the largest k such that it is in a k-(r,s) nucleus.