With the growing volume and volatile user preferences on Web information, the performance of information access has become a critical factor for Web site design. How the information and pages are organized and represented on a Web site dramatically influences the performance of the navigation on the Internet. Hence, providing a helpful navigation guide and estimating the performance of information retrieval are of significant importance. Based on the graph theory, the Web navigation problem is addressed in two aspects: the navigation as a Steiner arborescence problem and the measure and improvement of information access on the Web. For the first problem, a Web site is represented as a digraph, and the Web navigation is formulated as a weighted Steiner arborescence problem (WSAP), which...[ Read more ]

With the growing volume and volatile user preferences on Web information, the performance of information access has become a critical factor for Web site design. How the information and pages are organized and represented on a Web site dramatically influences the performance of the navigation on the Internet. Hence, providing a helpful navigation guide and estimating the performance of information retrieval are of significant importance. Based on the graph theory, the Web navigation problem is addressed in two aspects: the navigation as a Steiner arborescence problem and the measure and improvement of information access on the Web. For the first problem, a Web site is represented as a digraph, and the Web navigation is formulated as a weighted Steiner arborescence problem (WSAP), which is NP-complete. The number of links required to retrieve the designated pages is assumed to be the most significant factor in Web navigation, and the problem is further simplified as a special case of the Steiner arborescence problem (SSAP). A modified shortest path heuristic (MSPH) is proposed for problem solving, and a simulation system is employed to illustrate the performance improvement by the Steiner arborescence based navigation guide. For the second problem, based on the analysis of the link structure of a Web site, a quantity called "accessibility" is defined and proposed to measure the availability of the Web pages in a numeric fashion. The relationship between the accessibility and the popularity of the Web pages is discussed for discovering potential problems of the representation of the Web pages. Consequently, the Web designer can improve the organization of the Web pages on a Web site. A case study is provided to demonstrate the improvement procedure.