电子学报 ›› 2019, Vol. 47 ›› Issue (7): 1591-1595.DOI: 10.3969/j.issn.0372-2112.2019.07.026

• 科研通信 • 上一篇    下一篇

大图上的SuperSimRank近似计算方法

张应龙1,2, 夏学文1,2, 余鹰2, 邓志刚2   

  1. 1. 闽南师范大学物理与信息工程学院, 福建漳州 363000;
    2. 华东交通大学软件学院, 江西南昌 330013
  • 收稿日期:2018-01-22 修回日期:2019-01-15 出版日期:2019-07-25
  • 作者简介:张应龙 男,1979年1月生.博士,现为闽南师范大学副教授.从事网络分析与挖掘的有关研究.E-mail:zhang_yinglong@126com
  • 基金资助:
    国家自然科学基金(No.61762036,No.61663009,No.61563016); 江西省自然科学基金(No.20171BAB202012,No.20181BAB202023); 江西省交通厅科研项目(No.2017D0038); 江西省教育厅科技项目(No.GJJ180322)

Accuracy Estimate and Optimization Techniques for SuperSimRank Computation on Massive Graphs

ZHANG Ying-long1,2, XIA Xue-wen1,2, YU Ying2, DENG Zhi-gang2   

  1. 1. School of Physics and Information Engineering, Minnan Normal University, Zhangzhou, Fujian 363000, China;
    2. School of Software, East China Jiaotong University, Nanchang, Jiangxi 330013, China
  • Received:2018-01-22 Revised:2019-01-15 Online:2019-07-25 Published:2019-07-25

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

关键词: SuperSimRank, 节点相似度, 大图

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.

Key words: SuperSimRank, nodes similarity, big graph

中图分类号: