Preferential Attachment in Graphs with Affinities

Jay Lee, Manzil Zaheer, Stephan Günnemann, Alex Smola
Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, PMLR 38:571-580, 2015.

Abstract

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 flexibility to take vertex to vertex affinities 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 affinity and on reflecting properties of different 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 satisfies the small world property. Experiments show that our model provides an excellent fit of many natural graph statistics and we provide an algorithm to infer the associated affinity function efficiently.

Cite this Paper

BibTeX
@InProceedings{pmlr-v38-lee15b, title = {{Preferential Attachment in Graphs with Affinities}}, author = {Lee, Jay and Zaheer, Manzil and Günnemann, Stephan and Smola, Alex}, booktitle = {Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics}, pages = {571--580}, year = {2015}, editor = {Lebanon, Guy and Vishwanathan, S. V. N.}, volume = {38}, series = {Proceedings of Machine Learning Research}, address = {San Diego, California, USA}, month = {09--12 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v38/lee15b.pdf}, url = {https://proceedings.mlr.press/v38/lee15b.html}, abstract = {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 flexibility to take vertex to vertex affinities 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 affinity and on reflecting properties of different 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 satisfies the small world property. Experiments show that our model provides an excellent fit of many natural graph statistics and we provide an algorithm to infer the associated affinity function efficiently.} }
Endnote
%0 Conference Paper %T Preferential Attachment in Graphs with Affinities %A Jay Lee %A Manzil Zaheer %A Stephan Günnemann %A Alex Smola %B Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2015 %E Guy Lebanon %E S. V. N. Vishwanathan %F pmlr-v38-lee15b %I PMLR %P 571--580 %U https://proceedings.mlr.press/v38/lee15b.html %V 38 %X 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 flexibility to take vertex to vertex affinities 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 affinity and on reflecting properties of different 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 satisfies the small world property. Experiments show that our model provides an excellent fit of many natural graph statistics and we provide an algorithm to infer the associated affinity function efficiently.
RIS
TY - CPAPER TI - Preferential Attachment in Graphs with Affinities AU - Jay Lee AU - Manzil Zaheer AU - Stephan Günnemann AU - Alex Smola BT - Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics DA - 2015/02/21 ED - Guy Lebanon ED - S. V. N. Vishwanathan ID - pmlr-v38-lee15b PB - PMLR DP - Proceedings of Machine Learning Research VL - 38 SP - 571 EP - 580 L1 - http://proceedings.mlr.press/v38/lee15b.pdf UR - https://proceedings.mlr.press/v38/lee15b.html AB - 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 flexibility to take vertex to vertex affinities 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 affinity and on reflecting properties of different 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 satisfies the small world property. Experiments show that our model provides an excellent fit of many natural graph statistics and we provide an algorithm to infer the associated affinity function efficiently. ER -
APA
Lee, J., Zaheer, M., Günnemann, S. & Smola, A.. (2015). Preferential Attachment in Graphs with Affinities. Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 38:571-580 Available from https://proceedings.mlr.press/v38/lee15b.html.

Related Material