Marin Bertier

Rachid Davide Frey

Rachid Guerraoui

Anne-Marie Kermarrec

Vincent Leroy

The Gossple Anonymous Social Network

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Context: The Web 2.0 has radically changed the way people interact with the Internet: this has turned from a read-only infrastructure to a collaborative readwrite platform with active players. Content is no longer generated only by experts but pretty much by everyone. Web 2.0 applications, such as LastFM, Flickr, CiteULike and Delicious [1], contain a goldmine of information. Yet, matching a specific query in such a mine might rapidly turn out to be like looking for a needle in a haystack, for the content of the Web is not indexed with a controlled vocabulary, e.g, ontology. Instead, freely chosen keywords are typically used to tag billions of items, i.e., with a folksonomy (folk + taxonomy). In short, the freedom left to the users to express their interests underlies the success of the Web 2.0 but it is also an impediment to navigation.

This paper proposes to improve navigation in such systems through implicit personalization: we associate every user with a network of anonymous acquaintances that are interested in similar items, independently of how they expressed their interests, e.g., which keywords they used to tag those items. These acquaintances are then implicitly used to guide and refine users' search operations.

Insight: To illustrate the benefit of implicit personalization, consider the following real example. After living for several years in the UK, John is back to Lyon in France. To maintain his kids' skills in English, he is looking for an English speaking baby-sitter who would be willing to trade baby-sitting hours against accommodation. There is no doubt that such an offer would be of interest to many of the young foreigners living in a big city such as Lyon. Yet, John's Google request "English baby-sitter Lyon" does not provide anything interesting for the term baby-sitter is mainly associated with daycare or local (French) babysitting companies. None of John's Facebook buddies in Lyon or the UK can help either as none has ever looked for an English speaking baby-sitter in Lyon. Yet, Alice living in Bordeaux after several years in the US, and who was looking for a similar deal with her kids, has been lucky enough to discover that teaching assistants in primary schools are a very good match. Clearly, John could leverage Alice's discovery if only he knew about it. Should a system be able to capture the affinity between Alice and John, through their common interest in international schools and British novels for example (Figure 1), John could use Alice's information.

Indeed, consider a collaborative tagging system through which Alice has annotated the teaching assistant URL with baby-sitter (Figure 1). Assume both Alice and John have expressed their interest in international schools and British novels by tagging related URLs. A personalized search could leverage these affinities to return Alice's teaching assistant URL first instead of the millions of URLs of standard (non English speaking) baby-sitter related URLs. Likewise, a personalized query expansion could expand John's query appropriately with tags derived from Alice's activities on the Web and make it easy to solve by any reasonable search engine. The crucial aspect here is the unusual (personal) association between baby-sitter and teaching assistant, which is relevant to a niche community (the one gathering Alice and John) while baby-sitter is dominantly associated with (non English speaking) daycare. Discovering such specific affinity is very rewarding for the users, yet challenging to automatically capture.

Challenges: First, capturing associations between tagging profiles is difficult with millions of users, each with a dynamic variety of interests. Meaningful associations that help retrieve appropriate matching results, without drowning these within tons of useless information, should be derived from a large amount of information about proximity between user profiles. Such information grows not only with the number of users, but also with the number of interests per user. To illustrate this, consider our previous example. John, besides being interested in a baby-sitter, does also search for music over the Internet. Despite their proximity as far as kids and English are concerned, Alice and John have opposite tastes music-wise. The fact that Alice and John are identified as acquaintances should not prevent John from benefiting from relevant music information using other acquaintances.

Second, discovering social acquaintances might be hampered by the resistance of users to publicize their tagging behavior. In fact, the apparent eagerness of companies to benefit from user-generated content might already dissuade users from generating new content and making their interests explicit 4 . A decentralized solution is appealing to address both the scalability and big-brother issues but poses nontrivial maintenance and efficiency issues, besides the fact that users might still be reluctant to reveal their interests to other unknown users.

Contributions: This paper presents Gossple, a system that takes up these challenges, in a pragmatic way, to automatically infer personalized connections in Internet-scale systems. Gossple nodes (users) continuously gossip digests of the tagging profiles (of their corresponding users) and locally compute a personalized view of the network, which is then leveraged to improve their Web navigation. The view covers multiple interests without any explicit support (such as explicit social links or ontology) and without violating anonymity: the association between users and profiles is hidden. In the context of the Alice-John example above, Gossple leverages the very fact that John's request can benefit from Alice's tagging profile, without knowing who the profile belongs to. Basically, every Gossple node has a proxy, chosen randomly, gossiping its profile digest on its behalf; the node transmits its profile to its proxy in an encrypted manner through an intermediary, which cannot decrypt the profile.

To reduce bandwidth consumption, the gossip exchange procedure is thrifty: nodes do not exchange profiles but only Bloom filters of those until similarity computation reveals that the two nodes might indeed benefit from the exchange. To limit the number of profiles maintained by each node, while encompassing the various interests of the user associated with the node, we introduce a new similarity metric, we call the set cosine similarity, as a generalization of the classical cosine similarity metric [START_REF] Yildirim | A random walk method for alleviating the sparsity problem in collaborative filtering[END_REF][START_REF] Cattuto | Semantic analysis of tag similarity measures in collaborative tagging systems[END_REF], as well as an effective heuristic to compute this new metric.

While Gossple can serve recommendation and search systems as well, we illustrate the effectiveness of Gossple through a query expansion application for collaborative tagging systems. We believe this application to be interesting in its own right. We compute scores between tags using Gossple and apply ideas from ranking Web pages (PageRank) to leverage the relative centrality of the tags through an algorithm we call GRank. 5Evaluation: We evaluated Gossple with a wide-range of Web 2.0 application traces, including Delicious, CiteULike, LastFM and eDonkey, up to 100, 000 users through simulation and in a real distributed system of 223 PlanetLab nodes.

We first show that our multi-interest similarity metric improves on stateof-the-art ones by up to 70% in the considered datasets. Our gossip exchange procedure effectively builds a Gossple network from scratch in less than 20 cycles, and maintains a baseline bandwidth of 15kbps. This is achieved with good anonymity guarantees through the use of onion-routing-like techniques.

We also evaluate our query expansion application independently and show how we retrieve items that state-of-the-art search systems do not (recall, also called completeness) whilst improving precision (accuracy) at the same time. We show, among other things, how Gossple addresses the Alice-John baby-sitter situation above. For instance, a query expansion of size 20 retrieves 40% of unsuccessful original queries while improving the precision by 58% with respect to the originally successful queries (against resp. 36% and 24% for competitors [START_REF] Zanardi | Social ranking: uncovering relevant content using tag-based recommender systems[END_REF]) on a Delicious trace. This is achieved in a thrifty manner: 10 acquaintances are enough to achieve effective query expansion in a 50, 000-user system, while exchanging gossip messages and profile digests of approximately 12.9KBytes and 603Bytes respectively.

In summary: The contributions of this paper are threefold: (i) an anonymous, thrifty gossip protocol; (ii) a set cosine similarity metric to compute semantic distances; and (iii) a query expansion application.

Roadmap: Section 2 details the Gossple protocol. Section 3 reports on its evaluation. Section 4 describes the application of Gossple to query expansion. Section 5 surveys the related work. Section 6 highlights some of the limitations of Gossple.

The Gossple Protocol

Gossple is a fully decentralized protocol aimed at building and maintaining dynamic communities of anonymous acquaintances. Such communities differ from networks of explicitly declared friends (e.g. Facebook) which are often not the most suited to enhance the search procedure as reported in [START_REF] Bender | Peer-to-peer information search: Semantic, social, or spiritual?[END_REF].

Overview

More specifically, Gossple provides each user with GNet, a network of semantically close anonymous interest profiles. Building and maintaining a node's GNet goes first through determining a metric to identify which profiles exhibit similar interests. This is particularly challenging for the goal is to capture the whole range of a node's interests while limiting the number of profiles in the GNet. Another challenge is to devise an effective communication procedure for profile exchange while limiting the amount of generated network traffic and hiding the association between nodes and profiles to preserve anonymity.

We detail in the following how Gossple addresses these challenges. We assume, for presentation simplicity, a one-to-one mapping between a user and a machine: we refer to a node henceforth. From an abstract perspective, we model the profile of a node as a set of items I = {i 1 , . . . , i n }. Each item can be described by a potentially large amount of meta-information, such as tags describing it in the case of a folksonomy. Depending on the target application, this set may represent downloaded files, a summary of published content, etc. In the following, we first present a novel multi-interest (set item cosine similarity) metric; then, we describe our thrifty gossip-based protocol to establish and maintain connections between nodes (i.e., compute GNet) using this metric. For presentation simplicity, we present our protocol in a modular manner: we present first how a node communicates with other nodes to review a large set of profiles, how it encodes a profile, and finally how it preserves its anonymity.

