Back to search

Purdue University

Higher-order Random Walk Methods for Data Analysis

Abstract

dc:description.abstract

Markov random walk models are powerful analytical tools for multiple areas in machine learning, numerical optimizations and data mining tasks. The key assumption of a frst-order Markov chain is memorylessness, which restricts the dependence of the transition distribution to the current state only. However in many applications, this assumption is not appropriate. We propose a set of higher-order random walk techniques and discuss their applications to tensor co-clustering, user trails modeling, and solving linear systems. First, we develop a new random walk model that we call the super-spacey random surfer, which simultaneously clusters the rows, columns, and slices of a nonnegative three-mode tensor. This algorithm generalizes to tensors with any number of modes. We partition the tensor by minimizing the exit probability between clusters when the super-spacey random walk is at stationary. The second application is user trails modeling, where user trails record sequences of activities when individuals interact with the Internet and the world. We propose the retrospective higher-order Markov process as a two-step process by frst choosing a state from the history and then transitioning as a frst-order chain conditional on that state. This way the total number of parameters is restricted and thus the model is protected from overftting. Lastly we propose to use a time-inhomogeneous Markov chain to approximate the solution of a linear system. Multiple simulations of the random walk are conducted to approximate the solution. By allowing the random walk to transition based on multiple matrices, we decrease the variance of the simulations, and thus increase the speed of the solver.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy (PhD)
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Computer Science

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Wu, Tao
Contributors dc:contributor
  • David F. Gleich
  • Ananth Grama
  • Bruno Ribeiro
  • Hemanta K. Maji

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Purdue University
Base URL
docs.lib.purdue.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Wu, Tao. Higher-order Random Walk Methods for Data Analysis. Dissertation thesis, https://docs.lib.purdue.edu/open_access_dissertations/1845