Please wait a minute...
浙江大学学报(工学版)
计算机技术、信息工程     
加权网络中基于多路径节点相似性的链接预测
郭景峰,刘苗苗,罗旭
1. 燕山大学 信息科学与工程学院,河北 秦皇岛 066004;
2. 东北石油大学 秦皇岛分校, 黑龙江 大庆 163318|
3. 燕山大学 河北省虚拟技术与系统集成重点实验室,河北 秦皇岛 066004
Link prediction based on similarity of nodes of multipath in weighted social networks
GUO Jing feng,LIU Miao miao,LUO Xu
1. College of Information Science and Engineering, Yanshan University, Qinhuangdao 066004, China;
2. Qinhuangdao Branch,Northeast Petroleum University, Daqing 163318, China; 
3. Key Laboratory for Computer Virtual Technology and System Integration of Hebei Province, Yanshan University,Qinhuangdao 066004, China
 全文: PDF(586 KB)   HTML
摘要:

鉴于现有大多数链接预测算法仅考虑了图的局部或全局特性,在预测准确率和计算复杂度上难以均衡,且有关加权网络的链接预测研究相对较少,提出新的加权社会网络链接预测算法(STNMP).引入节点对边权强度的概念,用于度量邻居节点间的局部相似度.提出路径相似性贡献的概念,定义多路径传输节点相似性,用于描述步长为2和3的所有路径及这些路径上的中间节点对于所连接的两个节点的相似性总贡献.在多个真实网络中对算法的有效性进行验证,以AUC作为评价指标,与经典相似性算法CN、Jaccard、AA等进行预测准确率的对比分析.结果显示,针对小规模社会网络,STNMP算法的预测准确率高于现有算法.

Abstract:

A novel algorithm similarity based on transmission nodes of multipath (STNMP) for link prediction in weighted social networks was proposed in view of the fact that most link prediction algorithms only considered local or global characteristics of the graph, which was difficult to achieve equilibrium in the prediction accuracy and the computational complexity, and researches on link prediction in weighted social networks were relatively less. The concept of the edge weight strength was introduced to measure the local similarity of neighbor node pairs. The similarity of transmission nodes of multipath was proposed and the definition of the path similarity contribution was given, which were used to describe the total contribution of all these paths of 2 and 3 paces to the similarity of node pairs. The effectiveness of the algorithm was verified through experiments on many real networks. The comparison and analysis on prediction accuracy of the algorithm were conducted with those classical link prediction algorithms based on the similarity index, such as common neighbor (CN), Jaccard and Adamic-Adar under the evaluation index of area under the receiver operating characteristic curve (AUC). Results showed the accuracy of STNMP algorithm was higher than those of existing algorithms for small scale of social network.

出版日期: 2016-07-23
:  TP 391  
基金资助:

国家自然科学基金资助项目(61472340);河北省秦皇岛市科技支撑资助项目(201502A003).

通讯作者: 刘苗苗,女,副教授. ORCID: 0000-0001-8569-0693.     E-mail: liumiaomiao82@163.com
作者简介: 郭景峰(1962-),男,教授,博导,从事数据挖掘、社会网络分析研究.
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章  

引用本文:

郭景峰,刘苗苗,罗旭. 加权网络中基于多路径节点相似性的链接预测[J]. 浙江大学学报(工学版), 10.3785/j.issn.1008-973X.2016.07.017.

GUO Jing feng,LIU Miao miao,LUO Xu. Link prediction based on similarity of nodes of multipath in weighted social networks. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 10.3785/j.issn.1008-973X.2016.07.017.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2016.07.017        http://www.zjujournals.com/eng/CN/Y2016/V50/I7/1347