Selecting acquaintances

Selecting relevant acquaintances requires nodes to rate each-other's profile.

Rating individuals. One way to build a node's GNet is to individually rate other nodes and select the ones that score the highest. Cosine similarity [START_REF] Mcgill | Introduction to modern information retrieval[END_REF] is widely used in the area of data mining. The score between two nodes increases when interests are similar, specific overlapping of interests being favored over large profiles. Our preliminary experiments have shown indeed that cosine similarity outperforms simple measures such as the number of items in common. Thus we implemented cosine similarity as a reference in our experiments. More specifically, let I ni be the set of items in the profile of node n, the item cosine similarity between two nodes is defined as follows: Fig. 2. Multi-interest rating vs. Individual rating Individual rating, and thus cosine similarity, selects nodes having the most similar profiles. Yet, this may lead to consider only the dominant interest, ignoring minor, potentially important, ones. In a large-scale system where a node can only keep track of a limited number of profiles, individual rating cannot capture emerging interests until they represent an important proportion of the profile, which they might never. Consider Bob whose tagging actions reveal that 75% of his interests are in football while 25% are in cooking. Selecting the profiles of the closest nodes might lead to only selecting those interested in football: the cooking topic will not be represented enough to provide interesting information. In Figure 2, the individual rating selects a view of 8 nodes interested only in football (users n 1 , n 2 , ... n 8 ).

ItemCos(n 1 , n 2 ) = |In 1 ∩In 2 | √ |In 1 |×|In 2 | . Individual
On the contrary, the GNet should preserve the distribution of 75% of football and 25% of cooking. We achieve this by rating a set of profiles as a whole rather than each profile independently. This is crucial to achieve scalability and limit the size of the GNet wrt the overall size of the network. In the example, multiinterest scoring would lead to selecting 2 nodes interested in cooking: n 9 and n 10 and 6 in football, covering Bob's interest in cooking as well.

Rating sets. Rating a set of profiles as a whole involves a balance between the extent to which nodes in the set share interests with a given node n, and how well the distribution of the interests in the set matches the one in n's profile. This is precisely what the Gossple item set cosine similarity metric achieves.

Let IVect n be the vector that represents the items in the profile of n. If item i is in the profile of node n IVect n [i ] = 1, otherwise 0. Following the same principle, SetIVect n (s) builds an item vector that represents the distribution of items in a set of nodes s with respect to the node n. Each value of this vector is computed as follows:

SetIVect n (s)[i ] = IVect n [i ] × u∈s IVectu [i]
IVectu . The rationale behind this metric is to represent the distribution of interests in GNet while normalizing the contribution of each node to favor specific interests. The items that are not present in the profile of node n are discarded since their distribution should not impact the score of GNet. Following the cosine similarity between nodes, a node n computes a score for a set of nodes as follows:

SetScore n (s) = (IVect n • SetIVect n (s)) × cos(IVect n , SetIVect n (s)) b
The first part of the formula sums all the values in the vector representing the distribution of items in s, while the second represents how well the distribution of the items in s matches the one in n's profile, i.e. how fair the contribution to all the interests of n is. b is the balance between the amount of shared interests and a fair distribution that does not favor any item. The set that scores the highest forms the node's GNet. It is important to notice that for b = 0 (no cosine impact), the distribution is not considered and the resulting GNet is exactly the same as the one obtained from the individual rating. Gossple's multi-interest metric is key to selecting the best set of profiles to fill a given node's GNet. This would however be of little use without an effective mechanism to review a large set of candidate profiles while ensuring rapid convergence to the ideal GNet. Gossple achieves this through a gossip protocol to establish and maintain connections between nodes. The Gossple protocol relies on two subprotocols (Figure 3): a Random Peer Sampling protocol (RPS) [START_REF] Jelasity | Gossipbased peer sampling[END_REF] and a multi-interest clustering protocol (GNet protocol). Each node maintains two corresponding data structures, a random view and the GNet.

Discovering acquaintances

RPS. In the RPS, each node maintains a view of a random subset of network nodes. Periodically, it selects a node from this view and they exchange parts of their views. This provides each node with a random, changing, subset the network used for the bootstrap and the maintenance of the GNet protocol. Each entry in the random view contains (i) the IP address and the Gossple ID of the node; (ii) a digest of its profile in the form of a Bloom filter (discussed in Section 2.4) and, (iii) the number of items in the profile (used for normalization). Gossple relies on Brahms [START_REF] Bortnikov | Brahms: byzantine resilient random membership sampling[END_REF], a byzantine resilient RPS, which provides the building blocks to build Gossple's anonymity (presented in Section 2.5).

Algorithm 1: GNet protocol

GNet protocol. GNet contains c entries composed of the same fields as the random view entries with the addition of a timestamp representing the last time the entry was updated in the view. c is a parameter of the system that selects the trade-off between the amount of available information and its personalization degree. In addition, each entry also contains the full profile of nodes that have been chosen as acquaintances. We denote by GNet n the GNet of a node n.

The GNet protocol (Algorithm 1) is also gossip-based and maintains a list of implicit acquaintances (nodes). Each node n periodically selects the oldest (according to the timestamp) node g in its GNet, or a node picked from the RPS view if GNet n is empty. Then n sends the descriptors of c nodes in GNet n to g and g does the same. Upon receiving the other node's GNet, n and g update their own GNet structure. It first computes the union of GNet n , GNet g and its own RPS view, then it selects the c nodes that maximize the Gossple metric described in Section 2.2. Selecting the best view consists of computing the score of all possible combinations of c nodes out of 3c nodes. Because the corresponding running time is exponential in c, our protocol uses a heuristic (Algorithm 2) as an approximation. It incrementally builds a view of size c from an empty view by adding at each step the node that provides the best view score. This heuristic has complexity O(c 2 ) and turns out to be very appropriate in our evaluations. In order to keep the bandwidth consumption of Gossple within reasonable bounds, nodes do not send their full profiles during gossip. Instead, they exchange a Bloom filter [START_REF] Bloom | Space/time trade-offs in hash coding with allowable errors[END_REF]: a compact representation of the set of items in the profile. The Bloom filter provides a reasonably good approximation of a node's profile that can be used to compute Gossple's metric with a negligible error margin (as we discuss in Section 3.3).

Gossiping digests

The Bloom filter, as depicted in Figure 4, is an array of bits representing a set. When an item is added to the set, h hash functions are used on the item to obtain h positions in the array: these are set to 1. In order to query for the presence of an item in the set, one uses the same hash functions and checks if all the bits at the h indexes are set to 1. In the case of several additions to the Bloom filter, the request can return true even if the item was never added to the set. The rate of false positives depends on the size of the set, h, and the number of items in the system. However, a Bloom filter never returns a false negative.

In Gossple, the Bloom filter is used as a first approximation of a node's profile. If a node remains in the GNet for K gossip rounds, it is considered as a good candidate and the entire profile is requested (K = 5 in our experiments). Once the full profile of the node has been retrieved, it is used to compute an exact similarity score. This prevents the expensive transfers of useless entire profiles of nodes that will reveal distant according to the Gossple metric. For example, the profile of a Delicious user is on average 12.9KBytes large, while the corresponding Bloom filter is only 603Bytes. This leads to a 20-fold improvement in bandwidth usage.

Since a Bloom filter can return false positive results, some nodes considered as acquaintances through their Bloom filters can be discarded when the exact score is computed with the profile. However, a node that should be in the GNet will never be discarded due to a Bloom filter approximation. Hence, an entry for a node in the GNet contains either the full profile of the node or a Bloom filter of the profile with a counter incremented at each cycle. When the counter reaches the value of K, it triggers the retrieval of the corresponding full profile. The pseudo-code of the GNet protocol is presented in Algorithm 1.

Preserving anonymity

The decentralized nature of Gossple somehow inherently preserves some level of anonymity, as compared to a central entity which would control and store all personal data. We go a step further by observing that, while personalized applications may benefit from the profile information contained in GNets, they need not know which nodes are associated with which profiles. In the Alice-John example, what matters is that John can leverage the information provided by Alice: he does not need to know Alice. This observation underlies our gossipon-behalf approach: each node n is associated with a proxy p that gossips on its behalf. Since P2P networks are subject to churn, p periodically sends snapshots of GNet n to n so that n can resume the gossip protocol on a new proxy without losing any information. This anonymity by proxy setup is achieved by an encrypted two-hop communication path à la onion routing [START_REF] Syverson | Anonymous connections and onion routing[END_REF]. Therefore p receives n's profile and its updates but does not know n's identity while the nodes relaying the communication cannot decrypt the profile. Gossple relies on the Byzantine resilience properties of the RPS protocol to prevent colluders from manipulating the selection of the proxy and the relays. Furthermore, we assume that the system is protected against Sybil attacks through a certificate mechanism or a detection algorithm [START_REF] Yu | Sybilguard: defending against sybil attacks via social networks[END_REF]. Finally, we also consider that it is a user's responsibility to avoid adding very sensitive information to her profile. In that case, the profile alone would be sufficient to find the identity of the user as it was the case in the famous anonymized AOL query-log dataset. Gossple ensures anonymity deterministically against single adversary nodes and with high probability against small colluding groups.

