信任社交网络中基于图熵的个性化推荐算法

doi:10.11772/j.issn.1001-9081.2018061202

计算机应用 ›› 2019, Vol. 39 ›› Issue (1): 176-180.DOI: 10.11772/j.issn.1001-9081.2018061202

信任社交网络中基于图熵的个性化推荐算法

蔡永嘉, 李冠宇, 关皓元

大连海事大学信息科学技术学院, 辽宁大连 116026

收稿日期:2018-06-12 修回日期:2018-07-20 出版日期:2019-01-10 发布日期:2019-01-21
通讯作者: 李冠宇
作者简介:蔡永嘉(1995-),男,江西乐平人,硕士研究生,CCF会员,主要研究方向:智能信息处理、个性化推荐;李冠宇(1963-),男,辽宁大连人,教授,博士生导师,博士,CCF会员,主要研究方向:语义物联网、智能信息处理;关皓元(1994-),男,辽宁沈阳人,硕士研究生,CCF会员,主要研究方向:智能信息处理。
基金资助:
国家自然科学基金面上项目（61371090）。

Personalized recommendation algorithm based on graph entropy in trust social network

CAI Yongjia, LI Guanyu, GUAN Haoyuan

College of Information Science and Technology, Dalian Maritime University, Dalian Liaoning 116026, China

Received:2018-06-12 Revised:2018-07-20 Online:2019-01-10 Published:2019-01-21
Supported by:
This work is partially supported by the Surface Program of National Natural Science Foundation of China (61371090).

摘要/Abstract

摘要： 随着社交网络的飞速发展引起了人们对推荐系统（RS）的广泛关注。针对社交网络中现有推荐方法仍存在冷启动问题以及未考虑用户所处的社交网络信息的情况，提出了在信任社交网络中基于图熵的个性化推荐算法（PRAGE）。首先，根据用户物品和它们之间的反馈信息建立用户物品图（UIG），同时引入信任机制建立用户信任图（UTG）；其次，通过对两个图使用随机游走算法得到用户与物品的初始相似度和基于信任机制的新的用户物品相似度；重复随机游走过程直至相似度稳定到收敛值；然后，使用UIG和UTG的图熵对两组相似度进行加权并最终相应地得出目标用户的最终推荐列表。在真实的数据集Epinions和FilmTrust上的实验结果表明，相比经典的基于随机游走算法，PRAGE的精确率分别提高了34.7%和19.4%，召回率分别提高了28.9%和21.1%，能够有效地缓解推荐的冷启动问题且在精确率和覆盖率指标上均优于对比算法。

关键词: 社交网络, 信任机制, 随机游走, 图熵, 推荐算法

Abstract: Widespread attentions have been drawn to Recommendation Systems (RS) as rapid development of social networks. To solve the cold-start problem and neglect to user's social network information in current recommendation algorithms, a novel Personalized Recommend Algorithm based on Graph Entropy (PRAGE) in trust social network was proposed. Firstly, a weighted User-Item Graph (UIG) was built based on feedback information, and a trust mechanism was introduced to establish a User Trust Graph (UTG). Secondly, by using random walk algorithm on two graphs, the initial similarity of user and item and new user-item similarity based on trust mechanism were obtained; the above algorithm process was repeated until the similarity value reaches convergence value. Then, a method to weight two sets of similarity values with graph entropies of both UIG and UTG was proposed and final recommendation list was accordingly created. The experimental results on two real-world datasets named as Epinions and FilmTrust reveal that, compared with classical Random Walk algorithm, the accuracy of PRAGE is increased by about 34.7%and 19.4% respectively, and its recall is increased by 28.9% and 21.1% respectively, which can alleviate cold start problem effectively and has better performance in accuracy and coverage.

Key words: social network, trust mechanism, random walk, graph entropy, recommendation algorithm

中图分类号:

TP301.6
TP18

蔡永嘉, 李冠宇, 关皓元. 信任社交网络中基于图熵的个性化推荐算法[J]. 计算机应用, 2019, 39(1): 176-180.

CAI Yongjia, LI Guanyu, GUAN Haoyuan. Personalized recommendation algorithm based on graph entropy in trust social network[J]. Journal of Computer Applications, 2019, 39(1): 176-180.

参考文献

[1] LV L, MEDO M, YEUNG C H, et al. Recommender systems[J]. Physics Reports, 2012, 519(1):1-49.
[2] JAIN A, LIU X, YU Q. Aggregating functionality, use history, and popularity of APIs to recommend mashup creation[C]//Proceedings of the 2015 International Conference on Service-Oriented Computing. Berlin:Springer, 2015:188-202.
[3] PERWEZ S K, ZUBAIR H M, GHALIB M R, et al. Association rule mining technique for psychometric personality testing and behaviour prediction[J]. International Journal of Engineering & Technology, 2013, 5(5):4349-4361.
[4] HAO F, LI S, MIN G, et al. An efficient approach to generating location-sensitive recommendations in Ad-Hoc social network environments[J]. IEEE Transactions on Services Computing, 2015, 8(3):520-533.
[5] AHMADIAN S, MEGHDADI M, AFSHARCHI M. A social recommendation method based on an adaptive neighbor selection mechanism[J]. Information Processing & Management, 2018, 54(4):707-725.
[6] 曾春,邢春晓,周立柱.基于内容过滤的个性化搜索算法[J].软件学报,2003,14(5):999-1004.(ZENG C, XING C X, ZHOU L Z. A personalized search algorithm by using content-based filtering[J]. Journal of Software, 2003, 14(5):999-1004.)
[7] PESSEMIER T D. Collaborative recommendations with content-based filters for cultural activities via a scalable event distribution platform[J]. Multimedia Tools & Applications, 2012, 58(1):167-213.
[8] 黄创光,印鉴,汪静,等.不确定近邻的协同过滤推荐算法[J].计算机学报,2010,33(8):1369-1377.(HUANG C G, YING J, WANG J, et al. Uncertain neighbors' collaborative filtering recommendation algorithm[J]. Chinese Journal of Computers, 2010, 33(8):1369-1377.)
[9] BOJNORDI E, MORADI P. A novel collaborative filtering model based on combination of correlation method with matrix completion technique[C]//Proceedings of the 2012 CSI International Symposium on Artificial Intelligence and Signal Processing. Piscataway, NJ:IEEE, 2012:191-194.
[10] GORI M, PUCCI A. ItemRank:a random-walk based scoring algorithm for recommender engines[C]//Proceedings of the 2007 International Joint Conference on Artificial Intelligence. San Francisco:Morgan Kaufmann, 2007:2766-2771.
[11] HAVELIWALA T H. Topic-sensitive PageRank:a context-sensitive ranking algorithm for Web search[J]. IEEE Transactions on Knowledge & Data Engineering, 2003, 15(4):784-796.
[12] PARK H, JUNG J, KANG U. A comparative study of matrix factorization and random walk with restart in recommender systems[J]. ArXiv Preprint, 2017, 2017:1708.09088.
[13] LI C, XIONG F. Social recommendation with multiple influence from direct user interactions[J]. IEEE Access, 2017, 5:16288-16296.
[14] LIU F, HONG J L. Use of social network information to enhance collaborative filtering performance[J]. Expert Systems with Applications, 2010, 37(7):4772-4778.
[15] EIRINAKI M, LOUTA M D, VARLAMIS I. A trust-aware system for personalized user recommendations in social networks[J]. IEEE Transactions on Systems, Man & Cybernetics Systems, 2014, 44(4):409-421.
[16] MORADI P, AHMADIAN S, AKHLAGHIAN F. An effective trust-based recommendation method using a novel graph clustering algorithm[J]. Physica A:Statistical Mechanics & Its Applications, 2015, 436:462-481.
[17] MASSA P, AVESANI P. Trust-aware recommender systems[C]//Proceedings of the 2007 ACM Conference on Recommender Systems. New York:ACM, 2007:17-24.
[18] YUAN W, GUAN D, LEE Y K, et al. Improved trust-aware recommender system using small-worldness of trust networks[J]. Knowledge-Based Systems, 2010, 23(3):232-238.
[19] DEHMER M. Information processing in complex networks:graph entropy and information functionals[J]. Applied Mathematics & Computation, 2008, 201(1/2):82-94.
[20] EAGLE N, MACY M, CLAXTON R. Network diversity and economic development[J]. Science, 2010, 328(5981):1029-1031.
[21] HERLOCKER J L, KONSTAN J A, TERVEEN L G, et al. Evaluating collaborative filtering recommender systems[J]. ACM Transactions on Information Systems, 2004, 22(1):5-53.
[22] DAVIS J, GOADRICH M. The relationship between precision-recall and ROC curves[C]//ICML '06:Proceedings of the 2006 International Conference on Machine Learning. New York:ACM, 2006:233-240.

信任社交网络中基于图熵的个性化推荐算法

Personalized recommendation algorithm based on graph entropy in trust social network

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	汤安迪, 韩统, 徐登武, 谢磊. 混沌精英哈里斯鹰优化算法[J]. 计算机应用, 2021, 41(8): 2265-2272.
[2]	张萌, 李维华. 用户互动表示下的影响力最大化算法[J]. 计算机应用, 2021, 41(7): 1964-1969.
[3]	余敦辉, 张蕗怡, 张笑笑, 毛亮. 基于知识图谱和重启随机游走的跨平台用户推荐方法[J]. 计算机应用, 2021, 41(7): 1871-1877.
[4]	杨丽, 王时绘, 朱博. 基于动态和静态偏好的兴趣点推荐算法[J]. 计算机应用, 2021, 41(2): 398-406.
[5]	孙鹤立, 徐统, 何亮, 贾晓琳. 融合用户历史行为与社交关系的个性化社交事件推荐方法[J]. 计算机应用, 2021, 41(2): 324-329.
[6]	赵旭剑, 王崇伟. 基于图卷积网络的微博新闻故事线抽取方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3139-3144.
[7]	朱思淼, 魏世伟, 魏思恒, 余敦辉. 基于弹幕情感分析和主题模型的视频推荐算法[J]. 计算机应用, 2021, 41(10): 2813-2819.
[8]	李翔锟, 贾彩燕. 融合重叠社区正则化及隐式反馈的协同过滤方法[J]. 计算机应用, 2021, 41(1): 53-59.
[9]	王韫烨, 程亚歌, 贾志娟, 付俊俊, 杨艳艳, 何宇矗, 马威. 基于安全多方的区块链可审计签名方案[J]. 计算机应用, 2020, 40(9): 2639-2645.
[10]	盛俊, 李斌, 陈崚. 基于模块度和标签传递的推荐算法[J]. 计算机应用, 2020, 40(9): 2606-2612.
[11]	李春英, 汤庸, 肖政宏, 李天送. 学术社交网络中的权威学者推荐模型[J]. 计算机应用, 2020, 40(9): 2594-2599.
[12]	田保军, 刘爽, 房建东. 融合主题信息和卷积神经网络的混合推荐算法[J]. 计算机应用, 2020, 40(7): 1901-1907.
[13]	杨书新, 梁文, 朱凯丽. 社交网络中对立影响最大化算法[J]. 计算机应用, 2020, 40(7): 1944-1949.
[14]	易东义, 邓根强, 董超雄, 祝苗苗, 吕周平, 朱岁松. 基于图卷积神经网络的医保欺诈检测算法[J]. 计算机应用, 2020, 40(5): 1272-1277.
[15]	杜旭升, 于炯, 叶乐乐, 陈嘉颖. 基于图上随机游走的离群点检测算法[J]. 计算机应用, 2020, 40(5): 1322-1328.