The Library
Sig-SR : SimRank search over singular graphs
Tools
Yu, Weiren and McCann, Julie A. (2014) Sig-SR : SimRank search over singular graphs. In: SIGIR '14, Queensland Australia. Published in: SIGIR '14: Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval pp. 859-862. ISBN 9781450322577. doi:10.1145/2600428.2609459
|
PDF
WRAP-Sig-SR-SimRank-search-graphs-Yu-2014.pdf - Accepted Version - Requires a PDF viewer. Download (710Kb) | Preview |
Official URL: http://dx.doi.org/10.1145/2600428.2609459
Abstract
SimRank is an attractive structural-context measure of similarity between two objects in a graph. It recursively follows the intuition that "two objects are similar if they are referenced by similar objects". The best known matrix-based method [1] for calculating SimRank, however, implies an assumption that the graph is non-singular, its adjacency matrix is invertible. In reality, non-singular graphs are very rare; such an assumption in [1] is too restrictive in practice. In this paper, we provide a treatment of [1], by supporting similarity assessment on non-invertible adjacency matrices. Assume that a singular graph G has n nodes, with r(<n) being the rank of its adjacency matrix.(1) We show that SimRank matrix S on G has an elegant structure: S can be represented as a rank r matrix plus a scaled identity matrix.(2) By virtue of this, an efficient algorithm over singular graphs, InvSR, is proposed for calculating all-pairs SimRank in O(r(n2+Kr2)) time for K iterations. In contrast, the only known matrix-based algorithm that supports singular graphs [1] needs O(r4n2) time. The experimental results on real and synthetic datasets demonstrate the superiority of InvSR on singular graphs against its baselines.
Item Type: | Conference Item (Poster) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Link theory, Electronic information resource searching, Electronic information resource searching -- Mathematics, SimRank, Graph theory -- Data processing | ||||
Journal or Publication Title: | SIGIR '14: Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval | ||||
Publisher: | ACM | ||||
ISBN: | 9781450322577 | ||||
Book Title: | Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval - SIGIR '14 | ||||
Official Date: | July 2014 | ||||
Dates: |
|
||||
Page Range: | pp. 859-862 | ||||
DOI: | 10.1145/2600428.2609459 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Reuse Statement (publisher, data, author rights): | © Author | ACM 2014. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in SIGIR '14: Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval, https://doi.org/10.1145/2600428.2609459 | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Date of first compliant deposit: | 31 January 2020 | ||||
Date of first compliant Open Access: | 17 February 2020 | ||||
Conference Paper Type: | Poster | ||||
Title of Event: | SIGIR '14 | ||||
Type of Event: | Conference | ||||
Location of Event: | Queensland Australia |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year