Dynamic and adaptive structuring of the World Wide Web based on user navigation patterns.

Johan Bollen & Francis Heylighen
Faculteit Psychologie
Vrije Universiteit Brussel
Pleinlaan 2
1050 Brussel - Belgium

A PostScript version of this paper (Word 5.1) can be downloaded here.
We also have a nicer (and longer) hypertext version with frames and hyper-indexes.

1.1. Navigation in the WWW

The WWW's size and the variability of its content is enormous. Experienced browsers can be expected to acquire a certain degree of familiarity with specific parts of the network, but this knowledge will be useless in each unexplored server with its own idiosyncratic design and linkage. We therefore presume information-seeking browsers to apply certain associative 'homing' or 'tuning' heuristics to retrieve information from the network, such as 'Hill-Climbing' [Schildt, 1987]. Hill Climbing in hypertext networks could be conceived as a heuristic in which users try to locate information in the network by always navigating towards a decreased 'associative' distance between their present position and their goal.

Users' assessments of 'associative distance' are most likely to be based on a set of general expectations concerning the associations between concepts and ideas. Users share these intuitions as they are part of their common sense understanding of the world. If one accepts the notion of users applying hill-climbing-like heuristics to retrieve information from hypertexts then two conclusions can be drawn concerning the desired characteristics of hypertext networks in general. First, the associative structure of hypertexts should maximally resemble that of its users so that their knowledge of associations can effectively be applied to browsing the network. Secondly, heuristic browsing at present works because hypertext networks are in fact associative in nature.[Jonassen, 1990] Hyperlinks represent associative relations, just as is the case in many neural networks [Mc Clelland & Rumelhart, 1989][Hinton et al., 1981]. But, in the case of the WWW, connections have no visible strengths or degree of relatedness assigned to them (except perhaps implicit in the typographic design) that heuristic browsers could use to navigate the network .

In conclusion, hypertext networks and the WWW lack control over precise direction of connections (are the right nodes connected as far as users' associative knowledge is concerned?) and modulation of existing connections. (how to choose among alternative links from the same page?) This problem defines the complexity and cognitive load involved in the navigation process.[Bollen, 1996][Van Dyke Parunak, 1991]

1.2. Technical Considerations.

The WWW has no levels of control above individual HTTP servers. Any algorithm trying to improve/adjust network structure is therefore limited to what individual HTTP servers can do and measure. The information available to individual HTTP servers is limited to where a certain browser came from and where he/she is going to. If it can be assumed that most browsers visit not more than 5 documents stored on the same server[Catledge&Pitkow, 1995], adaptive or dynamic hypertext systems will have to rely on very partial information concerning browser navigation behaviour. Also, the control of any system for the automatic adaptation of structure for the WWW is limited to every small and local network stored on individual servers. Many of the existing systems for flexible hypertext depend on extensive information being stored and managed besides the actual hypertext network, such as users' explicit appraisals of relevance [Mathe & Chen, 1994] or semantic knowledge networks that aid users in establishing useful connections [Berger et al., 1994]. They will for the above mentioned limitations be very difficult or even impossible to implement for the WWW.

Any system capable of dynamically adapting network structure and content to the demands of its users must be able to deal with these limitations. It should therefore use information that is locally available to HTTP servers and operate on local documents and their connections to other non-local documents.

As an expansion of the principles outlined in the previous chapter, (i.e. hypertext networks are associative networks much like neural networks), we constructed a hypertext network in which each connection between two nodes A and B is associated with a unique uni-directional measure of the strength of their associative relation. The strength of this relation is dynamically derived from browsers' navigation patterns by a set of 3 Hebbian learning rules. (Hebb's original law of learning [Hebb, 1967] stated that if within a learning network two nodes were stimulated at the same or nearly the same time, learning should take place by increasing the strength of the connection between these two nodes. We have replaced the notion of excitation by navigation: a node is excited if it is being retrieved)

2.2. The learning rules:

1. Frequency: if the connection from node A to node B has been used, it will be strengthened by a small reward Fb.

2. Symmetry: if the connection rfom node A to node B has been used, the connection between the nodes B and A will be strengthened by a small reward Sb.

3. Transitivity: if the connection from node A to node B has been used, and subsequently the connection from node B to node C has been used, the connection between node A and C will be strengthened by a small reward Tb.

As the network is being browsed, these learning rules will change the value of connections among nodes in the network, based on local patterns of user navigation. They operate in parallel and strictly locally to reinforce worthwhile, existing connection (frequency) and initiate new, previously non-existing connections among nodes (symmetry and transitivity)

