Graph Transformation Based Guidance for Web Navigation

Abstract

With growing information volume and diverse user preferences on the web, the performance of web information retrieval has become a critical issue. Web navigation is dramatically influenced by the organizations of web contents. Hence, useful navigation guidance can considerably accelerate the information retrieval process. In this paper, web navigation is formulated as a Directed Group Steiner Forest (DGSF) problem in line graph representation of the website. A heuristic algorithm is proposed to tackle the DGSF problem and attain the suboptimal solution in polynomial time. Simulations are conducted to compare the mean searching time for the proposed DGSF-based navigation guidance and other approaches. The results suggest that the DGSF-based navigation guidance can significantly reduce the mean searching time, especially when the number of web pages is large while the number of destination pages is moderate. The discussion is also made for extending the model to take into account the websites owner’s interests and other concerns as well.