Skip to main content
eScholarship
Open Access Publications from the University of California

Random graphs with attribute affinity

  • Author(s): Radcliffe, Mary L.
  • et al.
Abstract

In this thesis, we study problems related to random graphs generated via attribute affinity. A random graph with attribute affinity is a graph for which we associate to each vertex an attribute vector from an alphabet [Gamma], and generate edges randomly, where the probability of an edge is determined by comparing the attributes of the associated vectors. In particular, we shall do the following : 1. For general random graphs in which the probability that v/i ̃ v/j is p/i, we develop a technique for obtaining concentration of both the adjacency and normalized Laplacian eigenvalues. This technique can be used to asymptotically establish the spectra of a stochastic Kronecker graph, an affinity graph with vertex set fixed at [Gamma]/t. 2. We then generalize these results to a multiplicative attribute graph, an attribute affinity model in which the vertex set is chosen randomly from [Gamma]/t. Specifically, we can determine asymptotically the normalized Laplacian eigenvalues in this regime. This allows us to determine asymptotic bounds on the diameter of the graph, which was shown to be asymptotically constant by Kim and Leskovec. 3. We establish a necessary and sufficient condition for the emergence of a giant component of a stochastic Kronecker graph with [Gamma] = {0, 1}. Moreover, the proof is adapted to establish the uniqueness and asymptotic size of such a component. This extends previous work of Mahdian and Xu, in which necessary and sufficient conditions were established in certain cases. 4. Using techniques similar to those for the spectrum, we can determine the uniqueness and asymptotic size of a giant component in a multiplicative attribute graph, when it exists. Conditions on the emergence of the component were established by Kim and Leskovec

Main Content
Current View