Fast computation of SimRank for static and dynamic information networks
Fast computation of SimRank for static and dynamic information networks
复制标题
DOI：
10.1145/1739041.1739098
复制
发表时间：
2010-03
期刊：
影响因子：
--
通讯作者：
Cuiping Li;Jiawei Han;Guoming He;Xin Jin;Yizhou Sun;Yintao Yu;Tianyi Wu
中科院分区：
文献类型：
--
作者：
Cuiping Li;Jiawei Han;Guoming He;Xin Jin;Yizhou Sun;Yintao Yu;Tianyi Wu
信息网络在许多应用中无处不在，对此类网络的分析引起了学术界的极大关注。信息网络分析的一个重要方面是度量网络中节点之间的相似性。SimRank是一种简单而有影响力的衡量标准，基于可靠的理论“随机冲浪者”模型。现有的工作计算SimRank相似性得分在迭代模式。我们认为，迭代方法是不可行的，效率低下时，在许多现实世界的情况下，网络动态变化，频繁。我们设想非迭代方法来弥合差距。它不仅允许用户增量地更新相似性分数，而且还可以导出任意节点子集的相似性分数。为了实现非迭代计算，我们建议通过使用Kronecker乘积和向量化算子将SimRank方程重写为非迭代形式。在此基础上，提出了一系列新的静态和动态信息网络的近似SimRank计算算法，并给出了相应的理论证明和分析。非迭代方法支持各种节点分析的有效处理，包括相似性跟踪和中心性跟踪不断发展的信息网络。我们所提出的方法的有效性和效率进行评估合成和真实的数据集。
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.