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