基于加权启发式搜索的鲁棒性信任路径生成

doi:10.13232/j.cnki.jnju.2018.06.012

南京大学学报(自然科学版) ›› 2018, Vol. 54 ›› Issue (6): 1161–1170.doi: 10.13232/j.cnki.jnju.2018.06.012

基于加权启发式搜索的鲁棒性信任路径生成

魏　桐，童向荣*

烟台大学计算机与控制工程学院，烟台，264005

接受日期:2018-08-21 出版日期:2018-12-01 发布日期:2018-12-01
通讯作者: 童向荣, txr@ytu.edu.cn E-mail:txr@ytu.edu.cn
基金资助:
国家自然科学基金(61572418)，山东省科技发展计划(2016GGX109004)

Robust trust path generation based on weighted heuristic search

Wei Tong，Tong Xiangrong*

School of Computer and Control Engineering，Yantai University，Yantai，264005，China

Accepted:2018-08-21 Online:2018-12-01 Published:2018-12-01
Contact: Tong Xiangrong, txr@ytu.edu.cn E-mail:txr@ytu.edu.cn

摘要/Abstract

摘要： 在社交媒体中，信任传递在用户交互关系的建立上发挥着至关重要的作用. 实际应用中，通常将信任传递过程应用于推荐系统来预测起始用户对特定目标用户的信任程度，从而更好地作出下一步决策. 选择的信任路径是否较优与预测的准确性息息相关. 针对路径长度和信任值在整条路径上的值分布，提出一种新的加权启发式搜索信任预测模型. 该模型将改进的经典A*算法应用于信任网络进行路径寻找，其中，改进的A*算法在寻路过程中使用了二次启发并将启发函数设置为筛选条件进行路径筛选. 该模型最终得到的信任路径具有相对较好的鲁棒性，相对提高了预测的准确性，而且在信任累加计算中融入了信任的衰减. 最后，通过对比实验验证该模型的有效性，并分析了参数的变化对结果预测的影响．

关键词: 信任传递, A*算法, 启发函数, 路径筛选, 信任预测

Abstract: Trust propagation plays an important role in establishing interactions between users. In practical application，it has been often used in recommendation system to help provide users more valuable and reliable information by collecting advice from other trustworthy users. It can predict the extent of trust from a source user to a specific target user and make further decisions more accurately. The quality of trust path is greatly relevant with the accuracy of predicted results. Thus，based on the length of trust path and the distribution of values on the whole path，we proposed a new trust prediction model called Weighted Heuristic Search Trust(WHST) model in this paper to find high quality paths for prediction. Firstly，the model applies Breadth－first Search(BFS)in path－finding to find all shortest paths which can reach the target user. Then，it employs the improved classical A*algorithm in path－selection to choose the optimal one from them. In this process，it uses two times heuristic function and sets heuristic functions as selection conditions to exclude invalid paths. Only the path with high trust and good robustness could be selected as the optimal path. We combined trust decay with trust aggregation to reflect the fact that trust is weakened in varying degrees as the path length extends. Finally，we evaluated the effectiveness of WHST by carrying out several comparison experiments. The influence of parameter adjustment exerted on the experimental results was discussed as well.

Key words: trust propagation, A*algorithm, heuristic function, path selection, trust prediction

中图分类号:

TP391

魏　桐，童向荣. 基于加权启发式搜索的鲁棒性信任路径生成[J]. 南京大学学报(自然科学版), 2018, 54(6): 1161–1170.

Wei Tong，Tong Xiangrong. Robust trust path generation based on weighted heuristic search[J]. Journal of Nanjing University(Natural Sciences), 2018, 54(6): 1161–1170.

参考文献

