Fast computation of Katz index for efficient processing of link prediction queries
From MaRDI portal
Abstract: Network proximity computations are among the most common operations in various data mining applications, including link prediction and collaborative filtering. A common measure of network proximity is Katz index, which has been shown to be among the best-performing path-based link prediction algorithms. With the emergence of very large network databases, such proximity computations become an important part of query processing in these databases. Consequently, significant effort has been devoted to developing algorithms for efficient computation of Katz index between a given pair of nodes or between a query node and every other node in the network. Here, we present LRC-Katz, an algorithm based on indexing and low-rank correction to accelerate Katz index-based network proximity queries. Using a variety of very large real-world networks, we show that LRC-Katz outperforms the fastest existing method, Conjugate Gradient, for a wide range of parameter values. We also show that this acceleration in the computation of Katz index can be used to drastically improve the efficiency of processing link prediction queries in very large networks. Motivated by this observation, we propose a new link prediction algorithm that exploits modularity of networks that are encountered in practical applications. Our experimental results on the link prediction problem show that our modularity based algorithm significantly outperforms the state-of-the-art link prediction Katz method.
Recommendations
- Fast Katz and commuters: efficient estimation of social relatedness in large networks
- Scalable Katz ranking computation in large static and dynamic graphs
- Fast link prediction for large networks using spectral embedding
- Fast matrix computations for pairwise and columnwise commute times and Katz scores
- Accurate similarity index based on activity and connectivity of node for link prediction
Cites work
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
- A new status index derived from sociometric analysis
- An Approximate Minimum Degree Ordering Algorithm
- Domain adaptation and sample bias correction theory and algorithm for regression
- Fast matrix computations for pairwise and columnwise commute times and Katz scores
- scientific article; zbMATH DE number 991428 (Why is no real title available?)
- scientific article; zbMATH DE number 1049347 (Why is no real title available?)
- scientific article; zbMATH DE number 218075 (Why is no real title available?)
- scientific article; zbMATH DE number 949303 (Why is no real title available?)
- Machine Learning: ECML 2004
- Parallel iterative methods for sparse linear systems
This page was built for publication: Fast computation of Katz index for efficient processing of link prediction queries
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2036769)
