The Library
Efficient pairwise penetrating-rank similarity retrieval
Tools
Yu, Weiren, McCann, Julie and Zhang, Chengyuan (2019) Efficient pairwise penetrating-rank similarity retrieval. ACM Transactions on the Web, 13 (4). pp. 1-52. doi:10.1145/3368616 ISSN 1559-1131.
|
PDF
WRAP-efficient-pairwise-penetrating-rank-retrieval-Yu-2019.pdf - Accepted Version - Requires a PDF viewer. Download (1472Kb) | Preview |
Official URL: https://doi.org/10.1145/3368616
Abstract
Many web applications demand a measure of similarity between two entities, such as collaborative filtering, web document ranking, linkage prediction, and anomaly detection. P-Rank (Penetrating-Rank) has been accepted as a promising graph-based similarity measure, as it provides a comprehensive way of encoding both incoming and outgoing links into assessment. However, the existing method to compute P-Rank is iterative in nature and rather cost-inhibitive. Moreover, the accuracy estimate and stability issues for P-Rank computation have not been addressed. In this article, we consider the optimization techniques for P-Rank search that encompasses its accuracy, stability, and computational efficiency. (1) The accuracy estimation is provided for P-Rank iterations, with the aim to find out the number of iterations, k, required to guarantee a desired accuracy. (2) A rigorous bound on the condition number of P-Rank is obtained for stability analysis. Based on this bound, it can be shown that P-Rank is stable and well-conditioned when the damping factors are chosen to be suitably small. (3) Two matrix-based algorithms, applicable to digraphs and undirected graphs, are, respectively, devised for efficient P-Rank computation, which improves the computational time from O(kn3) to O(υ n2+υ6) for digraphs, and to O(υn2) for undirected graphs, where n is the number of vertices in the graph, and υ (≪ n) is the target rank of the graph. Moreover, our proposed algorithms can significantly reduce the memory space of P-Rank computations from O(n2) to O(υn+υ4) for digraphs, and to O(υ n) for undirected graphs, respectively. Finally, extensive experiments on real-world and synthetic datasets demonstrate the usefulness and efficiency of the proposed techniques for P-Rank similarity assessment on various networks.
Item Type: | Journal Article | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics T Technology > TK Electrical engineering. Electronics Nuclear engineering |
|||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||||||||
SWORD Depositor: | Library Publications Router | |||||||||||||||
Library of Congress Subject Headings (LCSH): | Web applications , Similarity (Geometry), Computers, Computer systems | |||||||||||||||
Journal or Publication Title: | ACM Transactions on the Web | |||||||||||||||
Publisher: | Association for Computing Machinery (ACM) | |||||||||||||||
ISSN: | 1559-1131 | |||||||||||||||
Official Date: | 18 December 2019 | |||||||||||||||
Dates: |
|
|||||||||||||||
Volume: | 13 | |||||||||||||||
Number: | 4 | |||||||||||||||
Page Range: | pp. 1-52 | |||||||||||||||
DOI: | 10.1145/3368616 | |||||||||||||||
Status: | Peer Reviewed | |||||||||||||||
Publication Status: | Published | |||||||||||||||
Reuse Statement (publisher, data, author rights): | © Author | ACM 2019. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in ACM Transactions on the Web http://dx.doi.org/10.1145/3368616 | |||||||||||||||
Access rights to Published version: | Restricted or Subscription Access | |||||||||||||||
Date of first compliant deposit: | 29 January 2020 | |||||||||||||||
Date of first compliant Open Access: | 11 February 2020 | |||||||||||||||
RIOXX Funder/Project Grant: |
|
|||||||||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year