Walk Prediction in Directed Networks

In this paper we consider the problem of directed and walk-specific spread of information in complex social networks. Traditional models tend to explain “explosive” information spreading on social media (e.g., Twitter) – a broadcast or epidemiological kind of model with a focus on the sequence of newly “infected” nodes generated from a source node to multiple targets. However, the process of (single-track) information flow, wherein there is a node-by-node (and not necessarily a newly visited node) trajectory of information transfer is also a common phenomenon. A key example of interest is the sequence of physician visits of a given patient (a referral sequence) in a physician network, wherein the patient is a carrier of information about treatment or disease. With this motivation in mind, we present a Bayesian Personalized Ranking (BPR) model to predict the next node on a walk of a given network navigator using features derived from network analysis. This problem is related to but different from the well-studied problem of link prediction. We apply our model to data from several years of U.S. patient referrals. We present experiments showing that the adoption of network-based features in the BPR framework improves hit-rate and mean percentile rank for next-node prediction.