title: Sampling Motif-Constrained Ensembles of Networks.
abstract: 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.
authors.affiliation: Max Planck Institute for the Physics of Complex Systems, 01187 Dresden, Germany.
authors.forename: Rico
authors.initials: R
authors.lastname: Fischer
authors.affiliation: Max Planck Institute for the Physics of Complex Systems, 01187 Dresden, Germany.
authors.forename: Jorge C
authors.initials: JC
authors.lastname: Leitão
authors.affiliation: Institut für Theoretische Physik, Universität Bremen, Hochschulring 18, 28359 Bremen, Germany.
authors.forename: Tiago P
authors.initials: TP
authors.lastname: Peixoto
authors.affiliation: Max Planck Institute for the Physics of Complex Systems, 01187 Dresden, Germany.
authors.forename: Eduardo G
authors.initials: EG
authors.lastname: Altmann