Behavior Based Adaptive Navigation Support Michal Holub Mária Bieliková Institute of Informatics and Software Engineering Institute of Informatics and Software Engineering Faculty of Informatics and Information Technologies Faculty of Informatics and Information Technologies Slovak University of Technology Slovak University of Technology Ilkovičova 3, 842 16 Bratislava, Slovakia Ilkovičova 3, 842 16 Bratislava, Slovakia holub@fiit.stuba.sk bielik@fiit.stuba.sk ABSTRACT recommendation based on monitoring user activities and social Web portals contain large amount of information. Users could principles is a viable approach for such cases. In this paper we really benefit from it if personalized presentation is used. For this introduce a method of navigation adaptation and social to be accomplished the website needs to “know” its users. When recommendation of links among users with similar behavior. surfing the Web users leave digital footprints in the form of navigational paths and actions taken. We present a method for 2. RELATED WORK adaptive navigation support and link recommendation. The People use different means of accessing information on a web method is based on an analysis of the user’s navigational patterns portal. The most common way is to follow hyperlinks, which and behavior on the web pages while browsing through a web accounts for more than half of all possibilities [7]. This introduces portal. We extract interesting information from a web portal and a problem with improper navigation containing large number of then recommend it. Finally, we provide our experience with links. The user has often a problem of deciding which link to use. a recommender system deployed on our faculty’s website, which Therefore a recommendation of links on the web page could bring recommends events by means of personalized calendar. significant improvement to user’s browsing experience. Other dominant mean of navigation is using the browser’s back button Categories and Subject Descriptors [12]. Accessing websites through the history, bookmarks and H.5.4 [Information Interfaces and Presentation (e.g., HCI)]: other means is insignificant. Hypertext/Hypermedia Navigation. H.3.3 [Information Storage User’s habits can be derived from the navigational patterns found and Retrieval]: Information Search and Retrieval Relevance in the sequences of links he uses in a particular web portal. Four Feedback. basic navigational patterns (path, loop, ring and spike) were described in [6]. From the prevailing patterns in browsing sessions different browsing strategies can be identified. General Terms Algorithms, Design, Experimentation, Verification. User’s interests are often determined based on the content of documents the user has read [5]. The user model can be expressed Keywords by concepts or keywords extracted from these documents [2]. If Adaptive navigation support, automatic interest estimation, we know what topics (usually expressed by the keywords) the user behavior, link recommendation, navigational patterns. prefers, we can recommend him documents (web pages) with similar content. The disadvantage is that documents should be written in language which we can process (a translation can help). 1. INTRODUCTION Web portals are being visited by various users pursuing different In [16] authors use rather different approach based on user goals. However, most websites offer all groups of visitors the behavior tracking to estimate his interest. For this we need to get same content. Therefore the visitors are often presented a feedback from the user. There are several ways how to implicitly information in which they have no interest [4]. determine user’s interest. When links are well annotated (like on news portals where links to articles contain a short introduction) While browsing through a web portal some users can discover the event of clicking on the link is considered as positive interest interesting pages that are hidden deeper in the hierarchy of the [8, 14]. However, in general scenarios we cannot always consider portal. If the users with similar goals knew about these pages they clicking on a link as truly positive interest in the web page. could find them interesting, too. Personalized navigation and To determine user’s interest we can also use actions he makes on a web page [11]. Printing the page or adding it to bookmarks show positive interest. Spending very short time reading it or even closing the browser prematurely shows negative interest [16]. With user’s interest determined navigation personalization as well as link recommendation can be done [9, 13]. In [10] authors Copyright is held by the author/owner(s). Workshop on the Practical propose a method of interesting link recommendation by Use of Recommender Systems, Algorithms and Technologies (PRSAT highlighting the links. They extract keywords from the pages 2010), held in conjunction with RecSys 2010. September 30, 2010, a user visits and recommend links that lead to other pages which Barcelona, Spain. contain the same keywords. Adaptive system Web Watcher, which we use the referrer field of HTTP request message. If the URL of implements this approach, can also show similar pages to the page previously visited page equals referrer value of currently visited that is currently being viewed based on this principle. The system page, we consider the pages to be in the same session. uses a proxy server to incorporate its toolbar into every web page. The process of dividing users into groups is presented in Alg. 1. Other method is based on monitoring the context in which the Similarity of users is expressed as Pearson correlation coefficient links are being used [1]. This method consists of creating [15] commonly used in collaborative filtering. a knowledge base from the links each user has clicked on. Then the clusters of links, which are often used together, are built from Algorithm 1 Group users according to their similarity. the knowledge base. Links from a cluster with the largest overlap 1: for each user u do with the current session of the user are recommended to him. 2: find patterns in clickstreams of u All methods mentioned share the same feature which is user 3: put u to group according to prevailing pattern interest estimation based on his actions. They prefer behavior of 4: for each group g do the users over content of the documents which they were shown. 5: for each user u in group g do 6: sort users in group g according to their similarity to u 3. ADAPTIVE LINK RECOMMENDATION We propose a method for adaptive recommendation of interesting Every user ends up in exactly one group according to the most links in a particular web portal (which we may or may not own). dominant pattern found in his surfing history. There is one more For a specific user we select links that similar users found group for users with no dominant navigational pattern. The order interesting. We also recommend links to this user based on his of similar users from one group is unique for each user. previous surfing sessions. Our recommender system extracts further information from the web pages, which is also shown to Alg. 2 presents the process of recommending links among users. the user. The recommended links are shown in special sections added to each web page of the portal. Algorithm 2 Recommend links for user u by similar users. 1: similar = select top K similar users When deciding which link to recommend we do not consider the 2: for each user v in similar do content of web pages. We based our recommendations solely on 3: for each page p visited by v and not visited by u do the analysis of user’s behavior. Our method thus does not depend 4: predict interest of user in page (u, p) on the language of the website. We are able to analyze interest 5: recommend top M pages with highest predicted interest and patterns on different language versions of the same portal. Our method of adaptive link recommendation works in two steps: Navigational patterns of users have to be of a certain minimal 1. Mining web usage history for navigational patterns. length (so that each sequence of two following pages does not represent a path pattern). After finding similar users to user u we 2. Recommendation of links based on user’s behavior. select top K of them to form a recommendation group. The groups In the first step we analyze the sequences of followed links from change according to new browsing sessions in which the users can each user’s session. In these sequences we look for navigational behave differently. This reflects the evolution of user’s behavior patterns. We use the prevailing pattern to categorize users, as it in time. However, at each time the user belongs to exactly one determines user’s surfing habits on a particular web portal. As an group according to the most dominant pattern in browsing history. output we get groups of users with similar navigational patterns. In the second step we monitor behavior of users on each visited 3.2 Determining interest of users web page of the portal. From their actions we automatically In order to recommend links to a particular user we need to estimate their interest in that page. We then recommend links to evaluate the interests of the users in his recommendation group. interesting pages among users of each group from the step one. We can recommend pages which other users liked. To determine user’s interest in a particular web page we observe actions he 3.1 Discovering navigational patterns makes on this page. These include time spent on a web page, number of scrolling events that occur and number of times he We find similar users based on comparison of navigational copies text into the clipboard. We chose these interest indicators patterns they follow in a closed web portal. We believe that users because their tracking is platform independent. who follow analogous paths should be recommended similar links. There are four basic navigational patterns according to [6]: Our method is based on the comparison of current user’s behavior with the behavior of other users. We compare the values of time Path – a sequence in which nodes do not repeat. and scrolling with values from other people who visited the same Ring – a sequence that starts and ends in the same node. page. If the value for the current user is more than X % higher Loop – a sequence that goes through already visited node. than the average, we consider it as a sign of positive interest in the page. In contrast, when it is more than X % lower than the Spike – a sequence that goes back through the same trail. average we consider it as a sign of negative interest. When the In each session a user visits several pages of the web portal. This value is around average (± X %) it is a sign of neutral interest. session is described by a vector whose elements are links to the This way we can also consider other interest indicating actions. web pages arranged in order they were visited. We consider The exact value of X depends on the calibration for selected a continuous sequence of links to be a session. For this purpose domain; in our experiments we used the value of 20 %. When no behavioral data for a particular web page is available we selects the links to be recommended. The user model consisting of cannot estimate the user’s interest. This is a problem with newly the session vectors and his behavior is being periodically updated. added pages as well as with pages visited for the first time. request Adaptive Proxy Server request We estimate the actual value of user’s interest in each page he modified response visits according to Figure 1. We increase this value by 0.1 when WebImp Plugin Website add personalized content the user also copied text into clipboard; otherwise we decrease it by 0.1. Resulting interest is in the interval <0,1> with 0 meaning response no interest and 1 meaning total interest in the visited web page. Behavior Plugin add tracking JavaScript Web browser store actions web pages personal calendar recommended links Domain pages, events SpyImp model analyze pages User model create events crawl behavior, analyzed pages data flow AdaptiveImp find navigational patterns find similar users control flow estimate user’s interest recommendations create recommendations Figure 2. Architecture of proposed link recommender system. Figure 1. Estimation of user's interest from his actions. Our plug-in to the adaptive proxy (WebImp) modifies the web page by adding special sections with recommended links. One of those sections is personalized calendar. Many web pages on the 3.3 Social recommendation of links web portal of our faculty inform about an upcoming event. We We recommend web pages by predicting user’s interest in yet automatically extract dates from these pages and create events. unseen pages using collaborative filtering method. We compute Using proposed method we determine user’s interest in such page. the predicted value of interest like this [15]: Then, if the interest is positive, we add the event to user’s N calendar. This way we also recommend events among users. u 1 (ru ,i ru ) S a ,u pa ,i ra N We monitor the portal and capture every change in text of a web S u 1 a ,u page (this could be for example a change in time and place of some event). Every changed page is marked as news and added to where pa,i means prediction of interest of user a in page i, ra is the a special news section. We also recommend other potentially average interest of user a in all visited pages, ru,i is the interest of interesting links which are neither events nor news. Figure 3 user u in visited page i, Sa,u is the value of Pearson correlation shows part of a web page enhanced with personalized sections. coefficient [15] between users a and u determining the similarity of their interests, and N is the number of similar users. 4. EVALUATION AND EXPERIMENTS To evaluate the proposed method for user’s interest estimation we developed software tools which support adaptive navigation by recommending information extracted from potentially interesting web pages to guests of particular web portal. We experimented with the web portal of our faculty (www.fiit.stuba.sk). We proposed client-server architecture with an adaptive proxy [3] in the middle as shown in Figure 2. Adaptive proxy can be extended to conduct various methods of web personalization on any web portal. We use proxy to put behavior tracking script into the web page. It sends logged behavioral data to the server when the user is active (i.e. when he uses the mouse). The user is aware of this when he agrees to use our proxy server. The data is anonymous – we only know a random ID associated with each user. The delay caused by the proxy server is imperceptible. One component (SpyImp) creates the domain model by analyzing web pages of selected web portal. Another server component Figure 3. Calendar (shows recommended event on 10/05/2010), (AdaptiveImp) is responsible for grouping of users, estimating additional links and personal news sections. their interests and making predictions for unseen pages. Then it We provided a series of experiments on our faculty website. 7. REFERENCES Actions of 24 users on a modified website were monitored for 3 [1] Baraglia, R., et al. 2006. A Privacy Preserving Web weeks. We compared our calculations with their explicit feedback. Recommender System. In Proc. of the ACM Symposium on Results indicate that time actively spent on a web page is the best Applied Computing, (Dijon, France). ACM Press, 559-563. interest indicator. Scrolling proved to indicate positive interest as [2] Barla, M. and Bieliková, M. 2009. On Deriving well. However, when the user does not use scrolling, it does not Tagsonomies: Keyword Relations coming from the Crowd. always mean he is not interested in the page. The accuracy of our In LNAI 5796, Proc. of Int. Conf. on Computational interest estimation method was 62 %. Collective Intelligence, ICCCI 2009, Springer, 309–320. The sections with recommended links – especially calendar – [3] Barla, M. and Bieliková, M. 2010. Ordinary Web Pages as a were attractive (according to answers from questionnaire) and the Source for Metadata Acquisition for Open Corpus User users found 55 % of recommended links and events interesting. Modeling. In IADIS Int. Conf. WWW/Internet. To appear. Some users were not satisfied with the recommendations. The [4] Barla, M., Tvarožek, M. and Bieliková, M. 2009. Rule-based problem was that they visited the website for the first time. Hence User Characteristics Acquisition from Logs with Semantics their user model was empty and we could not provide suitable for Personalized Web-based Systems. Computing and recommendations. This is a common problem with recommender Informatics, Vol. 28, No. 4, 399-427. systems and new users. We tried to overcome it by recommending the most interesting events (links) according to behavior of all [5] Brusilovsky, P. 1996. Methods and Techniques of Adaptive users. However, this is not always a suitable solution. Hypermedia. User Modeling and User-Adapted Interaction, Vol. 6, No. 2-3, Springer Netherlands, 87-129. 5. CONCLUSION AND FUTURE WORK [6] Canter, D., Rivers, R. and Storrs, G. 1985. Characterizing We have presented a method for adaptive recommendation of User Navigation through Complex Data Structures. Behavior interesting links. Our approach is based on collaborative filtering, and Information Technology, Vol. 4, No. 2, 93-102. which has a potential to be used in unusual ways. We presented [7] Cockburn, A. and McKenzie, B. 2001. What do Web Users one of them when considering data about user’s actions instead of Do? An Empirical Analysis of Web Use. Int. Journal of content of pages. This way we are able to predict user’s interest Human-Computer Studies, Vol. 54, No. 6, 903-922. for unvisited pages. Our method achieves solid results and can be [8] Das, A.S., et al. 2007. Google News Personalization: further improved in a recommender system which will combine Scalable Online Collaborative Filtering. In Proc. of the 16th content analysis with behavior, which is our plan for future work. Int. Conf. on World Wide Web (Banff, Canada), ACM Press, In this paper we presented a useful application of our method by 271-280. creating personalized calendar of events on our faculty’s website. [9] Gurský, P., et al. 2009. User Preference Web Search – Using this method we can also personalize other sections of a web Experiments with a System Connecting Web and User. page as well. In our opinion recommender systems should bring Computing and Informatics. Vol. 28, No. 4, 515-553. added value to users by doing further analysis of the domain which is being adapted. On the web they should recommend [10] Joachims, T., Freitag, D. and Mitchell, T. 1997. particular objects (e.g. events) instead of simply listing potentially WebWatcher: A Tour Guide for the World Wide Web. In interesting links to web pages. In order to accomplish this we Proc. of the Int. Conf. on Artificial Intelligence (Nagoya, need to use more text processing algorithms in our recommender Japan), Morgan Kaufmann, 770-777. systems so that they “understand” the meaning of text on the web. [11] Krištofič, A. and Bieliková, M. 2005. Improving Adaptation We ran up against a problem with incorporating the sections with in Web-Based Educational Hypermedia by means of personalized content into a website. In order to do this we need to Knowledge Discovery. In Proc. of 16th ACM Conf. on know the semantics of the website’s structure. This is also useful Hypertext and Hypermedia, ACM Press, 184-192. during page analysis and content extraction. We consider the [12] Milic-Frayling, N., et al. 2004. Smartback: Supporting Users special tags in HTML5 (e.g. nav, footer) to be insufficient so we in Back Navigation. In Proc. of the 13th Int. Conf. on World came up with a descriptive XML file which pairs HTML tags and Wide Web (NY, USA), ACM Press, 63-71. their IDs with their predefined meaning (left menu, right menu, [13] Návrat, P., Taraba, T., Bou Ezzeddine, A. and Chudá, D. etc.). This way our recommender system understands the structure 2008. Context search enhanced by readability index. IFIP of a website and can alter some sections. We think that there is a WCC Series 276, Springer, 373-382. need for further development of this format and we see an opportunity for its adoption by other recommender systems. [14] Suchal, J. and Návrat, P. 2010. Full Text Search Engine as Scalable k-nearest Neighbor Recommendation System. IFIP WCC Series 331, Springer, 165-173. 6. ACKNOWLEDGEMENTS [15] Sugiyama, K., Hatano, K. and Yoshikawa, M. 2004. This work was supported by grants VG1/0508/09, KEGA 028- Adaptive Web Search based on User Profile Constructed 025STU-4/2010 and the Foundation of Tatrabanka. It is a partial without any Effort from Users. In Proc. of the 13th Int. Conf. result of the Research & Development Operational Program for on World Wide Web (NY, USA), ACM Press, 675-684. the project SMART II, ITMS 25240120029, co-funded by ERDF. We wish to thank members of PeWe group, pewe.fiit.stuba.sk for [16] Velayathan, G. and Yamada, S. 2006. Behavior-based web valuable discussions and their help in experimental evaluation. page evaluation. In Proc. of the 15th Int. Conf. on World Wide Web (Edinburgh, Scotland), ACM Press, 841-842.