Statistical model to predict the next move on network only using movement history

Question

Is it possible to build a statistical model that predicts the next move in a graph solely based on past movements and the structure of the graph?

I have made an example to illustrate the problem:

1. Time is discrete. In every round you either stay at your current node/vertex or you move to one of the connected nodes. Since time is discrete and you at most can advance one node each round there is no velocity.
2. Past route / movement history: {A, B, C} -- And the current position is: C

3. Valid next moves: C, B, X, Y, Z

   1. If you choose C you stay fixed,
   2. if B you move backwards,
   3. and if X, Y, or Z implies moving forward.

4. There are no weights on either links or nodes.

5. There is no final destination node. Part of the movement behaviour observed is random and part of it will have some regularity to it.

A very simple model -- that does not take account of the movement history -- would just predict that C, B, X, Y, and Z each had a 1/5 probability to be the next move.

But based on the structure and the movement history, I am guessing it is possible to make a better statistical model. Fore instance X should have a lower probability, since one could have moved there directly from node B in the previous round. Similarly B should also have a lower probability since the person could have remained fixed in the previous round.

---

If the user moves back to B, then the movement history will look like this {A, B, C, B} and the valid moves will be A, B, C, D, E, X. Moving to C should have lower probability, since you could have remained fixed. Moving to X should also have a lower probability, since you could have move there from C in the previous round. Earlier history may also influence the prediction, but should be given less weight than recent history -- ie. 2 rounds ago you could have stayed in B, or you could have moved to A, D, E, X -- 3 rounds ago you could have stayed at A.

---

Looking around I discovered that similar problems are faced in:

• mobile telecommunication, where the operaters try to predict which cell tower the user will move to next so they can smoothly hand over the call/data transmission.
• web navigation, where browsers/search engines try to predict which page you will go to next such that they can pre-load and cache the page, such that waiting time is reduced. Similarly map applications try to predict which map tiles you will request next, and preload these.
• and of course the transport industry.

Answer 1

Do you really want a statistical model, or just an algorithm for guessing the next node given all previous ones? If the latter then consider proceeding as follows.

Suppose you've gone $\ldots\rightarrow A\rightarrow B\rightarrow C$ and need to decide which of $X$, $Y$ or $Z$ is the most likely next node.

1. First-order Markov. Historically, let's say $n_C(X)$ moves from $C$ have been to $X$, $n_C(Y)$ to $Y$ and $n_C(Z)$ to $Z$. Define $n_C=n_C(X)+n_C(Y)+n_C(Z)$. Adding a flattening constant $\kappa$ to each count, the (Dirichlet-Multinomial) predicted probabilities for the next move are $p_C(X) = \frac{\kappa+n_C(X)}{3\kappa+n_C}$ etc.

2. Second-order Markov. As above, but we're looking at moves following $BC$. The counts $n_{BC}(X)$ etc will be lower (we're taking a smaller, more specific. slice of the history), so the flattening effect of adding $\kappa$ to the historical counts will be proportionally greater. As before, we define $p_{BC}(X) = \frac{\kappa+n_{BC}(X)}{3\kappa+n_{BC}}$ and so on.

3. Continue in this way, forming probabilities $p_{C}(\cdot), p_{BC}(\cdot), p_{ABC}(\cdot), \ldots$ until the history is long enough that there is only one choice for the next node. Going further back is now pointless. Let $p_\textrm{history}(W)$ be the maximum of all of the $p_\cdot(\cdot)$ probabilities. Your prediction for the next node is $W$.

This just leaves the question of: what value should $\kappa$ take? $\kappa=1$ would be the traditional starting point. Try cross-validation (train on part of your data, test on the rest) to fine-tune that value.

Answer 2

Hint for the non-time varying version: You can treat this as updating (use Bayes' theorem) probability estimates given some data. A multinomial likelihood and Dirichlet prior would be the standard approach. https://en.wikipedia.org/wiki/Dirichlet-multinomial_distribution

For the prior it sounds like you would want the prior probability to assign equal probabilities of transitioning to each possible node.

To add in the effects of time (older tranitions matter less than newer ones) is more complex. You could add in a decay function so that you get partial transitions.

In general the structure alone of the diagram will tell you nothing about the transition probabilities.

Answer 3

A few answers and a few questions.

For simplicity let's start by assuming you're just seeing one long chain of movements. The simplest model would involve a Multinomial distribution for each node (essentially at each node there is a specific die to roll to determine where you go next). Our goal would be to estimate the parameters of these dice. As Ash mentioned the Bayesian approach would be to put a Dirichlet Prior Distribution on each die, and update this prior with new data to obtain a Dirichlet Posterior Distribution. You can think of a Dirichlet distribution as a dice factory. The fact that the posterior distribution is also a Dirichlet is because the Dirichlet distribution is the Conjugate Prior to the Multinomial distribution. While this may sound quite confusing it's actually very simple. The prior can be interpreted as pseudo-counts, essentially pretending that you've already seen some data (even though you haven't).

For example, if you are at Z you can go to C, D, Z (our die is three sided here). We can use a Dirichlet prior that acts as though we've already seen one transition from Z to each of those states. So each probability will equal 1/3. If the player transitions to C, we would update our distribution with one more count, so transition from Z to C would have probability 2/4 and the other would each have probability 1/4. If we use a prior with more pseudo-counts as though we had seen 10 transitions from Z to each of the other states, the updated probabilities (11/31, 10/31, 10/31), would be much closer to the original ones, this is a stronger prior. The strength of the prior is normally determined by Cross-Validation.

The model I described above is referred to as memoryless, because the probability of transitioning from one state to another depends only on your current state. If you wanted to do something more elaborate you could incorporate not only where you currently are, but also where you were last step, although at this point the number of parameters you have to estimate will increase dramatically, and therefore the variance in estimating will as well.

Question:

You gave some intuition of the form of "Why would I go from B->C->X when I could just go from B->X?" These ideas seem to be specific to the problem you're working on, so I can speak directly to it. Although if that is a concern, perhaps you want to use the non-memoryless (memoryfull?) model, or incorporate this information in your prior. If you would like to explain what the real life significance of this graph is, and therefore where this intuition is coming from perhaps we can be more helpful.

Note:

You want to look up Markov Models, maybe no so much Hidden Markov Models. Those have a hidden state that is controlling the observed data, and trying to learn to use them might get in the way of this project.