Gossple Evaluation

We report on the effectiveness and cost of Gossple by means of both simulation (100, 000 nodes) and PlanetLab deployment (446 nodes). The former provides insights about Gossple's behavior with a very large number of participants while the latter about the inherent overhead of Gossple in a real distributed setting.

Setting and methodology

We evaluated the quality of Gossple's GNet, its convergence speed, as well as its bandwidth consumption and behavior under churn. We considered various Web 2.0 datasets: (i) a trace crawled from Delicious (social URL bookmarking) in January 2009; (ii) a trace from CiteULike (reference management system) available on October 9, 2008; (iii) a LastFM (music recommender system) trace crawled in Spring 2008 and composed of the 50 most listened-to artists for each user; and (iv) an eDonkey (P2P file-sharing) trace [START_REF] Handurukande | Peer Sharing Behaviour in the eDonkey Network, and Implications for the Design of Server-less File Sharing Systems[END_REF]. Table 5 provides the figures for each trace. We configured Gossple's GNets size to 10 and the gossip cycle length to 10 seconds. We deliberately select a small GNet size in order to stress the system and highlight the impact of the selection of each acquaintance.

In this section, we evaluate the quality of a node's GNet through its ability to provide the node with interesting items. This measures the basic usefulness of Gossple's GNets in search applications and recommender systems. We remove a subset (10%) of the items in the profile of each node, which we call the hidden interests of the node. Gossple uses the remaining part of the profile to build the GNets. We express the quality of a GNet in terms of recall, i.e. the proportion of hidden interests of a node n that are present in the profile of at least one node in n's GNet. The better the GNet, the more hidden interests it contains. Each hidden interest is present in at least one profile within the full network: the maximum recall is always 1. Recall is enough to evaluate quality here because n contacts a fixed number of nodes. We further evaluate precision in Section 4.

We evaluate the overall quality by computing the recall for the whole system: we divide the sum of the number of hidden interests retrieved by Gossple for each node and divide it by the sum of the number of hidden interests of each node.

Metric (the quality of GNets)

Our item set cosine similarity (multi-interest) metric enables Gossple to cover the diversity of user interests in a large scale system by assessing the quality of the whole GNet at once, instead of rating profiles individually. Parameter b in the definition of SetScore (cf. Section 2.2) represents the weight of minor interests wrt major ones. We evaluate the impact of b using the hidden-interest test described above. Intuitively, too small a value of b will achieve poor results because the GNet will fail to provide items related to minor interests. On the other hand, too high a value of b might select profiles with too little in common with the node to provide relevant items. Figure 6 presents the normalized recall achieved by GNets on the datasets with increasing values of b. The score is normalized to take as a reference the case when b = 0, equivalent to individual rating. As expected, the performance initially increases with increasing values of b, but it decreases for greater values of b. Multi-interest improves recall from 17% (LastFM) to 69% (Delicious). For all datasets, Gossple significantly improves the quality of GNets over traditional clustering algorithms illustrated by the b = 0 configurations. The exact recall values are given in Table 5. We also observe that the improvement of multi-interest has more impact when the base recall is low. Further experiments, omitted due to space constraints, revealed that this is because Gossple is particularly good at finding rare items. Finally, we observe that the maximum performance is not obtained for a specific value of b, but for a full range of values, b ∈ [START_REF] Yildirim | A random walk method for alleviating the sparsity problem in collaborative filtering[END_REF][START_REF] Mcgill | Introduction to modern information retrieval[END_REF], across all datasets. This demonstrates Gossple's effectiveness on a wide variety of datasets without requiring prior fine tuning of parameters.

Convergence time

We evaluate Gossple's ability to build and maintain a useful GNet for each node. First, we consider the time required to build a network of Gossple acquaintances from empty GNets. Then we consider the maintenance of this network by evaluating convergence in a dynamic scenario where nodes join an existing stable network.

Bootstrapping. We consider a simulation of 50, 000 nodes and a real-world Plan-etLab deployment with 446 nodes on 223 machines. Figure 7 plots the hiddeninterests' recall (cf. Section 3.2) during the construction of the Gossple network.

It is normalized by the value obtained by Gossple at a fully converged state.

As expected, the multi-interest clustering (b = 4) constantly outperforms the standard one (b = 0), although it requires slightly longer to reach a stable state. The difference is minimal, Gossple reaches 90% of its potential after only 14 gossip cycles in simulation in our Delicious traces for instance. This convergence is extremely fast given the size of the network (50, 000) and the small size of the GNet and RPS [START_REF] Syverson | Anonymous connections and onion routing[END_REF]. The measures conducted on LastFM confirm the scalability of the protocol: for twice as large a network, only 3 more cycles are needed to reach the same convergence state. The PlanetLab deployment confirms the simulation results. The smaller scale of the experiments causes Gossple's GNets to reach 90% of their potential after an average of 12 cycles and stabilize after 30. This confirms the scalability of our protocol by demonstrating convergence times that grow very slowly with the size of the network.

Maintenance. Bootstrapping represents a worst-case scenario for the convergence of our protocol. It is, in fact, a one-time event in the life of a Gossple network. During normal operation, the system will instead experience perturbations that cause it to deviate from a stable state in which each node has converged to its best possible GNet. Examples of such perturbation include variations in the interests of users, or the presence of nodes that join and leave the network.

To evaluate the impact of these perturbations, we consider a scenario where 1% of new nodes join an existing Gossple network at each gossip cycle. We measure the hidden-interest recall of these new nodes to see how many gossip cycles are needed for them to reach a quality of GNet equivalent to the one of the previously converged nodes (i.e. 1 on the normalized score). Joining an existing network is indeed faster than bootstrapping, as 9 cycles are enough to reach a 90%-quality GNet. Clearly, this represents an upper bound on the time required for convergence in the presence of dynamic profiles or nodes that leave the network. In both of these cases, nodes that are required to converge only need to partially reconstruct their GNets as they already have some good neighbors to rely on. Moreover, the removal of disconnected nodes from the network is automatically handled by the clustering protocol through the selection of the oldest peer from the view during gossip exchanges as discussed in detail in [START_REF] Voulgaris | Epidemic-style management of semantic overlays for content-based searching[END_REF].

Bandwidth

The bandwidth consumption of Gossple when the GNets are built from scratch is depicted in Figure 8. This cost is the result of: (i) the exchange of profile digests upon gossip; (ii) the download of the full profiles of nodes in the GNet; (iii) the extra communication required to maintain anonymity. Each node gossips through the RPS and the GNet protocols every 10s: each message containing respectively 5 and 10 digests. This results in a maximum bandwidth consumption of 30kbps in the most demanding situation, that is during the burst at the beginning of the experiment. This is because no profile information has yet been downloaded. 6 As soon as the GNets start to converge, the rate of exchange of full profiles decreases, as shown by the line depicting the total number of downloaded profiles per user. This causes bandwidth consumption to decrease to the fixed cost of gossiping digests, 15kbps, a clearly irrelevant value for almost any user on the network today.

If Gossple did not use Bloom filters, on the other hand, profile information would be exchanged continuously, thereby increasing bandwidth consumption. In the considered data trace, replacing Bloom filters with full profiles in gossip messages makes the cost 20 times larger. Finally, we observe that, while Gossple's anonymity protocol continuously sends keep-alive messages, the only ones that impact bandwidth are those sent when new profile information needs to be exchanged.

Gossple at Work: Query Expansion

A query expansion system seeks to extend a query with additional keywords to improve the results. We now describe how to use Gossple to expand queries within a collaborative tagging system, such as Delicious or CiteULike, where every node is associated with a tagging profile. As we show, Gossple significantly improves the completeness (recall [START_REF] Brin | The anatomy of a large-scale hypertextual web search engine[END_REF]) and accuracy (precision [START_REF] Brin | The anatomy of a large-scale hypertextual web search engine[END_REF]) of the results, wrt the state-of-the-art centralized personalized approach, namely Social Ranking [START_REF] Zanardi | Social ranking: uncovering relevant content using tag-based recommender systems[END_REF].

Overview