2.3. Communicating Dynamical Network Structure.

The structure of a dynamically adaptive hypertext network, as coded in the underlying connection strength, must in some way be communicated to its browsers. We opted for a system in which out-going links from a particular node are ordered according to their connection strength: the strongest connection would appear on top, weaker connections on the bottom of the list. This principle has already been outlined by [Tomek, Maurer & Nassar, 1993] and [Kaplan, Fenwick & Chen, 1993]To avoid extensive scrolling, the ordered list of out-going connections was sliced in packages of 10, with the possibility to browse through the list by selecting a 'next 10 items' hyperlink.

Content: Our choice for the content of our Adaptive Web network had to be as a-selective as possible. Also, the content of our network had to be large enough to allow for extensive, deep browsing without having to return upon one's previous path, yet its size had to remain manageable for implementation and data-analysis. We opted for the 150 most frequent English nouns, as derived from the LOB corpus [Johansson & Hofland, 1989) (a frequency analysis of a large base of spoken and written English). As far as semantics and associative relations are concerned, word-frequency seemed to be a relatively a-select criterion for the selection of our words. Also, frequent nouns are also often those that have the best generally understood meaning.

Initialisation: The connections in our network of 150 nouns were initialised to small, random values (1/100>v>0),that were a factor 100 smaller than the rewards administered by the 3 learning rules to allow the interface to generate an initial, random ordering of links according to descending connection strength.

The different rewards administered to connections by our learning rules, were set to the following values:

Frequency: Fb=1, Transitivity: Tb=0.5 , Symmetry: Sb=0.3

These values were chosen so as to reflect the perceived relative importance of a certain learning rule to the network's development. Frequency, as the sole selection principle for existing connections, was considered most important and therefore administered relatively high rewards in comparison to the Transitivity and Symmetry learning rules that generate new and original links whose usefulness has not yet been proven. We presumed the success of our experiment not to be critically dependent upon the precise reward values involved.

Implementation: The nodes and their connections were stored as cards in a HyperCard stack that communicated with our Webstar server through AppleEvents. The stack kept track of individual browsing patterns using 'cookies', administered rewards to the connections in the network as indicated by the learning rules and generated the on-line HTML documents (in accordance with the previously mentioned interface presentation principle of node ordering).

