Abstract
We propose a novel stochastic process that is with probability αibeing absorbed at current state i, and with probability 1 - αifollows a random edge out of it. We analyze its properties and show its potential for exploring graph structures. We prove that under proper absorption rates, a random walk starting from a set S of low conductance will be mostly absorbed in S. Moreover, the absorption probabilities vary slowly inside S, while dropping sharply outside, thus implementing the desirable cluster assumption for graph-based learning. Remarkably, the partially absorbing process unifies many popular models arising in a variety of contexts, provides new insights into them, and makes it possible for transferring findings from one paradigm to another. Simulation results demonstrate its promising applications in retrieval and classification.
Original language | English |
---|---|
Title of host publication | Advances in Neural Information Processing Systems 25 |
Subtitle of host publication | 26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012 |
Pages | 3077-3085 |
Number of pages | 9 |
Volume | 4 |
Publication status | Published - 1 Dec 2012 |
Externally published | Yes |
Event | 26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012 - Lake Tahoe, NV, United States Duration: 3 Dec 2012 → 6 Dec 2012 |
Conference
Conference | 26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012 |
---|---|
Country/Territory | United States |
City | Lake Tahoe, NV |
Period | 3/12/12 → 6/12/12 |
ASJC Scopus subject areas
- Computer Networks and Communications
- Information Systems
- Signal Processing