Accuracy Estimate and Optimization Techniques for SuperSimRank Computation on Massive Graphs

ZHANG Ying-long; XIA Xue-wen; YU Ying; DENG Zhi-gang

doi:10.3969/j.issn.0372-2112.2019.07.026

您当前的位置：

首页 >

文章列表页 >

Accuracy Estimate and Optimization Techniques for SuperSimRank Computation on Massive Graphs

更新时间：2025-07-16

- Accuracy Estimate and Optimization Techniques for SuperSimRank Computation on Massive Graphs
- Acta Electronica Sinica Vol. 47, Issue 7, Pages: 1591-1595(2019)
- 作者机构：
  
  1. 闽南师范大学物理与信息工程学院,福建,漳州,363000
  2. 华东交通大学软件学院,江西,南昌,330013
  3. 闽南师范大学物理与信息工程学院,福建,漳州,363000
  4. 华东交通大学软件学院,江西,南昌,330013
- 作者简介：
- 基金信息：
- DOI：10.3969/j.issn.0372-2112.2019.07.026
  CLC： TP311
- Published Online：25 July 2019，
  
  Published：2019
- 稿件说明：
移动端阅览
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：

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

Views

227

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

⁰