基于最短路径随机游走算法的研究和应用论文.pdf

学位论姗权使用授权书f 掣燃必 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。 同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者虢酗萝 签字喙p l z - m 翻产 导师签名： ? j 刈 签字目期伽f 年移月甲日 中图分类号：t p 3 9 3 ：0 4 1 4 u d c ：0 0 4 8 学校代码：1 0 0 0 4 密级：公开 北京交通大学 硕士学位论文 基于最短路径的随机游走算法研究与应用 r e s e a r c ha n d a p p l i c a t i o no fr a n d o mw a l ka l g o r i t h mb a s e do n 作者姓名：王云峰 导师姓名：徐保民 学号：1 0 1 2 0 5 2 1 职称：副教授 学位类别：工学学位级别：硕士 学科专业：计算机科学与技术研究方向：数据挖掘 北京交通大学 2 0 1 2 年6 月 致谢 本论文的工作是在我的导师徐保民教授的悉心指导下完成的，徐保民教授严 谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢两年来 徐老师对我的关心和指导。 也感谢给予我支持和帮助的校内外的老师专家们，从与他们讨论当中，我学 到了很多知识也被他们做科研的专业精神所打动。感谢他们对我科研工作的指导 和帮助，在此表示衷心的感谢。 在实验室工作及撰写论文期间，黄鹏等同学对我论文中的研究工作给予了热 情帮助，在此向他们表达我的感激之情。 在两年的研究生生活期间，谢其扬等同学对的日常生活提供了极大地帮助， 在此向4 也4 j j 表示真挚的感谢。 另外也感谢家人，他们的理解和支持使我能够在学校专心完成我的学业。 j b基銮 亟太一堂亟 堂焦 途 塞塑蔓 摘要 摘要：近年来，人们越来越多地关注数据集中数据点之间的关系。不同种类的网 络相继涌现。有链接和节点类型都单一的同质网络如以朋友友谊为基础建立起来 的社交网站；以网络链接形成的互联网。另外还有多种链接和节点类型形成的异 质网络如医学领域病人，疾病与治疗方法或者科学合作网中出版社，科学家与作 品这些节点形成多种链接类型的异质网。链路挖掘就是利用数据集合的链接信息 进行挖掘的技术。 近年来链路预测越来越受到关注。链路预测旨在评估复杂网络节点问连接的 可能性并做出预测。局部随机游走l r w ( l o c a lr a n d o mw a l k ) 是只考虑有限步的随 机游走，基于最短路径的局部随机游走方法l r w d ( l o c a lr a n d o mw a l k w i t h d i s t a n c e ) 是利用最短路径步数作为局部随机游走有限步数。并提出最短路径分步的 概念以分析l r w d 方法在不同复杂网络上的性能。我们认为随机游走中游走者从 初始点首次到达终点的概率在最终两点连接的可能性指标r f l 起着最重要的作用。 如此游走者都是按照自己的步数游走而不是整个复杂网络按照统一的一个步数游 走。从整体性质到局部性质这种变化不仅为复杂网络的研究提供一个新的视角而 且证明了最短路径在复杂网络中的重要作用。最后作者还提出了最短路径频数分 布和最短路径分布熵的概念，并用它们来度量网络动态演化中表现出的聚集现象。 作者还将最短路径和随机游走思想应用到聚类算法中形成新的k - m e a n s 算法。 新的聚类算法应用数据点链接信息的方式不同于以往其他算法。新k m e a n s 算法是 将数据点之间的距离转化为随机游走的转移概率，然后进行游走。以此种方式实 现距离空问的转换。实质上转换节点对的距离借鉴了节点与整个网络的其他节点 距离。然后基于k l 距离构建目标函数。 关键词：链路挖掘；最短路径；随机游走；链路预测：k m e a n s 距离算法；熵 分类号：t p 3 9 3 ；0 4 1 4 l l l 韭复- 銮一适太堂亟堂焦途塞垦墨至篓i a b s t r a c t a b s t r a c t ：r e c e n t l gm a n yd a t a s e t so fi n t e r e s ta r eb e s td e s c r i b e da sal i n k e d c o l l e c t i o no fi n t e r r e l a t e do b j e c t s e x a m p l e so fh o m o g e n e o u sn e t w o r k si n c l u d es i n g l e m o d es o c i a ln e t w o r k s ，s u c ha sp e o p l ec o n n e c t e db yf r i e n d s h i pl i n k s ，o rt h ew 州a c o l l e c t i o no fl i n k e dw e b p a g e s t h e s em a yr e p r e s e n th o m o g e n e o u sn e t w o r k s ，c o n t a i n e d as i n g l e o b j e c tt y p ea n dl i n kt y p e ，o rr i c h e r , h e t e r o g e n e o u sn e t w o r k s ，i nw h i c ht h e r e m a yb em u l t i p l eo b j e c ta n dl i n kt y p e s ，l i k et h o s ei nm e d i c a ld o m a i n sd e s c r i b i n gp a t i e n t s ， d i s e a s e s ，t r e a t m e n t sa n dc o n t a c t s ，o ri nb i b l i o g r a p h i cd o m a i n sd e s c r i b i n gp u b l i c a t i o n s ， a u t h o r s ，a n dv e n u e s a na r e ac a l l e dl i n km i n i n gh a se m e r g e df r o mt h el a r g e ra r e ao fd a t a m i n i n g ，w h o s ep u r p o s ei st oe x t r a c th i d d e nk n o w l e d g ef r o ml a r g e ，l i n k e dd a t as e t s l i n km i n i n ge n c o m p a s s e saw i d er a n g eo ft a s k s ；h o w e v e ro u rr e v i e wo n l yw i l l c o v e rt w ob r a n c h e s o u rg o a li st oi n t r o d u c et h er a n d o mw a l ki d e ab a s e do nd i s t a n c e b e t w e e nn o d e s f i r s t l y , w eg i v eab r i e fs u m m a r yo nr a n d o mw a l ko nc o m p l e xn e t w o r k sa n dd i s c u s s s o m ep o s s i b l er e s e a r c hi s s u e s 。w ep r o p o s eat h e o r e ma b o u tp r o b a b i l i t ya r r i v i n gf o r h i t t i n gt i m eb a s e do nd i s t a n c eb e t w e e nn o d e s i nt h i sp a p e r , w er e v i e ws e v e r a lm e t h o d sf o rl i n kp r e d i c t i o n t h e nw ep r o p o s e da n i m p r o v e dl i n kp r e d i c t i o nm e t h o dl r w d ( l o c a lr a n d o mw a l kw i t hd i s t a n c e ) b a s e do n e x i s t i n gl r w ( l o c a lr a n d o n lw a l k ) w i t ht h es h o r t e s td i s t a n c e i nl r w d ，o u r h y p o t h e s i si st h a tp r o b a b i l i t yo ft h er a n d o mw a l k e rr e a c h i n gad e s t i n a t i o nn o d ef o rt h e f i r s tt i m em a k e sam a j o rc o n t r i b u t i o nt ol i n ke s t a b l i s h m e n t t om e e tt h i sa s s u m p t i o n ，w e r e p l a c et h eo p t i m a ls t e po fl r w m e t h o d sw i t ht h ed i s t a n c eo fn o d ep a i r s t h eo p t i m a l s t e pi ss p e c i f i e da sl o c a lp r o p e r t i e sn o to v e r a l lf e a t u r e so fn e t w o r k r a n d o mw a l k e r s w a l ki nt h e i ro w n p a c ew i t hn e wc r i t e r i an o tw a l ks i m u l t a n e o u s l yi nt h ew h o l en e t w o r k t h i sc h a n g en o to n l yp r o v i d e st h en e w p e r s p e c t i v e sa n dm e t h o d si nl i n kp r e d i c t i o nf o r r e s e a r c h e r s ，b u ta l s od e m o n s t r a t e st h er o l eo fs h o r t e s td i s t a n c ei nc o m p l e xn e t w o r k t h e nw e p r o p o s ed i s t a n c ef r e q u e n c yd i s t r i b u t i o na n dd i s t r i b u t i o ne n t r o p yt oa n a l y z et h e e v o l u t i o no ft h ec o m p l e xn e t w o r k s n e x t ，w e 扛a n s p l a n tt h i sr a n d o mw a l ki d e ai n t oa n o t h e rb r a n c h ；o b j e c tc l u s t e r i n g b a s e do n1 i n ki n f o r m a t i o n w eu s ee u c l i d e a nd i s t a n c et ob u i l dc o m p l e xn e t w o r k 。t h e w a l k e rs t e p sb a s eo nt h ed i s t a n c eb e t w e e nn o d ep a i ra n du p d a t e st h ed i s t a n c eo fn o d e p a i r w eh a v et h ea p p r o x i m a t es t a t i o n a r yt r a n s i t i o np r o b a b i l i t yd i s t r i b u t i o n a n du s et h i s 1 v j e 丞銮适态堂亟堂焦论塞旦墨i b 一! d i s t r i b u t i o nt ob u i l dn e w c l u s t e r i n gs i m i l a r i t y a f t e rt h a tw eb u i l dc r i t e r i o nf u n c t i o nw i t h k - ld i s t a n c e k e y w o r d s ：l i n km i n i n g ；d i s t a n c e ；r a n d o mw a l k ；l i n kp r e d i c t i o n ；k - m e a n s ；e n t r o p y c l a s s n o ：t p 3 9 3 ：0 4 1 4 立，- 一壅一窑 适丕堂亟 堂 鱼 途塞 旦丞 目录 摘要i i i a b s t r a c t i v l 绪论1 1 1 背景简介1 1 1 1 链路挖掘背景分析l 1 1 2 链路预测2 1 1 3 基于链接信息的聚类分析3 1 2 相关技术知识背景5 1 2 1 随机游走5 1 2 2 图上的随机游走5 1 2 3k r l e a i s 聚类算法6 1 2 4 复杂网络简介7 1 3 本文的主要贡献和创新点一7 1 4 研究意义。8 2 复杂网络上的随机游走理论9 2 1 图论基础一9 2 1 1 基本概念9 2 。1 。2 最短路径9 2 2 复杂网络1 0 2 2 1 复杂网络的度11 2 2 2 最短路径长度1 2 2 3复杂网络上的随机过程1 3 2 3 1 基于最短路径的首达概率定理1 3 2 3 2 基于复杂网络的随机游走表示1 6 2 3 3 随机游走的主要参数1 7 2 3 4 基于随机游走的相似性指标17 2 4 本章小节1 8 3k m e a n s 聚类分析1 9 3 1聚类简介1 9 3 2 基本定义与概念1 9 3 3模式表达，属性选择与抽取1 9 v i 3 4相似性度量2 0 3 5 k m e a n s 聚类算法2 1 3 5 1 算法介绍2 1 3 5 2 质心与目标函数2 2 3 5 3 欧几里得空间上离散型k m e a n s 算法的证明2 3 3 5 4 连续型k - m e a n s 方法2 6 3 5 5 模糊k m e a n s 聚类2 6 3 5 6 初始质心2 7 3 6 本章小结2 9 4基于最短路径随机游走的链路预测模型3 0 4 1方法描述3 0 4 1 1 局部随机游走模型3 0 4 1 2 基于最短路径的局部随机游走模型3 1 4 2数据与指标31 4 2 1 数据分析31 4 2 2 指标选择3 3 4 3实现结果分析3 3 4 4 本章结论3 7 5基于随机游走和k l 距离的聚类分析3 9 5 1 背景介绍3 9 5 2 数据分析3 9 5 3 原始数据相似度4 0 5 4平稳m a r k o v 链的构建4 1 5 5基于k l 的聚类分析4 2 5 5 1 转换后的数据相似度距离选择，4 2 5 5 2 聚类算法过程4 4 5 5 3 实验结果分析4 5 5 6 本章小结4 6 6 结论4 8 6 1 工作总结4 8 6 2未来工作展望4 9 参考文献5 0 作者简历5 4 独创性声明5 5 j 塞窒 垣太堂亟堂僮途塞旦 丞 学位论文数据集5 6 j e立童 望 盔 堂亟堂焦迨塞绻迨 1 绪论 1 1 背景简介 1 1 1 链路挖掘背景分析 现在很多各受关注的数据集合其实都不是由一些独立的实体组成的，人们越 来越关注实体之间的关系。有的数据集合可以表示为同质网络，其中只有一种节 点和一类连接。有的数据集合可以表示为异质网络，其表达的信息可能更加丰富， 网络包含不同利t 类的节点和连接，甚至网络自身具有层次。简单的社会网络就是 同质网络，节点间通过好友关系连接。而在医学领域的网络可能包括患者，疾病， 治疗方法等节点和以及它们之问的连接。在出版领域网络可能包括出版物，作者， 出版公司等节点以及它们之间的连接。链路挖掘是涉及链路的数据挖掘技术，在 对实例问具有联系的数据集合上建立描述或预测数学模型。链路挖掘根据任务分 类包括实例排序，社团发现，集团分类，链路预测和子图发现。与此同时网络分 析已经深入到某些特定领域，如社会网络分析，超文本挖掘和网页分析还有最近 一些复合算法的研究。本文中主要讨论链路预测和基于链路的聚类算法这两个链 路挖掘的子领域。 实体间的链路或者更一般的说法叫做关系是普遍存在的。这些链路通常表现 着实体的某些模式，例如重要性，分类性等。在一些情况下，我们并不是对全部 的链路感兴趣，可能只是对预测实例间是否存在链路感兴趣。在另一些领域，比 如涉及到网络的时间演化。基于现阶段网络的演化过程，我们可能对预测链路的 产生可能性感兴趣。只要将实体的链路考虑进来，那么更多的复杂模式将会自然 而然的产生。我们将进一步分析其复杂网络的结构，例如发现社团，群体或子图。 传统的数据挖掘算法像关联规则，聚类分析都是试图通过搜集实例本身的简 单信息挖掘一些模式。这与经典的统计推断一致，都是给出个独立的明确的模 型。人们总是将这个学习过程看作是从一个同质网络上消除链接信息后抽取节点 属性的过程。 随着信息技术的发展，人们对数据挖掘的要求也越来越高。些数据集合具 有丰富的结构和节点链接关系。为了进一步促进数据挖掘的效果，这些因素都是 不得不考虑的。所以这些数据集用网络或者图来描述会更加合适。一个领域常常 是由不同类型的实体组成的，实体之间由不同的链接组成。因此有一个领域演化 j e塞 銮适盍堂亟堂焦迨塞 缝 淦 出来的网络有不同种类节点和边组成。简单地应用统计推断的方法，假设点之间 是独立的可能会得不到符合实际的结果 1 。将实体间潜在的联系应用到数据挖掘 中能够提高预测模型的精准度。相互连接的实体问往往是相关的并且链接也往往 产生在具有某些共同特性的实体问。另外，网络的结构自身特性也在模型预测上 起到了重要的作用，比如复杂网络中节点的度，度的相关性等一些网络特性。 利用链路结构优化信息检索的结果是一个非常重要的应用。p a g e r a n k 算法和 网络中心节点和权威节点的发现算法都是应用了网络的结构 4 】。这些算法都是基 于网页之问的引用关系得来的。最近还有对这些算法的改进，如在 5 】中，h i d e a k i i s h i i 和r o b e r t ot e m p o 提出了几个分布式随机计划来计算p a g e r a n k 值，此方法 可以利用节点与邻居节点通过链路传递的信息来更新p a g e r a n k 值。论文最主要的 意义是证明了这种分布式随机方法最终在均值平方意义下可以收敛到p a g e r a n k 的 真实值。这些算法都是建立在相互引用的链接的基础之上的。r i c h a r d s o n 等人【6 】 将网页内容和网络结构联系起来建立了一个联合模型。 另类相关的工作是超文本链接和网页分类。这类工作源于社区信息检索。 超文本集通常具有一个信息量丰富的结构，我们应该尽量开发这个结构来提供分 类的精确度。除了单词，超文本同时具有双向链接既具有出度也具：仃入度。传统 的信息检索模型没有充分利用超文本链接的结构。在网页分类问题上，整个网络 被看做一个大的有向图。目标是基于当前网页的特征和与之相连的网页特征给网 络添加类标，如利用入度链接的锚文本和邻接文本可以获得更好地分类。在【7 】【8 中，j o nm k l e i n b e r g 等人将其中的文本信息分类后进行了详细讨论并且探讨了网 络上一些性质。最后提出了一个联合统计模型。有的模型证明如果简单考虑邻居 网页的词汇只会降低模型性能，与之相对应的是考虑类别信息会提高模型信息， 比如层次类别。但是文献【9 的实验表明也表明，简单的利用链接信息如仅仅将邻 居节点的词汇当做当前节点词汇，根据当前网页同邻居节点的共通特征将它们分 到同一类并不能明显提高效果。 近年来社会和协同过滤也越来越受到关注，它们也被看做链路挖掘的范围。 社会网是高度动态的网络对象。随着节点和边的快速增长和相互沟通而表现的社 会结构的变化，整个社会复杂网络随时间的增长和变化都非常迅速。社会网络往 往表现为复杂网络的一些性质，而社会网络迄今为止并没有系统和深入的研究。 复杂网络的知识将在后面的章节涉及。 1 1 2 链路预测 链路预测是基于对象属性和其它已存在的链路预测实体间链路的存在性。例 j e塞窒适友兰亟堂僮途塞 缝迨 如预测好友关系，预测演员的合作关系【1 1 ，例如邮件联络关系，电话联络关系和 文章合作关系。文献【1 2 】中应用网页内容和引用关系预测语义关系。通常情况下， 设计算法时，数据集合中大部分链接用于训练或者形成模型，另一部分用于预测， 来检验模型的精确度。或者从网络的演化角度看，利用时间t 时网络的边和节点属 性去预测t + 1 的链接情况。这个问题有时被看做o l 类标的分类问题，即预测两个 实体是否存在潜在的连接的可能性，若下一步有存在连接的可能性则值为1 ，若没 有则为0 。一种是完全基于网络结构特性的预测方法，在 1 3 1 中d l i b e n n o w e l l 和 j k l e i n b e r g 做了一个关于各种基于网络性质的算法的综述。另一种方法是基于节 点属性信息的链路预测方法。l h u n g a r 等人在【1 4 中介绍了一种结构化回归模 型，这个模型就是利用了关系特征去预测边的存在性。这种关系特征是通过数据 库查询定义的。在实际应用中网络结构和节点属性信息对于链路预测和节点属性 推断都有帮助。尽管如此在算法当巾如何融合这两方面的信息仍然是个问题。除 了在解决某个领域的具体问题时的特定情况，普适的融合方法仍然没有得到系统 的研究与探讨。最近有一篇文章提出了一个利用节点属性和网络结构来预测链路 和节点属性的模型，论文证明模型大大提高有监督和无监督的链路预测算法的性 能。 预测链路是非常困难的，因为大多数有用的先验数据是非常缺乏和离散的。 许多研究者 1 5 1 表明建立链路预测的统计模型的困难之一就是边的先验概率是非 常的小。这对于统计模型的建立和演化，特别对于最后的预测质量都是非常不利 的。一种解决办法是建立整体预测模型。有些方法是建立在整个网络的边，标签 信息上的。这样的模型往往会应用到马尔科夫链方法。 1 1 3 基于链接信息的聚类分析 聚类的目标是找到数据集合中自然存在的分类。通过某币 ，方式将数据集合进 行分割使得同簇的数据点之间相似度大于异簇数据点之间的相似度。与分类不同 的是聚类是非监督方法，它可以从数据集合中发现模式。这使得聚类在诸多领域 得到应用，例如探索科学数据，信息检索，生物计算，网页分析等等。而在模式 识别，统计和机器学习中聚类算法已经得到广泛应用。其中层次凝聚算法f 1 6 18 】 和k - m e a n s 1 9 算法是最为常用的聚类算法。基于概率模型的聚类算法f 2 0 ，2 1 1 1 搀应 用也越来越广泛。 鹣 图1 1 分层次墩聚的复杂嗍络 f i 9 1 ih i e r a r c h i c a ls t r u c t u r ei nn e t w o r k s 在具有链接关系的数据集合里，聚类元素对象的定义都有很多利一。我们可以 对单个的实体进行聚类，也可以对实体的集合进行聚类，甚至可以对于原数据集 合形成的图的子图进行聚类。如何通过潜在的网络结构来定义两个实体或者予图 的相似性，是这类问题的关键所在。这个领域发展较晚，研究工作也非常稀少， 文献 2 2 】是较早有成果的研究工作。 基于链路的聚类应用也十分广泛。例如通过网页集合的聚类寻找h u b 节点用 以识别镜像网站。例如通过出版领域的聚类来发现经常一起出版著作的作者群体 或者基于引用共同的参考文献或通过具有共同的发明与发现的聚类发现一个新的 研究领域。例如 2 3 】在流行病领域聚类来发现具有相似接触人群或相似传播模式疾 病。 4 1 2 相关技术知识背景 1 2 1 随机游走 问题研究的源头可以追溯到p e a r s o n 和r a y l e i g h 在各自领域的研究 2 4 1 。“随 机游走”也叫“随机漫步”，这个概念最早见于k a r lp e a r s o n 发表于n a t u r e 上的文 章，在文章中p e a r s o n 提出了随机游走的问题描述，并且只给出了一个二维空间上 的解决方案。l o r dr a y l e i g h 随后总结了一二维随机游走的情况，并发展出三维情 况下类似于p e a r s o n 游走的问题。自此以后随机游走在各个领域都有了广泛的应用。 其实随机游走在常见于生活中的各种现象中，例如分子在空气中的布朗运动， 墨汁在水巾的扩散等。这种随机现象还在计算机和统计等领域被模拟( 图1 2 ) 。 ( a ) 计算机模拟七个小球的随机游走( b ) 墨汁在水1 1 _ l 扩散( c ) 气体分子在空气中 图i 2 计算机模拟的和自然中的随机游走现象 f i 9 1 2r a n d o mw a l kp h e n o m e n o ni nn a t u r a la n da r t i f i c i a lf i e l d 在物理领域，除了简单地模拟布朗运动，随机游走还应用到量子物理上。在 经济领域随机游走假说用于模型定价。在生态学上模拟生物个体的活动，描述生 态分布和动态地描述动物数量的增减。最后在计算机科学领域，随机游走可以应 用到马尔科夫链蒙特卡洛算法( m c m c ) 。 1 2 2 图上的随机游走 给定一个图和一个起点。游走者从起点出发，随机选取起点的一个邻居并移 动到邻居节点。这个邻居节点将作为新的起点。如此重复上述过程得到的节点序 列就是一个随机过程( 图1 3 ) 。 鬣葶 潼9潦 毒a 饕0 妒 0 f 渗 0 、潦f 0 广， 图1 3 一个游走者以红球为起点进行随机瓣走 f i 9 1 3aw a l k e rs t a r t i n gf r o mr e db a l l 经典的随机游走理论【2 6 】都是在简单但无限图上的游走，研究其在这种图上的 行为规律，例如游走者返回起点的概率是否为1 ( 常返态) 。随着实际网络的规模越 来越大，效率等问题使得有限图上的随机游走的研究引起越来越多的关注。例如 在首达时间内游走者是否访问过给定节点，是否访问过所有节点等。多久之后随 机游走者的概率分布趋向于极限分布。 随机游走的特性使得它在网络科学里面应用十分广泛。例如在复杂网络里有 基于随机游走的搜索算法，有随机游走模型产生的复杂网络，还可以用随机游走 的方法模拟网络演化。在链路预测中还产生了平均通勤时间，重启随机游走等算 法。随机游走也是上文提到的基于链路的数据挖掘领域中经常应用的知识。例如 基于随机游走的聚类分析 2 7 ，图像处理 2 8 等。 1 2 3k m e a n s 聚类算法 k - m e a n s 概念首次见于1 9 6 7 年 2 9 ，其思想更可以追溯到1 9 5 7 年 3 0 】。k - m e a n s 是一种简单快速的经典聚类算法，非常适合与其他算法结合起来解决实际问题。 在科学研究中k - m e a n s 可以应用于开发新的算法，减少复杂度，利于研究者将精力 集中到新的思想在算法中的作用。这也是本文在后面将随机游走思想应用到聚类 分析中时，采用k - m e a n s 算法的原因。k m e a n s 的缺点是对于初值具有较强的敏感 6 滞 雒 性，初始聚类时必须人为指定聚类数和核心。目前针对k - m e a n s 算法的缺陷也有不 少研究者对其进行了改进。 ：跳 蝶嚣 越辫 1 2 4 复杂网络简介 ：菇：曩 鼹簿 骥辫i 嚣凌辫 图1 4 一个数据集合的聚类过程 f i 9 1 4ac l u s t e r i n gp r o c e s so f d a t ac o l l e c t i o n 复杂网络是一个综合学科，兴起于上个世纪九。卜年代。计算机科学，生物学， 社会科学，物理和数学等领域的研究者在各自领域的真实网络中总是能发现一些 共同的性质和规律。我们把这利t 既不完全规则又不完全随机的真实网络统一叫做 复杂网络。复杂网络科学充分借鉴了数学图论分支的概念系统来描述自身科学体 系。复杂网络科学具有某些共同的网络拓扑性质。例如著名的六度空间试验。2 0 世纪6 0 年代，心理学家米尔格兰姆设计了一个连锁信件实验。他将一封写有一个 股票经纪人的信件随机发放到美国各地城市的部分市民手里。要收信者将信件再 发送给自己认为最有可能与此经纪人有联系的朋友，再要求朋友如此做。最终这 个经纪人收到了大部分信件，平均每封信转手6 2 次。这种小世界性表明实际网络 具有比规则网络更小的平均节点距离。复杂网络比较真实地反应了生活中的真实 网络。 随着复杂网络科学的快速发展，其不断完善的体系为链路预测的研究提供了 理论支持。因此，对于预测的结果更能够从理论的角度进行解释。而复杂网络本 身特性和演化机制都会成为链路预测领域的基础。复杂网络科学的背景由来决定 了其研究的复杂性和应用的价值与广泛性。 1 3 本文的主要贡献和创新点 ( 1 ) 第二章主要是介绍了复杂网络图论基础和统计概念，在复杂网络上建立随机 7 磐一 鬻 辩 j 匕立窑适盔堂 亟 堂焦途塞缝途 游走理论框架。将最短路径引入到随机游走中，提出基于最短路径的首达概率定 理并给予证明。此定理也足本文的数学基础所在。 ( 2 ) 第三章详细介绍了k m e a n s 聚类算法的知识，对于欧式窄间上离散型的聚类 算法过程给出了详细数学证明。证明过程与各种相似性距离的比较为第五章中数 据点距离空间的转换奠定基础。 ( 3 ) 第四章提出了复杂网络上的基于最短路径的局部随机游走预测模型。在网络 的演化过程中，本文利用基于最短路径的首达概率构建了随机游走指标。并与之 前的局部随机游走算法进行比较。在比较当中发现不同结构的网络预测效果不同。 进而提出最短路径频数分布的概念进行定性分析。最后还提出最短路径分布熵的 概念对三个网络表现出来的聚集现象进行说明。 ( 4 ) 第五章将最短路径和随机游走思想应用到聚类算法中形成新的k m e a n s 算 法。新的聚类算法应用数据点链接信息的方式不同于以往其他基于算法。新k m e a n s 算法是将数据点之间的距离转化为随机游走的转移概率，然后进行游走。以此利- 方式实现距离空间的转换。实质上转换节点对的距离借鉴了节点到整个网络的节 点的距离。 1 4 研究意义 复杂网络上的随机游走在数据挖掘中有广泛的应用，它不需要太多前提，是 一种自学习的方法。所以对于随机游走思想本身的研究具有广泛的理论和应用价 值。 第二章推导出的基于最短路径的首达概率的结论，对随机游走中有限步最终 到达概率进行了结构分析。游走者步数小于最短路径是首达概率为0 ，这不仅有理 论意义而且在实际应用中必然会简化随机游走模型中的指标公式，提高算法查询 与搜索效率。 第四章中经过改进的局部随机游走预测模型提高了算法预测精度。并且提出 最短路径频数分布和最短路径分布熵的概念，理论上为复杂网络结构分析提供了 新的工具。 第三章和第五章提出了基于链路信息的k - m e a n s 聚类算法。在算法设计当中引 入第四章的基于最短路径的随机游走思想。但是不同以往其它基于链路信息的聚 类算法，本文将链路信息应用到距离空间的转换上，让每个距离重复借鉴整个距 离空间其它距离的信息。这种方法无疑为链路挖掘提供了一个新角度。 j 立銮适盔堂亟堂焦途塞复盘旦鳖土丝瞳塑i 遗焘堡逾 2 复杂网络上的随机游走理论 2 1 图论基础 2 1 1 基本概念 定义l ：( 二元关系) 两个具体事物口和b 按照次序排列，记作 ，称 为一个有序对，记两个集合a a 和b b 的有序积为爿b = f l 口a ，6 b ) 。 有序集合的一个子集合称为一个二元关系。当a 和b 两个事物组成偶数对与次序无 关时，称其为无序对，用( 以，6 ) 表示，而无序积用爿 b 表示。 定义2 ：( 图) 假设节点集合为y ，边集合为e ，记g = ( v ，e ) 为一个图。若 中的边元素由两个节点的有序对组成，则g 为有向图。若e 中的边元素由两个节 点的无序对组成，则g 为无向图。 定义3 ：( 邻居节点) 与一个节点相连的节点酬做这个节点的邻居节点或一阶 邻居节点。这条边相对于两端点叫做邻边。若一个节点最少需要两条边连接节点， 则这个点叫做二阶邻居节点，如此类推可得门阶邻居节点。 定义4 ：( 简单图与完全图) 两端点重合的边称为环，当两端点之间的链边大 于一条时，称这些边为多重边。没有环及多重边的图叫做简单图。本文探讨的网 络是无环并且无多重边的，在复杂网络研究当中往往将多重边转化为带权重的单 边。若图中任意两点都有连边则此图叫做完全图。对于完全图g = ( y ，e ) ，有lvl = 以， i z i = n ( n z - 1 ) r 。 定义5 ：( 路径) 给定图g = ( y ，e ) ，则交替序列“= v 0 e i p ! e 2 k 一。巳k 称为一条长 度为，z 的路径，其中e 的两个端点是v f 一。，_ ，两点之间最短的路径叫做最短路径。 若路径“中所有的边均不相同，则称“为一条道路。两点之间最短的一条道路为最 短道路。在无向图中，显然最短路径和最短道路在意义上是相同的。 2 1 2 最短路径 对于一个大规模的复杂网络，寻找网络的最短路径仍然是一个有待系统研究 的课题。但是最短路径无疑在复杂网络中起着重要作用。本文的核心思想就是最 短路径在复杂网络中的应用。这里介绍一个最基本的求最短路径的算法。 j b 立童通厶堂亟堂焦途塞 复苤旦鳖土曲瞳扭一鲎垂堡垒 给定图g = ( v ，e ) ，其权重函数“v ) 表示以“和v 为端点的边的权重，求起始 点到终点的最短路径。设任意一条路径，其路径权重函数为w o o = w ( e ) 。 p d i j k s t r a 算法简述【3 4 3 5 1 ： 1 给始点一个标号，( ) = 0 ，对所有v “。，令，( = 。步数f = 0 ，有标号集 合为s o = 砜 。 2 在第f 步结束时，若已经选好的标号节点集合为s = u 0 ，, ，l f j ) ，令初始点到 “的距离为的标号z ( u ) = d ( u 。，u ) 。女果用墨表示尚未选好的标号节点集合， 用一( “；) 表示每一个这类标号节点u i 的邻居节点集合，对每一个v n 一( “) ， 用m i n l ( v ) ，l ( u i ) 十“吩 ，) ) 代替“。这里w ( v ) 表示吩，y 两点之间连边的边权。 如果f ( v ) 取值z ( ) + “，l ，) ，则计算m i n ( v ) ) ，并把具有最小值的节点记为“， 旦置换s + 。= s u “+ ，) 。 3 若i = p ( g ) 一2 ，停止。否则用i + 1 代替i ，转入第2 步。 定义6 ( 图的矩阵) 对于给定的图g = ( v ，e ) ，其中iv 咒。定义g 的邻接 矩阵为d = ( 以) ，对于无权图邻接矩阵定义为 妒莘鬻善薹蒙篆 对于有权图，当节点f ，相邻接时， 的权值。当节点f ，不邻接时，叱= o 。 点的度毛= d ( i ) 。 2 2 复杂网络 吒= ，其中是以节点f ，j 为端点的边 在复杂网络中d ( i ) = d i = 吒亦可表示节 ， 复杂网络科学反应真实世界中各种网络的联系与演化机制。比如i n t e r n e t 网是 由路由器和电脑为节点组成的复杂网络，节点间由各种物理数据线或者无线连接。 社会网是以人类自身为节点，人们之间的相互关系组成的复杂网络，时尚或思想 可以在这个网络上传播。互联网是通过网页链接起来的巨大虚拟复杂网络。从最 早的规则网络到利用随机网络设计的大规模网络，再到1 9 9 8 年瓦兹和斯绰伽兹提 出介于规则网和随机网之间的小世界网模型。纵观整个发展过程，复杂网络科学 是从传统图论等数学领域推导符合实际系统的理论到从实际网络出发总结发现并 1 0 标定复杂网络性质的过程。复杂网络科学的发展过程主要是受以下几点的影响： 、随着计算机的计算能力的增强，人们可以采集，模拟和计算大规模网络，从 中发现些网络特性。二、各个科学领域界限日渐模糊，专家们可以更容易得各 个领域数据集发现网络的一般信息。三、复杂网络科学自身发展的要求。作为一 个科学分支，复杂网络必须要有自我界定的性质和统一的自我构建和推演方法。 经过复杂网络数年的发展，一些在大部分实际网络当中能够得到反应的经典模型 也被提出。o n d , 世界模型，无标度模型等。 本节主要介绍复杂网络的一些基础知识。主要是网络度的特性，为下文介绍 复杂网络上的链路预测做准备。 2 2 1 复杂网络的度 定义7 ( 度) 对于邻接矩阵d ，定义节点f 的度为所有与其相连的边的总数， ，1 k i = y d 护平均度定义为 - 二y k l ，最大度为：七。，= m a x 砖。任取一个点， j r j； 1 i r ，l 、 此点度为尼的概率为p ( k 】= 竺型，这个概率分布即为度的分布。 n 绝大多数实际网络都具有s c a l e f r e e 性质。其中最基本的一条是复杂网络的度 r 分布遵循幂律性质。p ( z ) = c p k ，其中7 是度的分布参数，c ，= 1 k 吖 l 还有另一个概率定义度的相关性，用来度量节点间是否连接。假设建立连接 原因是由于两端