计算机科学 ›› 2017, Vol. 44 ›› Issue (6): 232-236.doi: 10.11896/j.issn.1002-137X.2017.06.039

• 人工智能 • 上一篇    下一篇

基于FP-Growth的图上随机游走推荐方法

卞梦阳,杨青,张敬伟,张会兵,钱俊彦   

  1. 桂林电子科技大学广西自动检测技术与仪器重点实验室 桂林541004,桂林电子科技大学广西自动检测技术与仪器重点实验室 桂林541004;桂林电子科技大学广西智能综合自动化高校重点实验室 桂林541004,桂林电子科技大学广西可信软件重点实验室 桂林541004,桂林电子科技大学广西可信软件重点实验室 桂林541004,桂林电子科技大学广西可信软件重点实验室 桂林541004
  • 出版日期:2018-11-13 发布日期:2018-11-13
  • 基金资助:
    本文受国家自然科学基金项目(U1501252,7,61363005),广西自然科学基金项目(2014GXNSFAA118353,4GXNSFAA118390,4GXNSFDA118036),广西自动检测技术与仪器重点实验室基金项目(YQ15110),广西高等学校高水平创新团队及卓越学者计划资助

Recommendation Method Based on Random Walk on Graph Integrated with FP-Growth

BIAN Meng-yang, YANG Qing, ZHANG Jing-wei, ZHANG Hui-bing and QIAN Jun-yan   

  • Online:2018-11-13 Published:2018-11-13

摘要: 推荐是促进诸如社交网络等应用活跃度的重要模式,但 庞大 的节点规模以及复杂的节点间关系给社交网络的推荐问题带来了挑战。随机游走是一种能够有效解决这类推荐问题的策略,但传统的随机游走算法没有充分考虑相邻节点间影响力的差异。提出一种基于FP-Growth的图上随机游走推荐方法,其基于社交网络的图结构,引入FP-Growth算法来挖掘相邻节点之间的频繁度,在此基础上构造转移概率矩阵来进行随机游走计算,最后得到好友重要程度排名并做出推荐。该方法既保留了随机游走方法能有效缓解数据稀疏性等特性,又权衡了不同节点连接关系的差异性。实验结果表明,提出的方法比传统随机游走算法的推荐性能更佳。

关键词: 社交网络,好友推荐,频繁项挖掘,随机游走

Abstract: Recommendation is one kind of important strategy to promote the active degree of different social networks.However,it is a big challenge to improve the recommendation performance on social networks for the large scale of nodes as well as the complex relationship.Random walk is an effective method to solve such kind of problem,but the traditional random walk algorithm fails to consider the influence of the neighboring nodes adequately.A recommendation method based on random walk on the graph integrated with FP-Growth was proposed,which is based on the graph structure of the social networks.It introduces the FP-Growth algorithm to mine the frequent degree between the adjacent nodes,and then constructs transition probability matrix for random walk computing.Recommendations will be made according to the importance rank of friends.This method not only retains the characteristics of random walk method,such as alleviating the data sparsity effectively,but also weighs the difference of the relationship between diffe-rent nodes.The experimental results show that the proposed method is superior to the traditional random walk algorithm in the recommendation performance.

Key words: Social networks,Friends recommendation,Frequent item mining,Random walk

[1] WANG Z Q,TAN Y W,ZHANG M.Graph-based Recommendation on Social Networks[C]∥Proceedings of the 12th International Asia-Pacific Web Conference(APWEB).Busan,2010:116-122.
[2] LI J,MA S C,HONG S.Recommendation on Social NetworkBased on Graph Model[C]∥Proceedings of the 31st Chinese Control Conference.Hefei,China,2012:25-27.
[3] PAGE L,BRIN S,MOTWANI R,et al.The PageRank citation ranking:Bringing order to the Web[C]∥Proceedings of the 7th International World Wide Web Conference.Brisbane,Australia,1998:161-172.
[4] CARMEL D,ZWERDLING N,GUY I,et al.Personalized social search based on the user’s social network[C]∥Proceedings of the 18th ACM Conference on Information and Knowledge Anagement.ACM,2009:1227-1236.
[5] HAVELIWALA T,KAMVAR S,JEH G.An analytical com-parison of approaches to personalizing PageRank:Technical Report 2003-35[R].Stanford InfoLab,2003.
[6] LIU W,Lü L.Link prediction based on local ran-dom walk[J].Europhysics Letters,2010,89(5):58007:1-6.
[7] KONSTAS I,STATHOPOULOS V,JOSE J M.On Social Networks and Collaborative Recommendation[C]∥Proceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval.USA:ACM,2009:195-202.
[8] TRAN G,TURK A,CAMBAZOGLU B B,et al.A RandomWalk Model for Optimization of Search Impact in Web Frontier Ranking[C]∥Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval.New York,USA,2015:153-162.
[9] LE T,ZHANG D.DBLPminer:A Tool for Exploring Biblio-graphic Data[C]∥2015 IEEE International Conference on Year Information Reuse and Integration (IRI).2015:435-442.
[10] MU J K.Application of Apriori Algorithm to Customer Analysis[J].Information Technology Journal,2013,12(21):6497-6501.
[11] HAN J W,PEI J,YIN Y W,et al.Mining Frequent Patternswithout Candidate Generation:A Frequent-Pattern Tree Approach[J].Data Mining and Knowledge Discovery,2004,8(1):53-87.
[12] GLEICH D F.PageRank beyond the Web[J].SIAM Rew.,2015,7(3):321-363.
[13] GARCAE,PEDROCHE F,ROMANCE M.On the localization of the personalized PageRank of complex networks[J].Linear Algebra and Its Applications,2013,9(3):640-652.
[14] PEDROCHE F,MORENO F,GONZLEZ A,et al.Leadership Groups on Social Network Sites Based on Personalized Page-Rank[J].Mathematical and Computer Modeling,2013,57(7/8):1891-1896.
[15] KLEINBERG J M.Authoritative sources in a hyper-linked environment[J].Journal of ACM,1999,46(5):604-632.
[16] JIN Z Y,WU Q Y,SHI D X,et al.Random Walk Based Inverse Influence Research in Online Social Networks[C]∥2013 IEEE International Conference on High Performance Computing and Communications & 2013 IEEE International Conference on Embedded and Ubiquitous Computing.2013:2206-2213.
[17] CHENG H B,TAN P N,STICKLEN J,et al.Recommendation via query centered random walk on k-partite graph[C]∥Proceeding of 7th IEEE International Conference on Data Mining.Omaha,NE,2007:457-462.
[18] FRANOIS F,AlLAIN P,RENDERS J M,et al.RandomWalk Computation of Similarities between Nodes of a Graph with Application to Collaborative Recommendation[J].IEEE Transac-tions on Knowledge and Data Engineering,2007,9(3):355-369.
[19] JIANG M,CUI P,CHEN X,et al.Social Recommendation with Cross-Domain Transferable Knowledge[J].Knowledge and Data Engineering,2015,1(27):3084-3097.
[20] ZHANG L Y,XU J,LI C P.A random-walk based recommendation algorithm considering item categories[J].Neurocomputing 2013,0:391-396.
[21] YING J C,KUO W N,TSENG V S,et al.Mining User Check-In Behavior with a Random Walk for Urban Point-of-Interest Recommen-dations[J].ACM Transactions on Intelligent Systems and Technology,2014,3(5):1-26.
[22] HUANG W,KATARIA S,CARAGEA C,et al.Recommending citations:translating papers into references[C]∥Proceedings of the 21st ACM International Conference on Information and Knowledge Management.2012:1910-1914.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!