基于逆向游走的PageRank社交网络影响力度量算法

J4 ›› 2015, Vol. 37 ›› Issue (11): 2134-2141.

基于逆向游走的PageRank社交网络影响力度量算法

郑孝遥，杨文建，鲍煜，罗永龙

（安徽师范大学数学计算机科学学院，安徽芜湖 241003）

收稿日期:2015-08-03 修回日期:2015-10-11 出版日期:2015-11-25 发布日期:2015-11-25
基金资助:
国家自然科学基金资助项目（61370050，61572036）；安徽高校自然科学研究资助项目（KJ2015A067,KJ2014A088）；芜湖市科技计划重点资助项目（2015cxy10）；安徽师范大学校创新基金资助项目（2015cxjj10）

A social networks influence measurement
algorithm based on reverse walk PageRank

ZHENG Xiaoyao，YANG Wenjian，BAO Yu，LUO Yonglong

Received:2015-08-03 Revised:2015-10-11 Online:2015-11-25 Published:2015-11-25

摘要/Abstract

摘要：

随着社交网络的发展，其节点影响力度量成为一个重要的研究领域。针对传统随机游走PageRank算法精确度不高的问题，提出一种逆向随机游走PageRank算法，该算法采用逆向查找消息传播源的思想，对网络中的每条有向边以概率ε进行逆向随机游走，通过迭代计算出每个节点的PageRank值。实验表明，本文提出的算法较传统的随机游走PageRank算法具有更好的稳定性，并在迭代次数较少时也能保持较高精度。

关键词: PageRank, 随机游走, 社交网络, 影响力度量

Abstract:

(School of Mathematics and Computer Science,Anhui Normal University,Wuhu 241003,China)Abstract:With the development of social networks, the influence measurement of nodes has become an important research area. Aiming at the accuracy problem of the traditional random walk PageRank algorithm, we in this paper propose a reverse random walk PageRank algorithm, which is based on the idea of reversely searching dissemination source, each directed edge starts the random walk with probability ε,and the value of PageRank is calculated by iteration. Experimental evaluation on publicly available datasets demonstrates that our algorithm has the improved stability and higher accuracy when there is less iteration.

Key words: PageRank;random walk;social networks;influence measurement

郑孝遥，杨文建，鲍煜，罗永龙. 基于逆向游走的PageRank社交网络影响力度量算法[J]. J4, 2015, 37(11): 2134-2141.

ZHENG Xiaoyao，YANG Wenjian，BAO Yu，LUO Yonglong. A social networks influence measurement
algorithm based on reverse walk PageRank [J]. J4, 2015, 37(11): 2134-2141.

参考文献

［1］Wu Xindong,Li Yi,Li Lei. Influence analysis of online social networks［J］. Chinese Journal of Computers,2014,37(4):735752.(in Chinese)
［2］Zhao Zhiying,Yu Hai,Zhu ZhiLiang, et al. Identifying influential spreaders based on network community structure［J］. Chinese Journal of Computer,2014,37(4):753766.(in Chinese)
［3］Liu Zhipeng,Pi Dechang. Mining social influence of nodes from mobile datasets［J］. Journal of Computer Research and Development,2013,50(Suppl.):244248.(in Chinese)
［4］Chen Hao,Wang Yitong. Thresholdbased heuristic algorithm for influence maximization［J］.Journal of Computer Research and Development,2012,49(10):21812188.(in Chinese)
［5］Das Sarma A,Molla A R,Pandurangan G, et al. Fast distributed PageRank computation［J］. Theoretical Computer Science,2015,56(10):113121.
［6］Ding Zhaoyun,Jia Yan,Zhou Bin, et al. Survey of influence analysis for social networks［J］. Computer Science,2014,41(1):4853.(in Chinese)
［7］Liu Yanheng,Li Feipeng,Sun Xin,et al. Social network model based on the transmission of information［J］. Journal of Communications,2013,34(4):19.(in Chinese)
［8］Zhao W,Chen H F,Fang H T. Convergence of distributed randomized PageRank algorithms［J］. IEEE Transactions on Automatic Control,2013,58(12):32553259.
［9］Ding Z,Jia Y,Zhou B,et al. Mining topical influencers based on the multirelational network in microblogging sites［J］. China Communications,2013,10(1):93104.
［10］Sarma A D,Nanongkai D,Pandurangan G,et al. Distributed random walks［J］. Journal of the ACM (JACM),2013,60(1):131.
［11］Page L,Brin S,Motwani R,et al. The PageRank citation ranking:bringing order to the Web［J］. Stanford Infolab,1999,9(1):114.
［12］Henzinger M R, Heydon A,Mitzenmacher M,et al. Measuring index quality using random walks on the Web［J］. Computer Networks,1999,31(1116):12911303.
［13］Li L,Xu G,Zhang Y,et al. Random walk based rank aggregation to improving web search.［J］. Knowledge Based Systems,2011,24(7):943951.
［14］Lee S,Jin H L,Lim J,et al. Robust stereo matching using adaptive random walk with restart algorithm［J］. Image and Vision Computing,2015,37:111.
［15］Csáji B C,Jungers R M,Blondel V D. PageRank optimization by edge selection［J］. Discrete Applied Mathematics,2014,169(6):7387.
［16］https://snap.stanford.edu/data/index.html.
［17］Zhong E,Fan W,Wang J,et al.ComSoc:adaptive transfer of user behaviors over composite social network［C］∥Proc of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2012:696704.
附中文参考文献：
［1］吴信东,李毅,李磊. 在线社交网络影响力分析［J］. 计算机学报,2014,37(4):735752.
［2］赵之滢,于海,朱志良,等. 基于网络社团结构的节点传播影响力分析［J］. 计算机学报,2014,37(4):753766.
［3］刘志鹏,皮德常. 从移动数据中挖掘网络节点的影响力［J］. 计算机研究与发展,2013,50(Suppl):244248.
［4］陈浩,王轶彤. 基于阈值的社交网络影响力最大化算法［J］. 计算机研究与发展,2012,49(10):21812188.
［6］丁兆云,贾焰,周斌,等. 社交网络影响力研究综述［J］. 计算机科学,2014,41(1):4853.
［7］刘衍珩,李飞鹏,孙鑫,等. 基于信息传播的社交网络拓扑模型［J］. 通信学报,2013,34(4):19.

