RANDOM DOT PRODUCT GRAPHS A MODEL FOR SOCIAL NETWORKS
Nickel, Christine Leigh Myers
MetadataShow full item record
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.