Random Graph Modeling: A survey of the concepts

Abstract

Random graph (RG) models play a central role in the complex networks analysis. They help to understand, control, and predict phenomena occurring, for instance, in social networks, biological networks, the Internet, etc. Despite a large number of RG models presented in the literature, there are few concepts underlying them. Instead of trying to classify a wide variety of very dispersed models, we capture and describe concepts they exploit considering preferential attachment, copying principle, hyperbolic geometry, recursively defined structure, edge switching, Monte Carlo sampling, etc. We analyze RG models, extract their basic principles, and build a taxonomy of concepts they are based on. We also discuss how these concepts are combined in RG models and how they work in typical applications like benchmarks, null models, and data anonymization.

References in corpus (31)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Modularity and community structure in networks
• Assortative mixing in networks
• Benchmark graphs for testing community detection algorithms
• The structure and dynamics of multilayer networks
• Analysis of weighted networks
• Characterization of complex networks: A survey of measurements
• Hierarchical Organization in Complex Networks
• Graph Embedding Techniques, Applications, and Performance: A Survey
• Hyperbolic Geometry of Complex Networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Scale-free topology of e-mail networks
• Synchronization reveals topological scales in complex networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Modeling the Internet's Large-Scale Topology
• Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
• Pseudofractal Scale-free Web
• Deterministic Scale-Free Networks
• Characterization and Modeling of weighted networks
• Emergence of a small world from local interactions: Modeling acquaintance networks
• Community structure and scale-free collections of Erdös-Rényi graphs
• A Model for Social Networks
• Fractal and Transfractal Recursive Scale-Free Nets
• Log-Networks
• A spatial model for social networks
• Evolving Clustered Random Networks
• Multifractal Network Generator
• Detection of node group membership in networks with group overlap
• Learning multifractal structure in large networks

Cited by in corpus (8)

• Topological optimization of hybrid quantum key distribution networks
• Random Graphs with Prescribed $K$-Core Sequences: A New Null Model for Network Analysis
• Node Copying: A Random Graph Model for Effective Graph Sampling
• Efficient Semi-External Depth-First Search
• Benchmarking Graph Data Management and Processing Systems: A Survey
• Sampling distributions and estimation for multi-type Branching Processes
• Scale-Invariant Strength Assortativity of Streaming Butterflies
• de Finetti Style Theorems With Applications to Network Analysis