Abstract
The methodology presented in this paper is based on concept mapping, which is a technique for representing knowledge in graphs. Its applications are broader and cover, in addition to presentation of knowledge, the complex organization of systems such as web sites. The paper presents a method for reaching consensus from several organizations of data/web site independently produced by different people. A class of methods was initiated, considering a number of parameters that can be chosen in order to match closely any specific real-life application. Although the methodology can be fully automated in terms of a suitable computer program, it is meant to be mainly a useful tool for experts in web site organization.
1. Introduction
This paper reports on a methodology that could be used to plan complex web sites. Such sites can typically be presented as directed graphs: directed links are established between related atomic contents. Since different users will typically propose different organizations of the content, the designer is faced with the problem of choosing the optimal organization.
The proposed method involves obtaining individual user graphs and comparing the frequencies of particular links. The average or consensus graph is produced after setting an appropriate frequency threshold and includes all links with frequencies above this threshold. A properly established threshold will result in a consensus graph, representing the optimal web site organization.
2. Background
We first used a similar methodology as part of our study on intuitiveness of the Functional Requirements for Bibliographic Records (FRBR) conceptual model [1, 2]. There, participants were asked to produce a concept map of a particular part of the bibliographic universe by drawing connections between various descriptions of FRBR entities [3]. While individuals had very different mental models, the consensus graph, obtained by using the sum of all of the frequencies of established links between descriptions, showed FRBR-like features. As we were interested in FRBR, we chose as the threshold the highest frequency at which all of the basic FRBR relationships were established. While a few non-FRBR connections were also present, they were less frequent then most of the FRBR connections.
After receiving such encouraging results we wished to test the methodology in a different environment. Immediately it seemed appropriate for web site development, because it establishes some sort of hierarchy in an organic manner. If we compare this method to card sorting and affinity diagramming, two methods that serve similar purposes and are recommended for web site development [4], our methodology should be at least as valid. Affinity diagramming is a technique for organizing concepts, by a group, akin to brainstorming, using sticky notes. Card sorting is a technique for eliciting mental models of individuals (or groups). Participants are asked to group cards into categories. It must be stressed that all of these techniques are not meant to be used as the sole basis for web site development.
Our method is based on concept mapping, which is a technique for representing knowledge as graphs. Knowledge graphs are networks of concepts, which consist of nodes and links [5]. Concept mapping is not only used in many different fields; the name itself can refer to different methods with different results [6]. Jackson and Trochim [6] describe concept mapping methods as being aimed at representing mental models of individuals. Despite extensive search, we have not identified any studies using concept mapping by participants in library or information science. According to Lanzing [5], concept mapping can be used to design a complex structure.
Our method differed from usual concept mapping on two very important issues: it was constrained to a large degree and it did not explicitly include concepts themselves, but rather instances of these concepts. Usually concept mapping requires participants to come up with concepts. We felt that in our case asking participants to directly come up with contents would not be productive. Therefore, we asked them to make a map of instances of contents that we had prepared for them. In this sense, our variation of the method is similar to ACSMM (Analysis-Constructed Shared Mental Models), where concepts are also provided to participants in advance [7]. Similarly to the ACSMM, we also wanted to obtain an overall representation of individual mental models.
The result of each individual concept mapping is a partially ordered set in which, generally speaking, pieces of paper at the top represent the more general (abstract) concepts, while pieces at the bottom represent more specific (concrete) concepts. The resulting arrangement of cards for each participant can be represented by a directed acyclic graph, representing a partial ordering of a given set of concepts. The elements of the set are the concepts described on pieces of paper. After obtaining a collection of partially ordered sets, one for each participant, we then use mathematical operations in order to produce a consensus map.
3. Mathematical and computational model
Here we specify a mathematical model that is detached from the current study and can be used in a number of similar approaches. For instance, such a model has been used in the study of the FRBR [1, 2]. The proposed model is quite general and can be fine-tuned to a specific real problem by adjusting several parameters. Finally, the results of the computations based on the input data may be applied directly or may be used as basis for an informed decision ultimately made by the experts.
The main structure used in the model is the one of a weighted directed graph D = (V, A, w) consisting of a finite set V of vertices and a number of directed edges (arcs) A where each arc a from A carries positive weight w(a). If there is at most one arc a = (u, v) leading from vertex u to vertex v, we may describe D by a matrix M(D). The matrix is called the adjacency matrix of D. If there is an arc aij = (vi, vj ) in D with the weight wij , then the i–j entry in matrix M(D) is equal to wij . If there is no arc from vi to vj then the corresponding matrix entry is equal to 0. If all weights in D are equal to 1, we may omit them and we say that D is an unweighted digraph (directed graph). Note that M(D) depends on the order imposed on the vertex set V = {v 1, v 2, …, vn }.
A digraph that can be described by a zero-one matrix is called simple. Note that if there is an arc a = (u, v) in a simple digraph, then there could be another arc b = (v, u) leading in the opposite direction. A weighted digraph D can be turned into an unweighted one, D′, by replacing all weights by 1. In such a case D′ is called the underlying unweighted digraph of D. It can also be turned into a simple digraph D″ by replacing all parallel arcs between any two vertices (u, v) by a single arc between the same ordered pair of vertices (u, v) and giving the new arc the sum of weights of original arcs. D″ is called the underlying (weighted) simple digraph. By applying the two steps simultaneously, we may turn any digraph D to an unweighted simple digraph D″′, called the underlying unweighted simple digraph. The theory of digraphs is rich and extensive. It would take us too far to present even the part that is used in our computations. We will therefore present a model of weighted digraphs using web sites.
A web site consists of a number of web pages. Each web page is a vertex of the digraph. The arcs correspond to local hyperlinks leading from one web page to another web page of the same site. The corresponding digraph D is therefore unweighted (each link gets weight 1), but may be non-simple if there are at least two links on one page leading to the same page of the same site. The underlying simple digraph D″ may be weighted and each weight corresponds to the number of links between the two pages (leading in the same direction). The digraph (D″)′ is the underlying simple unweighted digraph. (Observe that (D′)″ may not be the same as (D″)′.) Note that the browser ‘back’ button will take us from any page to the previously viewed page. This link is not part of the digraph, but we will use it in describing an important class of digraphs.
A digraph D is strongly connected if we may start at any page u and reach any other page v using links of the site (without using the ‘back’ button in the browser).
A digraph is weakly connected if the underlying undirected graph is connected. To reach any page in a weakly connected internet graph one needs something like Google’s ‘backward links’ functionality or Wikipedia’s ‘what links here?’
A digraph is acyclic if there is no page v such that by clicking on links we may reach the same page again. Directed acyclic graphs correspond to partial orders (partially ordered sets or posets). This means that the pages may be ordered in such a way that all links point forwards. In such a case the corresponding matrix M(D) has non-zero entries only in the upper triangle.
A digraph D is rooted with root r, if the page r is a unique page with the property that any other page v can be reached from r by following the links of the site. It is easy to see that in a rooted digraph there is no arc from any vertex v to the root r. The root may be viewed as a ‘home-page’, that is, the unique starting page of the site, from which the whole site can be explored.
A digraph is arborescence, if it is weakly connected and there is at most one directed path from any page u to any other page v. If we forget about the directions of arcs, we obtain undirected edges and the underlying (undirected) graph. A digraph is weakly connected if and only if the underlying graph is connected.
A rooted arborescence is called a rooted tree. A rooted tree is a digraph with a tree as underlying graph and all arcs are directed away from the root. For each vertex v of a rooted tree there is a unique directed path from r to v.
In a web site design we are given a set of pages and we have to choose the ‘best’, the ‘most natural’ hyperlinks between them in order to facilitate the user exploring the site in the most productive way. Sometimes this means that we want to minimize the number of clicks before we can find the page that we are interested in. In practice a user may be interested in the ‘story’, that is, a collection of pages giving comprehensive information about his interests.
There are web sites that require special structure, such as a poset or rooted tree. In practice this may require two types of hyperlinks: the backbone links maintaining a structure of a poset or rooted tree; and the sporadic links that may be used for explanatory purposes and could violate the required web site structure.
Let D = (V, A, w) be a weighted digraph and let t be a positive number, called threshold value. By D(t) we denote the digraph on the vertex set V in which only arcs a such that w(a) > t are kept, and other arcs are removed from the digraph D. We call D(t) the threshold graph. Now we are in position to represent the problem in our model, as stated in Table 1.
Representation of the problem.
The idea behind this problem may be that individuals propose the structure of the site according to their perception of web pages and their dependencies. These structures are given as input data, each as a 0–1 matrix. The result could be a web site that best represents the majority of mental models. As mentioned earlier, we may require some properties from the resulting digraph. In certain cases we may have to add or remove some arcs in order to ensure that the resulting digraph meets such properties. We also have to have some measure that tells us how well the resulting digraph represents the input data. In a rare case when the input data are composed of identical networks, the output network will be the same and we have a perfect match with no dispersion. We would expect the solution to be stable. This means that small changes in input data do not change the output digraph.
Our proposed solution uses the well-known greedy method approach of the Kruskal-type algorithm [8, 9] for a minimum-cost spanning tree. In our case the maximum spanning tree is sought. We expect to have two predicates available, Feasible(T) and Ok(T). In the original Kruskal algorithm the edges are undirected: Feasible(T) means that T has no cycle; Ok(T) is true if T is a connected graph. Our algorithm can be described as in Table 2.
Algorithms.
The above description uses two functions: Ok(T) and Feasible(T) that have to be specified separately. In this sense it describes a whole class of algorithms. While there are several different possibilities for both Feasible(T) and Ok(T), in Table 3 we present only some of the options.
Functions Feasible(T) and OK(T).
In principle any choice from (a)–(d) can be combined with any choice from (A)–(C). In practice some combinations can be more meaningful than others. In the next section we present results based on two simple strategies S1 and S2, presented in Table 4.
Strategies S1 and S2.
As presented, using our terminology above, the final arboresence may not be rooted, which means that not all pages would be reachable from the homepage (both strategies S1 and S2 have this problem). This can be fixed by using (B) as the stopping condition, (b) as the feasibility condition and adjusting threshold, but than one may obtain something that is not a tree. As an alternative, one could try using Chu–Liu/Edmonds’s algorithm [10, 11], which is an analogue of Kruskal’s algorithm for directed graphs (it always produces optimal directed rooted tree; however, the root node must be selected in advance – but one can always try all nodes for root or just choose the node with largest outdegree). For the currently most efficient implementation of this algorithm, see Gabow et al. [12]. However, in our approach the presence of an un-rooted arborescence may be regarded as a warning sign to the designer that the proposed model of pages should be redesigned in order to make it better acceptable.
4. Study
The study was performed in December 2010 by library and information science students as a part of course requirements at the University of Ljubljana. Five groups of three students were asked to perform a user study on 10 individuals, resulting in 50 elicited mental models.
The process leading to the study was done in a systematic manner. First, a topic of the imaginary web site was chosen, based on various proposals from the students. After some discussion, a virtual tourist agency was chosen, as it was viewed as an example that would be of most interest to the general public. Then, a detailed list of contents (nodes in a graph) was produced, simulating a user brainstorming session. As we were only interested in categorization, we did not produce an exhaustive list of contents for concrete services of the agency (i.e. while we tried to cover most services that a tourist agency might offer, we did not name all of the specific destinations, etc., but rather just some examples). We were well aware of the trade-off between reading load and potential misunderstandings and decided that the contents should be described using single words and phrases. In rare cases, some clarification was given.
Next, a pilot study was conducted, where each group asked one individual to make a concept map (generally using the same methodology as in the real study, described later). The ultimate study protocol was then decided and the contents were changed, both adding descriptions and altering existing ones.
The study aimed to find out how to arrange contents in a way that would enable the users of a web site to orientate themselves and to find the information they seek as quickly as possible. Participants were presented with 47 pieces of paper, each containing a description of a particular piece of content. They were asked to arrange the pieces of paper into a hierarchy according to their line of thinking, that is, to arrange them in the way that made the most sense to them. The participants were encouraged to make duplicates, essentially placing the same piece of information in different places in the hierarchy if needed. On the other hand, they were prohibited from making up new nodes. Participants were asked to think aloud and any comments were welcome.
In the analysis the top node (the homepage) was added to the 47 descriptions. The nodes were labelled 1–48, as seen in Table 5, containing translations of the Slovenian descriptions used in the study.
List of the contents of an imaginary tourist agency web site.
We took the basic matrix D(V, A, w) and used different strategies and different applications (Python, Microsoft Excel, Wolfram Mathematica, Pajek) to calculate the results and to produce the figures. In Figure 1 the basic matrix D(V, A, w) is shown as a graph (the thicker the line, the more frequent the connections).
All of the links made by participants.
While some sort of main structure is visible in Figure 1, it is often necessary to take into consideration only those links that appear more than a certain number of times for greater clarity, as the lowest frequency connections clearly cannot be seen as relevant for the majority. While in our previous study, as already mentioned, we tested a particular model and were therefore interested in the highest frequency where all of the connections in this model were present, here we had no structure as a guide. Therefore, we had to find other criteria to determine appropriate thresholds.
While Christensen and Olson [13] suggest that the most appropriate threshold is usually between a third and a quarter of the number of participants, it would appear that the best representation of the results in our case is the threshold range between 10 and 13 established links, that is around one-fifth of the number of participants. The lower threshold is interesting because it is the highest threshold where all the nodes are connected (Strategy S1), as we would want the web site to have some sort of a structure. On the other hand, the lowest threshold where each node has only one predecessor (or none) is at 13 connections. While the consensus of one-fifth of the participants may not seem like much of a consensus, it takes into account choices for all of the nodes involved in the example. If we chose a higher threshold, we would certainly see the strongest connections, but would not be able to tell much about the example. Conversely, if we chose a lower threshold, randomly established connections could threaten the understanding and applicability of the result. The results using strategy S1 are presented in Figure 2, the threshold being 10. However, as discussed earlier, there is an alternative to simply setting thresholds. To obtain results in Figure 3, a Kruskal type greedy algorithm was applied (Strategy S2). The data in Figure 3 can be presented in a hierarchical display, such as in Table 6 (the number in front of the description is the card number and the number in parentheses is the frequency of established links between the direct hierarchical predecessor and the card described).
Graph at threshold value 10.
Rooted tree obtained by using a Kruskal-type algorithm.
Hierarchical display.
5. Results
As we have seen, the rooted tree in Figure 3 is a good example of organization obtained by our study. In it, the top node is connected to data about the agency, transport, accommodation, general tourist information, online guides, FAQ, promotions, trips and tours, and holiday packages.
Overall, the most common connection was from homepage (no. 1) to tours and trips (no. 18), which was established 46 times. Also very common were connections from holiday packages (no. 33) to holiday packages – sea (no. 38) and holiday packages – mountains (no. 39), which were present in 45 and 44 cases, respectively.
Unsurprisingly, there were strong connections from transport and accommodation to lower levels (e.g. car rental, hotel accommodation). Participants had the most divergent results concerning various types of trips and tours. It was interesting to note that individual participants chose different criteria based on the nature of the individual trip or tour, that is, they did not consistently use just one criterion.
One interesting observation is that participants did not consider viewing trips around Slovenia (35) as falling under tours around Europe (no. 36), although Slovenia is indeed part of Europe. While the reason may be that Slovenian users want to reach data about Slovenia directly, this may also be caused by the distinction between tours and trips. Interestingly, participants did not place active tours and trips (no. 21) under the category of tours and trips according to content (no. 20).
Perhaps the biggest surprise was the direct association of any visit to a wine road (no. 22) with the list of trips around Slovenia. It may be that the participants were influenced by the only example given of a wine road being in Slovenia (no. 28), or perhaps they identified wine roads as a typically Slovenian phenomenon. While this connection was made by 13 participants, which is a relatively small number, it was still more common than any other direct link to visits to wine roads.
It has to be noted that the study took place in December 2010, which explains why New Year’s celebrations (no. 46) were explicitly tied to promotions (no. 15) in 13 cases. Further, if we consider all of the links at the threshold level of 10 (Figure 2), the trip to Vienna (no. 27) was seen as falling directly under promotions (no. 15), trips and tours according to location (no. 19) or tours around Europe (no. 36), with the latter variant being the most commonly chosen. While, again, either a different view of Vienna compared with the rest of Europe or a distinction between trips and tours may have played a role, this only highlights the fact that different people chose different criteria as the most important.
The cruise around the Greek islands (no. 43) was seen by some as belonging in the packages branch (no. 36), while others considered it to be a tour (no. 38), the only example in the study that was distinct in this way.
There were two paths to general tourist information (no. 11) either directly from the home page, or through data about the agency (no. 2). This may be a result of differing mental models about the what contents called ‘data about the agency’ actually include, even though the description did contain some additional information for clarification.
Participants most frequently commented on the number of nodes, generally agreeing that the volume made the task difficult. On the other hand, the relative scarcity of nodes on the lower levels of hierarchy left participants baffled in some cases. A small minority of participants also had trouble associating tourist destinations with particular continents.
The comments made by participants during the study were helpful for better understanding not only of their mental models, which were sometimes difficult to completely grasp solely from the layout of the pieces of paper, but also of the potential shortcomings of the methodology involved. It was not always clear to the participants what their task was. Also, participants’ reluctance to establish duplicates suggests that researchers would need to play a more proactive role in any future research. The ambivalence of the results regarding tours and trips would suggest that a more detailed study into these phenomena would be in order.
6. Conclusions
The methodology was found to be satisfactory, although it has its drawbacks. However, the biggest complaint of the participants – the relatively large number of nodes – is something that cannot be avoided in similar procedures, even when working with a prototype. It also has to be stressed that this methodology is not to be used on its own, but rather in combination with other methods. This should also help alleviate the problem of not always getting a clear hierarchy using this method.
While in this study the participants had no influence on the concepts chosen, this method would work equally well with a user-specified set of concepts, as long as it was pre-set. This would imply a two-stage process.
The general structure of the site obtained from individual maps is, for the most part, clear and logical. Thus, the method fulfilled the two most important requirements of user-based design.
In comparison with group activities, such as affinity diagramming, this method offers a way for less vocal individuals to have an equal say. On the other hand, unlike card sorting, there are more chances for individuals to express the perceived nature of relationships between individual pieces of information. Also, the method is relatively inexpensive and does not require extensive knowledge of mathematics or statistics, even though it is deeply rooted in the two fields. It allows for several extensions and modifications. For instance, the weights of the ‘surplus’ edges, that is, the edges obtained by Strategy S1 and not by Strategy S2, may be used as a measure of quality of the web site organization. A useful modification would involve data gathering directly from the web server logs.
As this methodology has now been used relatively successfully in two studies in two completely different environments in information science, it should receive more attention as a relatively cheap and easy way of eliciting mental models of complex information space. While it may not be robust enough to stand on its own, this technique is an appropriate complement to more widely used approaches. Although the methodology presented in this paper can be fully automated as a suitable computer program, it is meant to be mainly a useful interactive tool to the experts in web site design.
Footnotes
Acknowledgements
This research was supported in part by the ARRS within the EUROCORES Program EUROGIGA (project GReGAS-N1-0011) of the European Science Foundation, ARRS projects P1-0294, P5-0361 and J5-4155. The authors would like to thank an anonymous referee for many useful remarks and for pointing out important references.