Much of the complexity of social, biological, and engineered systems arises from a network of complex interactions connecting many basic components. Network analysis tools have been successful at uncovering latent structure termed communities in such networks. However, some of the most interesting structure can be difficult to uncover because it is obscured by the more dominant structure. Our previous work proposes a general structure amplification technique called HICODE that uncovers many layers of functional hidden structure in complex networks. HICODE incrementally weakens dominant structure through randomization allowing the hidden functionality to emerge, and uncovers these hidden structure in real-world networks that previous methods rarely uncover. In this work, we conduct a comprehensive and systematic theoretical analysis on the hidden community structure. In what follows, we define multi-layer stochastic block model, and provide theoretical support using the model on why the existence of hidden structure will make the detection of dominant structure harder compared with equivalent random noise. We then provide theoretical proofs that the iterative reducing methods could help promote the uncovering of hidden structure as well as boosting the detection quality of dominant structure.
翻译:社会、生物和工程系统的复杂性很大程度上来自连接许多基本组成部分的复杂互动网络。网络分析工具成功地揭示了这些网络中被称为社区的潜在结构。然而,一些最有趣的结构可能很难发现,因为它被更为占主导地位的结构所掩盖。我们以前的工作提出了一种称为HICODE的一般结构放大技术,它揭示了复杂网络中许多层次的功能隐蔽结构。HICODE通过随机化逐步削弱主导结构,允许隐藏功能出现,并在现实世界网络中发现这些以前很少发现的隐蔽结构。在这项工作中,我们对隐藏的社区结构进行了全面和系统的理论分析。在下文中,我们定义了多层结构的区块模型,并利用模型提供理论支持,说明为什么隐藏结构的存在将使对主导结构的探测与相当的随机噪音相比更加困难。我们然后提供理论证据,说明迭代减少方法可以帮助发现隐藏结构,提高主导结构的探测质量。