...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Knowledge and Data Engineering, IEEE Transactions on >Fast All-Pairs SimRank Assessment on Large Graphs and Bipartite Domains
【24h】

Fast All-Pairs SimRank Assessment on Large Graphs and Bipartite Domains

机译：大图和二分域上的快速全对SimRank评估

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

SimRank is a powerful model for assessing vertex-pair similarities in a graph. It follows the concept that two vertices are similar if they are referenced by similar vertices. The prior work exploits partial sums memoization to compute SimRank in time on a graph of vertices and edges, for iterations. However, computations among different partial sums may have redundancy. Besides, to guarantee a given accuracy , the existing SimRank needs iterations, where is a damping factor, but the geometric rate of convergence is slow if a high accuracy is expected. In this paper, (1) a novel clustering strategy is proposed to eliminate duplicate computations occurring in partial sums, - nd an efficient algorithm is then devised to accelerate SimRank computation to time, where is typically much smaller than . (2) A new differential SimRank equation is proposed, which can represent the SimRank matrix as an exponential sum of transition matrices, as opposed to the geometric sum of the conventional counterpart. This leads to a further speedup in the convergence rate of SimRank iterations. (3) In bipartite domains, a novel finer-grained partial max clustering method is developed to speed up the computation of the Minimax SimRank variation from to time, where is the number of edges in a reduced graph after edge clustering, which can be typically much smaller than . Usi
机译：SimRank是用于评估图中顶点对相似性的强大模型。遵循这样的概念：如果两个顶点由相似的顶点引用，则它们是相似的。先前的工作利用部分总和记忆来在顶点和边图上及时计算SimRank，以进行迭代。但是，不同部分和之间的计算可能会有冗余。此外，为了保证给定的精度，现有的SimRank需要进行迭代，其中i是阻尼因子，但是如果期望很高的精度，则几何收敛速度会很慢。在本文中，（1）提出了一种新颖的聚类策略，以消除部分和中出现的重复计算，然后设计了一种有效的算法来将SimRank计算加速到一定时间，该时间通常小于。 （2）提出了一个新的微分SimRank方程，该方程可以将SimRank矩阵表示为过渡矩阵的指数和，而不是常规对应物的几何和。这导致SimRank迭代的收敛速度进一步加快。 （3）在二分域中，开发了一种新颖的细粒度的部分最大聚类方法，以加快计算Minimax SimRank变化的时间，其中，是边缘聚类后的约简图中的边缘数，通常为比...小得多。乌西

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号