A General Formalism for Inhomogeneous Random Graphs

Abstract

We present and investigate an extension of the classical random graph to a general class of inhomogeneous random graph models, where vertices come in different types, and the probability of realizing an edge depends on the types of its terminal vertices. This approach provides a general framework for the analysis of a large class of models. The generic phase structure is derived using generating function techniques, and relations to other classes of models are pointed out.

7 pages, no figures. To appear in Phys. Rev. E

Cited by in corpus (95)

• The structure and function of complex networks
• Multilayer Networks
• The structure and dynamics of multilayer networks
• Critical phenomena in complex networks
• Networks beyond pairwise interactions: structure and dynamics
• Nonequilibrium phase transition in the coevolution of networks and opinions
• The phase transition in inhomogeneous random graphs
• Class of correlated random networks with hidden variables
• Percolation on complex networks: Theory and application
• Self-similarity of complex networks and hidden metric spaces
• Average path length in random networks
• Average path length in uncorrelated random networks with hidden variables
• Generating simple random graphs with prescribed degree distribution
• The entropy of network ensembles
• Maximum likelihood: extracting unbiased information from complex networks
• Conjoining Speeds up Information Diffusion in Overlaying Social-Physical Networks
• Structural Inference of Hierarchies in Networks
• Bayesian stochastic blockmodeling
• Self-organized network evolution coupled to extremal dynamics
• Entropies of complex networks with hierarchically constrained topologies
• Recent advances of percolation theory in complex networks
• Evolution of scale-free random graphs: Potts model formulation
• Topological properties of a time-integrated activity driven network
• Random Graphs with Hidden Color
• The k-core and branching processes
• Properties of Random Graphs with Hidden Color
• Analytic solution of a static scale-free network model
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• Graph Annotations in Modeling Complex Network Topologies
• Emergence of Symmetry in Complex Networks
• The shortest path to complex networks
• Bootstrap percolation in inhomogeneous random graphs
• Analysis of scale-free networks based on a threshold graph with intrinsic vertex weights
• A preferential attachment model with random initial degrees
• Community Detection in Complex Networks Using Density-based Clustering Algorithm
• An extended formalism for preferential attachment in heterogeneous complex networks
• Information-theoretic thresholds for community detection in sparse networks
• Enhancing neural-network performance via assortativity
• Intrinsic degree-correlations in static model of scale-free networks
• Crossovers in ScaleFree Networks on Geographical Space
• Clustering determines the dynamics of complex contagions in multiplex networks
• Inversion method for content-based networks
• Information-theoretic thresholds for community detection in sparse networks
• Turing instability in Reaction-Diffusion models on complex networks
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• Information Propagation in Clustered Multilayer Networks
• Perturbing General Uncorrelated Networks
• Fluctuation-dissipation relations for complex networks
• Networks with given two-point correlations: hidden correlations from degree correlations
• A connection between MAX $\kappa$-CUT and the inhomogeneous Potts spin glass in the large degree limit
• Minimal models of weighted scale-free networks
• Spin models on random graphs with controlled topologies beyond degree constraints
• Variational principle for scale-free network motifs
• Aging and percolation dynamics in a Non-Poissonian temporal network model
• Dynamics in online social networks
• Shortest path discovery of complex networks
• Heider and coevolutionary balance: From discrete to continuous phase transition
• First Passage Percolation on Inhomogeneous Random Graphs
• Large deviation principles for empirical measures of colored random graphs
• Random Simplicial Complexes: Models and Phenomena
• Diffusion on hierarchical systems of weakly-coupled networks
• Dynamic Hidden-Variable Network Models
• Heterogeneity shapes groups growth in social online communities
• Rigorous results on the threshold network model
• On the evolution of random graphs on spaces of negative curvature
• Percolation transition and distribution of connected components in generalized random network ensembles
• Hierarchical and mixing properties of static complex networks emerging from the fluctuating classical random graphs
• Entropy of labeled versus unlabeled networks
• A large-deviations principle for all the components in a sparse inhomogeneous random graph
• Second to first order phase transition; coevolutionary versus structural balance
• Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT
• Robustness of networks against propagating attacks under vaccination strategies
• Measuring Generalized Preferential Attachment in Dynamic Social Networks
• Diffusion of Real-Time Information in Social-Physical Networks
• Clustering Coefficients of Protein-Protein Interaction Networks
• Mutual Information for the Stochastic Block Model by the Adaptive Interpolation Method
• Multicoloured Random Graphs: Constructions and Symmetry
• Strength Distribution in Derivative Networks
• Random Popular Matchings with Incomplete Preference Lists
• Random Networks Tossing Biased Coins
• A novel configuration model for random graphs with given degree sequence
• Phase transition in the controllability of temporal networks
• On the log-normality of the degree distribution in large homogeneous binary multiplicative attribute graph models
• The diameter of Inhomogeneous random graphs
• Phase transition in a power-law uniform hypergraph
• Spectral Properties of the Threshold Network Model
• Node isolation in large homogeneous binary multiplicative attribute graph models
• A Self-organized model for network evolution
• Evolution of a modified binomial random graph by agglomeration
• Statistical properties of a generalized threshold network model
• Neighborhood Structure Configuration Models
• Graph model selection by edge probability sequential inference
• Random Spatial Networks: Small Worlds without Clustering, Traveling Waves, and Hop-and-Spread Disease Dynamics
• Interplay between Network Topology and Dynamics in Neural Systems
• Bootstrap percolation in power-law random graphs