社交属性网下基于链路预测及节点度的推荐算法

›› 2019, Vol. 31 ›› Issue (2): 119-129.

社交属性网下基于链路预测及节点度的推荐算法

江若然, 张玲玲

中国科学院大学经济与管理学院, 北京 100190

收稿日期:2017-02-27 出版日期:2019-02-28 发布日期:2019-03-07
通讯作者: 张玲玲,中国科学院大学经济与管学院教授,博士生导师,博士
作者简介:江若然,中国科学院大学经济与管学院硕士研究生,硕士;张玲玲,中国科学院大学经济与管学院教授,博士生导师,博士
基金资助:
国家自然科学基金项目（71471169）

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

Jiang Ruoran, Zhang Lingling

School of Economics and Management, University of Chinese Academy of Sciences, Beijing 100190

Received:2017-02-27 Online:2019-02-28 Published:2019-03-07

摘要/Abstract

摘要：

社交网络的出现使现代人们沟通交流的方式发生了颠覆性的变化。不断有研究者从社会角度和技术角度对社交网络进行研究。链路推荐是一个非常重要的任务，一方面增强网络内部联系，另一方面改善用户体验。目前，在考虑网络结构信息和节点属性信息的社交属性拓展网络模型中链路预测算法中还没有很好的综合利用两种信息对链路生成的影响。本文在基于局部信息的链路预测算法下考虑不同类型共同邻居节点对链路生成的影响，并将其应用于社交属性拓展网络模型中。在改进的算法中，用户共同邻居节点和属性共同邻居节点对链接相关性的影响被给予不同的处理。在Google＋社交数据集的实验表明，在社交属性拓展网络模型下，本文改进算法优于不考虑共同邻居节点影响的算法。在总结实验结果中用户共同邻居节点和属性共同邻居节点对链接生成的不同影响后，对不同类型节点的处理方法提出指导性建议。

关键词: 链路预测, 社交属性网, 节点的度, 推荐系统, 共同邻居

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

江若然, 张玲玲. 社交属性网下基于链路预测及节点度的推荐算法[J]. , 2019, 31(2): 119-129.

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

参考文献

[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