Preferential attachment models for random graphs are successful in capturing many characteristics of real networks such as power law behavior. At the same time they lack exibility to take vertex to vertex anities into account, a feature that is commonly used in many link recommendation algorithms. We propose a random graph model based on both node attributes and preferential attachment. This approach overcomes the limitation of existing models on expressing vertex anity and on reecting properties of dierent subgraphs. We analytically prove that our model preserves the power law behavior in the degree distribution as expressed by natural graphs and we show that it satises the small world property. Experiments show that our model provides an excellent t of many natural graph statistics and we provide an algorithm to infer the associated anity function eciently.
['Jay Lee', 'Manzil Zaheer', 'Stephan Günnemann', 'Alexander J. Smola']
Preferential Attachment in Graphs with Affinities