基于链接重要性和数据场的链接预测算法

摘要：针对现有基于节点相似性的链接预测方法忽略了网络拓扑本身链接强度的信息，带权的拓扑路径方法中权值较难确定等缺陷，提出一种基于链接重要性和数据场的链接预测算法。首先，将所有链接边赋予不同的链接权重；其次，考虑潜在链接节点间的相互影响，对部分没有链接的节点进行链接预估计；最后，利用数据场势函数计算两节点间的相似值。在典型的网络数据进行的实验结果表明，所提方法在分类指标和推荐指标中都有很好的表现：以AUC为评价指标时，比同复杂度的局部路径（LP）算法提高了3到6个百分点；以DCG为评价指标时比LP算法提高了1.5到2.5个DCG值。算法整体上提高了预测准确性，且由于参数确定简单，复杂度又不高，在实际中易于部署。

关键词：链接预测；数据场；链接重要性；节点相似性；复杂网络

中图分类号： TP391.4

文献标志码：A

Abstract： The existing link prediction methods based on node similarity usually ignore the link strength of network topology and the weight value in the typological path method with weight is difficult to set. To solve these problems， a new prediction algorithm based on link importance and data field was proposed. Firstly， this method assigned different weight for each link according to the topology graph. Secondly， it took into account the interaction between potential link nodes and preestimated the link values for the partial nodes without links. Finally， it calculated the similarity between two nodes with data field potential function. The experimental results on some typical data sets of the realworld network show that， the proposed method has good performance with both classification index and recommended index. In comparison to the Local Path （LP） algorithm with the same complexity， the proposed algorithm raises Area Under Curve （AUC） by 3 to 6 percentages， and raises Discounted Cumulative Gain （DCG） by 1.5 to 2.5 points. On the whole， it improves the prediction accuracy. Because of its easy parameter determination and low time complexity， this new approach can be deployed simply.

Key words： link prediction； data field； link importance； node similarity； complex network

0引言

自文献[1]LibenNowell等[1]首次提出社会网络链接预测的问题以来，链接预测已成为社会网络分析的热点。链接预测是通过已知的网络结构等信息预测和估计目标网络中尚未被观察到的或者在未来会出现的链接，可应用于科学研究、社会安全、行政商业决策、分子生物学的蛋白质关系预测、犯罪网络调查、各种推荐系统等，如文献[2-4]。此外，通过对链接预测的技术和方法进行研究，可以加深对于复杂网络的总体演变规律的理解，进而推动其他复杂网络研究分支的发展。

目前主流的链接预测方法主要分为基于概率模型的算法[5-9]（如文献[5-9]）、基于节点相似性的预测算法[1，10-19]（如文献[1，10-19]）。利用概率模型进行链接预测的基本思想是建立含有一组可调参数的模型，然后使用一些优化策略寻找最优的参数值，使得所得到的模型能够更好地再现真实网络的结构和关系特征。网络中两个没有链接的节点对建立链接的概率等于在这组最优参数下，它们之间建立链接的条件概率。概率模型的优势在于较高的预测精确度，同时使用了网络的结构信息和节点的属性信息；但计算的复杂度以及非普适性的参数使其应用范围受到限制。基于节点相似性算法主要基于网络的拓扑信息进行链接预测，该方法对于集聚系数较低的网络预测准确性较低，但计算简单，可扩展性良好，且可被用于实时预测任务中，因此，本文主要研究基于节点相似性的链接预测算法。很多学者对基于节点相似性的方法作了相关研究，如文献[1，10-19]，典型的方法有共同邻居（Common Neighbor， CN）算法[1]、局部路径（Local Path， LP）算法[10]和Katz（A new status index named after Katz L）[13]请明确这3个算法到底指代的哪个文献？Katz是指代文献13吗？CN指代哪个文献，LP指代哪个文献？请逐个明确。等，详细信息可参考文献[10，13，20]。以CN为基础的10余种算法都只把网络中有直接链接的表示为1，没有直接链接的表示为0，没有考虑链接的重要性信息，而现实的网络链接中显然是存在链接强度的。基于路径拓扑的相似性方法，如LP和Katz算法的权值确定不直观，且Katz的权值必须满足一定的条件，计算时间复杂度较高，每次权值的改变都需要重新计算，实际使用效率不高。

针对以上问题，本文提出了基于链接重要性和数据场的链接算法――WCDF（Weighted Complete Data Field）。该算法对现有的链接作加权处理，同时考虑了潜在链接间的影响，对一些没有链接的边进行链接预估计，最后利用数据场势函数计算两节点间的相似值，在整体上提高了预测的准确率。

1相关工作

