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

Weiren Yu, Julie A. McCann

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.
Original languageEnglish
Title of host publicationProceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Short Papers)
PublisherAssociation for Computational Linguistics
Pages327-334
Number of pages8
DOIs
Publication statusPublished - 2015
Event53rd Annual Meeting of the Association for Computational Linguistics / 7th International Joint Conference on Natural Language Processing - Beijing, China
Duration: 26 Jul 201531 Jul 2015

Conference

Conference53rd Annual Meeting of the Association for Computational Linguistics / 7th International Joint Conference on Natural Language Processing
Abbreviated titleALC IJCNPL 2015
CountryChina
CityBeijing
Period26/07/1531/07/15

Bibliographical note

ACL materials are Copyright © 1963–2019 ACL; other materials are copyrighted by their respective copyright holders. Materials prior to 2016 here are licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 International License.

Fingerprint Dive into the research topics of 'Co-Simmate : quick retrieving all pairwise co-Simrank scores'. Together they form a unique fingerprint.

  • Cite this

    Yu, W., & McCann, J. 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) (pp. 327-334). Association for Computational Linguistics. https://doi.org/10.3115/v1/P15-2054