I am writing a load test for a web application. I have a few month's worth of access logs that tell me relative hit rates of various URLs. However, the access logs do not contain enough information to tell me where a user is likely to click next. In other words, the access logs cannot help me deduce whether, given that a user is currently on page A, they are more likely to go to page B or page C.

I know which page transitions are possible, i.e. you can navigate directly from page A to page B, but not from page A to page D. I can use that information to construct a graph. If I weight the edges of the graph subject to certain constraints (e.g. the sum of the weights of all edges out of a node must equal 1), I will have a Markov chain. I would like to use the Markov chain to model variability in user behavior, but it is not obvious how to assign the weights.

If I know the relative hit rates that I want to achieve, and I know the Markov's chain's structure but not its weights, what techniques are available for assigning the weights?

  • The problem is called Web site link prediction. In combination with "markov chain" approach Google Scholar gives some responses: people.kmi.open.ac.uk/jianhan/p169-zhu.pdf . Might not be the shortest way to get the answer, though.
    – dzieciou
    Commented Apr 28, 2012 at 16:46

1 Answer 1


This is a pretty interesting problem, actually :)

You could try using a Markov Chain Monte Carlo approach. I haven't worked with these types of models myself, but the idea is that you start with a given long-run distribution and use Monte Carlo modelling to develop the actual Markov chain. I know this is a pretty well-used technique for simulation calculations. If you don't know much about Monte Carlo methods, don't worry, the basic ideas are quite simple (and powerful).

You could also try a PageRank algorithm approach. The idea would be to construct your page links and initially assign equal weights based on the link structure (ie the user is equally likely to visit any possible linked page from the current page) and then assign a small chance that the user will visit any page uniformly randomly (they "surf" somehow to a random page uniformly at random). This can help develop a Markov chain with some realistic aspects of your system, such as that pages with more links are visited more often, but it's possible that every page can be visited at some point. The nice thing about models generated using a PageRank algorithm is that they lend themselves well to analysis, both computationally and analytically. (EDIT: I guess this method might not be exactly what you're looking for, since you already have the hit rates determined. But it might be helpful if you want to generate realistic "general" data for your hit rates.)

Hope this helps out.

  • Thank you. I started reading about the Gibbs sampler yesterday. I do not yet understand how to map Markov Chain Monte Carlo methods to my problem, but I hope it will become clearer in time.
    – user246
    Commented Apr 26, 2012 at 15:57
  • I hope it goes well. I'm always interested to hear about applications of Markov chains. Commented Apr 26, 2012 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.