Efficient Computation of Mean Truncated Hitting Times on Very Large Graphs
Previous work has shown the effectiveness of random walk hitting times as a measure of dissimilarity in a variety of graph-based learning problems such as collaborative filtering, query suggestion or finding paraphrases. However, application of hitting times has been limited to small datasets because of computational restrictions. This paper develops a new approximation algorithm with which hitting times can be computed on very large, disk-resident graphs, making their application possible to problems which were previously out of reach. This will potentially benefit a range of large-scale problems.
Code (0)
등록된 구현이 없습니다.
Tasks
Collaborative FilteringSimilar Papers 제목 키워드 기반
ULTRA-MC: A Unified Approach to Learning Mixtures of Markov Chains via Hitting Times
This study introduces a novel approach for learning mixtures of Markov chains, a critical process applicable to various fields, including healthcare and the analysis of web users. Existing research has identified a clear…
Hitting times of local and global optima in genetic algorithms with very high selection pressure
The paper is devoted to upper bounds on the expected first hitting times of the sets of local or global optima for non-elitist genetic algorithms with very high selection pressure. The results of this paper extend the ra…
The Likelihood of Mixed Hitting Times
We present a method for computing the likelihood of a mixed hitting-time model that specifies durations as the first time a latent L\'evy process crosses a heterogeneous threshold. This likelihood is not generally known …
On some dynamical features of the complete Moran model for neutral evolution in the presence of mutations
We present a version of the classical Moran model, in which mutations are taken into account; the possibility of mutations was introduced by Moran in his seminal paper, but it is more often overlooked in discussing the M…
Anytime Cooperative Implicit Hitting Set Solving
The Implicit Hitting Set (HS) approach has shown to be very effective for MaxSAT, Pseudo-boolean optimization and other boolean frameworks. Very recently, it has also shown its potential in the very similar Weighted CSP …