• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Neural Networks and Learning Systems, IEEE Transactions on >Backtrackless Walks on a Graph
【24h】

Backtrackless Walks on a Graph

机译：图上的无轨走

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

摘要

The aim of this paper is to explore the use of backtrackless walks and prime cycles for characterizing both labeled and unlabeled graphs. The reason for using backtrackless walks and prime cycles is that they avoid tottering, and can increase the discriminative power of the resulting graph representation. However, the use of such methods is limited in practice because of their computational cost. In this paper, we present efficient methods for computing graph kernels, which are based on backtrackless walks in a labeled graph and whose worst case running time is the same as that of kernels based on random walks. For clustering unlabeled graphs, we construct feature vectors using Ihara coefficients, since these coefficients are related to the frequencies of prime cycles in the graph. To efficiently compute the low order coefficients, we present an $O(vert Vvert^{3})$ algorithm which is better than the $O(vert Vvert^{6})$ worst case running time of previously known algorithms. In the experimental evaluation, we apply the proposed method to clustering both labeled and unlabeled graphs. The results show that using backtrackless walks and prime cycles instead of random walks can increase the accuracy of recognition.
机译：本文的目的是探索无回溯步幅和质数周期用于标记和未标记图的特征。使用无回溯步道和质数周期的原因是，它们避免了摆动，并可以提高所得图形表示的判别力。但是，由于其计算成本，实际上限制了此类方法的使用。在本文中，我们提出了一种有效的计算图形内核的方法，该方法基于标记图中的无回溯游走，其最坏情况下的运行时间与基于随机游走的内核的运行时间相同。对于聚类未标记图，我们使用Ihara系数构造特征向量，因为这些系数与图中的质数周期频率有关。为了有效地计算低阶系数，我们提出了一种$ O（vert Vvert ^ {3}）$算法，该算法优于以前已知算法的$ O（vert Vvert ^ {6}）$最坏情况下的运行时间。在实验评估中，我们将提出的方法应用于标记和未标记图的聚类。结果表明，使用无回溯游走和质数周期代替随机游走可以提高识别的准确性。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号