Paper Info
Title
Fast Katz and Commuters: Efficient Estimation of Social Relatedness in Large Networks
Abstract
Motivated by social network data mining problems such as link prediction and collaborative filtering, significant research effort has been devoted to computing topological measures including the Katz score and the commute time. Existing approaches typically approximate all pairwise relationships simultaneously. In this paper, we are interested in computing: the score for a single pair of nodes, and the top-k nodes with the best scores from a given source node. For the pairwise problem, we apply an iterative algorithm that computes upper and lower bounds for the measures we seek. This algorithm exploits a relationship between the Lanczos process and a quadrature rule. For the top-k problem, we propose an algorithm that only accesses a small portion of the graph and is related to techniques used in personalized Page Rank computing. To test the scalability and accuracy of our algorithms we experiment with three real-world networks and find that these algorithms run in milliseconds to seconds without any preprocessing.
Year
DOI
Venue
2010
10.1007/978-3-642-18009-5_13
ALGORITHMS AND MODELS FOR THE WEB GRAPH
Keywords
DocType
Volume
quadrature rule,social network,iterative algorithm,upper and lower bounds,data acquisition,collaborative filtering,data mining,data analysis
Conference
6516
ISSN
Citations 
PageRank 
0302-9743
7
0.55
References 
Authors
17
6
Name
Order
Citations
PageRank
Pooya Esfandiar1352.87
Francesco Bonchi24173200.47
David F. Gleich391957.23
CHEN GREIF432143.63
Laks V. S. Lakshmanan56216696.78
Byung-Won On632928.76