Dissertation/Thesis Abstract

Random Graphs with Attribute Affinity
by Radcliffe, Mary L., Ph.D., University of California, San Diego, 2012, 91; 3511135
Abstract (Summary)

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 Γ, 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 ivj is pij, 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 Γ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 Γ 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 Γ = {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

Indexing (document details)
Advisor: Graham, Fan RK Chung
Commitee: Dasgupta, Sanjoy, Graham, Ron, Kemp, Todd, Verstraete, Jacques
School: University of California, San Diego
Department: Mathematics
School Location: United States -- California
Source: DAI-B 73/10(E), Dissertation Abstracts International
Subjects: Applied Mathematics, Mathematics
Keywords: Attribute affinity, Diameter, Giant components, Laplacian, Random graphs, Random matrices, Spectrum
Publication Number: 3511135
ISBN: 9781267384492
Copyright © 2019 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy