Authority Flow-based Ranking in Heterogeneous Networks: Prediction, Personalization, and Learning to Rank

Abstract

Many real-world datasets, including biological networks, the Web, and social media, can be effectively modeled as networks or graphs, in which nodes represent entities of interest and links mimic the interactions or relationships among them. Such networks often contain multiple entity or relationship types, which are referred to as heterogeneous networks. Networks also evolve due to the existence of temporal features that characterize the entities or to the temporal relationships among them. Finding important/authoritative entities in real-world networks is a long-standing and well-defined challenge. In this dissertation, I focus on two variants of the problem. The first is the prediction of the ranking of scientific publications in a future state of a citation network. I introduce a new measure labeled the future PageRank score. I develop FutureRank, a prediction algorithm for predicting the future PageRank scores from the historical network structure, and evaluate the FutureRank algorithm on multiple bibliographic dataset. Next, I focus on personalized ranking in social media. I extend a social media dataset to include relationships (edge types) between authors, blog posts, categories (topics) of the posts, and events (collections of posts). I then apply personalized ranking algorithms over the historical posts and events that have been visited by a user and use the ranking to recommend additional posts. I evaluate the personalized recommendations through an experiment with real users, as well as an extensive study of synthetic users whose preferences are defined based on intuitive criteria. Finally, I present an approach for learning to rank (algorithms) applied to heterogeneous networks. Existing methods for learning to rank are typically limited to content-based features, while many real world problems correspond to relational features. I develop a framework for learning to rank, which targets authority flow-based ranking models on heterogeneous networks. I propose algorithms for both pointwise and pairwise learning. However, this framework can easily utilize any loss function from a non-relational learning domain. Experiments show that even with a small amount of training data, both pointwise and pairwise algorithms perform successfully and converge very fast. In addition, these solutions are shown to be robust against noise.