We prove asymptotic equipartition properties for simple hierarchical structures (modelled as multitype Galton-Watson trees) and networked structures (modelled as randomly coloured random graphs). For example, for large n, a networked data structure consisting of n units connected by an average number of links of order n / log n can be coded by about H × n bits, where H is an explicitly defined entropy. The main technique in our proofs are large deviation principles for suitably defined empirical...

We prove asymptotic equipartition properties for simple hierarchical structures (modelled as multitype Galton-Watson trees) and networked structures (modelled as randomly coloured random graphs). For example, for large n, a networked data structure consisting of n units connected by an average number of links of order n / log n can be coded by about H × n bits, where H is an explicitly defined entropy. The main technique in our proofs are large deviation principles for suitably defined empirical...

Motivated by the Watts-Strogatz model for a complex network, we introduce a generalization of the Erdős-Rényi random graph. We derive a combinatorial formula for the moment sequence of its spectral distribution in the sparse limit.

The convergence rate of the expectation of the logarithm of the first return time $R_n$, after being properly normalized, is investigated for ergodic Markov chains. I. Kontoyiannis showed that for any β > 0 we have $log\left[R_n\left(x\right)P_n\left(x\right)\right]=o\left(n^{\beta }\right)$ a.s. for aperiodic cases and A. J. Wyner proved that for any ε >0 we have $-(1+\epsilon )logn\le log\left[R_n\left(x\right)P_n\left(x\right)\right]\le loglogn$ eventually, a.s., where $P_n\left(x\right)$ is the probability of the initial n-block in x. In this paper we prove that $E[log{R}_{(L,S)}-(L-1)h]$ converges to a constant depending only on the process where $R_{(L,S)}$ is the modified first return time with...