dc.contributor.author 
Nickel, Christine Leigh Myers 

dc.date.accessioned 
20080201T20:35:05Z 

dc.date.available 
20080201T20:35:05Z 

dc.date.issued 
20080201T20:35:05Z 

dc.identifier.other 
etdplt095 

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
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<v
f(xu ¢ xv)¸·Quv =2E(H)
u<v
(1 ¡ f(xu ¢ xv))¸ and is dependent upon
the distribution from which the vectors are drawn.
We examine three versions of the Random Dot Product Graph on n vertices. In the
dense model, the vectors are drawn from Ua[0; 1], the ath power (a > 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. 
en 
dc.description.provenance 
Submitted by Mark Cyzyk (mcyzyk@jhu.edu) on 20080201T20:34:49Z
No. of bitstreams: 1
CLMNthesis.pdf: 2285921 bytes, checksum: fe6a4c2390566f0d41b24211b2009033 (MD5) 
en 
dc.description.provenance 
Approved for entry into archive by Mark Cyzyk(mcyzyk@jhu.edu) on 20080201T20:35:05Z (GMT) No. of bitstreams: 1
CLMNthesis.pdf: 2285921 bytes, checksum: fe6a4c2390566f0d41b24211b2009033 (MD5) 
en 
dc.description.provenance 
Made available in DSpace on 20080201T20:35:05Z (GMT). No. of bitstreams: 1
CLMNthesis.pdf: 2285921 bytes, checksum: fe6a4c2390566f0d41b24211b2009033 (MD5) 
en 
dc.language.iso 
en_US 
en 
dc.title 
RANDOM DOT PRODUCT GRAPHS A MODEL FOR SOCIAL NETWORKS 
en 
dc.type 
Thesis 
en 