Co-Simmate : quick retrieving all pairwise co-Simrank scores

Yu, Weiren and McCann, Julie A. (2015). Co-Simmate : quick retrieving all pairwise co-Simrank scores. IN: Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Short Papers). Association for Computational Linguistics.

Abstract

Co-Simrank is a useful Simrank-like measure of similarity based on graph structure. The existing method iteratively computes each pair of Co-Simrank score from a dot product of two Pagerank vectors, entailing O(log(1/e)*n^3) time to compute all pairs of Co-Simranks in a graph with n nodes, to attain a desired accuracy e. In this study, we devise a model, Co-Simmate, to speed up the retrieval of all pairs of Co-Simranks to O(log2 (log(1/e))*n^3) time. Moreover, we show the optimality of Co-Simmate among other hop-(u^k) variations, and integrate it with a matrix decomposition based method on singular graphs to attain higher efficiency. The viable experiments verify the superiority of Co-Simmate to others.

Divisions: Engineering & Applied Sciences
Engineering & Applied Sciences > Systems analytics research institute (SARI)
Additional Information: © 2015 Association for Computational Linguistics.Co-Simrank is a useful Simrank-like mea-sure of similarity based on graph structure. The existing method iteratively computes each pair of Co-Simrank score from a dot product of two Pagerank vectors, entailing C(log(l/e)n3) time to compute all pairs of Co-Simranks in a graph with n nodes, to attain a desired accuracy e. In this study, we devise a model, Co-Simmate, to speed up the retrieval of all pairs of Co-Simranks to C(log2(log(l/e))n3) time. Moreover, we show the optimality of Co-Simmate among other hop-(-ufc) variations, and inte-grate it with a matrix decomposition based method on singular graphs to attain higher efficiency. The viable experiments verify the superiority of Co-Simmate to others.
Event Title: 53rd Annual Meeting of the Association for Computational Linguistics / 7th International Joint Conference on Natural Language Processing
Event Type: Other
Event Dates: 2015-07-26 - 2015-07-31
Published Date: 2015
Authors: Yu, Weiren
McCann, Julie A.

Download

[img]

Version: Accepted Version


Export / Share Citation


Statistics

Additional statistics for this record