基于最短路径的随机游走算法研究与应用

《基于最短路径的随机游走算法研究与应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、岁参未交硕士学位论文基于最短路径的随机游走算法研究与应用ResearchandApplicationofRandomWalkAlgorithmBasedonDistance作者：王云峰导师：徐保民北京交通大学2012年6月学位论姗权使用授权书f掣燃必本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索，提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。(保密的学位论文在解密后适用本授权说明)学位论文作者虢酗萝签字

2、喙plZ-m翻／产导师签名：?j刈签字目期伽f'年移月／甲日中图分类号：TP393：0414UDC：004．8学校代码：10004密级：公开北京交通大学硕士学位论文基于最短路径的随机游走算法研究与应用ResearchandApplicationofRandomWalkAlgorithmBasedon作者姓名：王云峰导师姓名：徐保民学号：10120521职称：副教授学位类别：工学学位级别：硕士学科专业：计算机科学与技术研究方向：数据挖掘北京交通大学2012年6月致谢本论文的工作是在我的导师徐保民教授的悉心指导下完成的，徐保民教授严谨的治学态度和科学的工作方法给了我极大

3、的帮助和影响。在此衷心感谢两年来徐老师对我的关心和指导。也感谢给予我支持和帮助的校内外的老师专家们，从与他们讨论当中，我学到了很多知识也被他们做科研的专业精神所打动。感谢他们对我科研工作的指导和帮助，在此表示衷心的感谢。在实验室工作及撰写论文期间，黄鹏等同学对我论文中的研究工作给予了热情帮助，在此向他们表达我的感激之情。在两年的研究生生活期间，谢其扬等同学对的日常生活提供了极大地帮助，在此向4也4J'J表示真挚的感谢。另外也感谢家人，他们的理解和支持使我能够在学校专心完成我的学业。jb基．銮．亟．．太一堂．．亟．±．堂焦途塞塑蔓摘要摘要：近年来，人们越来越多地关注数

4、据集中数据点之间的关系。不同种类的网络相继涌现。有链接和节点类型都单一的同质网络如以朋友友谊为基础建立起来的社交网站；以网络链接形成的互联网。另外还有多种链接和节点类型形成的异质网络如医学领域病人，疾病与治疗方法或者科学合作网中出版社，科学家与作品这些节点形成多种链接类型的异质网。链路挖掘就是利用数据集合的链接信息进行挖掘的技术。近年来链路预测越来越受到关注。链路预测旨在评估复杂网络节点问连接的可能性并做出预测。局部随机游走LRW(LocalRandomWalk)是只考虑有限步的随机游走，基于最短路径的局部随机游走方法LRWD(LocalRandomWalkwith

5、Distance)是利用最短路径步数作为局部随机游走有限步数。并提出最短路径分步的概念以分析LRWD方法在不同复杂网络上的性能。我们认为随机游走中游走者从初始点首次到达终点的概率在最终两点连接的可能性指标rfl起着最重要的作用。如此游走者都是按照自己的步数游走而不是整个复杂网络按照统一的一个步数游走。从整体性质到局部性质这种变化不仅为复杂网络的研究提供一个新的视角而且证明了最短路径在复杂网络中的重要作用。最后作者还提出了最短路径频数分布和最短路径分布熵的概念，并用它们来度量网络动态演化中表现出的聚集现象。作者还将最短路径和随机游走思想应用到聚类算法中形成新的k-me

6、ans算法。新的聚类算法应用数据点链接信息的方式不同于以往其他算法。新k．means算法是将数据点之间的距离转化为随机游走的转移概率，然后进行游走。以此种方式实现距离空问的转换。实质上转换节点对的距离借鉴了节点与整个网络的其他节点距离。然后基于KL距离构建目标函数。关键词：链路挖掘；最短路径；随机游走；链路预测：k—means距离算法；熵分类号：TP393；0414lll韭—复-銮一适太堂亟±堂焦途塞△垦墨至＆△篓IABSTRACTABSTRACT：RecentlgManydatasetsofinterestarebestdescribedasalinkedcoll

7、ectionofinterrelatedobjects．Examplesofhomogeneousnetworksincludesinglemodesocialnetworks，suchaspeopleconnectedbyfriendshiplinks，ortheW州acollectionoflinkedwebpages．Thesemayrepresenthomogeneousnetworks，containedasingle—objecttypeandlinktype，orricher,heterogeneousnetworks，inwhichtherema