  Finding dense components in graphs is of great importance in analyzing the
structure of networks. Popular and computationally feasible frameworks for
discovering dense subgraphs are core and truss decompositions. Recently,
Sariyuce et al. introduced nucleus decomposition, a generalization which uses
higher-order structures and can reveal interesting subgraphs that can be missed
by core and truss decompositions.
  In this paper, we present nucleus decomposition in probabilistic graphs. We
study the most interesting case of nucleus decomposition, k-(3,4)-nucleus,
which asks for maximal subgraphs where each triangle is contained in k
4-cliques. The major questions we address are: How to define meaningfully
nucleus decomposition in probabilistic graphs? How hard is computing nucleus
decomposition in probabilistic graphs? Can we devise efficient algorithms for
exact or approximate nucleus decomposition in large graphs?
  We present three natural definitions of nucleus decomposition in
probabilistic graphs: local, global, and weakly-global. We show that the local
version is in PTIME, whereas global and weakly-global are #P-hard and NP-hard,
respectively. We present an efficient and exact dynamic programming approach
for the local case and furthermore, present statistical approximations that can
scale to large datasets without much loss of accuracy. For global and
weakly-global decompositions, we complement our intractability results by
proposing efficient algorithms that give approximate solutions based on search
space pruning and Monte-Carlo sampling. Our extensive experimental results show
the scalability and efficiency of our algorithms. Compared to probabilistic
core and truss decompositions, nucleus decomposition significantly outperforms
in terms of density and clustering metrics.
