2012/06/20 by Purnamrita Sarkar, Andrew Moore, Sarkar, Purnamrita +1
Computer Science · Physics and Astronomy · #Complex Network Analysis Techniques #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Physics and Society (physics.soc-ph) #Social and Information Networks (cs.SI) #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1206.5259
openalex publication_date 2012/06/20 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
Recently there has been much interest in graph-based learning, with applications in collaborative filtering for recommender networks, link prediction for social networks and fraud detection. These networks can consist of millions of entities, and so it is very important to develop highly efficient techniques. We are especially interested in accelerating random walk approaches to compute some very interesting proximity measures of these kinds of graphs. These measures have been shown to do well empirically (Liben-Nowell & Kleinberg, 2003; Brand, 2005). We introduce a truncated variation on a well-known measure, namely commute times arising from random walks on graphs. We present a very novel algorithm to compute all interesting pairs of approximate nearest neighbors in truncated commute times, without computing it between all pairs. We show results on both simulated and real graphs of size up to 100; 000 entities, which indicate near-linear scaling in computation time.