Imperial College London


Faculty of EngineeringDepartment of Computing

Professor of Computer Systems



+44 (0)20 7594 8375j.mccann Website




Miss Teresa Ng +44 (0)20 7594 8300




260ACE ExtensionSouth Kensington Campus






BibTex format

author = {Yu, W and McCann, J and Zhang, C},
doi = {10.1145/3368616},
journal = {ACM Transactions on the Web},
pages = {1--52},
title = {Efficient pairwise penetrating-rank similarity retrieval},
url = {},
volume = {13},
year = {2019}

RIS format (EndNote, RefMan)

AB - 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.
AU - Yu,W
AU - McCann,J
AU - Zhang,C
DO - 10.1145/3368616
EP - 52
PY - 2019///
SN - 1559-1131
SP - 1
TI - Efficient pairwise penetrating-rank similarity retrieval
T2 - ACM Transactions on the Web
UR -
UR -
UR -
VL - 13
ER -