大图上的SuperSimRank近似计算方法

张应龙; 夏学文; 余鹰; 邓志刚

doi:10.3969/j.issn.0372-2112.2019.07.026

您当前的位置：

首页 >

文章列表页 >

大图上的SuperSimRank近似计算方法

科研通信 | 更新时间：2025-07-16

- 大图上的SuperSimRank近似计算方法
- Accuracy Estimate and Optimization Techniques for SuperSimRank Computation on Massive Graphs
- 电子学报 2019年47卷第7期页码：1591-1595
- 作者机构：
  
  1. 闽南师范大学物理与信息工程学院,福建,漳州,363000
  2. 华东交通大学软件学院,江西,南昌,330013
  3. 闽南师范大学物理与信息工程学院,福建,漳州,363000
  4. 华东交通大学软件学院,江西,南昌,330013
- 作者简介：
- 基金信息：
  
  国家自然科学基金 (No.61762036，No.61663009，No.61563016）;江西省自然科学基金 (No.20171BAB202012，No.20181BAB202023）;江西省交通厅科研项目 (No.2017D0038）;江西省教育厅科技项目 (No.GJJ180322）
- DOI：10.3969/j.issn.0372-2112.2019.07.026
  中图分类号： TP311
- 网络出版：2019-07-25，
  
  纸质出版：2019
- 稿件说明：
移动端阅览
张应龙, 夏学文, 余鹰, 等. 大图上的SuperSimRank近似计算方法[J]. 电子学报, 2019,47(7):1591-1595.

ZHANG Ying-long, XIA Xue-wen, YU Ying, et al. Accuracy Estimate and Optimization Techniques for SuperSimRank Computation on Massive Graphs[J]. Acta Electronica Sinica, 2019, 47(7): 1591-1595.
张应龙, 夏学文, 余鹰, 等. 大图上的SuperSimRank近似计算方法[J]. 电子学报, 2019,47(7):1591-1595. DOI： 10.3969/j.issn.0372-2112.2019.07.026.

ZHANG Ying-long, XIA Xue-wen, YU Ying, et al. Accuracy Estimate and Optimization Techniques for SuperSimRank Computation on Massive Graphs[J]. Acta Electronica Sinica, 2019, 47(7): 1591-1595. DOI： 10.3969/j.issn.0372-2112.2019.07.026.

摘要

网络数据具有规模大的特点，而基于关系的相似度计算复杂度高，因此大图上的相似度计算具有很大挑战.文章针对一个新的相似度度量SuperSimRank在大图上的优化计算问题展开研究.首先提出了阈值过滤技术，使得在计算过程中忽略那些对SuperSimRank值影响较小但消耗计算资源的路径值，并通过严格数学证明论证了近似值和准确值的误差；然后在此基础上提出了高效的外存算法，该算法避免了随机访问文件而是通过顺序的读写文件，极大的减少了I/O代价；最后实验验证了算法的有效性.

Abstract

Due to the high computational cost and space cost in computing node similarity

it is a challenge when it comes to efficiently computing the similarity on big graphs.In this paper

the following problem will be resolved:how to fast compute SuperSimRank similarity on massive graphs using a single PC.A threshold sieving technology and an external algorithm are introduced.With the help of threshold sieving technology

our external algorithm can efficiently compute the similarity on massive graphs.Experimental results demonstrate the efficiency of the computation.

关键词

Keywords

references

浏览量

227

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据