Abstract
In this paper we derive a network formation model for social network. First, we create a fully-connected network with m0 vertices. At each time step, a new vertex is added into the network, and randomly selects one existing vertex to establish an edge with equal probability. Then, each neighbors of attached vertex forms an edge with the new vertex with probability a. We call this operation triadic attachment. We derive the mean degree and the clustering coefficient for this model. We also analyze the stationary mean degree and the stationary clustering coefficient. Furthermore, we extend this model by adding edges to pairs of existing vertices. We derive the mean degree and the clustering coefficient for this extended model. Finally we show that the parameters of our model can be chosen such that the mean degree and the clustering coefficient match very well those of popular online social networks such as Facebook, Flickr and Orkut.