Exponential random graph models for networks with community structure

Abstract

Although the community structure organization is one of the most important characteristics of real-world networks, the traditional network models fail to reproduce the feature. Therefore, the models are useless as benchmark graphs for testing community detection algorithms. They are also inadequate to predict various properties of real networks. With this paper we intend to fill the gap. We develop an exponential random graph approach to networks with community structure. To this end we mainly built upon the idea of blockmodels. We consider both, the classical blockmodel and its degree-corrected counterpart, and study many of their properties analytically. We show that in the degree-corrected blockmodel, node degrees display an interesting scaling property, which is reminiscent of what is observed in real-world fractal networks. The scaling feature comes as a surprise, especially that in this study, contrary to what is suggested in the literature, the scaling property is not attributed to any specific network construction procedure. It is an intrinsic feature of the degree-corrected blockmodel. A short description of Monte Carlo simulations of the models is also given in the hope of being useful to others working in the field.

8 pages, 2 figures

References in corpus (3)

• Benchmark graphs for testing community detection algorithms
• Comparing community structure identification
• Stochastic blockmodels and community structure in networks

Cited by in corpus (13)

• The Statistical Physics of Real-World Networks
• Reconstruction methods for networks: the case of economic and financial systems
• Extracting significant signal of news consumption from social networks: the case of Twitter in Italian political elections
• Reducing Degeneracy in Maximum Entropy Models of Networks
• Reconstructing networks
• Ensemble nonequivalence in random graphs with modular structure
• Reconstructing mesoscale network structures
• Testing biological network motif significance with exponential random graph models
• Multiscale network renormalization: scale-invariance without geometry
• Stylized facts in social networks: Community-based static modeling
• The Fitness-Corrected Block Model, or how to create maximum-entropy data-driven spatial social networks
• Beyond traditional box-covering: Determining the fractal dimension of complex networks using a fixed number of boxes of flexible diameter
• Model-based reconstruction of real-world fractal complex networks