We use Gossple GNets to compute a data structure we call TagMap (Figure 9), a personalized view of the relations between all tags in a node's profile and in its GNet. This is updated periodically to reflect the changes in the GNet. A query from the node is then expanded using the TagMap of that node through a centrality algorithm we call GRank , which we derived from the seminal PageRank [START_REF] Brin | The anatomy of a large-scale hypertextual web search engine[END_REF] algorithm. While PageRank computes the relative importance of Web pages (eigenvector centrality [START_REF] Abiteboul | Adaptive on-line page importance computation[END_REF]), GRank computes the relative importance of tags on a given node: we refer to this notion as the tag centrality from now on. GRank estimates the relevance of each tag in the TagMap wrt the query and assigns a score to the tag. We then recursively refine the correlation between tags by computing their distance using random walks, along the lines of [START_REF] Fogaras | Towards scaling fully personalized pagerank: Algorithms, lower bounds, and experiments[END_REF].

TagMap

The GNet of a node n contains a set of profiles covering its interests. These profiles are used to compute the TagMap of a node n, namely a matrix TagMap n , where TagMap n [t i , t j ] is a score that reflects the distance between tags t i and t j as seen by node n. We denote by IS n the information space of node n, namely its profile and the profiles in its GNet; T ISn and I ISn denote the set of all the tags and items in IS n . The TagMap uses item-based cosine similarity to compute a score between the tags. The information needed to fill the TagMap is, for each tag in T IS n , the number of occurrences of the use of that tag per item, i.e., for all t ∈ T ISn , a vector V n,t of dimension

|I IS n | is maintained such that V t [item i ] = v,
where v is the number of times the item item i has been tagged with t in IS n . More precisely: TagMap n [t i , t j ] = cos(V n,ti , V n,tj ). Table 10 depicts an example of a node's TagMap. In this example TagMap n [Music, BritPop] = 0.7.

GRank

The TagMap contains a personalized view of the scores between pairs of tags. This information can be directly used to expand queries as in [START_REF] Zanardi | Social ranking: uncovering relevant content using tag-based recommender systems[END_REF]. In this approach, called Direct Read (DR), the number of tags q added to the initial query is a parameter of the query expansion algorithm. With DR, a query is expanded with the q tags scoring the highest. More precisely: DRscore n (t i ) =

t∈query TagMap[t, t i ]. While this approach seems intuitive, it gives bad results when the item sparsity of the system is high. This is very likely to happen for niche content: with a very large number of items, the relationships between tags might not always be directly visible in the TagMap. To illustrate the issue, consider the TagMap presented in Table 10 and a query on Music with q = 2. The TagMap exhibits a high score between Music and BritPop (based on a given set of items). In addition, there is a low score between Music and Bach suggesting that the node is more interested in BritPop than in Bach. However BritPop and Oasis have also a high score in the same TagMap (gathered from a different set of items), DR will never associate Music and Oasis whilst this association seems relevant for that node. In fact, DR would instead expand the query with Bach, increasing the result set size and reducing the precision of the search (Figure 11).

Our approach is based on the observation that, by iterating on the set of newly added tags, more relevant tags can be selected for the query. We capture this idea through an algorithm inspired by PageRank [START_REF] Brin | The anatomy of a large-scale hypertextual web search engine[END_REF], which we call GRank 7 . In short, GRank runs a personalized PageRank on the tag graph extracted from the TagMap and assigns the set of priors to the tags in the query. More specifically, considering the weighted graph provided by the TagMap, all the tags in T ISn are vertices and, for each non-null score in the TagMap, we add an edge weighted by the score. These scores affect the transition probabilities when generating the query expansion. As opposed to PageRank, where each link is chosen with equal probability, in GRank , the transition probability (TRP) from one tag to another depends on the edge weight provided by the TagMap:

TRP n (t 1 , t 2 ) = TagMap n [t1 ,t2 ] t∈T ISn TagMap n [t1 ,t]
To limit the computation time of a score (which can be prohibitive in a large graph), instead of running an instance of GRank per query, we divide the computation per tag in the query, forming partial scores. These are approximated through random walks [START_REF] Fogaras | Towards scaling fully personalized pagerank: Algorithms, lower bounds, and experiments[END_REF] and cached for further use whenever the same tag is used in a new query. Still, a centralized server computing GRank for all nodes would not scale. It can only be applied in the context of Gossple where each node provides its processing power to compute its own GRank .

Expanding a query using GRank then simply consists in adding to the original query the q tags scoring the highest. All tags receive a score which is transmitted to the companion search engine.

Evaluation

We evaluated Gossple's ability to achieve a complete and accurate query expansion. We describe our experimental setup, report on the evaluation of the Gossple query expansion mechanisms on Delicious and CiteULike traces, and finally, we consider synthetic traces modeling the baby-sitter example given in the introduction, as well as the behavior of a mad tagger trying to disrupt Gossple's operation.

Evaluation setup. Workload. Each node is associated with a user (and her profile) from a real trace (Delicious or CiteULike). The profiles drive the generation of requests: let I n be the set of items in n's profile, n generates a query for each item i ∈ I n such that at least two users have i in their profiles. The initial query consists of the tags used by n to describe item i since they are also likely to be the ones n would use to search for i. We evaluate Gossple's query expansion using the generated queries. Given a query from node n on an item i, we first remove i from n's profile so that n's GNet and TagMap are not built with it, then we determine if i is indeed an answer to the expanded query.

Search engine. Although any search engine could be used to process a query expanded by GRank , for the sake of comparison, we consider the search engine and ranking method used in [START_REF] Zanardi | Social ranking: uncovering relevant content using tag-based recommender systems[END_REF]. The search engine runs on the set of items available in the real trace. An item is in the result set if it has been tagged at least once with one of the tags of the query. To rank the items, the score of an item is the sum, for each tag in the query, of the number of users who made an association between the item and the tag, multiplied by the weight of the tag.

Evaluation criteria. The query expansion mechanism is evaluated along the two classical and complementary metrics: recall (completeness) and precision (accuracy). Recall expresses the ability of the query expansion mechanism to generate a query that includes the relevant item in the result set. In these experiments, we are interested in the item i for which the query has been generated. A query succeeds when i is in the result set: recall is 1 if i is in the result set, 0 otherwise. Note that the size of the result set increases with the length of the query expansion, potentially reducing the visibility of the relevant item. To balance this effect, we also assess the quality of the query expansion by evaluating precision. We consider the absolute rank (based on the score provided by the search engine) of the items in the result set as a metric for precision: namely, the precision is defined as the difference between the rank with query expansion and the rank with the initial query.

Recall is evaluated on the queries that do not succeed without query expansion. This comprises 53% of the queries in the CiteULike trace and 25% in the Delicious one. These results show that a significant proportion of items have been tagged by several users with no tags in common and highlights the importance of query expansion. Precision is evaluated on the queries that are successful even without query expansion since they provide a reference rank for the item. Impact of Gossple's personalization.

Our first results, in Figure 12, isolate the impact of personalization through a TagMap based on a small GNet wrt to a global TagMap based on all users' profiles. Figure 12 shows the extra recall obtained with query expansion sizes from 0 to 50 on the Delicious8 traces with GNet sizes from 10 to 2, 000. We compare these results with those of Social Raking, i.e. the case where GNet contains all the other users. The figure presents the proportion of items that were found with the query expansion out of the ones that were not found without. For example, the point (x = 20, y = 0.37) on the Gossple 10-neighbor curve says that 37% of the requests not satisfied without query expansion are satisfied with a 20-tag expansion based on a GNet of 10 nodes.

expansion. The measures show that the personalized view, provided by Gossple and leveraged in the Gossple query expansion system, efficiently clustered users into interest communities enabling users interested in international schools and English novels to expand babysitter with teaching assistant. The second trace shows that the Gossple personalization of TagMap limits the impact of a user trying to force an association between tags. We call this situation a Gossple bombing, in reference to Google bombing. If an attacker builds a profile with very diverse items, then no node adds the attacker to its GNet and the attack fails.

If the attacker targets a specific community, then it can have an impact on their query expansion, but the number of users affected is very limited.

5 Related Work

Semantic overlays

Explicit approaches. Many user-centric approaches [START_REF] Amer-Yahia | Efficient network aware search in collaborative tagging sites[END_REF][START_REF] Mislove | Exploiting social networks for internet search[END_REF][START_REF] Bender | Peer-to-peer information search: Semantic, social, or spiritual?[END_REF] consider an explicit (predefined) social network, typically derived from systems such as Facebook, LinkedIn, LastFM or MySpace, to improve the search on the Web. The assumption here is that the explicit, declared, relationships between users reflect their shared interests [START_REF] Mislove | Measurement and analysis of online social networks[END_REF] and can help their search. In many cases, however, and as pointed out in [START_REF] Bender | Peer-to-peer information search: Semantic, social, or spiritual?[END_REF][START_REF] Ahn | Analysis of topological characteristics of huge online social networking services[END_REF], the information gathered from such networks turns out to be very limited in enhancing the navigation on the Web. A couple of alternative approaches exploit the unknown acquaintances of a user to improve the search further [START_REF] Khambatti | Structuring peer-to-peer networks using interest-based communities[END_REF]. These require the user to explicitly declare a list of topics of interest and assume a strict topic classification, rendering it impossible to dynamically detect new communities. Gossple goes a step further and automatically assigns acquaintances to users solely based on their common items: Gossple's associations naturally evolve over time.

Implicit approaches. Some approaches form semantic acquaintances by associating users with those that successfully answered their queries in the past [START_REF] Handurukande | Peer Sharing Behaviour in the eDonkey Network, and Implications for the Design of Server-less File Sharing Systems[END_REF][START_REF] Sripanidkulchai | Efficient content location using interestbased locality in peer-to-peer systems[END_REF][START_REF] Cholvi | Efficient search in unstructured peer-to-peer networks[END_REF][START_REF] Chen | Enhancing search performance in unstructured p2p networks based on users' common interest[END_REF][START_REF] Sedmidubsky | Adaptive approximate similarity searching through metric social networks[END_REF][START_REF] Eyal | Self organizing semantic topologies in p2p data integration systems[END_REF]. In file sharing communities, these approaches gradually transform a random overlay into weakly structured communities that improve the success ratio of queries. A major drawback is the need for a warm-up phase to establish the network based on a reasonable sample of queries: the first queries are sent to random users, leading to poor results. Furthermore, because the acquaintances of a user only reflect her last few queries, queries on new topics are inefficient.

Gossple actively locates the acquaintances of a user independently of her past queries but based on her (full interest) profile instead. In order to avoid the warm-up phase, some (active) clustering approaches rely on gossip. [START_REF] Voulgaris | Epidemic-style management of semantic overlays for content-based searching[END_REF] uses the number of shared files in common as a proximity metric. While this approach improves search, it overloads generous nodes that share many files. [START_REF] Jin | Efficient search for peer-to-peer information retrieval using semantic small world[END_REF] considers the cosine similarity of the users as a metric to penalize non-shared interests. This gives better performance than simple overlap and underlies our Gossple metric. These approaches also tend to choose uniform acquaintances that only reflect the primary interest of a user, while Gossple spreads the acquaintances among all the interests of a user. As discussed in [START_REF] Le-Blond | Clustering in p2p exchanges and consequences on performances[END_REF], a user has usually several areas of interests, typically non-correlated: on average, a node requires three clusters to find 25% of the data it is looking for. [START_REF] Patel | Rappel: Exploiting interest and network locality to improve fairness in publish-subscribe systems[END_REF] uses gossip to select semantic acquaintances for RSS feed transmission. The selection algorithm increases the score of nodes that provide items not covered by other acquaintances. Gossple's multi-interest metric can be considered a generalization of this idea. In [START_REF] Crespo | Semantic overlay networks for p2p systems[END_REF], a centralized ontology-based analysis of all the items in the system assigns a type to each one of them and infers users' interests. This procedure is centralized and relies on an external source of knowledge for the classification, while Gossple is fully distributed and only uses the item interest pattern of users as a source of information. In [START_REF] Banaei-Kashani | Swam: a family of access methods for similaritysearch in peer-to-peer data networks[END_REF], the attributes of the items generate a navigable overlay. This approach is centered on items rather than users, and does not scale with the number of items a user shares. It is also limited to items which carry a lot of metadata, like music or text files. The system proposed in [START_REF] Li | Ssw: A small-world-based overlay for peer-to-peer search[END_REF] is fully distributed: it clusters items in order to obtain semantic coordinates. The node joins the unstructured community responsible for most of its items and obtains small-world links to other communities. Although the node has to advertise the items which are not part of its main community, this approach scales quite well with the size of the user profile. However, it suffers from the same drawback as [START_REF] Banaei-Kashani | Swam: a family of access methods for similaritysearch in peer-to-peer data networks[END_REF] and requires items with a lot of metadata for clustering.

Query expansion

Personalized systems. Personalized query expansion has so far considered two approaches. The first consists in leveraging information about users' past behavior. In [START_REF] Carman | Tag data and personalized information retrieval[END_REF], the query is expanded by tags already used in previous queries. In [START_REF] Jie | Personalized faceted query expansion[END_REF], the query is expanded using the information available on the user's local computer. The tags are chosen with a local search engine and completed by user feedback. In both cases, no information is inferred from other users. The second approach [START_REF] Amer-Yahia | Efficient network aware search in collaborative tagging sites[END_REF][START_REF] Mislove | Exploiting social networks for internet search[END_REF][START_REF] Bender | Peer-to-peer information search: Semantic, social, or spiritual?[END_REF] consists in enhancing the queries using an explicit social network of the user. As already discussed, this is not always appropriate.

Global approaches. Centralized Web search engines often rely on handwritten taxonomies (Wordnet, Open Directory Project, Yahoo! Directories) to expand queries. Instead, we only consider knowledge that is automatically extracted from the user's profile. [START_REF] Bender | Exploiting social relations for query expansion and result ranking[END_REF] proposes a query-expansion framework that uses social relations to rank results. However, only the scoring model is personalized. The query-expansion mechanism exploits the co-occurrence of tags in the full document collection leading to a non-personalized query-expansion output. Social Ranking [START_REF] Zanardi | Social ranking: uncovering relevant content using tag-based recommender systems[END_REF] is somehow similar but relies on the cosine similarity of tags to infer their proximity. This is, in a sense, the closest to our query expansion technique. We presented our comparison in Section 4.4.

Concluding Remarks

We presented Gossple, an Internet-scale protocol that discovers connections between users and leverages them to enhance navigation within the Web 2.0.

With little information stored and exchanged, every Gossple node (user) is associated with a relevant network of anonymous acquaintances. Nodes can join and leave the system dynamically and the profile of a node that left the system is eventually automatically removed from all personalized networks. No central authority is involved and there is no single point of failure. Decentralization makes it furthermore possible to effectively perform certain tasks, such as computing the TagMap and the GRank, which would have been computationally prohibitive in a centralized system. Interestingly, Gossple naturally copes with certain forms of free-riding: nodes do need to participate in the gossiping in order to be visible and receive profile information. As we have also shown, the impact of arbitrary tagging, or even individual malicious tagging, is very limited.

Yet, Gossple has some limitations and many extensions might need to be considered. Our gossip-on-behalf approach is simple and lightweight, but users may require additional security even by enduring a higher network cost. It would be interesting to devise schemes where extra costs are only paid by users that demand more guarantees. It would also be interesting to explore the benefits of a social network of explicit friends. For instance, Gossple could take such links into account as a ground knowledge for establishing the personalized network of a user and automatically add new implicit semantic acquaintances. This would pose non-trivial anonymity challenges.

Fig. 1 .

 1 Fig. 1. Associating John to Alice enables John to leverage the unusual association between the keywords teaching assistants and baby-sitter.

Fig. 3 .

 3 Fig. 3. Gossple network

Fig. 4 .

 4 Fig. 4. The Bloom filter of a profile

Fig. 5 .Fig. 6 .

 56 Fig. 5. Dataset properties

Fig. 7 .Fig. 8 .

 78 Fig. 7. Recall during churn

Fig. 9 .Fig. 10 .

 910 Fig. 9. Expanding queries with Gossple

Fig. 11 .

 11 Fig. 11. Example of query expansion

Fig. 12 .

 12 Fig. 12. Extra recall (Delicious)

  Do once for each T time units begin g = oldest node in GNetn Send GNetn ∪ ProfileDigestn to g

		Algorithm 2: Scoring heuristic
		Input: set of nodes candidateSet
		Output: a view of size viewSize
		bestView = {}
		for setSize from 1 to viewSize do
	Receive GNetg from g	foreach candidate ∈ candidateSet do
	compute GNetn using	candidateView =
	(GNetn ∪ GNetg ∪ RPSn )	bestView ∪ {candidate}
	increment timestamp of GNetn	viewScore =
	foreach u ∈ GNetn do	SetScore(candidateView )
	if u ∈ GNetn for K cycles & u's full profile has not been fetched then fetch u's profile	bestCandidate = candidate that got the highest viewScore bestView = bestView ∪ {bestCandidate} candidateSet-= {bestCandidate}
	end	Result: bestV iew

See recent events with privacy threats of Facebook.

Classical file sharing applications could also benefit from our approach: our experiments with eDonkey (100, 000 nodes) provided very promising results.

The is burst is slightly longer on PlanetLab due to the lack of synchronization between nodes.

PageRank provides information about the importance of vertices in a graph. Personalized PageRank (PageRank with priors) compute centrality wrt a set of vertices.

Experiments on the CiteULike trace lead to the same conclusions but the results are not presented for space reasons.

⋆ This work is supported by the ERC Starting Grant GOSSPLE number 204742

The figure highlights the benefit of personalization over a TagMap that would involve all users such as Social Ranking. Even though increasing the size of the GNet up to 100 has a positive impact on recall, larger sizes degrade performance. With a 30-tag query expansion, a 10-node GNet has a recall of 43%; recall goes up to 47% in a 100-node network and drops to 42% in the case of Social Ranking. As the number of node profiles integrated in the TagMap increases, relevant tags are gradually swallowed by less relevant tags or popular ones. This is clearly an illustration of how the baby-sitter/teaching assistant association in the example presented in Section 1 could be diluted if we had considered all users.

Impact of Gossple's centrality. We evaluate here the impact of computing the relative importance of tags (GRank ) over the DR query expansion. As mentioned previously, personalization is mostly responsible for increasing recall. However, computing the relative importance of tags (i.e., tag centrality) significantly improves the precision of the results. This is clearly illustrated in Figure 13, which compares our results against those of the non personalized DR query expansion, i.e. Social Ranking.

On Figure 13(right), as the query expansion size increases, the recall for items which were not found initially, improves. With a 20-tag query expansion, we observe a 37% recall of the items which were not originally found. Yet, this is accompanied by a significant drop in the precision for 71% of the items originally found. GRank however with a 20-, resp. 50-tag query expansion, increases the recall of items not found initially up to 40%, resp. 56%, while increasing the ranking of approximately 58, 5% resp. 40% of the items which were returned to the initial query. This is a clear illustration of the impact of GRank on the precision. Interestingly enough, Gossple improves the precision for approximately 50% of the items when using a query expansion of 0. This is due to the fact that in Gossple the tags' weights reflect their importance.

To summarize, while the direct use of the TagMap improves the recall over existing approaches, mostly through personalization, the precision is significantly improved through the centrality provided by GRank . The latter is of utmost importance as the better precision enables us to expand queries with more tags. Synthetic traces. We also assessed the benefit of Gossple, on specific cases, through two synthetic traces. Due to space limitations, we only give an overview of these experiments. The first trace was generated to demonstrate the ability of Gossple to address the baby-sitter example of the introduction with query


Marco C Pretorius
email: marco.pretorius@gmail.com

Judy Van Biljon

Estelle De Kock

Added Value of Eye Tracking in Usability Studies: Expert and Non-expert Participants

Keywords: Usability, Eye tracking, expert, non-expert

This paper investigates the value of eye tracking in evaluating the usability of a Learning Management System, at an open distance learning university where the users' computer and Web skills vary significantly. Eye tracking utilize the users' eye movements, while doing a task, to provide information about the nature, sequence and timing of the cognitive operations that took place. This information supplements, but does not replace standard usability testing with observations. This forces the questions of when the added value of eye tracking justifies the added cost and resources. Existing research has indicated significant differences in the usability experienced by experts and non-experts on the same system. The aim of this paper is to go one step further and shed light on the type and severity of the usability problems experienced by non-expert users. Usability testing with eye tracking is a resource intensive method but our findings indicate that eye tracking adds concise, summarised evidence of usability problems that justifies the cost when testing special groups such as users deficient in Web and computer skills. The contribution of this paper is to highlight the added value of eye tracking as a usability evaluation method in working with Web non-expert users. Furthermore, the findings improve our understanding of the knowledge differences between expert and non-expert Web users and the practical challenges involved in working with non-expert users.

Introduction

The Web is evolving into the preferred delivery mode for Learning Management Systems (LMS) which offer services such as student enrolment, coursework notice boards and assignment submission. A LMS is defined as a Web-based application used by institutions and companies that want to get involved in e-learning either for providing services to third parties, or for educating and training their own people [START_REF] Avgeriou | Towards a Pattern Language for Learning Management Systems[END_REF]. In developing countries the students' computer and Web skills vary, some are experts with sophisticated skills while others lack the most basic computer skills. The problem is compounded by the fact that the system is used occasionally and under time constraints such as registering or submitting an assignment before a due date and even financial constraints where students use commercial internet facilities. When the Web interface of a LMS becomes the only access point, usability becomes critical. Designing for novice users has been well-researched. However, eye tracking as evaluation tool for evaluating non-expert web users is novel. This raised the question: What is the added value of eye tracking in evaluating non-expert web users?

We can predict that computer expertise will influence usability positively, but the use of eye tracking could possibly help to find the severity of the effect on non-expert users and if anything can be done to improve the usability for these users. To answer these questions we conducted a usability study on the assignment submission section of a university LMS purposively selecting expert and non-expert users respectively. In order to identify the added value of eye tracking, we captured data by different means including eye tracking, observation (direct observations and video recordings) and a post-test questionnaire. We analysed the data sets separately and compared the findings to see if eye tracking did contribute additional knowledge.

Eye tracking has been used to research the difference between experienced and less experienced users in information retrieval tasks [START_REF] Dillon | An empirical comparison of the usability for novice and expert searchers of a textual and a graphic interface to an art-resource database[END_REF] and different styles have been associated with experienced and less experienced users [START_REF] Aula | Eye-Tracking Reveals the Personal Styles for Search Result Evaluation[END_REF]. In general expert users perform faster, more accurate and have more defined search paths whereas nonexperts waste time searching or looking at irrelevant information [START_REF] Law | Eye Gaze Patterns Differentiate Novice and Experts in a Virtual Laparoscopic Surgery Training Environment[END_REF][START_REF] Kasrskis | Comparison of expert and novice scan behaviours during VFR flight[END_REF]. However, eye tracking has not previously been widely applied to studies of behavioural aspects of students using a LMS. What is lacking is an explanation of the implications the difference between expert and non-experts could have for the usability of a LMS.

The main contribution of the paper is to identify the added value of eye tracking in investigating usability problems experienced by non-experts in using a LMS. The scope of the research is limited to the evaluation of one LMS but the data sets captured through video and audio recordings, eye tracking video recordings, eye tracking data files and post-test questionnaires are triangulated to provide more reliability.

Related Usability Studies

Any research comparing expert and non-expert users of an interactive system has to take cognisance of the fundamental distinction between these two, founded in their knowledge and experience and therefore we first review knowledge categories before discussing usability evaluation paradigms, focusing on heuristic evaluation and eye tracking. There are different empirical definitions of experts and non-experts but two (strongly overlapping) criteria used for the differentiation between experts and non-experts are knowledge and the time spent working with a particular system [START_REF] Prumper | Errors in computerized office work : Differences between novices and expert users[END_REF]. Given this fact that expertise is related not only to time spent working with the system, we use the term non-expert rather than novice. Furthermore, the term non-expert is useful for grouping categories such as novices and intermediate users, both not expert. Focusing on the knowledge component, Prumper et al. [START_REF] Prumper | Errors in computerized office work : Differences between novices and expert users[END_REF] states that experts operate at higher cognitive levels, i.e. using knowledge from different categories than nonexperts do.

Working with non-experts require more structure in terms of doing tasks, more assistance and more encouragement in reporting problems [START_REF] Äijö | Are non-expert evaluations valuable? 18[END_REF], but Fields, Keith et al. [START_REF] Fields | Designing for Expert Information Finding Strategies[END_REF] emphasize the value of user groups with varying forms of expertise. Popovic [START_REF] Popovic | Expert and Novice user differences and implications for product design and usability Human Factors and Ergonomics Society Annual Meeting Proceedings[END_REF] states that all interactive interface design should support and facilitate the transitional process from novice to expert user. Gorman [START_REF] Gorman | Types of Knowledge and Their Roles in Technology Transfer[END_REF] classifies four knowledge categories, i.e. declarative knowledge (what), procedural knowledge (how), judgement knowledge (when) and wisdom (why) that we will use as reference.

The way experts and non-expert users use interactive Web sites is differentiated by the difference in their knowledge (particularly domain-specific knowledge) [START_REF] Popovic | Expert and Novice user differences and implications for product design and usability Human Factors and Ergonomics Society Annual Meeting Proceedings[END_REF] and also by the way they approach and solve problems [START_REF] Tabatabai | Expert-Novice Differences in Searching the WebAIS Electronic Library (AISeL)[END_REF]. Äijö and Mantere [START_REF] Äijö | Are non-expert evaluations valuable? 18[END_REF] conducted a study on the usefulness of non-experts in identifying the usability problems in an interactive Web service. They found that non-experts were capable of reporting usability problems on the interface but had difficulties in reporting usability problems related to interactivity with the system. This concurs with Kotze et al. [START_REF] Kotze | Don't do this -Pitfalls in using anti-patterns in teaching[END_REF] who state that although experts and non-experts may differ in all the categories, novices rely more on declarative and to a lesser extent on weak heuristics based on procedural knowledge while experts rely more on judgment knowledge.

