Sampling Motif-Constrained Ensembles of Networks

Area of Science:

• Network science
• Computational sociology
• Statistical physics

Background:

• Assessing statistical significance of network properties relies on null models.
• Exponential random graph models (ERGM) are theoretically sound but often fail in practice due to inconsistency or sampling difficulties.
• These issues are particularly problematic for networks with specified clustering coefficients or motif counts.

Purpose of the Study:

• To develop a robust method for sampling networks from constrained ensembles, specifically addressing limitations of ERGMs.
• To enable the generation of networks with prescribed motif counts and arbitrary degree sequences.
• To investigate relationships between network transitivity, homophily, and motif correlations in social networks.

Main Methods:

• Utilized the Wang-Landau method for multicanonical sampling.
• Developed a method to sample networks with arbitrary degree sequences and imposed motif counts in polynomial time.
• Applied the method to analyze real-world social network data.

Main Results:

• Successfully overcame practical limitations of ERGMs in generating constrained network ensembles.
• Enabled efficient sampling of networks with specified motif counts.
• Quantified correlations between different network motifs, finding single motifs can explain up to 60% of motif profile variation.
• Investigated the relationship between transitivity and homophily in social networks.

Conclusions:

• The Wang-Landau method provides a powerful and practical approach for network ensemble generation and analysis.
• This method facilitates deeper understanding of network structure and the interplay of motifs.
• Findings offer insights into the organization of social networks and the predictive power of specific motifs.