论文标题
在两层随机模型上隐藏的社区检测：理论观点
Hidden Community Detection on Two-layer Stochastic Models: a Theoretical Perspective
论文作者
论文摘要
隐藏的社区是最近提出的一个新的图理论概念[4]，其中作者还提出了一种称为Hicode（隐藏社区检测）的元信息，用于检测隐藏的社区。通过实验证明了Hicode，它能够发现以前的弱层覆盖了薄层，并以较高的精度揭示了弱和强层。但是，作者没有为表现提供理论保证。在这项工作中，我们将重点放在综合两层网络上的Hicode的理论分析上，其中层彼此独立，每一层都是由随机块模型生成的。我们在以下方面通过两层随机块模型网络桥接它们的缝隙：1）我们表明，局部优化模块化的分区对应于接地层，表明模块化优化算法可以检测强层； 2）我们证明，当减少发现的层时，Hicode会增加所有未还原层的绝对模块，显示其层还原步骤使弱层更容易检测到。我们的工作为Hicode建立了坚实的理论基础，这表明它有望在两层网络中揭示弱和强层社区的层面。
Hidden community is a new graph-theoretical concept recently proposed [4], in which the authors also propose a meta-approach called HICODE (Hidden Community Detection) for detecting hidden communities. HICODE is demonstrated through experiments that it is able to uncover previously overshadowed weak layers and uncover both weak and strong layers at a higher accuracy. However, the authors provide no theoretical guarantee for the performance. In this work, we focus on the theoretical analysis of HICODE on synthetic two-layer networks, where layers are independent of each other and each layer is generated by stochastic block model. We bridge their gap through two-layer stochastic block model networks in the following aspects: 1) we show that partitions that locally optimize modularity correspond to grounded layers, indicating modularity-optimizing algorithms can detect strong layers; 2) we prove that when reducing found layers, HICODE increases absolute modularities of all unreduced layers, showing its layer reduction step makes weak layers more detectable. Our work builds a solid theoretical base for HICODE, demonstrating that it is promising in uncovering both weak and strong layers of communities in two-layer networks.