We now review the use of eye tracking in usability studies. The human eye reads a line of text in discrete chunks through a series of fixations and fast eye movements to take in the next section [START_REF] Beymer | An Eye Tracking Study of How Pictures Influence Online Reading[END_REF]. Eye tracking is based on the fact that a record of a person's eye movements while doing a task provides information about the nature, sequence and timing of the cognitive operations that took place [START_REF] Rudmann | Eye tracking in Cognitive State Detection for HCI[END_REF].

Eye tracking studies have been used in diagnosing the effectiveness of Website designs with point of interest detection and information transmission via eye movement (scan path) as two main indicators [START_REF] Yoneki | Sentient Future Competition: Ambient Intelligence by Collaborative Eye Tracking[END_REF]. Based on this relation between cognition and eye behaviour the trace of navigation pathways and user attention patterns is used to study the cognitive processes involved in reading [START_REF] Aula | Eye-Tracking Reveals the Personal Styles for Search Result Evaluation[END_REF], picture perception [START_REF] Äijö | Are non-expert evaluations valuable? 18[END_REF][START_REF] Beymer | An Eye Tracking Study of How Pictures Influence Online Reading[END_REF], visual search [START_REF] Bednarik | An eye-tracking methodology for characterizing program comprehension processes[END_REF], problem solving [START_REF] Kasrskis | Comparison of expert and novice scan behaviours during VFR flight[END_REF], face perception [START_REF] Karn | Eye tracking in human-computer interaction and usability research: Ready to deliver the promises[END_REF] and many other tasks.

In HCI eye tracking has been used to study the usability of Web pages [START_REF] Jacob | The Mind's Eye: Cognitive and Applied Aspects of Eye Movement Research[END_REF], menu searching, information searching from Web pages and search result evaluation [START_REF] Aula | Eye-Tracking Reveals the Personal Styles for Search Result Evaluation[END_REF]. Eye tracking studies on the difference between expert and non-expert users in HCI are difficult to find but some have been done in other fields. The eye movements of experts and novices were compared in a virtual aiming task done in a laparoscopic surgery training system. The results showed significant differences in performance as well as eye movement between the two groups [START_REF] Law | Eye Gaze Patterns Differentiate Novice and Experts in a Virtual Laparoscopic Surgery Training Environment[END_REF]. A study in the field of aviation compared expert and novice pilots to find that experts have better defined, more consistent and efficient eye-scanning patterns [START_REF] Kasrskis | Comparison of expert and novice scan behaviours during VFR flight[END_REF].

Eye tracking has the advantage of providing visual evidence of usability problems but the method has been criticized for reliability and objectivity. Sutcliffe and Namoune [START_REF] Sutcliffe | Investigating User Attention and Interest in Websites[END_REF] question the reliability of eye tracking for determining which features are attended because they found that users discovered areas of interest by short fixations or proximal fixations i.e., it is difficult to know exactly what the user was looking at. Further criticism on eye tracking is the objectivity: the analysis of patterns is mostly based on the opinion and interpretations of the individual evaluator [START_REF] Ehmke | Identifying Web Usability Problems from Eye-Tracking Data[END_REF].

Correlating eye-movement metrics with usability problems is proposed as a more rigorous, verifiable mapping of eye tracking patterns to usability problems [START_REF] Ehmke | Identifying Web Usability Problems from Eye-Tracking Data[END_REF].

Method

The method for this usability and eye tracking study was based on the methodology by Pretorius et al. [START_REF] Pretorius | The Added Value of Eye Tracking in the Usability Evaluation of a Network Management Tool[END_REF]. Section 3.1 presents the participants' profile, section 3.2 discusses the procedure followed and section 3.3 provides more detail on how the data was captured.

Participant Profile

The intended user group for the LMS is students who have to submit assignments online. A screening questionnaire was used to screen the participants for this evaluation. This questionnaire reflected the possible participant's LMS experience, computer and Internet experience, culture, age and gender. Regarding expert and nonexpert users, results showed that individuals' ratings of their overall knowledge were better predictors than were estimations of frequency of use [START_REF] Vu | Metacognitive Processes in Human-Computer Interaction: Self-Assessments of Knowledge as Predictors of Computer Expertise[END_REF].

The screening questionnaire asked participants to rate their experience level as an Internet user. The following ratings were available: Never used the Web; Beginnerhave read pages on the Web; Novice -have entered addresses and used bookmarks; Competent -can use a search engine to find information; and Proficient -know way around and have done Web transactions like e-banking.

From the 23 questionnaires completed, we selected 10 students, five who rated themselves as proficient Internet users and another five who rated themselves between a beginner and competent level. The first group were referred to as expert participants and the latter group as non-expert participants.

The participants had all used some sections of the LMS, their experience ranged from less than one year; between one and two years; and two years or more.

Our participants included five male and five female students. One student was below 20; six between 21 and 25; one between 26 and 30; and two above 30. The mother tongue (first language they learned to speak) of the 10 participants was as follow (number of participants indicated in brackets): English (2); isiXhosa (2); Afrikaans (2); SiSwati (1); Sesotho (1); Xitsonga (1); Yoruba (1).

Conducting the Test

One participant was tested at a time. On arrival, the participant was briefed about the experiment, which was followed by an explanation of the equipment to be used. The details of the material to be recorded were explained and the participant was required to complete an informed consent form.

A variation of the think aloud protocol was used, where participants were asked to comment if they were looking for something and could not find it; if they liked something particular about the Website; and if they disliked something particular.

Participants completed three tasks available from a task list (discussed in Section 4). Following the tasks, a quick interview was conducted to ask the participants what they liked most about the system, what they did not like, as well as questions about issues that the administrator picked-up. This was followed by a post-test questionnaire and a debriefing where the participant was thanked and given the opportunity to see the data.

Data Collection Method

Data was collected and calculated as follows: live video recordings were captured, including the screen, participant's face and mouse/keyboard movements; were taken during the test as well as a full evaluation of the video at a later stage; audio in the form of the participant or the test administer speaking were included with the video files; eye tracking video recordings included a cursor which indicates the participant's eye movements; eye tracking data files; a post-test questionnaire was used to capture the participants' perception of the user interface and the system; and continuous monitoring of tasks.

The usability laboratory consists of an observer room and a participant room, separated by a one-way mirror. The participant room is equipped with a 17" TFT monitor with resolution of 1280x1024 and a Tobii 1750 eye tracker, allowing the eye movement of participants on the screen to be recorded. A 9-point eye tracking calibration was used at all times.

Results and Findings

This section discusses the results and findings obtained from the usability test.

Task 1

The participant had to submit a written assignment (a Word file) for this task. This was done by entering or browsing for the correct file, before selecting the appropriate file format from a drop-down box. The Word file format was the default choice.

The usability results, as depicted in Table 1, showed a clear distinction between expert participants and non-expert participants. The expert participants had no problems with this task with task completion time ranging between 27 and 50 seconds. Expert participants made no errors and no assistance were needed.

In contrast, the non-expert participants struggled a great deal with task completion times significantly longer. Four of these participants made errors during this task; three needed assistance; and one was not able to complete the task. The participant who could not complete the task received assistance, but this did not help; a complete run through of the task was needed. The task completion time of this participant was removed from the sample (exceeded nine minutes). This task had to be turned into a training task that would help the participant to complete the subsequent tasks in the task list. This non-expert participant did not understand computer terms such as "minimise" and "desktop". None of the non-expert Web participants could comprehend the term "File Name", where the name of the task file is entered or selected. One participant asked what a file name is and another entered the course code as the file name. The participant asked "how do I load a file from my PC to the LMS?" with a confused facial expression. After clicking "continue" without entering a file name, the participant received an error message which read: "ERROR: The type of file does NOT match the selected file type. (xxxxxx!=DOC)". The participant did not understand the error message.

One participant clicked on "continue" without entering a file name; after the error message the participant entered the course code as the file name. Another participant entered his own name in the file name text box. The participant clicked 'continue' and received an error message; repeating the same mistake three times.

The eye tracking results provide clear evidence of the difference in usability between expert and non-expert participants. The scan paths for non-expert participants (Figure 1) are much longer and have more fixations scattered over the screen. This shows us that participants searched and did not know exactly what to do.

As stated in the usability results, all five non-expert Web participants could not comprehend the word "File Name". The scan paths for expert users (Figure 2) are much shorter with fewer fixations. Eye tracking allows an evaluator to see what the participant was reading (and not reading) thereby identifying the problem areas on the screen as well as the information that goes unnoticed.

