RANDOM DOT PRODUCT GRAPHS A MODEL FOR SOCIAL NETWORKS
Embargo until
Date
2008-02-01T20:35:05Z
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Johns Hopkins University
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.