社会网络链接预测算法探讨范文

1相关研究

目前，社会网络链接预测研究主要分为如下3个方向：

（1）基于节点相似度的链接预测。根据预先设定好的相似度评分函数对节点间的相似度进行打分，然后根据打分值将所有没被发现的链接进行排序，相似度分数越高则该两个节点存在链接的可能性越大。该方法的缺点是考虑网络拓扑结构，而忽视了网络的其它因素，例如时间因素，从而导致预测结果差强人意。

（2）基于概率模型的链接预测。首先利用社会网络中的节点或者边构造一个统计模型，然后利用该统计模型进行链接预测。统计模型构建是该方法的核心，将直接影响后续链接预测的结果。该方法主要有两个缺点：一是获取节点信息的难度很大，无法获得足够的先验知识，因此统计模型构建非常困难；二是算法的复杂性比较高，因此在实际应用中具有一定难度。

（3）基于监督学习的链接预测。根据已知的网络信息获取链接关系，并在这些链接关系中提取相关的特征属性构建分类器，然后根据该分类器对未知网络进行二类划分，即判断链接关系存在或者不存在。该方法的主要缺点是社会网络中的节点不是简单的统计上的独立采样点，节点之间存在着联系，并不满足传统的机器学习条件。近几年，研究者对链接预测的研究越来越深入，并不断加入影响算法的新因素。除实现基本的发现隐藏链接的任务外，还需要考虑新的细节。例如，可以考虑时间演化尺度下社会网络中的链接预测。随着时间的推移，社会网络中节点之间的链接在不断变化，可能会有新链接的产生，也可能有旧链接的消亡，因此链接预测需要考虑时间因素。

2算法提出

共有邻居相似度算法是一种经典的基于节点相似度的链接预测方法，该算法利用两个节点共有邻居的多少来确定链接存在的概率，即共有邻居越多链接存在的概率越高，反之则越低。例如，如果两个人之间的学历、爱好和收入都比较相近，就可以认为他们之间的相似度较高。然而该算法仅考虑共有邻居的数目，没有考虑其它因素（例如时间因素），显然是不全面的。因此，本文尝试将时间因素融入到共有邻居相似度算法，提出了新的节点相似度评价标准。

2．1问题定义为简化问题，只考虑无向社会网络，首先给出无向社会网络的定义。定义1：无向社会网络可以定义为G＝＜V，E＞，其中V是节点的集合，E是边的集合。上述定义是基于传统的静态社会网络，但社会网络是动态变化的。考虑社会网络的时间属性，提出了基于不同时刻快照的社会网络定义。定义2：无向社会网络可以定义为由不同时刻的快照所组成的图序列G＝＜GΔt1，GΔt2，…，GΔtn＞，其中GΔti是时间Δti的网络图，同时满足1≤i≤n。然后再给出基于定义2的链接预测定义。

2．2共有邻居相似度共有邻居相似度认为如果两个节点拥有越多的共同节点，则这两个节点越相似。定义4：对于节点u和节点v，其共有邻居相似度定义如下。共有邻居相似度算法简单高效，但是仅仅依靠共有邻居的多少来判断两个节点的相似度显然是不够的，需要考虑社会网络的时间属性。

2．3结合时间属性的链接预测算法设计移动平均线是金融学中用来从短期的噪声数据中提取金融长期发展趋势的一种手段，它通过求取某指标值在某段时间内的平均值来预测未来发展趋势。这里采用移动平均线的原理来提取平均共有邻居相似度。定义5：假定有n个时间点的社会网络快照，对于节点u和节点v，其平均共有邻居相似度定义如下。输出：节点u和节点v的相似度算法描述：（1）找出节点u和节点v在所有子图上的共有邻居；（2）根据定义5计算节点u和节点v的平均共有邻居相似度。算法完毕。3结语社会网络链接预测是数据挖掘的一个新的研究方向。链接预测侧重于挖掘社会网络中所隐藏的关系模式，具有重大的研究意义。考虑节点的时间属性，采用平均共有邻居相似度来平滑节点的动态变化，可以有效去除噪声数据。本文将共有邻居相似算法与时间属性相结合，提出了结合时间属性的链接预测算法。

作者：仇丽青陈卓艳单位：山东科技大学信息科学与工程学院