论文标题
最可能的最密集的子图
Most Probable Densest Subgraphs
论文作者
论文摘要
计算最密集的子图是一个原始的图形操作，在检测生物，社交，网络和金融网络中的社区，事件和异常方面具有关键的应用。在本文中，我们研究了不确定的图表中最可能的最稠密子图（MPD）发现的新问题：找到最有可能在不确定图中诱导最密集的子图的节点集。我们通过考虑各种密度概念，例如集团和模式密度，研究TOP-K MPDS，并找到具有最大的封存概率在最浓度子图内的节点，从而进一步扩展了问题。我们表明，计算诱导最密集子图的节点集的概率是＃p-hard。然后，我们使用端到端精度确保基于采样的有效算法来计算MPD。我们对大脑和社交网络的彻底实验结果和现实案例研究证明了解决方案的有效性，效率和实用性。
Computing the densest subgraph is a primitive graph operation with critical applications in detecting communities, events, and anomalies in biological, social, Web, and financial networks. In this paper, we study the novel problem of Most Probable Densest Subgraph (MPDS) discovery in uncertain graphs: Find the node set that is the most likely to induce a densest subgraph in an uncertain graph. We further extend our problem by considering various notions of density, e.g., clique and pattern densities, studying the top-k MPDSs, and finding the node set with the largest containment probability within densest subgraphs. We show that it is #P-hard to compute the probability of a node set inducing a densest subgraph. We then devise sampling-based efficient algorithms, with end-to-end accuracy guarantees, to compute the MPDS. Our thorough experimental results and real-world case studies on brain and social networks validate the effectiveness, efficiency, and usefulness of our solution.
