We present in this paper an approach to Web information foraging. We implemented a technique that helps Web users undertaking information foraging by simulating their behavior using a colony of arti cial ants. Experiments were conducted on a website dedicated to the domain of Health. The results are promising and show the ability of our Web information foraging approach to nd relevant Web pages.
A recent paradigm related to accessing relevant information on the Web is Information Foraging. The task of information foraging consists in browsing the Web to collect information related to speci c user needs under a time constraint. Recent work on information foraging are focalized to de ne algorithms that are able to discover in an automatic way the sur ng paths that web users would follow while seeking information on the Web. The development of such systems may allow the users to spend less time locating the needed information; moreover this will also help them to easily identify the best sources containing that information.
The task of foraging is grounded on the Optimal Foraging Theory [10] developed by anthropologists to model the animal behavior while foraging food.The Information Foraging Theory was rst developed in 1999 [7]. The authors established their study on the similarity between the animal food foraging behavior described in the Optimal Foraging Theory and the behavior of humans while seeking information online. The theory is based on the assumption that, when searching for information, users rely on their senses to perceive the information scent that helps them to reach their goal just like animals do when they follow the scent of their preys.
Information foraging consists in simulating the behavior of real users while seeking information on the Web. At the beginning, the information foraging process starts from a Web page and then according to the information need of the user, it decides which Web pages to visit in order to reach Web pages containing relevant information to the user. At the end of the process, a collection of sur ng paths containing relevant Web pages is produced.
In this paper an approach to Web information foraging based on Ant Colony Optimization is proposed and evaluated. The arti cial ants simulate the behavior of Web users while searching for information on the Web taking into consideration the complex structure of the Web and its volume. For this purpose, we propose a Web sur ng model and implement a Web sur ng strategy.
The rest of the paper is organized as follows. In section 2, we report the studies that are the most related to our concern. Web information foraging described is then described in section 3. In section 4, we present the contribution we developed for Web information foraging using Ant Colony Optimization. Section 5 summarizes the experiments we conducted on a medical website and the results we achieved. 2
In the study presented in [8], the authors consider the Web as a semantic space and try to predict the navigational choices of Web users. The notion of information scent is introduced, which is measured as the mutual relevance between the user's goal and the Web pages' content. The authors tested their model on a database of selected tasks collected by a survey of more than 2000 web users. The results show that the measure of information scent is able to generate good estimations of web user interactions by predicting the links the users will click on and also when they decide to leave the website.
Strong regularities in Web sur ng behavior were studied in [4] from a theoretical point of view. The authors proposed a model for studying sur ng behaviors and the experiments they held showed common sur ng behaviors. The study conducted in [3] shows that the Web pages are distributed over the sites according to a universal power law, which is an example of their strong regularities.
In [5] and [6] the authors consider Web topology, information distribution and interest pro le in building a Wisdom information foraging agent. They found out that the unique distribution of agent interest leads for regularities in Web sur ng. They also undertook an interesting study on three categories of users according to their interest and familiarity with the Web: A random user, a rational user and a recurrent user. The result is that independently from the type of users, the regularities of sur ng are the same, which means that the user ability for predicting the sur ng chain is predominant.
In [9] the author presents di erent interactive information retrieval models and shows the importance of developing such systems. Interactive information retrieval is based on human behavior and the fact that the feedback of Web users when performing a search on the Web can enhance the user experience and the performance of IR systems.
Link analysis has considerably improved the e ectiveness of Web Search engines, thanks to the analysis of the hyperlink structure of the Web. According to [2], hyperlinks provide a valuable source of information for web information retrieval and a large number of links is created by independent individuals everyday.
In real life, web users generally do not get all the information they're looking for from the rst Web page they visit. Our approach not only o ers them the opportunity to have a direct access to the most relevant Web pages but also they can explore the whole sur ng path which contains Web pages with complementary information that may interest them as well. This new way to access information is ensured thanks to the fact that information foraging is inspired from human Web navigation behavior. Our approach takes advantage from some related research areas such as interactive information retrieval and link analysis. It particularly takes into consideration the Web pages' information content, their distribution on the Web and the relation between them. The evaluation of our proposal was held on a real website, unlike previous works that were tested on log les or other forms of data. 3
The Web is usually represented as a directed graph G(P, L). The vertices P correspond to the Web pages, where two Web pages pi and pj are connected via a directed edge if pi contains a link referring to pj . Considering a user with a speci c interest, we may assume that he is interested in visiting a branch of the webgraph, one node at a time starting from an initial Web page and ending at a page containing some relevant information concerning his interest.
The transition choices that the user makes during the navigation de ne his sur ng strategy. The set of visited Web pages while navigating is called a sur ng path. The goal of information foraging is to determine the optimal paths to reach relevant Web pages for a given user interest. To this purpose, at each click on a page pi , the question is to nd the best move to another page pj in order to build a sur ng path.
In the literature it has been outlined that the sur ng behaviors di er from one user to another, depending on the familiarity of the user with the Web environment, as well as his goal behind browsing the Web. In particular, three types of sur ng behaviors have been identi ed in [5], but not formalized:
A pseudo random strategy which concerns users that are not familiar with the Web and are browsing it without having a strong interests in any speci c topics; A rational strategy which is the closest to real-life Web navigation as most of Web users behave rationally. They usually have a speci c goal behind Web sur ng and they try to reach it by selecting the Web pages that seem the closest to their information need; A recurrent strategy concerning users who are familiar with the Web and have a well-de ned goal behind browsing it. This kind of users always makes the best decision when they have to move from the current Web page they are into a new one by selecting the most relevant Web page among to the possible pages.
When sur ng, Web users are guided by the information scent they get from Web pages. Starting with a weak amount, the information scent increases as the user gets closer to the Web pages that interest him. In order to model the user's information need (interest), we consider a vector containing keywords that represent topics in which the user is interested.
As mentioned in the previous section, the majority of Web users behave rationally when seeking information on the Web [5]. The aim of our work is to develop algorithms to e ciently implement the rational sur ng strategy. To this purpose we have applied Ant Colony Optimization (ACO). The main reason to choose ACO resides in the fact that it simulates the ants' food foraging behavior which is similar to the human information foraging behavior on the Web.
The ant system algorithm [1] includes several ant generations, each
generation is composed of NbAnts ants. Where NbAnts is the population size of the
ant colony. Each arti cial ant starts building a solution from an initial state i
generated randomly. Recall that a solution is a connection of states and it is
constructed using a stochastic process. The ant chooses a new state j from the
current state's neighborhood Ni, with a probability computed by Formula (
To each state i is assigned an amount of pheromone denoted by phero[i]. The pheromone information is initialized with a very small value in order to simulate the fact that real ants deposit a very small amount of pheromone on the ground when starting their food foraging. Two structures are needed to compute the ant algorithm, a table named Phero to store the pheromone amount yielded by the ants each time they build a solution and a table called sol to save the best solution found by each ant. phero[k] corresponds to the pheromone amount associated with the solution found by ant k and sol[k] is the best solution determined by ant k. The tables are updated at each generation of ants. Besides, two variables namely best and bestsol are used to save respectively the best solution found during the current generation and the best solution computed since the beginning of the process. During the search, the pheromone amount, which represents the e ectiveness of the solution, will be computed and associated with each solution found by the ants.
The strategies of updating pheromone simulate the evaporation of natural
pheromone followed by a production of this chemical substance. The evaporation
phenomenon gives rise to rule (
We present here the adaptation of the Ant Colony System algorithm to Web information foraging in order to simulate the rational sur ng behavior.
As we previously mentioned in section 3, rational users are interested in speci c topics and they forage in order to locate Web pages that contain information on those topics. When they reach a new Web page, they will try to decide whether or not the content su ciently matches their interest and, if not, predict which Web page at the next level will become a more interesting one. In predicting the next-level contents, they will rely on the information scent they get from the titles or descriptions of various hyperlinks inside the current Web page. We notice that the information scent is analogous to the pheromone that guides the ants when they're seeking food. In our adaptation, the arti cial ants simulate the behavior of Web users that have a rational sur ng strategy.
Input: N (A part of the Web); user interest;
Output: bestsol, a sur ng path ending with a relevant Web page;
1: procedure ACO-WIF
2: for i=1 to NbAnts do phero[i]= 0.1; . pheromone initialization
3: end for
4: select at random a solution s from N ; . a sur ng path namely s
5: best := bestsol := s;
6: for i=1 to MaxIter do
7: for k=1 to NbAnts do
8: sol[k] := build Sol();
9: update the online pheromone using Formulas (
In other words, the ant decides stochastically to consider the most relevant Web page among the outgoing Web pages when q q0 and a Web page drawn at random otherwise.
The evaluation of a sur ng path quality is performed by applying the tness function f to the last Web page of the path. This function represents the similarity between the user interest and the description of the Web page which contains the title of the page and eventually some tags and keywords. It can be computed using one of the similarity functions de ned in literature. if q
q0
then P (pi; pj) =
(1 if pj = argmax(phero[j] (heurjv) ) for pj 2 Ni
(
We performed our experiments on MedlinePlus, an online medical Website produced by the National Library of Medicine of the U.S. It provides information on over 900 diseases, health conditions and wellness issues. Our experiments deal with health topics described in an XML le that includes pages describing medical topics. The data for health topics is available at http://www.nlm.nih. gov/medlineplus/xml.html. We worked on the version of the 25th February 2016 where the number of Web pages was equal to 1946. Each topic is speci ed by a title and contains the following elements: a URL, a unique identi er, the language of the topic (English or Spanish), the date of its creation, topic synonyms, translation to other languages, a full summary, a list of related topics, which are internal links to similar topics and external links. 5.2
Di erent user interests were experimented for evaluating the rational sur ng strategy. The results we focused on are: the last Web page on the sur ng path (the most relevant one), its URL, its score, the sur ng depth of the path and the sur ng time in milliseconds. Table 1 exhibits the obtained results for the rational sur ng strategy.
Relevant Page User interest
From table 1, we can observe that our approach is able to nd relevant Web pages to the user based on the vector describing his interest. The developed program also makes use of the health topics' synonyms provided by MedlinePlus in order to locate the most relevant Web pages to the user. For example, in the third instance of the table the user interest was "Hypotension" and the result returned by the program was a Web page entitled "Low Blood Pressure" which is a synonym of Hypotension.
In this work, we presented an approach to Web information foraging based on Ant Colony Optimization. We proposed a model for Web sur ng in order to simulate the Web sur ng behavior of real Web users. This idea was inspired from the information foraging theory which states that Web users and animals have similar behaviors when looking for information/food. Furthermore, a real website was used for the experiments instead of an arti cial one or log les as it was performed in the literature. The results show the ability of our program to nd relevant Web pages in a short time based on a user interest. The outcomes consist in a set of sur ng paths ranked by relevance. This o ers the user the possibility to go more in depth with getting information on a certain topic without spending too much time on visiting a lot of Web pages.
As a perspective, we intend to investigate Web information foraging in social and information sharing networks such as Twitter.