[1]　Ahn H J. A new similarity measure for collaborative filtering to alleviate the new user cold－starting problem. Information Sciences，2008，178(1)：37－51，doi：10.1016/j.ins.2007.07.024.
[2] Han X，Wang L Y，Farahbakhsh R，et al. CSD：A multi－user similarity metric for community recommendation in online social networks. Expert Systems with Applications，2016，53：14－26.
[3] Wei J，He J H，Chen K，et al. Collaborative filtering and deep learning based recommendation system for cold start items. Expert Systems with Applications，2017，69：29－39.
[4] Rishwaraj G，Ponnambalam S G，Loo C K. Heuristics－based trust estimation in multiagent systems using temporal difference learning. IEEE Transactions on Cybernetics，2017，47(8)：1925－1935.
[5] Golbeck J A. Computing and applying trust in web－based social networks. Ph.D. Dissertation. College Park：University of Maryland at College Park，2005.
[6] Massa P，Avesani P. Trust metrics on controversial users：Balancing between tyranny of the majority and echo chambers. International Journal on Semantic Web and Information Systems，2007，3(1)：39－64.
[7] Lesani M，Montazeri N. Fuzzy trust aggregation and personalized trust inference in virtual social networks. Computational Intelligence，2009，25(2)：51－83.
[8] Kim Y A，Song H S. Strategies for predicting local trust based on trust propagation in social networks. Knowledge－Based Systems，2011，24(8)：1360－1371.
[9] Ghavipour M，Meybodi M R. Trust propagation algorithm based on learning automata for inferring local trust in online social networks. Knowledge－Based Systems，2017，143：307－316.
[10] Yao Y，Tong H，Yan X，et al. Matri：A multi－aspect and transitive trust inference model ∥ Proceedings of the 22nd International Conference on World Wide Web. Rio de Janeiro，Brazil：ACM，2013：1467－1476.
[11] Jsang A. A logic for uncertain probabilities. International Journal of Uncertainty，Fuzziness and Knowledge－Based Systems，2001，9(3)：279－311.
[12] Wang Y H，Hang C W，Singh M P A probabilistic approach for maintaining trust based on evidence. Journal of Artificial Intelligence Research，2011，40(1)：221－267.
[13] Liu G C，Yang Q，Wang H G，et al. Assessment of multi－hop interpersonal trust in social networks by three－valued subjective logic ∥ IEEE INFO－COM 2014－IEEE Conference on Computer Communications. Toronto，Canada：IEEE，2014：1698－1706.
[14] Liu G L，Chen Q，Yang Q，et al. OpinionWalk：An efficient solution to massive trust assessment in online social networks ∥ IEEE INFOCOM 2017－IEEE Conference on Computer Communications. Atlanta，GA，USA：IEEE，2017.
[15] Zohreie M，Shakeri H. A Model for evaluating trust between users in social networks based on subjective logic ∥ 2016 6th International Conference on Computer and Knowledge Engineering(ICCKE). Mashhad，Iran：IEEE，2017：304－309.
[16] Kurdi H，Alshayban B，Altoaimy L，et al. Trusty Feer：A subjective logic trust model for smart city peer－to－peer federated clouds. Wireless Communications and Mobile Computing，2018，2018：1073216.
[17] Hart P E，Nilsson N J，Raphael B. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics，1968，4(2)：100－107.
[18] Pohl H. First results on the effect of error in heuristic search. Machine Intelligence，1970，5：219－236.
[19] Pearl J，Kim J H. Studies in semi－admissible heuristics. IEEE Transactions on Pattern Analysis and Machine Intelligence(PAMI)，1982，4(4)：392－399.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于加权启发式搜索的鲁棒性信任路径生成

Robust trust path generation based on weighted heuristic search

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10

[1]	朱伟,张帅,辛晓燕,李文飞,王骏,张建,王炜. 结合区域检测和注意力机制的胸片自动定位与识别[J]. 南京大学学报(自然科学版), 2020, 56(4): 591-600.
[2]	李昭阳,龚安民,伏云发. 基于EEG脑网络下肢动作视觉想象识别研究[J]. 南京大学学报(自然科学版), 2020, 56(4): 570-580.
[3]	郑建兴,李沁文,王素格,李德玉. 基于翻译模型的异质重边信息网络链路预测研究[J]. 南京大学学报(自然科学版), 2020, 56(4): 541-548.
[4]	黄雨婷,徐媛媛,张恒汝,闵帆. 融合标签结构依赖性的标签分布学习[J]. 南京大学学报(自然科学版), 2020, 56(4): 524-532.
[5]	任睿,张超,庞继芳. 有限理性下多粒度q⁃RO模糊粗糙集的最优粒度选择及其在并购对象选择中的应用[J]. 南京大学学报(自然科学版), 2020, 56(4): 452-460.
[6]	陈俊芬,赵佳成,韩洁,翟俊海. 基于深度特征表示的Softmax聚类算法[J]. 南京大学学报(自然科学版), 2020, 56(4): 533-540.
[7]	王宝丽,姚一豫. 信息表中约简补集对及其一般定义[J]. 南京大学学报(自然科学版), 2020, 56(4): 461-468.
[8]	陈石,张兴敢. 基于小波包能量熵和随机森林的级联H桥多电平逆变器故障诊断[J]. 南京大学学报(自然科学版), 2020, 56(2): 284-289.
[9]	周昊,沈庆宏. 基于改进音形码的中文敏感词检测算法[J]. 南京大学学报(自然科学版), 2020, 56(2): 270-277.
[10]	罗春春,郝晓燕. 基于双重注意力模型的微博情感倾向性分析[J]. 南京大学学报(自然科学版), 2020, 56(2): 236-243.
[11]	王露,王士同. 改进模糊聚类在医疗卫生数据的Takagi⁃Sugeno模糊模型[J]. 南京大学学报(自然科学版), 2020, 56(2): 186-196.
[12]	陈睿, 伏云发. 基于EEG握力变化及想象单次识别研究[J]. 南京大学学报(自然科学版), 2020, 56(2): 159-166.
[13]	杨红鑫,杨绪兵,张福全,业巧林. 半监督平面聚类算法设计[J]. 南京大学学报(自然科学版), 2020, 56(1): 9-18.
[14]	刘胜久,李天瑞,珠杰,刘佳. 带权图的多重分形研究[J]. 南京大学学报(自然科学版), 2020, 56(1): 85-97.
[15]	张银芳,于洪,王国胤,谢永芳. 一种用于数据流自适应分类的主动学习方法[J]. 南京大学学报(自然科学版), 2020, 56(1): 67-73.