Throughout the task list, eye tracking data showed that the majority of participants did not read the instructions. Figure 3 demonstrates such an example where a participant did not read the instructions. The instructions are indicated by a rectangle. The phrase "Here is your final chance to check that your assignment is correct" is included in these instructions. Only one of ten participants read these instructions.

Task 2

The participant had to submit a written assignment that included selecting a file in the correct (PDF) file format. The usability results showed a 70% completion rate but all participants made errors in not selecting the correct file format, with four participants needing assistance. Once the participants wanted to proceed with the task, without selecting the correct file format, the following error message was displayed: "ERROR: The type of file does NOT match the selected file type. (PDF!=DOC)".

All non-expert participants received this error at least twice. One participant received the error five times. The PDF file was opened, but the participant could not distinguish between a Word and PDF file. Consequently, this participant could not complete the task. One participant was given assistance after receiving the error four times. The assistance given was that the file is a PDF file and not a Word file. This did not help the participant, as the difference between PDF and Word was not understood. The participant shook her head in frustration during the task. Two participants submitted Word files instead of the PDF file after receiving the error twice.

Like in the first task, one non-expert participant entered his own name under file name again. After receiving the error six times, instructions were given as where to select the file format. The participant proceeded to guess the file format, by selecting each one available, until PDF was reached and accepted. This shows that the file format and PDF terminology is not understood. Three expert participants received the error message once only, correcting their mistake very quickly. One expert proceeded to submit the wrong file, a Word file. The last expert participant searched in Help and FAQ to find a solution.

The evidence from the eye tracking data supports the problem with understanding technological terms. Eye tracking data showed that all participants read the full error message; however only three participants (experts) continued to complete the task correctly after the first error message. None of the non-expert participants fixated on the word "File Format" or on the drop-down box arrow where the file format had to be selected. This indicates that the error message was not comprehended.

Task 3

Task 3 was the same as task one and would give an indication of the learnability of the Website. The usability results showed that eight of the participants completed the task faster than in task one. The average task time went from 68.67 to 34.70 seconds. Task completion was 100 %. This demonstrates that once a participant knows the basics of this Website, they use it without problems.

The expert participants had no problems with this task with task completion time ranging between 10 and 60 seconds. Expert participants made no errors and no assistance was needed. In this case, the two participants whose times did not improve were experts who double checked the files they were submitting. All non-experts completed the task faster with task completion time ranging between 22 and 63 seconds. One non-expert participant struggled with the file type again, selecting PDF instead of Word. This participant learnt the process, but still struggled with the term file type, another non-expert struggled with the term file name.

Figure 4 demonstrates the same stage of the task as given in Task 1 for the same participant (a non-expert). Notice the improved shorter scan path and much less fixations. This demonstrates that the participants quickly learnt how to use this system. Research shows that a large number of fixations point to a less efficient search [START_REF] Karn | Eye tracking in human-computer interaction and usability research: Ready to deliver the promises[END_REF]. Once the participant knew what to do, the process was much faster.

Post-test Questionnaire

All the participants were positive about the system despite the evidence that some of them found it difficult to use. Results showed that all questions had a median of 4 (5-point Lickert scale) or above. Only one question regarding error messages given by the Website had a median of 3. This discrepancy between their experience and response highlights the usefulness of eye tracking in identifying problems that would not have been reported. We can only speculate that this may be due to social desirability bias, quiescence or participants forgetting some of the difficulties they experienced. Participant comments in the post-test questionnaire included:  "Think it would be difficult for a person who rarely uses computers. They may have a problem understanding things like the file type."  "It will be very useful if users could be shown how to use this Website. I had a friend who had to show me how to work it."

These comments provide further evidence that it is necessary to distinguish between expert and non-expert users.

Discussion

The aim of this research was to examine the findings from the different usability methods namely, usability testing with observation, eye tracking and the post-test questionnaires. Looking at the findings for the three tasks evaluated, the eye tracking data supported the observations by providing concise, objective evidence of what was observed. Hence, the value of eye tracking lies in triangulating and corroborating the observations rather than in replacing the observations made on the user testing. Different user's data can be overlaid to highlight specific problems. This summarised format is useful in providing the data to clients and managers who do not have the time to view all the recordings. In both cases the expertise of the observer or evaluator can influence the results but the scan paths and heat maps from eye tracking data provides a form of concise, summarised data that is difficult to match with other evaluation methods.

Eye tracking equipment is expensive and dedicated expertise is needed to use the equipment optimally as we have also experienced in our study. Therefore the overhead of cost and expertise needs to be carefully considered against the possible gains. Furthermore, our findings corroborate the fact that eye tracking is a tool to supplement usability evaluations and it does not replace standard usability testing with observations. This returns us to the questions of when the added value of eye tracking is justified.

The value of eye tracking, based on our findings is that it provides summarised, concise evidence. Furthermore, it is especially useful in capturing problems where users may be hesitant or unable to identify usability problems. For example, the disparity between the user-satisfaction reported in the post-test questionnaires, the user-satisfaction captured in the observations and the user-satisfaction captured in the eye tracking data. Despite the usability problems encountered, and captured by the objective measures, all the non-expert participants reported satisfaction with the system. In contrast the experts were more critical in the user satisfaction questionnaire while their efficiency and effectiveness usability measures rated higher. At this point we can only speculate about the reasons for the discrepancy between the objective and subjective results for non-experts. Data capturing errors such as the halo effect and social desirability bias could play a role since users have been found to make different judgments about the interfaces of scenarios for serious educational use [START_REF] De Angeli | Designing Interactive Systems archive Proceedings of the 6th conference on Designing Interactive systems[END_REF]. This raises questions about the reliability of using subjective measures (post-test questionnaires in this study) for usability testing and emphasizes the importance of adding eye tracking data as objective evidence.

From a design perspective, error messages should be as short and simple as possible, when designing for non-expert users. From a practical perspective our study showed that participants had trouble with the most basic of terms e.g. File type. In designing a LMS it would be difficult to avoid using basic terms and therefore we recommend the use of a training video to provide a standardised, minimum body of knowledge before attempting any task. In the repeat task all non-experts' times improved; this means that the students learnt the system but they needed assistance in getting past the critical errors. From the design perspective, the negative effects of errors were compounded by the use of domain specific terms and the length of the error messages. It has been noted that non-experts provide valuable information about users' individual reactions and they are an important group in usability evaluations [START_REF] Äijö | Are non-expert evaluations valuable? 18[END_REF]. Our findings support the usefulness of non-expert input on the declarative (identifying problems with terminology) and procedural (identifying problems with instruction flow) knowledge levels.

Conclusion and Future Work

This study investigated the added value of eye tracking in usability testing of expert and non-expert Web users while doing LMS tasks. The usability and eye tracking data showed differences in terms of task time (considerably longer for non-experts), scan paths (longer for non-expert participants with more fixations scattered over the screen) and comprehension of terminology and error messages (non-experts had more difficulty understanding and kept repeating mistakes). Non-experts are known to have longer task times and scan paths than experts [START_REF] Law | Eye Gaze Patterns Differentiate Novice and Experts in a Virtual Laparoscopic Surgery Training Environment[END_REF][START_REF] Kasrskis | Comparison of expert and novice scan behaviours during VFR flight[END_REF], but what is surprising is the difficulty non-experts had in comprehending the most basic terminology and error messages to the point where it rendered the system unusable.

The added value of eye tracking was to pin-point the particular problem areas through users' scan paths, i.e., the problematic terms that caused many fixations as well as the instructions that were not read. Eye tracking data also provided visual evidence to back-up the observations made by the usability evaluator. In this study, where the findings from the post-test questionnaire and the usability testing observations were in conflict, eye tracking data provided evidence to allow resolution that the users were indeed experiencing usability problems.

We conclude that the additional cost of eye tracking is justified when working with users where usability problems may be purposely or unintentionally disguised. The number of participants used was satisfactory for a usability study, where five to eight participants are deemed sufficient [START_REF] Barnum | Usability Testing and Research[END_REF][START_REF] Nielsen | Why You Only Need to Test With 5 Users[END_REF]. However, we plan to validate these findings further by having more participants completing a more comprehensive set of tasks. Future research will test these findings on different Learning Management Systems and also investigate the use of eye tracking with other user groups.

Figure 1 :

 1 Figure 1: Non-expert participant: long scan path with many fixations.

Figure 2 :

 2 Figure 2: Expert participant: short scan path with few fixations.

Figure 3 :

 3 Figure 3: Participant gaze plot: not reading instructions.

Figure 4 :

 4 Figure 4: Improved scan path and less fixations compared to same participant in Figure 1.

Table 1 :

 1 Usability results for task 1

		Completed Time (in seconds)	Errors	Assistance needed
	Expert	5	27-50	0	0
	Non-Expert	4	68-161	4	3