Local Large Deviations: A McMillian Theorem for Typed Random Graph Processes

Abstract

For a finite typed graph on n nodes and with type law µ on finite alphabet Γ, we define the spectral potential ρ_λ(., µ), of the graph. From the ρ_λ(., µ) we define the Kullback action or the divergence function, H_λ(π || v), with respect to an empirical link measure, π, as the Legendre dual. For the finite typed random graph conditioned to have an empirical link measure π and empirical type measure µ, we prove a Local large Deviation Principle (LLDP), with rate function H_λ(π || v) and speed n. From this LLDP, we obtain a full conditional large deviation principle and a weak variant of the classical McMillian Theorem for the typed random graph models. Given the typical empirical link measure, λ_µ⊗µ, we show that, the number of typed random graphs is equal to eⁿ||^λ_µ⊗µ||H(λ_µ⊗µ⁄||λ_µ⊗µ||) approximately. Note that we do not require any topological restrictions on the space of finite graphs for these LLDPs.