JacSim: An accurate and efficient link-based similarity measure in graphs
- Title
- JacSim: An accurate and efficient link-based similarity measure in graphs
- Author
- 김상욱
- Keywords
- Link-based similarity measure; Similarity computation; SimRank; Pairwise normalization problem
- Issue Date
- 2017-11
- Publisher
- ELSEVIER SCIENCE INC
- Citation
- INFORMATION SCIENCES, v. 414, page. 203-224
- Abstract
- SimRank is a well-known link-based similarity measure successfully applied in many graph-related applications. Despite of the current success of SimRank, it suffers from the problem caused by its pairwise normalization paradigm in similarity computation. In this paper, we propose JacSim (Jaccard-based SimRank) that solves the pairwise normalization problem in an effective way. JacSim computes the similarity score of a node-pair by combining two different computation manners: Jaccard coefficient and pairwise normalization. We point out two problems of existing measures targeted at solving the pairwise normalization problem and provide effective solutions to them: (1) JacSim eliminates the redundancy hidden in their similarity computation; (2) JacSim enables to control the degree of importance of the two scores obtained by employing Jaccard coefficient and pairwise normalization. In order to take advantage of links weights in similarity computation, we propose a weighted version of JacSim applicable to weighted graphs. Furthermore, to accelerate JacSim, we provide a linear recursive matrix form of JacSim, which is composed of only linear operations. We demonstrate the effectiveness and efficiency of our JacSim by conducting extensive experiments with real-world datasets. The results show that JacSim outperforms existing measures significantly in term of accuracy and also provides better performance than the similarity measures targeted to solve the pairwise normalization problem. (C) 2017 Elsevier Inc. All rights reserved.
- URI
- https://www.sciencedirect.com/science/article/pii/S0020025516307411?via%3Dihubhttps://repository.hanyang.ac.kr/handle/20.500.11754/116316
- ISSN
- 0020-0255; 1872-6291
- DOI
- 10.1016/j.ins.2017.06.005
- Appears in Collections:
- COLLEGE OF ENGINEERING[S](공과대학) > COMPUTER SCIENCE(컴퓨터소프트웨어학부) > Articles
- Files in This Item:
There are no files associated with this item.
- Export
- RIS (EndNote)
- XLS (Excel)
- XML