[1]	昌阳, 马慧芳, . 基于染色随机游走的可重叠社区发现[J]. 计算机工程与科学, 2022, 44(05): 834-844.
[2]	刘云, 肖添, 王梓宇. 动态特征选择算法对恶意行为检测的优化研究[J]. 计算机工程与科学, 2022, 44(04): 665-673.
[3]	袁泉, 晏飞扬, 文志云, 张振康, . 基于谱聚类的社交网络差分隐私保护算法研究[J]. 计算机工程与科学, 2022, 44(02): 251-256.
[4]	谢小杰, 梁英, 王梓森, 董祥祥, . 社交网络用户隐私泄露量化评估方法[J]. 计算机工程与科学, 2021, 43(08): 1376-1386.
[5]	马汉达, 景迪. 基于SSD和时序模型的微博好友推荐算法[J]. 计算机工程与科学, 2021, 43(07): 1291-1298.
[6]	李举, 马慧芳, 李青青, 宿云. 融合结构-属性交互二部图随机游走的社区搜索方法[J]. 计算机工程与科学, 2021, 43(06): 1067-1075.
[7]	李晓红, 王闪闪, 马堉银, 马慧芳. 融合相似度图和随机游走模型的多标签短文本分类算法[J]. 计算机工程与科学, 2021, 43(06): 1081-1087.
[8]	张琦, 张祖凡, 甘臣权. 融合社会关系的社交网络情感分析综述[J]. 计算机工程与科学, 2021, 43(01): 180-190.
[9]	杨丰瑞, 李前洋, 罗思烦, . 一种基于降噪自编码器的隐式反馈推荐算法[J]. 计算机工程与科学, 2020, 42(08): 1500-1505.
[10]	杨丰瑞, 李前洋, 罗思烦, . 基于降噪自编码器的社会化推荐算法[J]. 计算机工程与科学, 2020, 42(05): 944-950.
[11]	胡亚红1,王一洲2,毛家发1. 基于PageRank和基准测试的异构集群节点性能评价算法研究[J]. 计算机工程与科学, 2020, 42(03): 391-396.
[12]	刘辉, ., 曾斌, 刘子恺. 融合邻居选择策略和信任关系的兴趣点推荐[J]. 计算机工程与科学, 2020, 42(02): 365-372.
[13]	孙燕, 孙茂松, 赵海兴, 冶忠林, . 表示学习中句子与随机游走序列等价性的一种新证明[J]. 计算机工程与科学, 2020, 42(02): 373-380.
[14]	严开1,2，李玲1,2,秦永彬1,2. 道路交通网络中的关键节点识别方法研究[J]. 计算机工程与科学, 2018, 40(11): 1983-1990.
[15]	蔡国永,毕梦莹,刘建兴. 基于标记信息级联传播树特征的谣言检测新方法[J]. 计算机工程与科学, 2018, 40(08): 1488-1495.