| Computer Technology, Information Engineering |
|
|
|
|
| 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 |
|
|
|
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.
|
|
Published: 23 July 2016
|
|
|
加权网络中基于多路径节点相似性的链接预测
鉴于现有大多数链接预测算法仅考虑了图的局部或全局特性,在预测准确率和计算复杂度上难以均衡,且有关加权网络的链接预测研究相对较少,提出新的加权社会网络链接预测算法(STNMP).引入节点对边权强度的概念,用于度量邻居节点间的局部相似度.提出路径相似性贡献的概念,定义多路径传输节点相似性,用于描述步长为2和3的所有路径及这些路径上的中间节点对于所连接的两个节点的相似性总贡献.在多个真实网络中对算法的有效性进行验证,以AUC作为评价指标,与经典相似性算法CN、Jaccard、AA等进行预测准确率的对比分析.结果显示,针对小规模社会网络,STNMP算法的预测准确率高于现有算法.
|
|
| ［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, ELIASSIRAD 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 Linyuan. 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. Highquality 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 Yangfu. 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 Zunqiang. 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 Shanliang, 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 Linyuan, ZHANG Yicheng. 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 Shuling. Research on link prediction methods based on the similarity ［D］. Harbin: Harbin Engineering University, 2012: 25-46．
［15］ 李彦敏.基于链接依赖度的链接预测［D］.长春：吉林大学, 2013: 20-33．
LI Yanmin. Link prediction based on link dependency ［D］. Changchun: Jilin University, 2013: 20-33．
［16］ 涂一娜. 具有时间感知的加权网络链路预测研究［D］. 长沙: 中南大学, 2014: 20-43．
TU Yina. Study on link prediction of the weighted networks with timeaware ［D］. Changsha: Zhongnan University, 2014: 20-43．
［17］ LV Linyuan, ZHOU Tao. Link prediction in weighted networks: the role of weak ties ［J］. Europhysics Letters, 2010, 89: 18001．
［18］ 余宏俊. 基于符号网络的社群分析方法研究［D］. 武汉：华中科技大学, 2011: 31-32．
YU Hongjun. The research of community analysis based on signed social networks ［D］. Wuhan: Huazhong University of Science and Technology, 2011: 31-32. |
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
