Abstract
Link-based similarity measures play a significant role in many graph based applications. Consequently, measuring node similarity in a graph is a fundamental problem of graph datamining. Personalized pagerank (PPR) and simrank (SR) have emerged as the most popular and influential link-based similarity measures. Recently, a novel link-based similarity measure, penetrating rank (P-Rank), which enriches SR, was proposed. In practice, PPR, SR and P-Rank scores are calculated by iterative methods. As the number of iterations increases so does the overhead of the calculation. The ideal solution is that computing similarity within the minimum number of iterations is sufficient to guarantee a desired accuracy. However, the existing upper bounds are too coarse to be useful in general. Therefore, we focus on designing an accurate and tight upper bounds for PPR, SR, and P-Rank in the paper. Our upper bounds are designed based on the following intuition: the smaller the difference between the two consecutive iteration steps is, the smaller the difference between the theoretical and iterative similarity scores becomes. Furthermore, we demonstrate the effectiveness of our upper bounds in the scenario of top-k similar nodes queries, where our upper bounds helps accelerate the speed of the query. We also run a comprehensive set of experiments on real world data sets to verify the effectiveness and efficiency of our upper bounds.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Gupta P, Goel A, Lin J, Sharma A,Wang D, Zadeh R. WTF: the who to follow service at Twitter. In: Proceedings of International World Wide Web Conference. 2013, 505᾿14
Liben-Nowell D, Kleinberg J. The link-prediction problem for social networks. Journal of the Association for Information Science and Technology, 2007, 58 (7): 1019–1031
Joshi A, Kumar R, Reed B, Tomkins A. Anchor-based proximity measures. In: Proceedings of International World Wide Web Conference. 2007, 1131–1132
Antonellis I, Molina H G, Chang C C. Simrank++: query rewriting through link analysis of the click graph. Proceedings of the VLDB Endowment, 2008, 1 (1): 408–421
Jeh G, Widom J. Scaling personalized web search. In: Proceedings of International World Wide Web Conference. 2003, 271–279
Jeh G, Widom J. SimRank: a measure of structural-context similarity. In: Proceedings of ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2002, 538-43
Sarkar P, Moore A W, Prakash A. Fast incremental proximity search in large graphs. In: Proceedings of International Conference on Machine Learning. 2008, 896-03
Sarkar P, Moore AW. A tractable approach to finding closest truncated-commute-time neighbors in large graphs. In: Proceedings of Uncertainty in Artificial Intelligence. 2007, 335-43
Zhao P, Han J, Sun Y. P-Rank: a comprehensive structural similarity measure over information networks. In: Proceedings of the 18th ACM Conference on Information and Knowledge Management. 2009, 553-62
Lizorkin D, Velikhov P, Grinev M N, Turdakov D. Accuracy estimate and optimization techniques for simrank computation. Proceedings of the VLDB Endowment, 2008, 1 (1): 422–433
Sun L, Cheng R, Li X, Cheung D W, Han J. On link-based similarity join. The Proceedings of the VLDB Endowment, 2011, 4 (11): 714–725
Zhang Y, Li C, Xie C, Chen H. Accuracy estimation of link-based similarity measures and its application. In: Proceedings of Web-Age Information Management WAIM. 2014, 100-12
Zhang Y, Li C, Chen H, Sheng L. Fast simrank computation over disk-resident graphs. In: Proceedings of International Conference of Database Systems for Advanced Applications. 2013, 16-0
Lizorkin D, Velikhov P, Grinev M N, Turdakov D. Accuracy estimate and optimization techniques for simrank computation. The International Journal on Very Large Data Bases, 2010, 19 (1): 45–66
Zhu F, Fang Y, Chang K C C, Ying J. Incremental and accuracyaware personalized pagerank through scheduled approximation. The Proceedings of the VLDB Endowment, 2013, 6 (6): 481–492
Lee P, Lakshmanan L V S, Yu J X. On top-k structural similarity search. In: Proceedings of International Conference on Data Engineering. 2012, 774–785
Yu W, Lin X, Zhang W. Towards efficient simrank computation on large networks. In: Proceedings of International Conference on Data Engineering. 2013, 601–612
Li X, Yu W, Yang B, Le J. ASAP: Towards accurate, stable and accelerative penetrating-rank estimation on large graphs. In: Proceedings of Web-Age Information Management. 2011, 415–429
Yu W, Le J, Lin X, Zhang W. On the efficiency of estimating penetrating rank on large graphs. In: Proceedings of Scientific and Statistical Database Management. 2012, 231–249
Fujiwara Y, Nakatsuji M, Shiokawa H, Mishima T, Onizuka M. Efficient ad-hoc search for personalized pagerank. In: Proceedings of the ACM SIGMOD International Conference on Management of Data. 2013, 445–456
Albert R, Barabasi A. Statistical mechanics of complex networks. Reviews of Modern Physics, 2002, 74: 47–97
Jin R, Ruan N, Xiang Y, Wang H. Path-tree: an efficient reachability indexing scheme for large directed graphs. ACM Transaction Database System, 2011, 36 (1): 1–44
Zheng W, Zou L, Feng Y, Chen L, Zhao D. Efficient simrank-based similarity join over large graphs. Proceedings of the VLDB Endowment, 2013, 6 (7): 493–504
Author information
Authors and Affiliations
Corresponding author
Additional information
Yinglong Zhang received his PhD from RenMin University, China in 2014. He is a lecturer at China East Jiaotong University, China. His research interests include data mining and information network analysis.
Cuiping Li received her PhD from the Chinese Academy of Science, China in 2003. She is a professor and doctoral supervisor at Renmin University, China. Her research interests include databases, data mining, information network analysis, and data stream management.
Chengwang Xie received his PhD from Wuhan University, China in 2010. He is an associate professor at East China Jiaotong University, China. His research interests include evolutionary computation and data miming.
Hong Chen received her PhD from the Chinese Academy of Science, China in 2000. She is a professor and doctoral supervisor at Renmin University, China. Her research interests include databases, data mining, data stream analysis and management, and sensor network data management.
Rights and permissions
About this article
Cite this article
Zhang, Y., Li, C., Xie, C. et al. Accuracy estimation of link-based similarity measures and its application. Front. Comput. Sci. 10, 113–123 (2016). https://doi.org/10.1007/s11704-015-4570-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11704-015-4570-7