摘要：近年来,人们越来越多地关注数据集中数据点之问的关系。不同种类的网络相继涌现。有链接和节点类型都单一的同质网络如以朋友友谊为基础建立起来的社交网站；以网络链接形成的互联网。另外还有多种链接和节点类型形成的异质网络如医学领域病人,疾病与治疗方法或者科学合作网中出版社,科学家与作品这些节点形成多种链接类型的异质网。链路挖掘就是利用数据集合的链接信息进行挖掘的技术。近年来链路预测越来越受到关注。链路预测旨在评估复杂网络节点间连接的可能性并做出预测。局部随机游走LRW(Local Random Walk)是只考虑有限步的随机游走,基于最短路径的局部随机游走方法LRWD(Local Random Walk with Distance)是利用最短路径步数作为局部随机游走有限步数。并提出最短路径分步的概念以分析LRWD方法在不同复杂网络上的性能。我们认为随机游走中游走者从初始点首次到达终点的概率在最终两点连接的可能性指标中起着最重要的作用。如此游走者都是按照自己的步数游走而不是整个复杂网络按照统一的一个步数游走。从整体性质到局部性质这种变化不仅为复杂网络的研究提供一个新的视角而且证明了最短路径在复杂网络中的重要作用。最后作者还提出了最短路径频数分布和最短路径分布熵的概念,并用它们来度量网络动态演化中表现出的聚集现象。作者还将最短路径和随机游走思想应用到聚类算法中形成新的k-means算法。新的聚类算法应用数据点链接信息的方式不同于以往其他算法。新k-means算法是将数据点之间的距离转化为随机游走的转移概率,然后进行游走。以此种方式实现距离空间的转换。实质上转换节点对的距离借鉴了节点与整个网络的其他节点距离。然后基于KL距离构建目标函数。