The two-star model: exact solution in the sparse regime and condensation transition

DOI10.1088/1751-8113/48/36/365001MaRDI QIDQ3448406zbMATH OpenOpenAlexFDO

Authors A. Annibale, O. T. Courtney

Publication date 23 October 2015

Published in Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.06458

zbMATH Keywords

complex networkscondensationlarge deviation

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Large deviations (60F10) Phase transitions (general) in equilibrium statistical mechanics (82B26)

Abstract: The $2$-star model is the simplest exponential random graph model that displays complex behavior, such as degeneracy and phase transition. Despite its importance, this model has been solved only in the regime of dense connectivity. In this work we solve the model in the finite connectivity regime, far more prevalent in real world networks. We show that the model undergoes a condensation transition from a liquid to a condensate phase along the critical line corresponding, in the ensemble parameters space, to the Erd"os-R'enyi graphs. In the fluid phase the model can produce graphs with a narrow degree statistics, ranging from regular to Erd"os-R'enyi graphs, while in the condensed phase, the "excess" degree heterogeneity condenses on a single site with degree $simsqrtN$. This shows the unsuitability of the two-star model, in its standard definition, to produce arbitrary finitely connected graphs with degree heterogeneity higher than Erd"os-R'enyi graphs and suggests that non-pathological variants of this model may be attained by softening the global constraint on the two-stars, while keeping the number of links hardly constrained.

Recommendations

• Critical phenomena in exponential random graphs
• Asymptotic structure of constrained exponential random graph models
• Phase transitions in the edge/concurrent vertex model
• The condensation phase transition in random graph coloring
• On the asymptotics of constrained exponential random graphs

Cited in

(9)

• An exactly solvable model for the dynamics of two spin-\frac{1}{2} particles embedded in separate spin star environments
• Resistance distance distribution in large sparse random graphs
• scientific article; zbMATH DE number 7639719 (Why is no real title available?)
• The birth of geometry in exponential random graphs
• Random matrices with row constraints and eigenvalue distributions of graph Laplacians
• A Gaussian integral that counts regular graphs
• First return times on sparse random graphs
• Hammerstein equations for sparse random matrices
• Statistical field theory of random graphs with prescribed degrees

This page was built for publication: The two-star model: exact solution in the sparse regime and condensation transition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3448406)