Recommendation Algorithm Based on Link Prediction and Node Degree Using a Social-Attribute Network

Abstract

Abstract:

Social networking platforms disruptively change the way modern people communicate. More and more researches have focused on social networks from the social and technological perspectives. Link recommendation is a very important task. It not only can enhance internal linkage, but also will help improve the user experience. The existing link prediction algorithms in social-attribute network model do not comprehensively utilize the network structure information and attribute node information. This paper proposes several improved algorithms of link prediction based on local information, which combine effects of different types of common neighbors on social-attribute network model. These improved algorithms are given diverse treatment for the different influence from user common neighbor node and attribute common neighbor nodes. The test results in Google+ data set show that improved algorithm outperforms the algorithm, which does not consider the influence of common neighbor nodes on social-attribute model. After summarizing the different effects of diverse common neighbor nodes on link prediction, this paper provides corresponding suggestions on processing of different types of nodes.

Key words: link prediction, social attribute networks, node degrees, recommendation system, common neighbors

Jiang Ruoran, Zhang Lingling. Recommendation Algorithm Based on Link Prediction and Node Degree Using a Social-Attribute Network[J]. , 2019, 31(2): 119-129.

References

[1] 吕琳媛,周涛. 链路预测[M]. 北京:高等教育出版社, 2013.
[2] Liben-Nowell D., Kleinberg J. The Link-Prediction Problem for Social Networks[J]. Journal of the American Society for Information Science and Technology, 2007,58(7):1019-1031.
[3] Lü L., Zhou T. Link Prediction in Complex Networks:A Survey[J]. Physica A:Statistical Mechanics and Its Applications, 2011,390(6):1150-1170.
[4] 吕琳媛. 复杂网络链路预测[J]. 电子科技大学学报, 2010,39(5):651-661.
[5] Zheleva E., Getoor L. To Join or Not to Join:The Illusion of Privacy in Social Networks with Mixed Public and Private User Profiles[C]. Proceedings of the 18th International Conference on World Wide Web ACM, 2009.
[6] Gong N. Z., Talwalkar A., Mackey L., et al. Jointly Predicting Links and Inferring Attributes Using a Social-Attribute Network (san)[EB/OL]. https://arxiv.org/pdf/1112.3265.pdf, 2011.
[7] Melville P., Sindhwani V. Recommender System in Encyclopedia of Machine Learning[M]. Boston:Springer, 2011.
[8] Bartunov S., Korshunov A., Park S. T., et al. Joint Link-Attribute User Identity Resolution in Online Social Networks[C]. Proceedings of the 6th International Conference on Knowledge Discovery and Data Mining, Workshop on Social Network Mining and Analysis ACM, 2012.
[9] La Fond T., Neville J. Randomization Tests for Distinguishing Social Influence and Homophily Effects[C]. Proceedings of the 19th International Conference on World Wide Web ACM, 2010.
[10] Kumar R., Novak J., Raghavan P., et al. Structure and Evolution of Blogspace[J]. Communications of the ACM, 2004,47(12):35-39.
[11] Backstrom L., Leskovec J. Supervised Random Walks:Predicting and Recommending Links in Social Networks[C]. Proceedings of the Fourth ACM International Conference on Web Search and Data Mining ACM, 2011.
[12] Yin Z., Gupta M., Weninger T., et al. LINKREC:A Unified Framework for Link Recommendation with User Attributes and Graph Structure[C]. Proceedings of the 19th International Conference on World Wide Web ACM, 2010.
[13] Yin Z., Gupta M., Weninger T., et al. A Unified Framework for Link Recommendation Using Random Walks[C]. Advances in Social Networks Analysis and Mining (ASONAM), 2010 International Conference on IEEE, 2010.
[14] Gong N. Z., Talwalkar A., Mackey L., et al. Joint Link Prediction and Attribute Inference Using a Social-Attribute Network[J]. ACM Transactions on Intelligent Systems & Technology, 2014,5(2):1-20.
[15] Candan K. S., Li W. S. Using Random Walks for Mining Web Document Associations[C]. Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer Berlin Heidelberg, 2000.
[16] Fercoq O. PageRank Optimization Applied to Spam Detection[C]. Network Games, Control and Optimization (NetGCooP), 2012 6th International Conference on IEEE, 2012.
[17] Tang J., Zhang J., Yao L., et al. Extraction and Mining of an Academic Social Network[C]. Proceedings of the 17th International Conference on World Wide Web ACM, 2008.
[18] Hu K., Xiang J., Yang W., et al. Link Prediction in Complex Networks by Multi Degree Preferential-Attachment Indices[EB/OL]. https://arxiv.org/ftp/arxiv/papers/1211/1211.1790.pdf, 2012.
[19] Adamic L. A., Adar E. Friends and Neighbors on the Web[J]. Social Networks, 2003,25(3):211-230.
[20] Zhou T., Lü L., Zhang Y. C. Predicting Missing Links via Local Information[J]. The European Physical Journal B, 2009,71(4):623-630.
[21] Martínez V., Berzal F., Cubero J. C. Adaptive Degree Penalization for Link Prediction[J]. Journal of Computational Science, 2016,13(1):1-9.
[22] Kim J. H., Candan K. S., Sapino M. L. PageRank Revisited:On the Relationship between Node Degrees and Node Significances in Different Applications[C]. Proceedings of the EDBT/ICDT 2016 Joint Conference, 2016.
[23] Salton G., McGill M. J. Introduction to Modern Information Retrieval[M]. Auckland:MuGraw-Hill, 1986.
[24] Lewis T. G. Network Science:Theory and Applications[M].New Jersey:John Wiley & Sons, 2011.
[25] Gong N. Z., Xu W., Huang L., et al. Evolution of Social-Attribute Networks:Measurements, Modeling, and Implications Using Google+[C]. Proceedings of the 2012 ACM Conference on Internet Measurement Conference ACM, 2012.
[26] Hanley J. A., McNeil B. J. The Meaning and Use of the Area under a Receiver Operating Characteristic (ROC) Curve[J]. Radiology, 1982,143(1):29-36.
[27] Clauset A., Moore C., Newman M. E. J. Hierarchical Structure and the Prediction of Missing Links in Networks[J]. Nature, 2008,453(7191):98-101.
[28] Fawcett T. An Introduction to ROC Analysis[J]. Pattern Recognition Letters, 2006,27(8):861-874