URPP Social Networks, University of Zurich, Andreasstrasse 15, CH-8050 Zürich, Switzerland.
IMT School for Advanced Studies Lucca, Piazza San Francesco 19, I-55100 Lucca, Italy.
Phys Rev E. 2017 Nov;96(5-1):052311. doi: 10.1103/PhysRevE.96.052311. Epub 2017 Nov 14.
Hierarchical organization is an important, prevalent characteristic of complex systems; to understand their organization, the study of the underlying (generally complex) networks that describe the interactions between their constituents plays a central role. Numerous previous works have shown that many real-world networks in social, biologic, and technical systems present hierarchical organization, often in the form of a hierarchy of community structures. Many artificial benchmark graphs have been proposed to test different community detection methods, but no benchmark has been developed to thoroughly test the detection of hierarchical community structures. In this study, we fill this vacancy by extending the Lancichinetti-Fortunato-Radicchi (LFR) ensemble of benchmark graphs, adopting the rule of constructing hierarchical networks proposed by Ravasz and Barabási. We employ this benchmark to test three of the most popular community detection algorithms and quantify their accuracy using the traditional mutual information and the recently introduced hierarchical mutual information. The results indicate that the Ravasz-Barabási-Lancichinetti-Fortunato-Radicchi (RB-LFR) benchmark generates a complex hierarchical structure constituting a challenging benchmark for the considered community detection methods.
层次结构是复杂系统的一个重要且普遍的特征；为了理解它们的组织，研究描述其组成部分之间相互作用的基础（通常是复杂的）网络起着核心作用。许多先前的工作表明，社会、生物和技术系统中的许多真实网络呈现出层次结构，通常以社区结构层次的形式出现。已经提出了许多人工基准图来测试不同的社区检测方法，但尚未开发出基准来彻底测试层次社区结构的检测。在这项研究中，我们通过扩展 Lancichinetti-Fortunato-Radicchi（LFR）基准图集合来填补这一空白，采用 Ravasz 和 Barabási 提出的构建层次网络的规则。我们使用这个基准来测试三种最流行的社区检测算法，并使用传统的互信息和最近引入的层次互信息来量化它们的准确性。结果表明，Ravasz-Barabási-Lancichinetti-Fortunato-Radicchi（RB-LFR）基准生成了一个复杂的层次结构，构成了所考虑的社区检测方法的一个具有挑战性的基准。
