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

Weiren Yu; Julie A. McCann

doi:10.3115/v1/P15-2054

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

Weiren Yu, Julie A. McCann

College of Engineering and Physical Sciences

Research output: Chapter in Book/Published conference output › Conference publication

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 language	English
Title of host publication	Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Short Papers)
Publisher	Association for Computational Linguistics
Pages	327-334
Number of pages	8
DOIs	https://doi.org/10.3115/v1/P15-2054
Publication status	Published - 2015
Event	53rd Annual Meeting of the Association for Computational Linguistics / 7th International Joint Conference on Natural Language Processing - Beijing, China Duration: 26 Jul 2015 → 31 Jul 2015

Conference

Conference	53rd Annual Meeting of the Association for Computational Linguistics / 7th International Joint Conference on Natural Language Processing
Abbreviated title	ALC IJCNPL 2015
Country/Territory	China
City	Beijing
Period	26/07/15 → 31/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.

Access to Document

10.3115/v1/P15-2054Licence: CC BY-NC-SA 3.0

Co-Simmate_quick retrieving all pairwise co-Simrank scores
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.
Accepted author manuscript, 121 KBLicence: CC BY-NC-SA 3.0

Cite this

@inproceedings{585b59b9e5964c87b2f2476883f96f79,

title = "Co-Simmate : quick retrieving all pairwise co-Simrank scores",

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.",

author = "Weiren Yu and McCann, {Julie A.}",

note = "ACL materials are Copyright {\textcopyright} 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. ; 53rd Annual Meeting of the Association for Computational Linguistics / 7th International Joint Conference on Natural Language Processing, ALC IJCNPL 2015 ; Conference date: 26-07-2015 Through 31-07-2015",

year = "2015",

doi = "10.3115/v1/P15-2054",

language = "English",

pages = "327--334",

booktitle = "Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Short Papers)",

publisher = "Association for Computational Linguistics",

}

Yu, W & McCann, JA 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, pp. 327-334, 53rd Annual Meeting of the Association for Computational Linguistics / 7th International Joint Conference on Natural Language Processing, Beijing, China, 26/07/15. https://doi.org/10.3115/v1/P15-2054

Co-Simmate : quick retrieving all pairwise co-Simrank scores. / Yu, Weiren; McCann, Julie A.
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, 2015. p. 327-334.

Research output: Chapter in Book/Published conference output › Conference publication

TY - GEN

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

AU - Yu, Weiren

AU - McCann, Julie A.

N1 - 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.

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

UR - http://www.aclweb.org/anthology/P15-2054

U2 - 10.3115/v1/P15-2054

DO - 10.3115/v1/P15-2054

M3 - Conference publication

SP - 327

EP - 334

BT - Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Short Papers)

PB - Association for Computational Linguistics

T2 - 53rd Annual Meeting of the Association for Computational Linguistics / 7th International Joint Conference on Natural Language Processing

Y2 - 26 July 2015 through 31 July 2015

ER -

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

Abstract

Conference

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this