论文标题
概率图中的核分解：硬度和算法
Nucleus Decomposition in Probabilistic Graphs: Hardness and Algorithms
论文作者
论文摘要
在分析网络的结构中，在图中找到密集的组件至关重要。用于发现密集子图的流行和计算可行的框架是核心和桁架分解。最近，Sariyuce等。引入了核分解，这是一种使用高阶结构的概括，可以揭示有趣的子图，这些子图可能会被核心和桁架分解所遗漏。 在本文中，我们介绍了概率图中的核分解。我们研究了核分解的最有趣的病例，k-（3,4） - 核核，该核素要求最大的亚图中的每个三角形在k 4-晶格中包含在其中。我们解决的主要问题是：如何在概率图中定义有意义的核分解？概率图中的计算核分解的难度如何？我们可以在大图中设计有效的算法以精确或近似核分解吗？ 我们介绍了概率图中核分解的三个自然定义：局部，全局和弱全球。我们表明本地版本是ptime，而全球和弱全球范围分别为＃p-hard和np-hard。我们为本地案例提出了一种有效而精确的动态编程方法，此外，目前的统计近似值可以扩展到大型数据集，而不会丢失准确性。对于全球和弱全球分解，我们通过提出有效的算法来补充我们的顽固性结果，这些算法具有基于搜索空间修剪和蒙特卡罗取样的近似解决方案。我们广泛的实验结果显示了我们算法的可扩展性和效率。与概率核心和桁架分解相比，核分解在密度和聚类指标方面显着胜过。
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.
