Fischer Rico, Leitão Jorge C, Peixoto Tiago P, Altmann Eduardo G
Max Planck Institute for the Physics of Complex Systems, 01187 Dresden, Germany.
Institut für Theoretische Physik, Universität Bremen, Hochschulring 18, 28359 Bremen, Germany.
Phys Rev Lett. 2015 Oct 30;115(18):188701. doi: 10.1103/PhysRevLett.115.188701. Epub 2015 Oct 29.
The statistical significance of network properties is conditioned on null models which satisfy specified properties but that are otherwise random. Exponential random graph models are a principled theoretical framework to generate such constrained ensembles, but which often fail in practice, either due to model inconsistency or due to the impossibility to sample networks from them. These problems affect the important case of networks with prescribed clustering coefficient or number of small connected subgraphs (motifs). In this Letter we use the Wang-Landau method to obtain a multicanonical sampling that overcomes both these problems. We sample, in polynomial time, networks with arbitrary degree sequences from ensembles with imposed motifs counts. Applying this method to social networks, we investigate the relation between transitivity and homophily, and we quantify the correlation between different types of motifs, finding that single motifs can explain up to 60% of the variation of motif profiles.
网络属性的统计显著性取决于零模型，这些零模型满足特定属性但在其他方面是随机的。指数随机图模型是生成此类受限集合的一个有原则的理论框架，但在实践中常常失败，要么是由于模型不一致，要么是由于无法从中采样网络。这些问题影响了具有规定聚类系数或小连通子图（基序）数量的网络这一重要情况。在本信函中，我们使用王 - 兰道方法来获得一种多正则采样，它克服了这两个问题。我们在多项式时间内，从具有规定基序计数的集合中采样具有任意度序列的网络。将此方法应用于社交网络，我们研究了传递性和同质性之间的关系，并量化了不同类型基序之间的相关性，发现单个基序可以解释高达60%的基序分布变化。
