In this paper the task of Information Foraging (IF) is considered as a useful paradigm to address Exploratory Search. In the context of IF, a Web navigation strategy is introduced and formalized, and a multi-agent based model is proposed to exploit a collaborative approach to Information Foraging. A system based on this model has been developed, and its preliminary evaluations on the ACM and DBLP repositories are reported. The results are promising and show the ability of the proposed Web Information Foraging system to nd relevant Web pages.
Nowadays, the human ability to explore the huge amount of data on the Web
is relatively limited [
In [
A recent paradigm related to Exploratory Search, and which aims at
discovering paths leading to relevant information on the Web is Information Foraging.
The idea of Information Foraging is grounded on the Optimal Foraging
Theory [
The task of Web Information Foraging consists in browsing the Web to collect
information related to speci c user's needs. An automatic Information Foraging
process simulates the user's behavior while sur ng on the Web with the aim
of nding relevant information. It starts with a topical user interest, then by
using an information scent measure [
In this paper, we propose a new collaborative Web Information Foraging
model; to make Web Information Foraging more e ective and e cient, we
propose to address it in a collaborative way. In fact, as outlined in [
The Web can be represented as a directed graph G(P; L), where the vertices P correspond to Web pages, and the edges L represent the connections between pages. A directed edge connects a page pi to a page pj if on page pi there exists a link referring to page pj . Let us consider a user with a topical interest, who starts sur ng on the Web from an initial Web page to reach a page containing relevant information to her/his interest. The sequence of visited Web pages during this process is called a sur ng path. The transition choices that the user makes when sur ng de ne her/his sur ng strategy, which a ects the way s/he selects the next Web page to visit, based on the information scent s/he perceives of each accessible page. The information scent of a given page is an estimation of how much useful information the user is likely to get on this page. Web sur ng strategies are related to users' behavior, which may depend on the users' familiarity with both the Web and computer science technologies, and also on their purpose behind Web sur ng.
In Section 2.1 we propose and formalize a Web sur ng strategy, and we exploit it by de ning and implementing a collaborative (multi-agent) system for Information Foraging. 2.1
In their Web navigation paths, users aim at increasing the information scent they perceive when moving from one Web page to another. If at time t a user is on a page pi, her/his motivation to move to a new page pj relies on the increase of information scent s/he would obtain in moving from the former to the latter page. The information scent increase at time t+1 with respect to time t can be modeled by a quantity proportional to the similarity between the content of the new selected page pj and the user's interest, which consist in a vector of keywords representing the user's information need and her/his motivation behind Web sur ng. We propose Formula (1) to estimate the information scent a user would get from a given Web page pj .
Inf oScent(pj ) = Inf oScent(pi) + S (1) where S is the similarity between the user's interest and the content of page pj . If we suppose that pi is the initial Web page from which the foraging starts, then the information scent at page pi would be equal to the similarity between its content and the user's interest.
In [
We propose a formalization of the rational sur ng behavior in Formula (2), which de nes the probability P (pi; pj ) to move from a page pi to one of its linked pages pj .
P (pi; pj ) =
Inf oScent(pj )
sim(pi; pj ) l2Ni (Inf oScent(pl) sim(pi; pl) ) (2) where and are parameters that control the relative weight of the InfoScent and the content-based similarity of pages pi and pj . Ni is the set of outgoing pages from page pi.
The outcome of a Web information foraging process consists in a sur ng path containing all the Web pages visited by the user during the Web browsing. The path starts from an initial page and ends with a target page which contains information relevant to the user's interests. The number of Web pages contained in the sur ng path is called the sur ng depth. A relevance score can be associated with a sur ng path, by assessing the similarity of the last page in the path and the formal representation of the user's interest (we do this by formally representing the above objects as vectors of terms and by applying the Cosine Similarity ).
In order to make the foraging process operational and e cient, and to the aim of de ning e ective systems based on this paradigm, it is unrealistic to provide just a path as a potential answer to an information need. To tackle the above issues, we propose a collaborative model that simulates the user's sur ng activity starting from several distinct initial pages; the proposed approach is presented in Section 2.2.
The collaborative approach to information foraging proposed in this Section is
based on the Web sur ng strategy described in section 2.1. By this approach
the foraging activity motivated by an information need is carried out by several
agents that act as aliases of a speci c Web user. The Web is the environment
where the agents operate. We adopt a graph-based representation of the Web
as previously explained, and we assume that each agent browses a part of the
Web graph with the aim of nding relevant information. Starting with the same
user interest, the agents forage information simultaneously in the Web with the
goal of reaching relevant Web pages. The collaboration feature is ensured through
the blackboard communication model, which o ers real-time communication and
results sharing between the agents as suggested in [
At the beginning of the process, several foraging agents are launched at the same time and each of them starts its foraging from an initial Web page randomly selected. Each time a foraging agent makes a move towards a new Web page using Formula (2), it evaluates its new partial solution (actual sur ng path) and communicates it to the other agents by writing it on the blackboard. The blackboard-handler agent will then sort the solutions according to their relevance to the user interest and will share the top solutions on the blackboard. If the proposed solution by the foraging agent is a top solution then the agent continues sur ng on the same path, else the agent abandons its current sur ng path and starts sur ng again from a new Web page de ned randomly. Procedure 1 presents the pseudo-code of the foraging agents' behavior.
Procedure 1: Foraging Agent 1. Select a Web page at random ; 2. Perceive the environment and check the neighborhood of the current Web page ; 3. Move to a new Web page using Formula 2 ; 4. Add the new Web page to the sur ng path ; 5. Communicate the sur ng path to the other agents by writing it on the blackboard ; 6. Wait for the blackboard-handler agent to sort the solutions ; 7. Check the blackboard ; if 8. the sur ng path belongs to the top solutions then
go to 2 ; else
9. Abandon the current sur ng path and Go to 1 ; Blackboard System The blackboard system is a communication model that allows information sharing between the agents in our system. More concretely, it is an area of shared memory accessible in read and write mode by all the agents. The blackboard facilitates the collaboration between the agents as it o ers them the possibility to exchange knowledge and share their partial solutions and suggestions for the sake of nding the best information sources that give answers to the user's interest.
Blackboard-Handler Agent The main function of this agent is to sort the solutions reported by the foraging agents in the blackboard according to their relevance to the user interest. Each time a foraging agent reports a new solution in the blackboard, the blackboard-handler agent inserts it in the right position in order to keep the top solutions sorted. Procedure 2 shows the pseudo-code of the blackboard-handler agent. 3
In this section we report the preliminary experiments that we have undertaken on both the DBLP and ACM repositories. Both repositories give access to sci
Procedure 2: Blackboard-Handler Agent 1. Check the blackboard ; 2. Sort the solutions proposed by the foraging agents according to their relevance ; 3. As soon as a new solution is reported by a foraging agent insert it in the right position in the sorted list containing the top solutions ; 4. Update the top solutions list on the blackboard ; 5. Go to 3; enti c publications through their websites where each scienti c publication has a corresponding Web page. Based on experiments conducted on the considered datasets, we xed the values of the empirical parameters of Formula (2) as follows: = 2; = 1. Furthermore, We used 80 foraging agents and xed the size of the top solutions list to 25. 3.1
We built our rst dataset using the XML version of the DBLP website available on http://dblp.uni-trier.de/xml. We constructed a partial graph of the website considering 65,336 articles that represent the nodes of the graph. After that, we linked all the articles that share at least one author in common. The obtained graph contains 65,336 nodes, it has a size of 640,810 and a density equal to 0:15 10 3.
As a second Dataset, we used the ACM-Citation-network V8 [
Table 1 shows the top ve results on the DBLP dataset for the user's interest described in the rst column. The second column exhibits the last page of the sur ng path found by the system. The third and fourth columns present respectively the score of the sur ng path and the sur ng depth.
Table 2 presents the outcomes yielded by our approach on the ACM citation network. For each user interest we give the full sur ng path starting from the rst visited page. We notice that the last page in the sur ng path is the most relevant to the user. However, the other pages are also related to the user's interest, and they may be interesting to her/him. 3.2
In order to validate our approach, we compared the results produced by our system to those returned by the DBLP and the ACM local search engines. In fact, both repositories are equipped with local search engines (http://dblp.unitrier.de/search/, http://dl.acm.org/), which give the Web users the opportunity to perform a keyword-based search for scienti c publications. We selected about Score Sur ng
Depth 0.86 4 User's Interest
Last Web page in the Sur ng Path
Approximate, Personalized, Information,
Retrieval, Database, Management, Systems
Approximate Retrieval: A Comparison of
Information Retrieval and Database
Management Systems Exploiting the Functionality of Object-Oriented 0.67
Database Management Systems for
Information Retrieval Models for Integrated Information 0.62
Retrieval and Database Systems Personalized Information Retrieval System 0.57
Enriching Information Retrieval 0.44 3 3 3 2 20 user's interests representing information needs related to scienti c domains and related research elds. We introduced the selected user's interests separately as inputs to our system, and then we performed a search with those same user's interests by using the local search engines of each website. The results produced by our approach were similar to those of the DBLP and ACM search engines, however there are some di erences it is worth to point out. The rst di erence is related to the fact that although the datasets we used do not cover the complete DBLP and ACM repositories, this did not a ect the results quality returned by our approach regarding the tested user's interests. The second di erence resides in the way of presenting the search results to the user. Both DBLP and ACM employ Information Retrieval techniques, for each search a set of results is returned. The results are ranked according to their relevance to the considered query, and each of them direct to a Web page dedicated to a scienti c publication. On the other hand, our approach returns a set of sur ng paths also ranked by their relevance. Each sur ng path contains one or more Web pages with the last one being the most relevant. Our way of presenting the search results using Information Foraging takes into consideration the relations between the di erent scienti c publications/Web pages, unlike the classical way used by the majority of search engines. For instance, the knowledge about the co-authorship relation in our DBLP dataset and the knowledge about the citation relation in the ACMCitation-network enhance the search process by allowing the system to bene t from those relations, thus not being only dependent on the keywords describing the user's interest. 3.3
We asked a group of 10 Master's and Ph.D. students to give us 3 topics related to their research area on which they want to get scienti c articles. At the end we got 30 di erent user interests, each one of them is modeled by a set of keywords that describe the information need of the user. After that, we have run our program for each user interest and presented the outcomes to the corresponding
User's Interests Ant, System,
Optimization Neural, Networks 2 1 Satis ability, Sat, 2
Optimization Information,
Foraging Information,
Retrieval, Algorithms
Sur ng Path user. We then asked each user to determine the position of the most relevant result among the list of ranked results.
Figure 2 details the feedback we got from the users. The values on the horizontal axis represent the position of the sur ng path that is the most relevant to the user while the values on the vertical axis correspond to the rate of the satis ed user interests. 4
We proposed in this paper a new collaborative multi-agent approach to Web Information Foraging where the foraging agents cooperate to nd relevant Web pages according to a user's interest. We de ned a Web sur ng strategy inspired from real Web users' behavior and gave the pseudo code of the software agents. In order to obtain a preliminary evaluation of our approach and compare it to classical IR, we considered two datasets with di erent sizes.
The results we achieved show the ability of our approach to nd relevant Web pages in an e ective way based on a user interest. Our approach is also capable of exploiting relations related to the Web structure. For instance, it can use the citations and co-author relations in order to access scienti c publications.