dc.contributor.author Nickel, Christine Leigh Myers dc.date.accessioned 2008-02-01T20:35:05Z dc.date.available 2008-02-01T20:35:05Z dc.date.issued 2008-02-01T20:35:05Z dc.identifier.other etd-plt-095 dc.identifier.uri http://jhir.library.jhu.edu/handle/1774.2/32525 dc.description.abstract We develop a new set of random graph models. The motivation for these mod- en_US els comes from social networks and is based on the idea of common interest. We represent a social network as a graph, in which vertices correspond to individu- als. In the general model, an interest vector xv, drawn from a speci¯c distribu- tion, is associated with corresponding vertex v. The edge between vertices u and v exists with some probability P(xi; xj) = f(xu ¢ xv); that is, it is equal to a func- tion of the dot product of the vectors. The probability of a graph H is given by PX[H] = ·Quv2E(H) u 1) of the uniform distribution on [0; 1], and f is the identity function. In this case, with probability approaching one as n approaches in¯nity, all ¯xed graphs appear as subgraphs. In the sparse model, the vectors are again drawn from Ua[0; 1], however the probability function is f(s) = s nb (b 2 (0;1)). With this change, subgraphs appear at certain thresholds and we examine the sequence of their appearance. In both cases, we show that the models obey a power law degree distribution, exhibit clustering, and have a low diameter; these are all characteristics found in social networks. The third version is a discrete model. Here the vectors are drawn from f0; 1gt (t 2 Z+)) and f(s) = s t . Each coordinate of xv is independently assigned the value 1 with probability p and 0 otherwise (p 2 [0; 1]). We de¯ne the probability order polyno- mial, or POP, of a graph H as a function that is asymptotic to P¸[H], the probability of H appearing as a (not necessarily induced) subgraph, and present geometric tech- niques for studying POP asymptotics. We give a general method for calculating the POP of H. We present formuals for the POPs and ¯rst moment results for trees, cycles, and complete graphs. We also prove a threshold result for K3 and describe a general method for proving threshold results when all the required POPs are known. dc.language.iso en_US en_US dc.title RANDOM DOT PRODUCT GRAPHS A MODEL FOR SOCIAL NETWORKS en_US dc.type Thesis en_US
﻿