目前，基于节点相似性的链接预测算法已有大量研究。两个节点之间相似性越大，则它们之间存在链接的可能性就越大，这是应用节点相似性进行链接预测的重要前提假设。LibenNowell等[1]另外，CN是指代文献1吗？请明确。要注意与前文的描述保持一致。提出共同邻居（CN）的方法。该方法认为如果两节点有更多的共同邻居，那么它们更倾向于建立链接，因此考虑了节点的共同邻居这一拓扑属性。Zhou等[10]提出一种新的基于节点相似性的资源分配（Resource Allocation， RA）算法，比其他基于节点相似方法[1，12]有更好的实验结果（如文献[1]和[12]）。该方法从网络资源分配的角度提出新的RA指标，对于网络中没有直接相连的两个节点x和y，它们的共同邻居可以成为媒介，协助建立链接。当网络的平均度较大的时候RA效果明显。Lü等[12]提出LP局部路径指标，该算法是在共同邻居CN指标的基础上考虑了三阶邻居的贡献，利用一个参数来控制三阶路径的作用大小。Katz[13]提出的Katz算法考虑所有的路径数，对于短路径赋予较大的权重，对于长路径赋予较小的权重。Katz算法提出的权重不易确定，同时Katz中的权值取值须小于邻接矩阵A最大特征值的倒数，这样才可以保证数列的收敛性，且计算复杂度较高。

对于链接强度的研究主要集中在具体网络节点的属性上，很少有文献研究从网络拓扑本身的角度挖掘权重信息。部分学者在链接强度上作了相关的工作。孙浩[21]提出了基于时间信息的在线社交网络的链接预测框架，在该链接预测框架中，使用核函数来提取网络的时间特征来形成基于时间信息的加权概要图，在时间局部性和时间再现性基础上再使用扩展的关系贝叶斯分类器来进行链接预测。李玉华等[22]给出一种基于链接重要性的动态链接预测方法，引入链接重要性的度量，对拓扑属性和语义相似度等属性进行修正，考虑动态性以反映时间因素对链接形成的影响。Murata等[23]针对于社交网络中两个节点间的事务次数作为链接的权值，进行链接预测。

综上所述，现在的基于节点相似性的算法，如CN、RA等算法没有考虑链接权重信息，部分学者如孙浩[21]、李玉华等[22]借助网络的特有属性信息，针对特定网络为链接加权处理，然而网络的私有属性通常不容易获得，并且研究的普适性不强；现有的基于带权路径的典型算法，如LP、Katz中的权值确定通常采用简单的试探，很难达到最优解。考虑到基于节点相似的算法有简单，可扩展性强，又同时又一定的提升改进空间，本文主要针对基于节点相似算法的不足加以改进，提升预测的准确率。

总之，在两个评价指标的实验中，WCDF算法与其他4种方法算法相比整体上有优势。与已有算法相比，本文算法还有如下优点：

1）与具有相同时间复杂度的LP算法相比，WCDF整体提高了准确率，比较高时间复杂度的Katz方法略有优势，并且WCDF参数的确定简单，容易求出次优解。而Katz的参数不仅有限制，而且每次参数的变化Katz都要重新计算，调整参数时间代价较高，而WCDF改变权值时和LP一样，不需要重新计算路径数信息。

2）WCDF算法在以AUC和DCG两种衡量指标中都有很好的整体效果，而Katz在以AUC为衡量指标时占优势，以DCG为衡量指标时不占优势，LP和RA在以AUC为衡量指标时不占优势，在以DCG为衡量指标时较占优势。

3）原有的LP、Katz算法中的β值没有固定的区间，不稳定，很难确定出优解，而且在Katz算法中β的取值须小于邻接矩阵A最大特征值的倒数，这样才可以保证数列的收敛性，每次参数的改变都需要重新计算，调整参数时间代价很大。WCDF算法参数的确定简单、直观：当参数σ达到一定的值后在很长区间内趋于稳定，采用几次简单的试探便能够在一定区间内找到很好的次优解，参数确定更直观，且参数的改变不需要重新计算路径数，调整参数时代价小。

4结语

针对已有基于节点相似性的链接预测方法的缺陷，提出一种基于链接重要性和数据场的链接预测方法。该方法从邻居节点的角度考虑了链接重要性的影响，同时在已有算法的基础上对没有直接相连的节点之间进行链接可能性进行预估计，且提出利用数据之间的吸引力来计算不同节点之间的相似性。本文方法在不增加时间复杂度的情况下，与其他算法相比，整体上提高了准确率，并且参数调节简单、直观，代价小，有一定的实用价值。但新方法中暂时只考虑了两节点间的拓扑信息，而节点的活跃性信息还没有计算在内，下一步工作将加入节点的活跃信息以及其他网络属性特征来计算节点相似度。

参考文献：

[1]LIBENNOWELL D， KLEINBERG J. The link prediction problem for social networks [J]. Journal of the American Society for Information Science and Technology， 2007， 58（7）： 1019-1031.

[2]HUANG Z， LI X， CHEN H. Link prediction approach to collaborative filtering [C]// JCDL05： Proceedings of the 5th ACM/IEEECS Joint Conference on Digital Libraries. Piscataway： IEEE Press， 2005： 141-142.

[3]BISCHOFF K， FIRAN C， GEORGESCU M. Social knowledgedriven music hit prediction [C]// ADMA 2009： Proceedings of the 5th International Conference on Advanced Data Mining and Applications. Berlin： Springer， 2009： 43-54.

