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

Fingerprint

Decomposition
Experiments

Bibliographical note

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

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.
Yu, Weiren ; McCann, Julie A. / Co-Simmate : quick retrieving all pairwise co-Simrank scores. 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. pp. 327-334
@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 = "{\circledC} 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.",
year = "2015",
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.

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/Report/Conference proceedingConference contribution

TY - GEN

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

AU - Yu, Weiren

AU - McCann, Julie A.

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

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

M3 - Conference contribution

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

ER -

Yu W, McCann JA. 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. 2015. p. 327-334