Take the 2-minute tour ×
Software Quality Assurance & Testing Stack Exchange is a question and answer site for software quality control experts, automation engineers, and software testers. It's 100% free, no registration required.

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?

share|improve this question
    
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 Apr 28 '12 at 16:46
add comment

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.

share|improve this answer
    
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 Apr 26 '12 at 15:57
    
I hope it goes well. I'm always interested to hear about applications of Markov chains. –  joshin4colours Apr 26 '12 at 17:23
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.