14 0

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%3Dihubhttp://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


qrcode

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE