复杂网络中的抽样链接预测

Sampling-based link prediction in complex networks

针对传统相似度算法无法预测给定顶点存在的链接问题,以抽样方法为基础,提出一种对复杂网络进行链接预测的方法,找出用户感兴趣节点的相关链接.根据用户感兴趣的节点,使用随机游走的方法,构造一个子图.设定该子图的大小使相似度估计值的误差小于给定的容错阈值.该方法仅在一个小的包含全局信息的子图上进行相似度计算,可以使计算时间大大减少.实验结果表明,算法的时间复杂度与数据集大小呈线性关系,基于局部指标的常见邻居(CN)算法、Jaccard以及PA指标算法的时间复杂度与数据集大小呈平方关系,以全局拓扑路径为基础的Katz算法的时间复杂度与数据集大小呈立方关系.

A method of predicting links in complex networks based on sampling method was proposed to find out the link corresponding to the nodes of interest to users,aiming at the problem that the traditional similarity algorithm could not predict the link of a given vertex.Firstly,a corresponding sub-graph of the nodes of interest to users was constructed by method of random walk.By setting an appropriate size of the sub-graph,the similarity error could be restricted to a given fault tolerant threshold range.Since the similarity computation of this method was only operated in a small sub graph which contained the global information,the time cost for computation was greatly reduced.As indicated,the time complexity of this algorithm is linear to the size of the data set;while the other similar algorithms based on local index,such as CN（common neighbor）,Jaccard and PA（preferential attachment）,are square to the size of the data set;for the global path based approach Katz,the time complexity is cubic to the size of the data set.