{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T04:27:04Z","timestamp":1772252824406,"version":"3.50.1"},"reference-count":17,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2024,6,12]],"date-time":"2024-06-12T00:00:00Z","timestamp":1718150400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Natural Science Foundation of China","award":["62372101"],"award-info":[{"award-number":["62372101"]}]},{"name":"Natural Science Foundation of China","award":["61873337"],"award-info":[{"award-number":["61873337"]}]},{"name":"Natural Science Foundation of China","award":["62272097"],"award-info":[{"award-number":["62272097"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>SimRank is a widely used metric for evaluating vertex similarity based on graph topology, with diverse applications such as large-scale graph mining and natural language processing. The objective of the single-source and top-k SimRank query problem is to retrieve the kvertices with the largest SimRank to the source vertex. However, existing algorithms suffer from inefficiency as they require computing SimRank for all vertices to retrieve the top-k results. To address this issue, we propose an algorithm named HitSimthat utilizes a branch and bound strategy for the single-source and top-k query. HitSim initially partitions vertices into distinct sets based on their shortest-meeting lengths to the source vertex. Subsequently, it computes an upper bound of SimRank for each set. If the upper bound of a set is no larger than the minimum value of the current top-k results, HitSim efficiently batch-prunes the unpromising vertices within the set. However, in scenarios where the graph becomes dense, certain sets with large upper bounds may contain numerous vertices with small SimRank, leading to redundant overhead when processing these vertices. To address this issue, we propose an optimized algorithm named HitSim-OPT that computes the upper bound of SimRank for each vertex instead of each set, resulting in a fine-grained and efficient pruning process. The experimental results conducted on six real-world datasets demonstrate the performance of our algorithms in efficiently addressing the single-source and top-k query problem.<\/jats:p>","DOI":"10.3390\/info15060348","type":"journal-article","created":{"date-parts":[[2024,6,13]],"date-time":"2024-06-13T06:23:11Z","timestamp":1718259791000},"page":"348","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["HitSim: An Efficient Algorithm for Single-Source and Top-k SimRank Computation"],"prefix":"10.3390","volume":"15","author":[{"given":"Jing","family":"Bai","sequence":"first","affiliation":[{"name":"College of Information Technology, Shanghai Jian Qiao University, 1111 Hucheng Ring Road, Pudong New Area, Shanghai 201306, China"},{"name":"School of Computer Science and Technology, Donghua University, 2999 Renmin North Road, Songjiang District, Shanghai 201620, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6494-5319","authenticated-orcid":false,"given":"Junfeng","family":"Zhou","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Donghua University, 2999 Renmin North Road, Songjiang District, Shanghai 201620, China"}]},{"given":"Shuotong","family":"Chen","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Donghua University, 2999 Renmin North Road, Songjiang District, Shanghai 201620, China"}]},{"given":"Ming","family":"Du","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Donghua University, 2999 Renmin North Road, Songjiang District, Shanghai 201620, China"}]},{"given":"Ziyang","family":"Chen","sequence":"additional","affiliation":[{"name":"School of Information Management, Shanghai Lixin University of Accounting and Finance, 2800 Wenxiang Road, Songjiang District, Shanghai 201209, China"}]},{"given":"Mengtao","family":"Min","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Donghua University, 2999 Renmin North Road, Songjiang District, Shanghai 201620, China"}]}],"member":"1968","published-online":{"date-parts":[[2024,6,12]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Jin, R., Lee, V.E., and Hong, H. (2011, January 21\u201324). Axiomatic ranking of network role similarity. Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA.","DOI":"10.1145\/2020408.2020561"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1019","DOI":"10.1002\/asi.20591","article-title":"The link-prediction problem for social networks","volume":"58","author":"Kleinberg","year":"2007","journal-title":"J. Assoc. Inf. Sci. Technol."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"408","DOI":"10.14778\/1453856.1453903","article-title":"Simrank++: Query rewriting through link analysis of the click graph","volume":"1","author":"Antonellis","year":"2008","journal-title":"Proc. VLDB Endow."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1145\/2207243.2207252","article-title":"Survey on web spam detection: Principles and algorithms","volume":"13","author":"Spirin","year":"2011","journal-title":"SIGKDD Explor."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Rothe, S., and Sch\u00fctze, H. (2014;:, January 22\u201327). CoSimRank: A Flexible & Efficient Graph-Theoretic Similarity Measure. Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, ACL 2014, Baltimore, MD, USA.","DOI":"10.3115\/v1\/P14-1131"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Jeh, G., and Widom, J. (2002, January 23\u201326). SimRank: A measure of structural-context similarity. Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Edmonton, AB, Canada.","DOI":"10.1145\/775047.775126"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/s00778-009-0168-8","article-title":"Accuracy estimate and optimization techniques for SimRank computation","volume":"19","author":"Lizorkin","year":"2010","journal-title":"VLDB J."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"317","DOI":"10.14778\/2735508.2735520","article-title":"Efficient Top-K SimRank-based Similarity Join","volume":"8","author":"Tao","year":"2014","journal-title":"Proc. VLDB Endow."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Fogaras, D., and R\u00e1cz, B. (2005, January 10\u201314). Scaling link-based similarity search. Proceedings of the 14th International Conference on World Wide Web, WWW 2005, Chiba, Japan.","DOI":"10.1145\/1060745.1060839"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Lee, P., Lakshmanan, L.V.S., and Yu, J.X. (2012, January 1\u20135). On Top-k Structural Similarity Search. Proceedings of the IEEE 28th International Conference on Data Engineering (ICDE 2012), Washington, DC, USA.","DOI":"10.1109\/ICDE.2012.109"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Tian, B., and Xiao, X. (July, January 26). SLING: A Near-Optimal Index Structure for SimRank. Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA.","DOI":"10.1145\/2882903.2915243"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"14","DOI":"10.14778\/3151113.3151115","article-title":"ProbeSim: Scalable Single-Source and Top-k SimRank Computations on Dynamic Graphs","volume":"11","author":"Liu","year":"2017","journal-title":"Proc. VLDB Endow."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Li, M., Choudhury, F.M., Borovica-Gajic, R., Wang, Z., Xin, J., and Li, J. (2020, January 20\u201324). CrashSim: An Efficient Algorithm for Computing SimRank over Static and Temporal Graphs. Proceedings of the 36th IEEE International Conference on Data Engineering, ICDE 2020, Dallas, TX, USA.","DOI":"10.1109\/ICDE48307.2020.00103"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"2202","DOI":"10.14778\/3407790.3407819","article-title":"SimTab: Accuracy-Guaranteed SimRank Queries through Tighter Confidence Bounds and Multi-Armed Bandits","volume":"13","author":"Liu","year":"2020","journal-title":"Proc. VLDB Endow."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"838","DOI":"10.14778\/2757807.2757809","article-title":"An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs","volume":"8","author":"Shao","year":"2015","journal-title":"Proc. VLDB Endow."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"937","DOI":"10.14778\/3099622.3099625","article-title":"READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank","volume":"10","author":"Jiang","year":"2017","journal-title":"Proc. VLDB Endow."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Wei, Z., He, X., Xiao, X., Wang, S., Liu, Y., Du, X., and Wen, J. (July, January 30). PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs. Proceedings of the 2019 International Conference on Management of Data, SIGMOD Conference 2019, Amsterdam, The Netherlands.","DOI":"10.1145\/3299869.3319873"}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/15\/6\/348\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T14:57:28Z","timestamp":1760108248000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/15\/6\/348"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,12]]},"references-count":17,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2024,6]]}},"alternative-id":["info15060348"],"URL":"https:\/\/doi.org\/10.3390\/info15060348","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-3170630\/v1","asserted-by":"object"}]},"ISSN":["2078-2489"],"issn-type":[{"value":"2078-2489","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,12]]}}}