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

发布时间：2018-12-27 16:46

【摘要】：针对传统相似度算法无法预测给定顶点存在的链接问题,以抽样方法为基础,提出一种对复杂网络进行链接预测的方法,找出用户感兴趣节点的相关链接.根据用户感兴趣的节点,使用随机游走的方法,构造一个子图.设定该子图的大小使相似度估计值的误差小于给定的容错阈值.该方法仅在一个小的包含全局信息的子图上进行相似度计算,可以使计算时间大大减少.实验结果表明,算法的时间复杂度与数据集大小呈线性关系,基于局部指标的常见邻居(CN)算法、Jaccard以及PA指标算法的时间复杂度与数据集大小呈平方关系,以全局拓扑路径为基础的Katz算法的时间复杂度与数据集大小呈立方关系.
[Abstract]:In view of the fact that the traditional similarity algorithm can not predict the link problem of a given vertex, based on the sampling method, a link prediction method for complex networks is proposed to find the relevant links of the nodes of interest to users. According to the nodes of interest to the user, a subgraph is constructed by using the random walk method. The size of the subgraph is set so that the error of similarity estimation is less than the given fault tolerance threshold. This method only computes the similarity on a small subgraph containing global information, which can greatly reduce the computation time. The experimental results show that the time complexity of the algorithm is linearly related to the size of the dataset, and the time complexity of the common neighbor (CN) algorithm based on the local index, the time complexity of the Jaccard and PA index algorithm is square to the size of the data set. The time complexity of the Katz algorithm based on the global topological path is cubic to the size of the dataset.
【作者单位】： 南京航空航天大学计算机科学与技术学院;扬州大学信息工程学院;
【基金】：国家自然科学基金资助项目(61379066)
【分类号】：O157.5

【相似文献】

相关期刊论文 前10条

1 吴迪;周利娟;林鸿飞;;基于随机游走的就业推荐系统研究与实现[J];广西师范大学学报(自然科学版);2011年01期

2 苏浩航;张义门;张玉明;解敏;满进财;;基于改进的压缩式随机游走算法对静态电源/地网的模拟[J];计算物理;2007年06期

3 宋锐;汤建勋;周健;;工作电流对二频机抖激光陀螺角随机游走影响的研究[J];激光杂志;2010年02期

4 周持中;一类具有吸收点的平面随机游走[J];岳阳大学学报;1996年02期

5 雷钰丽;李阳;王崇骏;刘红星;谢俊元;;基于权重的马尔可夫随机游走相似度度量的实体识别方法[J];河北师范大学学报(自然科学版);2010年01期

6 俞琰;邱广华;;基于局部随机游走的在线社交网络朋友推荐算法[J];系统工程;2013年02期

7 何建军;李仁发;;改进的随机游走模型节点排序方法[J];计算机工程与应用;2011年12期

8 邓贵仕,赖宝全;反馈式随机游走模型及其在股票投资中应用[J];大连理工大学学报;2004年06期

9 戴颖;;深圳股票市场的随机游走检验[J];商业经济;2005年11期

10 周军军;王明文;何世柱;石松;;基于随机游走和聚类平滑的协同过滤推荐算法[J];广西师范大学学报(自然科学版);2011年01期

相关会议论文 前3条

1 郑伟;王朝坤;刘璋;王建民;;一种基于随机游走模型的多标签分类算法[A];NDBC2010第27届中国数据库学术会议论文集A辑一[C];2010年

2 朱松豪;罗青青;梁志伟;;一种改进图像标注的新方法[A];第24届中国控制与决策会议论文集[C];2012年

3 燕飞;张铭;谭裕韦;唐建;邓志鸿;;综合社会行动者兴趣和网络拓扑的社区发现方法[A];NDBC2010第27届中国数据库学术会议论文集(B辑)[C];2010年

相关重要报纸文章 前1条

1 长盛基金管理有限公司研究部副总监 李骥;投资自己熟悉的股票[N];证券时报;2006年

相关博士学位论文 前6条

1 邓凯英;复杂网络搜索策略及相关模型的数值方法[D];东北师范大学;2015年

2 徐晓华;图上的随机游走学习[D];南京航空航天大学;2008年

3 孙甲申;基于主题模型和随机游走的标签技术研究[D];北京邮电大学;2013年

4 吕强;面向高性能和强表达力的自动规划[D];中国科学技术大学;2013年

5 赵学华;统计网络模型若干关键问题研究[D];吉林大学;2014年

6 廖振;基于查询点击核心图的查询推荐问题研究[D];南开大学;2013年

相关硕士学位论文 前10条

1 何岱洧;Z~d上使Schramm的上界达到的旋转配置[D];复旦大学;2014年

2 田新春;回火老化效应及其扩散方程[D];兰州大学;2015年

3 鞠薇;基于随机游走和图割算法的PET-CT肺肿瘤分割[D];苏州大学;2015年

4 祝霖;基于随机游走的动态社团划分算法[D];上海交通大学;2015年

5 孙星;基于部分吸收随机游走的协同显著性检测[D];大连理工大学;2015年

6 宋文静;基于多条随机游走的图像检索[D];河南大学;2015年

7 汪帮菊;基于随机游走的复杂网络聚类算法研究[D];安徽大学;2016年

8 兰佳妮;基于分组—偏向随机游走的闪存地址映射及磨损均衡算法研究[D];西南交通大学;2016年

9 金连宝;基于分层信息融合和随机游走的显著性检测[D];南昌航空大学;2016年

10 冯维思;多属性随机游走在社会网络中的应用[D];西南大学;2016年

，

本文编号：2393331