General interface to the experiment: Participants first received a short page (http://cleamc11.vub.ac.be/ADHYPEXP.html) outlining the general principles of our experiment and what we expected from our experimental subjects. From there on, a link was offered to the actual Adaptive Web network. The adaptive pages themselves consisted of a header indicating the browser's position in the network, e.g. 'cat', that was followed by a vertically ordered list of 10 node names that could be reached from that position (e.g. 'dog', 'pet', etc.) According to the previously mentioned "presentation principle" (chapter 2.3), this list was ordered to descending connection strength and in its turn followed by a 'more links...'-reference that led to the following 10 connections. Once a certain connection from the list was selected (e.g. 'dog'), the browser was then referred to that next node. The header again being the selected noun, followed by an ordered list of connections from the selected node, and so on.

Subjects: The experiment was announced to several newsgroups and mailing lists and was made available to the general Internet public via our HTTP server. Since our subjects connected to the experiment via the Internet, we had very little control over their actions . Actual browsing behaviour could not be monitored and registration of individual characteristics was entirely voluntary. Only very partial data were retrieved concerning gender, language, nationality, etc.

Two experiments: Two experiments were conducted independently within an interval of 3 months, with a different random initialisation of connection weights, a different group of subjects and the addition of the symmetry rule in the second experiment to speed up network development (by the creation of more original links).

Each of the two mentioned experiments involved over 600 participants, resulting in a total of 1200 participants for the two experiments. At an average of about 10 links per participant, this amounts to more than 6000 selections per experiment. Each experiment consisted of 2 to 3 weeks of intensive browsing, often by more than 5 simultaneously browsing participants.

4.2. Network development.

Rapid: After only 2500 link selections (out of 150^2 possible links) both experimental networks had achieved a well-organised structure. This was in particular true for the second experiment, where the addition of the symmetry learning rule practically doubled the introduction of new links in the initial stages of network development. Afterwards network development slowed down and settled in on the connections that had been established. Table 1 illustrates how connections from the node 'MIND' are gradually built up and how the ordering of connections slowly settles throughout the development of the network.

MIND
table	thought	thought	thought	thought
order	idea	idea	idea	idea
figure	research	knowledge	knowledge	knowledge
party	problem	change	theory	view
question	need	development	development	education
school	light	research	change	theory
act	development	view	research	development
history	change	need	view	research
fact	view	problem	need	change
wife	law	theory	education	problem
Jumps: 0	600	1200	2400	4200

Table 1: evolution of 10 strongest links from the word "Mind": initial random linking pattern, after 0 (random initial state), 600, 1200, 2400 and 4200 browsed connections.

Clustering: "Hypertext Browsing is the ultimate accretion medium."[Jonassen, 1989] After an initial phase of rapid development of new, meaningful links that superseded the random, initialised connections, nodes got clustered in medium-sized groups or "families" of associatively related nodes. A cluster analysis (using powers of the network's matrix to find strongly inter-connected groups of nodes) of the second experiment's final network structure revealed the following 9 clusters of associated words, each denoted by an intuitive label for the underlying conceptual category:
"Time": age, time, century, day, evening, moment, period, week, year
"Space": place, area, point, stage
"Movement": action, change, movement, road, car
"Control": authority, control, power, influence
"Cognition": knowledge, fact, idea, thought, interest, book, course, development, doubt, education, example, experience, language, mind, name, word, problem, question, reason, research, result, school, side, situation, story, theory, training, use, voice
"Intimacy": love, family, house, peace, father, friend, girl, hand, body, face, head, figure, heart, church, kind, mother, woman, music, bed, wife
"Vitality": boy, man, life, health
"Society": society, state, town, commonwealth
"Office": building, office, work, room
Although the learning algorithms only work on links and not on groups of nodes, it is remarkable how well the resulting clusters fit in with intuitive categories. With rare exceptions (e.g. "side" in the "Cognition" cluster), all of these words seem to be located in the right class.

Positive feedback and network development. Our interface principle, ordering of available links according to their connection strength, combined with the Hebbian principle underlying our Frequency learning rule, introduced a positive feedback loop into the functioning of our Adaptive Web. Since the strongest connections always appeared on top of the list of available connections, they also had the highest probability of being selected by browsers. This in turn made these connections more eligible for rewards administered by the Frequency learning rule. We expected this "Matthew"-effect to keep reinforcing the same existing connections and hamper the introduction of new, original connections into the system. A temporal analysis of the development of the 20 strongest links in the network showed however that at least 6 out of these 20 connections had been introduced by the Symmetry and Transitivity learning rule. This demonstrates that in spite of the positive feedback loop which reinforces only the already successful connections, a large part of the connections still emerged without having been explicitly selected by human browsers. They had been independently proposed by the Adaptive Web system's Symmetry and Transitivity learning rules and were then be picked up by a fast, positive feedback loop of rewards by the Frequency learning rule.

Reliability and Validity of the learning mechanism: As mentioned, the structure of hypertext networks should as accurately as possible reflect their browsers' general knowledge of associations. In order to achieve such networks by our Adaptive Web system the process in which they are being generated needs to be as reliable and valid as possible. Reliability of network development can be measured as the extent to which trained, Adaptive Webs converge to one single state when being trained by the same browsers. This state might however be stable but need not necessarily be "true". The validity of network development is equally important as its reliability and can be measured by the extent to which each developed network actually resembles the browsers' associations. To test whether network development under the Adaptive Web System generates reliable and valid network structure, hypertext networks need to be repeatedly trained by exactly the same browser, whose associations are known in full detail. These considerations led us to the development of a simulated, idealised software browser which was programmed so that it could train hundreds of adaptive networks by browsing them using a fixed and known map of associations (derived from the association-data gathered in Adaptive Web experiments).

Reliability was then measured as the QAP correlation [Hubert & Schultz, 1976] between 20 independently trained networks. (each 3000 jumps by the Artificial Browser). This correlation averaged to 0.79, indicating a relatively high reliability. Validity was measured as the QAP correlation between 20 independently trained networks (3000 jumps by the Artificial Browser each) and the browsers associative map. This correlation averaged to 0.82, indicating a high overlap and consequently a relatively high network validity.

Apart from the practical implementation of this system for adaptive hypertext, further research will necessarily concentrate on establishing accurate models of human navigation behaviour. Can the relation between certain browsing strategies and the required network structure be quantitatively modelled and expressed as guide-lines to network designers?

A number of other issues concerning the limitations of our experimental set-up need to be addressed as well. First, the nodes in our experiments are represented by single words that are also used as their own reference-markers. But in actual hypertext networks nodes consist of texts, images and sounds, that are being referred to by composed markers that do not always have a clear and definite relation to the 'meaning' of the material they are referring to. Clearly, the reliability and validity of network development would have been much more difficult to measure under these conditions and we therefor chose to limit the complexity of our nodes' content and reference markers to a bare minimum. A number of implementations with more realistic, real-life hypertext networks are underway and this will enable us to determine the efficacy of the system in more realistic circumstances.

Also, our subjects were asked to browse the network in a completely associative manner. We have opted for this approach to prevent the uncontrollable effects of individual, idiosyncratic strategies. It would however be interesting to know how the application of forced goal-directed strategies (in which for example our subjects were assigned a random start- and goal-position in the network) would influence the generated network structure. This would involve a different briefing (instruction to browse goal-directed) and a number of minor adjustments to the interface (individual assignment of random start- and goal-position).

Finally, one could argue that the present method might not be suited for personal tailoring of hypertext as the network structure is the same for each user and shaped by the combined browsing of a group of users. Adaptive networks such as these can however be trained by individual users as well and will reflect this individual user's associative profile. One could even imagine a hybrid system in which a large, collective network is trained by the browsing preferences of the majority of its users (an Adaptive WWW), while each user of the network is training a small, personal adaptive network on the client-side by his/her individual browsing of the collective network. The ordering of the links from any node in the larger network might then be generated according to a combination of the values contained in the individually trained networks on the client-side and those of the collective network. Both networks would however self-organise according to the same learning principles as outlined in this paper.

- Bollen, Johan (1996), Cognitive Complexity vs. Connectivity: efficiency analysis of hypertext networks, in Heylighen F. (eds.) (1997), The Evolution of Complexity, Kluwer Academic, Dordrecht [in print].

- Bollen, J. & Heylighen F., 1996, Algorithms for the self-Organization of distributed, multi-user networks. Possible applications to the future WWW., in Trappl, R. (ed.), Proceedings of the 13th European Meeting on Cybernetics and Systems Research, Austrian Society for Cybernetic Studies, Vienna, p.911-917

- Catledge, Lara D & Pitkow, James E. (1995), Characterizing Browsing Strategies in the World Wide Web. Computer Networks and ISDN Systems, 27, p.1065-1073

- Hebb, D.O. (1967) The organization of behavior: a neuropsychological theory, Science Editions, N.Y.

- Hinton, Geoffrey & James Anderson (1981) (eds). Parallel Models of Associative Memory, Hillsdale, N.J.

- Hubert, L. and & Schultz, J. (1976), Qudratic Assignment as a general data analysis strategy, British Journal of Mathematical and Statistical Psychology, v. 29, p. 190-241.

- Johansson S. & Hofland, K., (1989): Frequency analysis of English vocabulary and grammar: based on the LOB corpus, Oxford : Clarendon Press. - 2nd v.

- Jonassen, D.H. (1990), Semantic Network Elicitation: tools for structuring Hypertext. In - R. McAleese and C. Green (eds.) Hypertext: State of the Art. Oxford, Intellect.

- Kaplan C., Fenwick J. & Chen J., (1993), Adaptive hypertext navigation based on user goals and context. User models and user adapted interaction, 3(2).

- Mathe, N. & Chen, J. (1994); A User-Centered Approach to Adaptive Hypertext based on an Information Relevance Model; Proceedings of the 4th Int. Conference on User Modeling, Hyannis, MA, August 15-19. pp. 107-114.

- Mc. Clelland, J. & Rumelhart, D. E. (1986) Parallel Distributed Processing. Volume 1: Foundations, Bradford Books, MIT Press.

-Mc Knigh et al (1991), Hypertext in Context, Cambridge series on Electronic Publishing, Cambidge University Press, Cambridge. p.95-98

- Tomek I., Maurer, H. & Nassar M. (1993), Optimal presentation of links in large hypermedia systems. In Proceedings of ED-MEDIA '93 - World Conference on Educational Multimedia and Hypermedia. AACE, p. 511-518

- Schildt, Herbert (1987) C - The complete reference (AI-based problem solving), Osborne- Mc.Graw Hill, London, p. 645

- Van Dyke Parunak, H. (1991), Ordering the information Graph, in, Berk, E & Devlin J. (eds.) Hypertext and Hypermedia Handbook, p. 299-325.