Fast computation of SimRank for static and dynamic information networks
Top Cited Papers
- 22 March 2010
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 465-476
- https://doi.org/10.1145/1739041.1739098
Abstract
Information networks are ubiquitous in many applications and analysis on such networks has attracted significant attention in the academic communities. One of the most important aspects of information network analysis is to measure similarity between nodes in a network. SimRank is a simple and influential measure of this kind, based on a solid theoretical "random surfer" model. Existing work computes SimRank similarity scores in an iterative mode. We argue that the iterative method can be infeasible and inefficient when, as in many real-world scenarios, the networks change dynamically and frequently. We envision non-iterative method to bridge the gap. It allows users not only to update the similarity scores incrementally, but also to derive similarity scores for an arbitrary subset of nodes. To enable the non-iterative computation, we propose to rewrite the SimRank equation into a non-iterative form by using the Kronecker product and vectorization operators. Based on this, we develop a family of novel approximate SimRank computation algorithms for static and dynamic information networks, and give their corresponding theoretical justification and analysis. The non-iterative method supports efficient processing of various node analysis including similarity tracking and centrality tracking on evolving information networks. The effectiveness and efficiency of our proposed methods are evaluated on synthetic and real data sets.Keywords
Funding Information
- Division of Information and Intelligent Systems (IIS-08-42769IIS-09-05215)
- National Natural Science Foundation of China (6.07E+15)
- Ministry of Science and Technology of the People's Republic of China (2008AA01Z120)
- National Aeronautics and Space Administration (NNX08AC35A)
This publication has 23 references indexed in Scilit:
- Accuracy estimate and optimization techniques for SimRank computationProceedings of the VLDB Endowment, 2008
- Evolutionary spectral clustering by incorporating temporal smoothnessPublished by Association for Computing Machinery (ACM) ,2007
- Substructure similarity search in graph databasesPublished by Association for Computing Machinery (ACM) ,2005
- The Structure and Function of Complex NetworksSIAM Review, 2003
- Exploiting hierarchical domain structure to compute similarityACM Transactions on Information Systems, 2003
- Cumulated gain-based evaluation of IR techniquesACM Transactions on Information Systems, 2002
- SimRankPublished by Association for Computing Machinery (ACM) ,2002
- Authoritative sources in a hyperlinked environmentJournal of the ACM, 1999
- Using Linear Algebra for Intelligent Information RetrievalSIAM Review, 1995
- Erratum: Inverting a Sum of MatricesSIAM Review, 1990