Sampling motif-constrained ensembles of networks

Abstract

The statistical significance of network properties is conditioned on null models which satisfy spec- ified 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 paper we use the Wang-Landau method to obtain a multicanonical sampling that overcomes both these problems. We sample, in polynomial time, net- works 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.

Updated version, as published in the journal. 7 pages, 5 figures, one Supplemental Material

References in corpus (6)

• Stochastic blockmodels and community structure in networks
• Triadic closure as a basic generating mechanism of communities in complex networks
• Performance Limitations of Flat Histogram Methods and Optimality of Wang-Landau Sampling
• Exploring the assortativity-clustering space of a network's degree sequence
• Analysis of the convergence of the 1/t and Wang-Landau algorithms in the calculation of multidimensional integrals
• Large-deviation properties of resilience of power grids

Cited by in corpus (15)

• Networks beyond pairwise interactions: structure and dynamics
• The Statistical Physics of Real-World Networks
• A Bayesian machine scientist to aid in the solution of challenging scientific problems
• Disentangling homophily, community structure and triadic closure in networks
• Network nestedness as generalized core-periphery structures
• The ambiguity of nestedness under soft and hard constraints
• What is the Entropy of a Social Organization?
• Micro, Meso, Macro: the effect of triangles on communities in networks
• Bayesian machine scientist to compare data collapses for the Nikuradse dataset
• Importance Sampling of Rare Events in Chaotic Systems
• Taming chaos to sample rare events: the effect of weak chaos
• Higher-order null models as a lens for social systems
• A null model for Dunbar's circles
• Large deviation and anomalous fluctuations scaling in degree assortativity on configuration networks
• Alice and the Caterpillar: A more descriptive null model for assessing data mining results