The spectra of multiplicative attribute graphs

A multiplicative attribute graph is a random graph in which vertices are represented by random words of length t in a finite alphabet Γ, and the probability of adjacency is a symmetric function Γt×Γt→[0,1]. These graphs are a generalization of stochastic Kronecker graphs, and both classes have been shown to exhibit several useful real world properties. We establish asymptotic bounds on the spectra of the adjacency matrix and the normalized Laplacian matrix for these two families of graphs under certain mild conditions. As an application we examine various properties of the stochastic Kronecker graph and the multiplicative attribute graph, including the diameter, clustering coefficient, chromatic number, and bounds on low-congestion routing.