一种基于LSH技术的链路预测方法

黄寿孟，夏王霞

（三亚学院信息与智能工程学院 海南 三亚 572022）

1 引言

社交网络可以用来描述现实社会中的实际网络，它包括人与人之间的社会关系，物种之间的捕食关系，科学研究中的合作关系等[1]。大量研究已经表明，在真实世界中各种不同社交网络具有许多共同的结构特征，例如小世界性质[2]、无标度性[3]、社团结构等[4-6]。网络中的链路预测是指如何通过已知的网络结构等信息，预测网络中尚未产生连接的两个节点之间产生连接的可能性。网络中的顶点代表用户，边代表用户关系，链路预测问题正是对用户未来关系的分析。

2 相关工作

2.1 局部敏感HASH技术

LSH即Locality Sensitive hash，用来解决在海量数据中进行相似性查找的问题，以图片搜索为例，用户向百度图搜提交待搜索图片，百度图搜将相似的图片返回展示。要实现这样一个应用，需要考虑以下几个步骤。

（1）提取用户提交的图片特征，即将提交图片转换成一个特征向量；

（2）预先将所有收集到的图片进行特征提取；

（3）把步骤（1）中提取的特征与步骤（2）中的特征集合，进行比对，并记录比对的相似值；

（4）对相似值由大到小排序，返回相似度最高的作为检索结果。

步骤（1）（2）是一个图片特征提取的问题，与LSH无关。LSH主要解决步骤（3）（4），在海量特征集中找到相似特征。那么，局部敏感HASH函数必须满足如下条件。

（1）进行相似性搜索时，在概率上可以保证返回值的相似性；

（2）函数族中的各函数，返回值在概率上相互独立，概率独立可以带来统计独立，满足叠加多个函数，提高查准率和通过组合能够避免伪正例、伪反例的好处；……