2019/12/13 by Mustafa Coskun, Coskun, Mustafa, Abdelkader Baggag +4 · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Advanced Clustering Algorithms Research #Advanced Graph Neural Networks #Algorithm #Artificial intelligence #Complex Network Analysis Techniques #Computation #Computer science #Data mining #FOS: Computer and information sciences #Index (typography) #Machine Learning (cs.LG) #Mathematics #Modularity (biology) #Node (physics) #Rank (graph theory) #Search engine indexing #Social and Information Networks (cs.SI) #Theoretical computer science #cs.LG #cs.SI
paper · pdf · doi:10.48550/arxiv.1912.06525
published in arXiv (Cornell University) (Cornell University)
arxiv created 2019/12/13 · openalex publication_date 2019/12/13 · arxiv updated 2019/12/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
Network proximity computations are among the most common operations in\nvarious data mining applications, including link prediction and collaborative\nfiltering. A common measure of network proximity is Katz index, which has been\nshown to be among the best-performing path-based link prediction algorithms.\nWith the emergence of very large network databases, such proximity computations\nbecome an important part of query processing in these databases. Consequently,\nsignificant effort has been devoted to developing algorithms for efficient\ncomputation of Katz index between a given pair of nodes or between a query node\nand every other node in the network. Here, we present LRC-Katz, an algorithm\nbased on indexing and low-rank correction to accelerate Katz index-based\nnetwork proximity queries. Using a variety of very large real-world networks,\nwe show that LRC-Katz outperforms the fastest existing method, Conjugate\nGradient, for a wide range of parameter values. We also show that this\nacceleration in the computation of Katz index can be used to drastically\nimprove the efficiency of processing link prediction queries in very large\nnetworks. Motivated by this observation, we propose a new link prediction\nalgorithm that exploits modularity of networks that are encountered in\npractical applications. Our experimental results on the link prediction problem\nshow that our modularity based algorithm significantly outperforms the\nstate-of-the-art link prediction Katz method.\n