Revisiting Preferential Attachment with applications to Twitter

Abstract. A hundred million users login daily on Twitter, that makes of this social network one of the ten most visited websites and the third largest social media by web referral. It has thus attracted recent interest. In this work, we propose a new model of random directed graphs as a way to better analyze Twitter and to make easier simulations of algorithms on it. Although it has long been proposed similar models for undirected social networks such as, e.g., Facebook – that are collectively referred by “preferential attachment” models – extending this approach to Twitter remained to be done. Indeed, the few existing random models for directed graphs do not match important properties of Twitter such as: a high proportion of bidirectional edges, and positive correlation between these edges and the out-degree distribution. In this paper, we briefly report on these models and show their limitations through experiments on the Twitter graph. Then, we introduce our random model that better accounts for the characteristics of Twitter, and we formally analyze the degree distribution of the digraphs generated, that is shown to be power-law. The key instrument in our proof will be a generic framework in order to compute, somewhat automatically, the first order of the outcome distribution for a large class of random processes that capture and generalize preferential attachment processes. In particular, all these processes are proved to be stationary up to a rescaling, that allows us to reduce the problem of determining the degree distribution to the much simpler computation of a fixed point. This general approach not only applies to our model, but also to more classical “preferential attachment” models, so, we expect our framework to find more applications in the field of random networks.

This is joint work with Frederic Giroire, Stephane Perennes and Stefano Ponziani.