[1] KUMAR R, NOVAK J, TOMKINS A. Structure and evolution of online social networks [C]∥ Proceedings of the ACM SIGKDD. New York: ACM, 2006: 611-617.
[2] GALLAGHER B, TONG H, ELIASSIRAD T, et al. Using ghost edges for classification in sparsely labeled networks [C]∥Proceedings of the ACM SIGKDD. New York: ACM, 2008: 256-264.
[3] 吕琳媛. 复杂网络链路预测[J]. 电子科技大学学报, 2010, 39(5): 651-661.
LV Linyuan. Link prediction of complex networks [J]. Journal of University of Electronic Science and Technology of China, 2010, 39(5): 651-661.
[4] YU H, BRAUN P, YILDIRIM M A, et al. Highquality binary protein interaction map of the yeast interactome network [J]. Science, 2008, 322(5898): 104110.
[5] NEWMAN M. The structure and function of complex networks [J]. SIAM Review, 2003, 45(2): 167-256.
[6] 张扬夫. 有向与加权网络的链路预测[D]. 湘潭:湘潭大学, 2011: 511.
ZHANG Yangfu. Link prediction in directed and weighted networks [D]. Xiangtan: Xiangtan University, 2011: 511.
[7] ADAMIC L, ADAR E. How to search a social network [J]. Social Networks, 2005, 27 (3): 187-203.
[8] NEWMAN M. Clustering and preferential attachment in growing networks [J]. Physical Review E, 2001, 64(2): 025102-1-4.
[9] 姚尊强.加权复杂网络的分析和预测[D]. 青岛: 青岛理工大学, 2012: 35-43.
YAO Zunqiang. The analysis and prediction of weighted complex networks [D]. Qingdao: Qingdao Technological University, 2012: 35-43.
[10] KATZ L. A new status index derived from social metric analysis [J]. Psychometrika, 1953, 18(1): 39-43.
[11] 张珊靓, 周晏. 基于随机游走的时间加权社会网络链接预测算法[J].计算机应用与软件, 2014, 31(7): 28-30.
ZHANG Shanliang, ZHOU Yan. Time weighted social networks link prediction algorithm based on random walk [J]. Computer Application and Software, 2014, 31(7): 28-30.
[12] ZHOU Tao, LV Linyuan, ZHANG Yicheng. Predicting missing links via local information [J]. The European Physical Journal B, 2009, 10(1140): 623-630.
[13] PANAGIOTIS S, ELEFTHERIOS T, YANNIS M. Transitive node similarity for link prediction in social networks with positive and negative links [C]∥ Proceedings of the 4th ACM Conference on Recommender System. Barcelona: ACM, 2010: 183-190.
[14] 李淑玲. 基于相似性的链接预测方法研究[D]. 哈尔滨:哈尔滨工程大学, 2012: 25-46.
LI Shuling. Research on link prediction methods based on the similarity [D]. Harbin: Harbin Engineering University, 2012: 25-46.
[15] 李彦敏.基于链接依赖度的链接预测[D].长春:吉林大学, 2013: 20-33.
LI Yanmin. Link prediction based on link dependency [D]. Changchun: Jilin University, 2013: 20-33.
[16] 涂一娜. 具有时间感知的加权网络链路预测研究[D]. 长沙: 中南大学, 2014: 20-43.
TU Yina. Study on link prediction of the weighted networks with timeaware [D]. Changsha: Zhongnan University, 2014: 20-43.
[17] LV Linyuan, ZHOU Tao. Link prediction in weighted networks: the role of weak ties [J]. Europhysics Letters, 2010, 89: 18001.
[18] 余宏俊. 基于符号网络的社群分析方法研究[D]. 武汉:华中科技大学, 2011: 31-32.
YU Hongjun. The research of community analysis based on signed social networks [D]. Wuhan: Huazhong University of Science and Technology, 2011: 31-32.

[1] 何雪军, 王进, 陆国栋, 刘振宇, 陈立, 金晶. 基于三角网切片及碰撞检测的工业机器人三维头像雕刻[J]. 浙江大学学报(工学版), 2017, 51(6): 1104-1110.
[2] 王桦, 韩同阳, 周可. 公安情报中基于关键图谱的群体发现算法[J]. 浙江大学学报(工学版), 2017, 51(6): 1173-1180.
[3] 尤海辉, 马增益, 唐义军, 王月兰, 郑林, 俞钟, 吉澄军. 循环流化床入炉垃圾热值软测量[J]. 浙江大学学报(工学版), 2017, 51(6): 1163-1172.
[4] 毕晓君, 王佳荟. 基于混合学习策略的教与学优化算法[J]. 浙江大学学报(工学版), 2017, 51(5): 1024-1031.
[5] 王亮, 於志文, 郭斌. 基于双层多粒度知识发现的移动轨迹预测模型[J]. 浙江大学学报(工学版), 2017, 51(4): 669-674.
[6] 廖苗, 赵于前, 曾业战, 黄忠朝, 张丙奎, 邹北骥. 基于支持向量机和椭圆拟合的细胞图像自动分割[J]. 浙江大学学报(工学版), 2017, 51(4): 722-728.
[7] 穆晶晶, 赵昕玥, 何再兴, 张树有. 基于凹凸变换与圆周拟合的重叠气泡轮廓重构[J]. 浙江大学学报(工学版), 2017, 51(4): 714-721.
[8] 黄正宇, 蒋鑫龙, 刘军发, 陈益强, 谷洋. 基于融合特征的半监督流形约束定位方法[J]. 浙江大学学报(工学版), 2017, 51(4): 655-662.
[9] 蒋鑫龙, 陈益强, 刘军发, 忽丽莎, 沈建飞. 面向自闭症患者社交距离认知的可穿戴系统[J]. 浙江大学学报(工学版), 2017, 51(4): 637-647.
[10] 戴彩艳, 陈崚, 李斌, 陈伯伦. 复杂网络中的抽样链接预测[J]. 浙江大学学报(工学版), 2017, 51(3): 554-561.
[11] 刘磊, 杨鹏, 刘作军. 采用多核相关向量机的人体步态识别[J]. 浙江大学学报(工学版), 2017, 51(3): 562-571.
[12] 郭梦丽, 达飞鹏, 邓星, 盖绍彦. 基于关键点和局部特征的三维人脸识别[J]. 浙江大学学报(工学版), 2017, 51(3): 584-589.
[13] 王海军, 葛红娟, 张圣燕. 基于核协同表示的快速目标跟踪算法[J]. 浙江大学学报(工学版), 2017, 51(2): 399-407.
[14] 张亚楠, 陈德运, 王莹洁, 刘宇鹏. 基于增量图形模式匹配的动态冷启动推荐方法[J]. 浙江大学学报(工学版), 2017, 51(2): 408-415.
[15] 刘宇鹏, 乔秀明, 赵石磊, 马春光. 统计机器翻译中大规模特征的深度融合[J]. 浙江大学学报(工学版), 2017, 51(1): 46-56.