The interplay of microscopic and mesoscopic structure in complex networks

Abstract

Not all nodes in a network are created equal. Differences and similarities exist at both individual node and group levels. Disentangling single node from group properties is crucial for network modeling and structural inference. Based on unbiased generative probabilistic exponential random graph models and employing distributive message passing techniques, we present an efficient algorithm that allows one to separate the contributions of individual nodes and groups of nodes to the network structure. This leads to improved detection accuracy of latent class structure in real world data sets compared to models that focus on group structure alone. Furthermore, the inclusion of hitherto neglected group specific effects in models used to assess the statistical significance of small subgraph (motif) distributions in networks may be sufficient to explain most of the observed statistics. We show the predictive power of such generative models in forecasting putative gene-disease associations in the Online Mendelian Inheritance in Man (OMIM) database. The approach is suitable for both directed and undirected uni-partite as well as for bipartite networks.

References in corpus (4)

• Community detection in graphs
• Stochastic blockmodels and community structure in networks
• Missing and spurious interactions and the reconstruction of complex networks
• Mixture models and exploratory analysis in networks

Cited by in corpus (17)

• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Parsimonious module inference in large networks
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• Entropy of stochastic blockmodel ensembles
• Bayesian stochastic blockmodeling
• Model Selection for Degree-corrected Block Models
• Spectral methods for the detection of network community structure: a comparative analysis
• Consistencies and inconsistencies between model selection and link prediction in networks
• Networking - A Statistical Physics Perspective
• Adapting Stochastic Block Models to Power-Law Degree Distributions
• Comparative Study for Inference of Hidden Classes in Stochastic Block Models
• Reconstructing mesoscale network structures
• Emergence of scale-free close-knit friendship structure in online social networks
• Motifs in Triadic Random Graphs based on Steiner Triple Systems
• Oriented and Degree-generated Block Models: Generating and Inferring Communities with Inhomogeneous Degree Distributions
• On the Role of Triadic Substructures in Complex Networks
• Non-Thermal Transitions in n-th Order Moral Decisions