基于链接重要性的动态链接预测算法研究

《基于链接重要性的动态链接预测算法研究》由会员分享，可在线阅读，更多相关《基于链接重要性的动态链接预测算法研究（57页珍藏版）》请在金锄头文库上搜索。

1、华中科技大学 硕士学位论文 基于链接重要性的动态链接预测算法研究 姓名：李栋才 申请学位级别：硕士 专业：计算机应用技术 指导教师：李玉华 2011-01-17 华中科技大学硕士学位论文华中科技大学硕士学位论文 I 摘 要 作为一种社会网络，科研合作网络中的实体关系就是两个作者之间合作发表一 篇论文。科研合作网络的一个重要问题就是预测两个作者之间的合作发表论文的情 况，在数据挖掘中，这一问题即是链接预测。在科研合作网络的链接预测问题中， 传统的方法一般基于图的拓扑属性计算或结合语义属性的分类，但已有的方法存在 两个主要问题：一篇论文在计算机表示的网络中形成的多条链接，往往是被同等对 待的，但实

2、际情况是不同作者的联系对一篇论文的贡献是不一样的。另一个问题是 在相关属性的计算过程中，均将历史数据同等对待，忽视了时间因素在链接形成过 程中的影响，显然这是不符合事实的。 针对以上两点，给出了一种基于链接重要性的动态链接预测算法。根据 Digital Bibliography ,;. ,;. nn termSett w twtw=， 其对应term权值向量记为 12 ,.,. n Ww ww=，那么两个作者 p v， q v在训练集时间 段 1 , k t t内的最终的语义相似度（semantic similarity，简记为SS）为式3-19 (,) * pq pq pq WW sim v

3、v WW = PP PP （3-19） (,) pq sim vv采用的是经典的余弦度量。 3.6 时间因素 在已有的链接预测算法中，均将历史的数据当作一个整体，即网络都是静态的。 像CN、AA、JC以及语义相似度度量等均是同等对待所有的历史链接。显然，在科 研合作网络中，作者的研究兴趣是在不断发生变化的，领域的研究热点也随着时间 不断的发生变化，而已有的算法均没有对这种变化进行考虑。类似的，在社会网络 中，网络在不断的演化中，动态加入的边与已有边所反映出来的一些信息也不尽相 同。经典马尔科夫模型49认为一个随机过程的未来状态只与当前状态有关，而与历 史状态无关。当然，k序马尔科夫模型可以考虑

4、当前状态直到前k个状态。马尔科夫 模型考虑了时间因素对于未来状态变化的影响。同样刻画了时间因素在对象演化过 程中影响的还有时间序列模型50列模型将对象的历史状态当作一个序列，然后以某 种特定的时间序列模型来反映这样一种趋势，从而能得出未来时刻的状态值。在这 里的链接预测背景中，时间序列无法应用，因为我们预测的是链接未来是否形成， 而如果仅仅把节点对之间的历史连接状态当作一个序列对待，似乎忽视了各种其它 因素。而如果将CN、AA等属性值当作序列值，得到的结果与链接形成与否无关。 在3.3、3.4以及3.5中提到的随时间t单调递增的权值函数( )Link t，( )Topo t， ( )Event

5、 t，( )Topic t均为反映相关属性与时间因素的动态相关性。在一个特定的领域， 华中科技大学硕士学位论文华中科技大学硕士学位论文 30 链接的形成与相关历史属性值的依赖程度也不一样。在时间序列模型中有两种最基 本最简单的模型即线性平均滑动模型t和指数模型 t e。在Liben14中提到的Katz度 量， 其用系数 l （1）来描述随着距离l的增加，该路径在整个结果所占的权值 的下降程度。该文中的实验指出，Katz14度量是效果最好的拓扑属性。t， t e， l 这一类系数已被实践证明在相关场合中适用，受此启发，这里给出部分( )Link t等函 数的具体形式。当然，要精确的刻画出CN、A

6、A、语义相似度、链接形成等因素受 时间因素的影响并非易事，目前还没有在链接预测中有这方面的相关模型。因此， 这里只是给出一些相对较简单，但在一定程度上能刻画出潜在影响的函数。 首先给出的就是类似Katz度量中的衰减系数 l ： t （1） 。其中为刻画相 关属性随着t的增大而受到影响的程度。 这里t表示链接发生时间离最新时间的距离。 比如如果以20012005年数据集为训练阶段数据，那么2001对应的t最大，2005对 应的t最小，即t的增长方向是从2005到2001的。这里刚好与( )Link t中随 t的增大 而增大是一个逆过来的关系，即t和 t增长的方向相反。 另外给出几个其它的权值函数

7、。1. t e。 可以控制增长幅度，也就是相关属 性受时间因素影响的程度。 2. t 3. t 这里t的增长方向和( )Link t所述的方向 相同，即从2001至2005为增长方向。 当然，上述函数中的t在具体的应用中要将具体的时间年份做一个简单的转换。 以函数t为例，2001到2005共有5年时间，那么2001对应的权值可为0.2，相应 的2002年为0.4，依次类推，具体还得由参数控制。 3.7 预测 在得到经过修正的拓扑属性、作者语义相似度后，这里将这些度量作为以节点 对为对象的一个个特征值，得到可描述该节点对特征的特征向量。 12 ,. ) n FVectorf ff=，其中 i f

8、表示单个的特征向量，也就是上述各节计算得到的各种 华中科技大学硕士学位论文华中科技大学硕士学位论文 31 度量，如CN，AA，JC，CE，(,) pq sim vv等。在此特征向量基础上，如2.1中所述， 将预测问题看作一个分类问题。每个节点对有一个特征向量FVector，另有一个反映 该节点对之间是否有链接的二元值label，其值只能为0或1。0表示没有链接，1表 示有链接。根据抽取到的DBLP上的数据集，一部分作为训练集，另一部分作为测 试集，训练得到分类器。这里采用的分类工具为开源的数据挖掘工具包Weka39。由 于分类并非最终预测算法的重点，故而具体采用的分类算法及其方法见2.1所述，