[4]PAVLOV M， ICHISE R. Finding experts by link prediction in coauthorship networks [EB/OL]. [20140115]. http：//sunsite.informatik.rwthaachen.de/Publications/CEURWS/Vol290/paper04.pdf.

[5]JEH G， WIDOM J， SIMRAN K. A measure of structural context similarity [C]// Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York， ACM Press， 2002： 538-543.

[6]BLONDEL V D， GAJARDO A， HEYMANS M， et al. A measure of similarity between graph vertices： applications to synonym extraction and Web searching [J]. SIAM Review， 2004， 46（4）： 647-666.

[7]SARUKKAI R R. Link prediction and path analysis using Markov chains [J]. Computer Networks， 2003， 33（6）： 377-386.

[8]FRIEDMAN N， GETOOR L， KOLLER D， et al. Learning probabilistic relational models [C]// IJCAI99： Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. San Francisco： Morgan Kaufmann Publishers， 1999： 1300-1309.

[9]HECKERMAN D， MEEK C， KOLLER D. Probabilistic entityrelationship models， PRMs， and plate models [C]// Proceedings of the ICML2004 Workshop on Statistical Relational Learning and its Connections to Other Fields. Banff： [s.n.]， 2004： 55-60.

[10]ZHOU T， L L， ZHANG Y C. Predicting missing links via local information [J]. The European Physical Journal B， 2009， 71（4）： 623-630.

[11]DONG Y， KE Q， WU B. Link prediction based on node similarity [J]. Computer Science， 2011， 38（7）： 162-199.（东昱晓，柯庆，吴斌.基于节点相似性的链接预测[J].计算机科学，2011，38（7）：162-199.）

[12]L L， JIN C H， ZHOU T. Similarity index based on local paths for link prediction of complex networks [J]. Physical Review E， 2009， 80（4）： 046122.

[13]KATZ L. A new status index derived from sociometric analysis [J]. Psychometrika， 1953， 18（1）： 39-43.

[14]SHEN Y. Link prediction in complex networks [D]. Guangzhou： South China University of Technology， 2011.（沈勇明.复杂网络链接预测[D].广州：华南理工大学，2011.）

[15]TENG Z. Research on link prediction for dynamic networks [D]. Jinan： Shandong University， 2012.（滕兆明.动态多维社会网络链接预测研究[D].济南：山东大学，2012.）

[16]YIN H. Research on link prediction for social networks [D]. Changchun： Jilin University， 2012.（殷涵.社会网络链接预测研究[D].长春：吉林大学，2012.）

[17]ZHAO C. Link prediction for social networks [D]. Harbin： Harbin Institute of Technology， 2012.（赵婵媛.社会网络链接算法研究[D].哈尔滨：哈尔滨工业大学，2012.）

[18]GAO S， DENOYER L， GALLINARI P. Temporal link prediction by integrating content and structure information [C]// Proceedings of the 20th ACM International Conference on Information and Knowledge Management. New York： ACM Press， 2011： 1169-1174.

[19]CUI A， FU Y， SHANG M， et al. The local structure of complex networks sprung up： common neighbor drive network evolution [J]. Acta Physica Sinica， 2011， 60（3）： 803-808.（崔爱香，傅彦，尚明生，等.复杂网络局部结构的涌现：共同邻居驱动网络演化[J].物理学报，2011，60（3）：803-808.）

[20]ADAMIC L A， ADAR E. Friends and neighbors on the Web [J]. Social Networks， 2003， 25（3）： 211-230.

[21]SUN H. Research on link prediction based on transactional information [D]. Qinhuangdao： Yanshan University， 2010.（孙浩.基于事物信息的链接预测算法研究[D].秦皇岛：燕山大学，2010.）

[22]LI Y， XIAO H， LI D， et al. Research of dynamic link prediction method based on link importance [J]. Journal of Computer Research and Development， 2011，48（z2）： 40-46.（李玉华，肖海岭，李栋才，等.基于链接重要性的动态链接预测方法研究[J].计算机研究与发展，2011，48（z2）：40-46.）

[23]MURATA T， SAKIKO M. Link prediction of social networks based on weighted proximity measures [C]// Proceedings of the 2007 IEEE/WIC/ACM International Conference on Web Intelligence. Washington， DC： IEEE Computer Society， 2007： 86-88.

[24]GRANOVETTER M S. The strength of weak ties [J]. Journal of American Sociology， 1973， 78（6）： 1368-1178.

[25]WATTS D. Network dynamics between order and disorder [M]. CHEN Y， translate. Beijing： China Renmin University Press， 2006： 14-17.（WATTS D.有序与无序之间的网络动力学[M].陈禹，译.北京：中国人民大学出版社，2006：14-17.）

[26]TAN C， TANG J， SUN J， et al. Social action tracking via noise tolerant timevarying factor graphs [C]// KDD10： Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM Press， 2010： 1049-1058.