05973247

a

05973247 Li, Xuefei Yu, Weiren Yang, Bo Le, Jiajin ASAP: towards accurate, stable and accelerative penetrating-rank estimation on large graphs. Wang, Haixun (ed.) et al., Web-age information management. 12th international conference, WAIM 2011, Wuhan, China, September 14--16, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-23534-4/pbk). Lecture Notes in Computer Science 6897, 415-429 (2011). 2011 Berlin: Springer EN

doi:10.1007/978-3-642-23535-1_36

Summary: Pervasive web applications increasingly require a measure of similarity among objects. Penetrating-Rank (P-Rank) has been one of the promising link-based similarity metrics as it provides a comprehensive way of jointly encoding both incoming and outgoing links into computation for emerging applications. In this paper, we investigate P-Rank efficiency problem that encompasses its accuracy, stability and computational time. (1) We provide an accuracy estimate for iteratively computing P-Rank. A symmetric problem is to find the iteration number $K$ needed for achieving a given accuracy $\epsilon $. (2) We also analyze the stability of P-Rank, by showing that small choices of the damping factors would make P-Rank more stable and well-conditioned. (3) For undirected graphs, we also explicitly characterize the P-Rank solution in terms of matrices. This results in a novel non-iterative algorithm, termed ASAP , for efficiently computing P-Rank, which improves the CPU time from $O(n ^{4})$ to $O( n ^{3} )$. Using real and synthetic data, we empirically verify the effectiveness and efficiency of our approaches.