9、这 里不再详细描述。具体的实验过程及相关分析结果见第4章实验设计与分析。 3.8 算法描述 本节结合前述各节的定义，给出基于链接重要性的动态链接预测算法的详细伪 码描述。 算法输入：数据集起始、终止时间 算法输出：输入时间段内分类预测结果。包括决策树模型、混淆矩阵以及 precision、recall、F-Measure等评价值。 graphPreprocess() /对初始的科研合作网络预处理 downPaper(); /从DBLP上下载论文信息。 deleteStopSpecialWord() /删除论文语义停顿词和一些特殊的字符 simWordUnion() /将相似词或词语原型相同的归

10、为一类 getAPList(); /得到作者、 论文列表， 并存储两者之间的关系 getMaxSubGraph(); /得到最大的连通分量 trimSubGraph(); /根据相关规则对最大分量进行过滤。 返回经过各种预处理后的最大连通分量图 G。 /* featureXX(int type) 华中科技大学硕士学位论文华中科技大学硕士学位论文 32 根据type的值计算XX度量的值，其中XX分别为3.4、3.5中提及的CN、AA、 JC、CE、SS度量 type=1 按传统的定义计算 type=2 引入链接重要性对传统定义进行修正 type=3 引入时间因素对传统定义进行修正 type=4

11、结合链接重要性和时间因素对传统定义进行修正 */ featureXX(int type) if type = 1 baseMethod(); if type = 2 LinkBaseMethod(); if type = 3 TimeBaseMethod(); if type = 4 LinkTimeBaseMethod(); / linkBaseDynLinkPrediction() 最终的预测算法 linkBaseDynLinkPrediction() G= graphPreprocess(); for each pair,(1,)i ji jn / n为图的节点数 featureXX(i

12、nt type); 在得到所有,(1,)i ji jn的特征向量(,) ij VectSCN AA JC CE SS Link= 后， / ij Link表示训练集中,i j是否有链接形成。 调用决策树算法进行分类。 华中科技大学硕士学位论文华中科技大学硕士学位论文 33 整个算法共2大部分， 分别为1. 抽取数据集并建立网络， 进行相关预处理。2. 根 据得到的网络，计算节点对,i j之间的相关度量，并根据得到的度量值利用决策 树算法进行分类预测。 下面给出算法复杂度分析。 downPaper() 从DBLP下载论文信息取决于网络环境和下载的论文数量， 而对每 篇论文的具体信息提取时，如果自

13、己编写正则表达式进行提取速度很快，而如果利 用开源包htmlParser则速度相对较慢。 删除停顿词和特殊字符以及归并相似词的复杂 度与论文规模P和停顿词的规模S成正比，为( *log( )O PS。在最大连通分量求解部 分，由于采用的邻接表结构，故此部分复杂度为()O VE+，其中V表示作者数，E表 示论文数。在度量计算时，复杂度为( * * )O n npp，其中n表示经过预处理后的最 大连通分量规模，p表示每个作者平均发表的论文数。 3.9 本章小结 本章详细的描述了整个预测算法的流程。首次从两个方面给出了问题的定义， 现实中的网络和计算机的表示。接下来给出了数据预处理的方法，这一步对接

14、下来 要介绍的实验部分很关键。 本章最主要的就是提出了链接重要性的度量，该度量基于作者在文章署名列表 的距离来反映一篇文章中不同作者之间关系的紧密程度，反映到计算机表示时，即 一篇文章产生的多条边，其权值不一样。基于链接重要性，可以无缝的对已有的被 证明对预测有帮助的各种拓扑度量进行调整。链接重要性在对拓扑属性的调整过程 中，符合现实意义，且保持了这些拓扑属性原本的特性。 在语义相似度的计算过程中，将经典的VSM模型的TF-IDF进行基于特定领域 的改进。在链接重要性的基础上，提出了作者单篇论文贡献值的度量，来刻画同篇 论文描述对不同作者的贡献。结合改进的TF-IDF和单篇论文贡献值的度量，给

15、出了 最终的作者语义相似度度量。 华中科技大学硕士学位论文华中科技大学硕士学位论文 34 引入时间因素，将网络看作一个动态变化的过程。分别将可反映时间因素对各 因素度量有影响的权值调整因子融入到链接重要性、拓扑属性修正、语义相似度度 量中。 虽然这里以科研合作网（co-authorship network）为应用背景，并结合网络本身 给出相关语义度量，但其中涉及的节点相似度计算和考虑时间影响、多因素融合等 思想同样适用于各种其它的社会网络，比如在线社区、web 论坛、电子商务等等。 华中科技大学硕士学位论文华中科技大学硕士学位论文 35 4 实验设计与分析 第 3 章全面介绍了一种基于链接重要性的动态链接预测算法。本章以科研合作 网络为背景，抽取 DBLP 上数据挖掘相关会议文章，经过充分合理的数据预处理，计 算相应的度量，并基于这些度量，比较了已有的方法、基于链接重要性修正和融入 时间因素等多种方法的预测准确性，验证论文中提出算法的有效性。 4.1 实验设计 本实验一共抽取DBLP上KDD、SIGMOD、VLDB、CIKM等数据挖掘相关的 22个会议自20002006年共7年的会议文章。共有论文13727篇，17368个作者， 共形成链接关系52073个，其中不计重复有39468个链接关系。平均