extfieldsofstudy:
Computer Science
Physics

text:
Agents, Bookmarks and Clicks: A topical model of Web traffic

Analysis of aggregate and individual Web traffic has shown that PageRank is a poor model of how people navigate the Web. Using the empirical traffic patterns generated by a thousand users, we characterize several properties of Web traffic that cannot be reproduced by Markovian models. We examine both aggregate statistics capturing collective behavior, such as page and link traffic, and individual statistics, such as entropy and session size. No model currently explains all of these empirical observations simultaneously. We show that all of these traffic patterns can be explained by an agent-based model that takes into account several realistic browsing behaviors. First, agents maintain individual lists of bookmarks (a non-Markovian memory mechanism) that are used as teleportation targets. Second, agents can retreat along visited links, a branching mechanism that also allows us to reproduce behaviors such as the use of a back button and tabbed browsing. Finally, agents are sustained by visiting novel pages of topical interest, with adjacent pages being more topically related to each other than distant ones. This modulates the probability that an agent continues to browse or starts a new session, allowing us to recreate heterogeneous session lengths. The resulting model is capable of reproducing the collective and individual behaviors we observe in the empirical data, reconciling the narrowly focused browsing patterns of individual users with the extreme heterogeneity of aggregate traffic measurements. This result allows us to identify a few salient features that are necessary and sufficient to interpret the browsing patterns observed in our data. In addition to the descriptive and explanatory power of such a model, our results may lead the way to more sophisticated, realistic, and effective ranking and crawling algorithms.

INTRODUCTION
Despite its simplicity, PageRank [6] has been a remarkably robust model of human Web browsing characterizing it as a random surfing activity. Such models of Web surfing have allowed us to speculate how people interact with the Web. As ever more people spend a growing portion of their time online, their Web traces provide an increasingly informative window into human dynamics. The availability of large volumes of Web traffic data enables systematic testing of PageRank's underlying navigation assumptions [20]. Traffic patterns aggregated across users have revealed that some of its key assumptions-uniform random walk and uniform random teleportation-are widely violated, making PageRank a poor predictor of traffic. Such results leave open the question of how to design a better Web navigation model. Here we expand on our previous empirical analysis [20,19] by considering also individual traffic patterns [14]. Our results provide further evidence for the limits of simple (memoryless) Markovian models such as PageRank. They suggest the need for an agent-based model with more realistic features, such as memory and topicality, to account for both individual and aggregate traffic patterns observed in realworld data.
Models of user browsing also have important practical applications. First, the traffic received by pages and Web sites has a direct impact on the financial success of many companies and institutions. Indirectly, understanding traffic patterns has consequences for predicting advertising revenues and on policies used to establish advertising prices [11]. Second, realistic models of Web navigation could guide the behavior of intelligent crawling algorithms, improving the coverage of important sites by search engines [8,25]. Finally, improved traffic models may lead to enhanced search ranking algorithms [6,28,17].

Contributions and outline
In the remainder of this paper, after some background on related and prior work, we describe a data set collected through a field study from over a thousand users on the main campus of Indiana University. We previously introduced a model of browsing behavior, called BookRank [3], which extends PageRank by adding a memory mechanism. Here we introduce a novel agent-based model, which also accounts for the topical interests of users. We compare the traffic patterns generated by these models with both aggregated and individual Web traffic data from our field study. Our main contributions are summarized below: • We show that the empirical diversity of pages visited by individual users, as measured by Shannon entropy, is not well predicted by either PageRank or BookRank. This suggests that a typical user has both focused interests and recurrent habits, meaning that the diversity apparent in many aggregate measures of traffic must be a consequence of the diversity across individual interests.
• When we build logical sessions by assembling requests based on referrer information and initiating sessions based on linkindependent jumps [19], we find that endowing the model with a simple memory mechanism such as bookmarks (as in the BookRank model) is sufficient to correct the mismatch between PageRank and the distributions of aggregate measures of traffic, but not to capture the broad distributions of individual session size and depth.
• We introduce an agent-based navigation model, ABC, with three key, realistic ingredients: (1) bookmarks are managed and used as teleportation targets, defining boundaries between logical sessions and allowing us to capture the diverse popularity of starting pages; (2) a back button is available to account for tabbed browsing and explain the branching observed in empirical traffic; and (3) topical interests drive an agent's decision to continue browsing or start a new session, leading to diverse session sizes. The model also takes into consideration the topical locality of the Web, so that an interesting page is likely to link to other interesting pages.
• Finally, we demonstrate that the novel ingredients of ABC allow it to match or exceed PageRank and BookRank in reproducing the empirical distributions of page traffic, link traffic, and of the popularity of session starting pages, while outperforming both PageRank and BookRank in modeling user traffic entropy and size and depth of sessions.

BACKGROUND
There have been many empirical studies of Web traffic patterns. The most common approach is the analysis of Web server logs. These have ranged from small samples of users from a few arbitrarily selected Web server logs [16] to large samples of users from the logs of large organizations [14]. One advantage of this methodology is that it allows us to distinguish individual users though their IP addresses (even if they may be anonymized), thus capturing individual traffic patterns [14]. Conversely, the methodology has the drawback of biasing both the sample of users and the sample of the Web graph being observed based on the choice of target server.
An alternative source of Web traffic data is browser toolbars, which gather traffic information based on the surfing activity of many users. While the population is larger in this scenario, it is still biased by users who have opted to install a particular piece of software. Moreover, traffic information from toolbars is not generally available to researchers. Adar et al. [1] used this approach to study the patterns of revisitation to pages, but did not consider whether pages are revisited within the same session or across different sessions. A related approach is to identify a panel of users based on desired characteristics, then ask them to install tracking software. This eliminates many sources of bias but incurs significant experimental costs. Such an approach has been used to describe the exploratory behavior of Web surfers [4]. These studies did not propose models to explain the observed traffic patterns.
The methodology adopted in the study reported here captures traffic data directly from a running network. This approach was first adopted by Qiu et al. [27], who used captured HTTP packet traces in the UCLA computer science department to investigate how browsing behavior is driven by search engines. Our study relies on a larger sample of users.
One of the important traffic features we study here is the statistical characterization of browsing sessions. A common assumption is that long pauses correspond to breaks between sessions. Based on this assumption, many researchers have relied on timeouts as a way of defining sessions, a technique we have recently found to be flawed [19]. This has led to the definition of time-independent logical sessions, based on the reconstruction of session trees rooted at pages requested without a referrer. The model presented here is in part aimed at explaining the broad distributions of size and depth empirically observed for these logical sessions.
An aspect of Web traffic that has not received much attention in the literature is the role of page content in driving users' browsing patterns. A notable exception is a study of the correlation between changes in page content and revisit patterns [2].
On the modeling side, the most basic notion of Web navigation is that users move erratically, performing a random walk through pages in the Web graph. PageRank [6] is a random walk modified by the process of teleportation (random jumps), modeling how users start new browsing sessions by a Poissonian process with uniformly random starting points. This Markovian process has no memory, no way to backtrack, and no notion of user interests or page content. The stationary distribution of visitation frequency generated by PageRank can be compared with empirical traffic data. We have shown that the fundamental assumptions underlying Page-Rank-uniform link selection, uniform teleportation sources and targets-are all violated by actual user behavior, making PageRank a poor model of actual users [20]. Such results leave open the question of how to design a better Web navigation model. That is the goal of the present paper; we use such a random walk as a null model to evaluate our alternative model.
More realistic models have been introduced in recent years to capture potentially relevant features of real Web browsing behavior, such as the back button [18,5]. There have also been attempts to model the role of the interplay between user interests and page content in shaping browsing patterns. Huberman et al. proposed a model in which pages visited by a user have interest values described by a random walk; the navigation continues as long as the current page has a value above a threshold [15]. This kind of model is closely related to algorithms designed to improve topical crawlers [21,24,25].
We previously proposed a model in which the users maintain a list of bookmarks from which they start new sessions, providing memory of previously visited pages [3]. We called this model BookRank, since the bookmark selection is carried out according to a ranking based on the frequency of visits to each bookmark. This model is able to reproduce a fair number of characteristics observed in empirical traffic data, including the page and link traffic distribu-tions. Unfortunately, BookRank fails to account for features related to the navigation patterns of individual users, such as entropy and session characteristics. This failure is not remedied by the introduction of a back button into the model. In the remainder of this paper, we extend the BookRank model to address these shortcomings.

Data acquisition
The HTTP request data we use in this study was gathered from a dedicated FreeBSD server located in the central routing facility of the Bloomington campus of Indiana University [19]. This system had a 1 Gbps Ethernet port that received a mirror of all outbound network traffic from one of the undergraduate dormitories. This dormitory is home to just over a thousand undergraduates split roughly evenly between men and women. To the best of our knowledge this is the largest population sample whose every click has been recorded and studied over an extended period of time.
To identify individual requests, we first capture only packets destined for TCP port 80. While this does eliminate Web traffic running on non-standard ports, it allows for an improved rate of capture that more than offsets the lost data. We make no attempt to capture or analyze encrypted (HTTPS) traffic using TCP port 443. For each packet we capture, we use a regular expression search to determine whether it contains an HTTP GET request. If we do find a request, we analyze the packet further and log the request, making note of the MAC address of the client, a timestamp, the virtual host and path requested, the referring URL, and a flag indicating whether the user agent matches a mainstream browser. We record the MAC address only in order to distinguish the traffic of individual users. We thus assume that most computers have a single primary user, which is reasonable: most students own computers, and only a few public workstations are available in the dormitory. Furthermore, as long as users do not replace their network interface card, this information remains constant.
The aggregate traffic was low enough to permit full rate of collection without dropping packets. While this collection system offers a rare opportunity to capture the complete browsing activity of a large population, we do recognize some potential disadvantages. Because we do not perform TCP stream reassembly, we can only analyze requests that fit in a single Ethernet frame. The vast majority of requests do so, but some GET-based Web services do generate extremely long URLs. Without stream reassembly, we also cannot log the Web server's response to each request, making us unaware of failed requests and redirects. A user can spoof the HTTP referrer field; we assume that few students do so. Finally, although they are in a residential setting, the students are at an academic institution and represent a biased sample of the population of Web users at large. This is an inevitable consequence of any local study of a global and diverse system such as the Web.
The click data was collected over a period of about two months, from March 5, 2008 through May 3, 2008. This period included a week-long vacation during which no students were present in the building. During the full data collection period, we detected nearly 408 million HTTP requests from a total of 1,083 unique MAC addresses.
Only a minority of HTTP requests reflect an actual human being trying to fetch a Web page for display. We retain only requests that are likely to be for actual Web pages, as opposed to media files, style sheets, Javascript code, images, and so forth. We make this determination based on the extension of the URL requested, which is imprecise but a reasonable heuristic in the absence of access to the MIME type of the server response. We also filtered out a small subset of users with negligible (mostly automated) activity. Finally, we removed some spoofed requests generated by an anonymization service that attempted to obscure traffic to an adult chat site. Privacy concerns and our agreement with the Human Subjects Committee of our institution also obliged us to strip off all identifiable query parameters from the URLs. Applying this anonymization procedure affects roughly one-third of the remaining requests. This procedure means that two URLs with different CGI variables will be treated as the same. While this is a mistaken assumption for sites in which the identity of the page being requested is a query parameter, it helps in the common case that the parameters affect some content within a largely static framework.
Once we have a filtered set of HTTP requests ("clicks"), we organize each user's clicks into a set of sessions. These sessions are not based on a simple timeout threshold; our prior work demonstrates that most statistics of timeout-based sessions are functions of the particular timeout used, which turns out to be arbitrary [19]. Instead, we organize the clicks into tree-based logical sessions using the referrer information associated with each request, according to an algorithm described formally in our previous work [19]. The basic notions are that new sessions are initiated by requests with an empty referrer field; that each request represents a directed edge from a referring URL to a target URL; and that requests are assigned to the session in which their referring URL was most recently requested.
The session trees built in this way offer several advantages. First, they mimic the multitasking behavior of users in the age of tabbed browsing: a user may have several active sessions at a time. Second, the key properties of these session trees, such as size and depth, are relatively insensitive to an additional timeout constraint introduced for the sake of plausibility [19]. In the current analysis, we impose a half-hour timeout as we form the sessions: a click cannot be associated with a session tree that has not received additional requests within thirty minutes.
Most importantly, the tree structure allows us to infer how users backtrack as they browse. Because modern browsers follow sophisticated caching mechanisms to improve performance, unless overridden by HTTP options, a browser will generally not issue another request for a recently accessed page. This prevents us from observing multiple links pointing to the same page (within a single logical session) and gives us no direct way of determining when the user presses the back button. However, session trees allow us to infer information about backwards traffic: if the next request in the tree comes from a URL other than the most recently visited one, the user must have navigated to that page, or opened it in a separate tab.
The dimensions of the resulting data set are shown in Table 1. In § 3.2, we present the most relevant properties of this data for the discussion that follows; more detailed analysis of the empirical sessions can be found in [19].

Data descriptors
Any statistical description strives to achieve a compromise between the need to summarize the behavior of the data and the need to describe such behavior accurately. In the case of many human activities, including those on the Web, we know that the data does not behave in a normal (Gaussian) fashion, but rather fits into heavytailed distributions approximated best by power laws [7,20]. In many cases, the mean and median are not a sufficient description of the data, as shown by a large and diverging variance and heavy skew. The next best description of any quantity is a histogram of its values. We therefore present these distributions in terms of their estimated probability density functions rather than measures of central tendency. To characterize the properties of our traffic data and evaluate the models proposed later in this paper, we focus on the distributions of the six quantities outlined below.
Page traffic The total number of visits to each page. Because of caching mechanisms, the majority of revisits to a page by a single user beyond the first visit within each session will not be represented in the data.
Link traffic The total number of times each link between pages has been traversed by a user, as identified by the referrer and destination URLs in each request. Again, because of caching behavior, we typically observe only the first click to a destination page within each session.
Empty referrer traffic The number of times each page is used to initiate a new session. We assume that a request without a referring page corresponds to the user initiating a new session by using a bookmark, opening a link from another application, or manually entering an address.
Entropy Shannon information entropy. For an individual user j, the entropy is defined as Sj = − i ρij log 2 ρij where ρij is the fraction of visits of user j to site i aggregated across sessions.
Session size The number of unique pages visited in a logical session tree.

Session depth
The maximum tree distance between the starting page of a session and any page visited within the same session. (Recall that session graphs have a tree-like structure because requests that go back to a previously visited page are usually served from the browser cache.) We have already characterized some of these distributions in preliminary work [3,19]. Another feature sometimes used to characterize random browsing behavior is the distribution of return time, which in this case would be the number of clicks between two consecutive visits to the same page by a given user [14,3]. However, cache behavior and overlapping sessions mean that this information cannot be retrieved in a reliable way from the empirical data.

Reference models
To properly analyze these distributions, we compare them with those generated by two reference models based on PageRank-like modified random walkers with teleportation probability pt = 0.15.
To obtain a useful reference model for traffic data that is based on individuals, we imagine a population of PageRank random walkers, as many as the users in our study. The first reference model (PageRank) is illustrated in Fig. 1. Each walker browses for as many sessions as there were empirical sessions for the corresponding real-world user. The PageRank sessions are terminated by the  constant-probability jumps, so the total number of pages visited by a walker may differ from the corresponding user. Teleportation jumps lead to session-starting pages selected uniformly at random. The second reference model (BookRank) is illustrated in Fig. 2. The key realistic ingredient that differentiates this model from Page-Rank is related to memory: agents maintain individual lists of bookmarks that are chosen as teleportation targets based on the number of previous visits. Initially, each agent randomly selects a starting page (node). Then, agents navigate the Web by repeating the following steps: 1. With probability 1−pt, the agent navigates locally, following a link from the present node selected with uniform probability. Unless previously visited, the new node is added to the bookmark list. The frequency of visits is recorded, and the list of bookmarks is kept ranked from most to least visited.
2. Otherwise, with probability pt, the agent teleports (jumps) to a previously visited page (bookmark). The bookmark with rank R is chosen with probability P (R) ∝ R −β .
The above mechanism mimics the use of frequency ranking in various features of modern browsers, such as URL completion in the address bar and suggested starting pages in new windows. The functional form P (R) for the bookmark choice is motivated by data on selection among a ranked list of search results [13].
In our simulations, browsing occurs on scale-free networks with N nodes and degree distribution P (k) ∼ k −γ , generated according to the growth model of Fortunato et al. [29]. We used a large graph with N = 10 7 nodes to ensure that the network would be larger than the number of pages visited in the empirical data (cf. Table 1). We also set γ = 2.1 to match our data set. This graph is constructed with symmetric links to prevent dangling links; as a result, each node's in-degree is equal to its out-degree.
Within a reference model's session, we simulate the browser's cache by recording traffic for links and pages only when the target page has not been previously visited in the same session. This way we can measure in the models the number of unique pages visited   in a session, which we can compare with the empirical session size. We assume that that cached pages are reset between sessions.

Data analysis
We first consider the aggregate distribution of traffic received by individual pages, as shown in Fig. 3. The empirical data show a very broad power-law distribution for page traffic, P (T ) ∼ T −α , with exponent α ≈ 1.75, 1 which is consistent with our prior results for host-level traffic [20,19].
Theoretical arguments [26] suggest that PageRank should behave in a similar fashion. If we disregard teleportation, a node of in-degree k may expect a visit if one of its neighbors has been visited in the previous step. The traffic it will receive will be therefore proportional to its degree, if no degree-degree correlations are present in the graph. This intuition, as well as prior empirical results [20], lead us to expect that PageRank's prediction of the distribution of traffic received by a Web page is described by a power law P (T ) ∼ T −α where α ≈ 2.1 is the same exponent observed in the distribution of the in-degree [7,12]. Indeed this is consistent with the distribution generated by the PageRank reference model in Fig. 3. On the other hand, the traffic generated by BookRank is biased toward previously visited pages (bookmarks), and therefore has a broader distribution (by three orders of magnitude) in better agreement with the empirical data, as shown in Fig. 3.
The distribution of weights ω across links between pages allows us to consider the diversity of traffic crossing each hyperlink in the Web graph. In Fig. 4, we compare the distribution of link traffic resulting from the reference models with that from the empirical data. The data reveals a very wide power law for P (ω) with degree 1.9. This is consistent with our prior results for host-level traffic [20].
The comparison with PageRank and BookRank in Fig. 4 is a vivid illustration of the diversity of links when we consider their probability of actually being clicked. A rough argument may again help to make sense of the PageRank reference model's poor performance at reproducing the data. If we disregard teleportation, the traffic to a page is roughly proportional to the page in-degree. The traffic expected on a link would be thus proportional to the traffic to the originating page and inversely proportional to the out-degree of the page if we assume that links are chosen uniformly at random. Since a node's in-degree and out-degree are equal in our simulated graphs, this would lead to a link traffic that is independent of the degree and therefore essentially constant for all links. This is reflected in the quickly decaying distribution of link traffic for PageRank. In the case of BookRank, the stronger heterogeneity in the probability of visiting pages is reflected in a heterogeneous choice of links, resulting in a broad distribution that fits the empirical data well as shown in Fig. 4. Our empirical data in Fig. 5 show clearly that all pages are not equally likely to be chosen as the starting point of a browsing session. Their popularity as starting points is roughly distributed as a power law with an exponent close to 1.8 (consistent with prior results for host-level traffic [20]), implying a diverging variance and mean when the number of sessions considered increases. While not unexpected from a qualitative point of view, this demonstrates how off the mark is one of the basic hypotheses underlying the Page-Rank class of browsing processes, namely uniform teleportation. PageRank assumes a uniform probability for a page to be chosen as a starting point, and its failure to reproduce the empirical data is evident in Fig. 5. The bookmarking mechanism, on the other hand, captures well the non-uniform probability of starting pages, so that the distribution generated by BookRank is a good match to the empirical data, as shown in Fig. 5.
We now turn from the aggregate properties of the system and attempt to characterize individual users. The simplest hypothesis would be that the broad distributions characterizing aggregate user behavior are a reflection of extreme variability within the traffic generated by single users, thus concluding that there is no such thing as a "typical" user from the point of view of traffic generated. To capture how diverse is the behavior in a group of users, we adopt Shannon's information entropy of a user as defined above. Entropy directly measures the focus of a user's interests, offering a better probe into single user behavior than, for instance, the   Given an arbitrary number of visits Nv, the entropy is maximum (S = Nv log(Nv)) when Nv pages are visited once, and minimum (S = 0) when all visits have been paid to a single page. The distribution of entropy across users is shown in Fig. 6. We observe that the reference PageRank model produces higher entropy than observed in the empirical data. One can interpret this by the way a PageRank walker picks starting pages with uniform probability, while a real user is more likely to start from a previously visited page, and therefore to revisit neighboring pages. BookRank is more similar to such repetitive behavior, and indeed we observe lower entropy values in Fig. 6. However, BookRank underestimates the entropy as well as its variability across users.
Finally, we can consider the distributions that characterize logical sessions, namely the size (number of unique pages) and depth (distance from a session's starting page) distributions. Figs. 7 and 8 show that both empirical distributions are rather broad, spanning three orders of magnitude, which is a surprisingly large proportion of very long sessions. In contrast, both PageRank and BookRank reference models generate very short sessions. The probabilistic teleportation mechanism that determines when a PageRank walker starts a new session is incapable of capturing broadly distributed session sizes. In fact, session size is upper-bounded by the length (number of clicks) of a session, which exhibits a narrow, exponential distribution P ( ) ∼ (1 − pt) . Note that the exponentially short sessions are not inconsistent with the high entropy of Page-Rank walkers (Fig. 6), which is a result of the frequent jumps to random targets rather than the browsing behavior.

ABC MODEL
The empirical analysis in the previous section demonstrates that a more sophisticated model of user behavior is needed to capture individual navigation patterns. We build upon the BookRank model by adding two additional ingredients.
First, we provide agents with a back button. A backtracking mechanism is needed to capture the tree-like structure of sessions (see also top row of Fig. 9). Our data also indicates that the incoming and outgoing traffic of a site are seldom equal. Indeed, the ratio between incoming and outgoing clicks is distributed over many orders of magnitude [20]. This violation of flow conservation cannot be explained by teleportation alone, demonstrating that users' browsing sessions have many branches. Finally, our prior results show that the average node-to-depth ratio of session trees is almost two. All of these observations are consistent with the use of tabs and the back button. Other studies have shown that the back button is used frequently [9,30]. We therefore use the back button to model any branching behavior.
The second ingredient has to do with the fact that the BookRank model fails to predict individual statistics: all agents are identical, session size has a narrow, exponential distribution, and the comparison with the empirical entropy distribution is unsatisfactory. In the real world, the duration of a session depends on the intentions (goals) and interests of a user; different users have different interests. Visiting relevant pages, those whose topics match the user's interests, will lead to more clicks and thus longer sessions. We therefore introduce the elements of different agents with distinct interests and page topicality into the model. The idea is that an agent spends some attention when navigating to a new page, and attention is gained when visiting pages whose topics match the user's interests. To model this process, we imagine that each agent stores some "energy" (units of attention) while browsing. Visiting a new page incurs a higher energy cost than going back to a previously visited page. Known pages yield no energy, while unseen pages may increase the energy store by some random amount that depends on the page's relevance to the agent. Agents continue to browse until they run out of energy, whereupon they start a new session.
We call the resulting model ABC for its main ingredients: agents, bookmarks and clicks. Clicks are driven by the topicality of pages and agent interests, in a way that is in part inspired by the InfoSpiders algorithms for topical crawlers [21,24,25]. InfoSpiders were designed to explore the Web graph in an adaptive and intelligent fashion, driven by the similarity between search topics and page content. Better matches led to more energy and more exploration of local link neighborhoods. Irrelevant pages led to agents running out of energy and dying, so that resources would be allocated to more promising neighborhoods. In ABC, this idea is used to model browsing behavior.
The ABC model is illustrated in Fig. 10. Each agent starts at a random page with an initial amount of energy E0. Then, for each time step: 1. If E ≤ 0, the agent starts a new session by teleporting to a bookmark chosen as in BookRank.
2. Otherwise, if E > 0, the user continues the current session, following a link from the present node. There are two alternatives: (a) With probability p b , the back button is used, leading back to the previous page. The agent's energy is decreased by a fixed cost c b . (b) Otherwise, with probability 1 − p b , a forward link is clicked with uniform probability. The agent's energy is updated to E − c f + ∆ where c f is a fixed cost and ∆ is a stochastic value representing the new page's relevance to the user. As in BookRank, the bookmark list is updated with new pages and ranked by visit frequency.
The dynamic variable ∆ in the ABC model is a measure of relevance of a page to a user's interests. The simplest way to model rel- evance is by a random variable, for example drawn from a Gaussian distribution. In this case the amount of stored energy behaves as a random walk. It has been shown that the session duration (number of clicks until the random walk reaches E = 0) has a power-law tail P ( ) ∼ − 3 2 [15]. However, our empirical results suggest a larger exponent [19]. More importantly, we know from empirical studies that the content similarity between two Web pages is correlated with their distance in the link graph, and so is the probability that a page is relevant with respect to some given topic [10,23,22]. Therefore, two neighbor pages are likely to be related topically, and the relevance of a page t to a user is related to the relevance of a page r that links to t. To capture such topical locality, we introduce correlations between the ∆ values of consecutively visited pages. For the starting page we use an initial value ∆0 = 1. Then, when a page t is visited for the first time in a given session, ∆t is determined by where r is the referrer page, is a random variable uniformly distributed in [−η, η] and η is a parameter controlling the degree of topical locality. In a new session we assume a page can again be interesting and thus provide the agent with energy, even if it was visited in a previous session. However, the same page will yield different energy in different sessions, based on changing user interests.

Simulation of ABC model
We ran two sets of simulations of the ABC model, in which agents navigate two distinct scale-free graphs. One (G1) is the artificial network discussed in § 3.3. Recall that N = 10 7 nodes and the degree distribution is a power law with exponent γ = 2.1 to match our data set. The second graph (G2) is derived from an independent, empirical, anonymous traffic data set. The data is obtained by extracting the largest strongly connected component from a traffic network generated by the entire Indiana University system population (about 100,000 people) [20]. This way there are no dangling links, but the nodes correspond to actual visited pages and the edges to actual traversed links. G2 is based on three weeks of traffic in November 2009; it has N = 8.14 × 10 6 nodes and the same degree distribution with exponent γ ≈ 2.1.
Within each session we simulate the browser's cache as discussed in § 3.3 so that we can measure the number of unique pages visited by the model agents and compare it with the empirical session size.
The proposed models have various parameters. In prior work [29], we have shown that the distribution of traffic with empty referrer generated by our models is related to the parameter β (cf. BookRank description in § 3.3). Namely, the distribution is well approximated by a power law P (T0) ∼ T −α 0 , where α = 1 + 1/β. To match the empirical exponent α ≈ 1.75 we set the parameter β = 1/(α − 1) = 1.33. We also fit the back button probability p b = 0.5 from the data.
The ABC model contains a few additional free parameters: the initial energy E0, the forward and backward costs c f and c b , and the topical locality parameter η. The initial energy and the costs are closely related, and together they control session durations. We therefore set E0 = 0.5 arbitrarily and use an energy balance argument to find suitable values of the costs. Empirically, the average session size is close to two pages. The net loss per click of an is the expected value of the energy from a new page. By set-  ting c f = 1 and c b = 0.5, we obtain an expected session size 1 − (1 − p b )E0/δE = 2 (counting the initial page). In general, higher costs lead to shorter sessions and lower entropy. We ran a number of simulations to explore the sensitivity of the model to the parameter η, settling on η = 0.15. Smaller values mean that all pages have similar relevance, and the session size and depth distributions become too narrow. Larger values imply more noise (absence of topical locality), and the session distributions become too broad. The results shown below refer to this combination of parameters.
The number of users in the simulation, and the number of sessions for each user, are taken from the empirical data. Because the model is computationally intensive, we partitioned the simulated users into work queues of roughly equal session counts, which we executed in parallel on a high-performance computing cluster.

Comparison of model with empirical data
The simulations of the ABC model users generate session trees that can be compared visually to those in the empirical data, as shown in Fig. 9. For a more quantitative evaluation of our model, we compare its results with empirical findings described in § 3. For each of the distributions discussed earlier, we also compare ABC with the reference BookRank model. The latter is simulated on the artificial G1 network.
A first aspect to check is whether the model is able to reproduce the general features of the traffic distributions. In Fig. 11 we plot the number of visits received by each page. Agreement between the ABC model and data is as good as or better than for the BookRank reference model. Similarly, the distributions of link traffic (Fig. 12) and teleportation traffic (Fig. 13) show that the ABC model reproduces the empirical data as accurately as BookRank.
The good agreement between both BookRank and ABC models and the data provides further support for our hypothesis that the rank-based bookmark choice is a sound cognitive mechanism to capture session behavior in Web browsing.
Let us now consider how our model captures the behavior of single users. The entropy distribution across users is shown in Fig. 14, where the model predictions are compared with the distribution found in the empirical data. The ABC model yields entropy distributions that are somewhat sensitive to the underlying network, but that in any case fit the empirical entropy data much better than BookRank, in terms of both the location of the peak and the variability across users. This result suggests that bookmark memory, back button, and topicality are crucial ingredients in explaining the focused habits of real users.
Having characterized traffic patterns from aggregating across user sessions, we can study the sessions one by one and analyze their statistical properties. In Fig. 15, we show the distribution of session size as generated by the ABC model. The user interests and topical locality ingredients account for the broad distribution of session size, capturing that of the empirical data much better that the short sessions generated by the BookRank reference model. Agents visiting relevant pages tend to keep browsing, and relevant pages tend to lead to other interesting pages, explaining the longer sessions. We argue that the diversity apparent in the aggregate measures of traffic is a consequence of this diversity of individual interests rather than the behavior of extremely eclectic users who visit a wide variety of Web sites -as shown by the narrow distribution of entropy.
The entropy distribution discussed above depends not only on session length, but also on how far each user navigates away from the initial bookmark where a session is initiated. One way of analyzing this is by the distribution of session depth, as shown in Fig. 16. The agreement between the empirical data and the ABC model is excellent and significantly better than the one observed with the BookRank baseline. Once again topicality is shown to be a key ingredient to understand real user behavior on the Web.

CONCLUSIONS
Several previous studies have shown that memoryless Markovian processes, such as PageRank, cannot explain many patterns observed in real Web browsing. In particular, the diversity of session starting points, the global diversity on link traffic, and the heterogeneity of session sizes. The picture is further complicated by  the fact that, despite such diverse aggregate measurements, individual behaviors are quite focused. These observations call for a non-Markovian agent-based model that can help explain the empirical data by taking into account several realistic browsing behaviors. Here we proposed three novel ingredients for such a model. First, agents maintain individual lists of bookmarks (a memory mechanism) that are used as teleportation targets. Second, agents have access to a back button (a branching mechanism) that also allows to reproduce tabbed browsing behavior. Finally, agents have topical interest that are matched by page content, modulating the probability that an agent continues to browse or starts a new session and thus allowing to capture heterogeneous session sizes.
We have shown that the resulting ABC model is capable of reproducing with remarkable accuracy the aggregate traffic patterns we observe in our empirical data. More importantly, our model offers the first account of a mechanism that can generate key properties of logical sessions. This allows us to argue that the diversity apparent in page, link, and bookmark traffic is a consequence of the diversity of individual interests rather than the behavior of very eclectic users. Our model is able to capture, for the first time, the extreme heterogeneity of aggregate traffic measurements while explaining the narrowly focused browsing patterns of individual users.
Of course, the ABC model is more complex than prior models such as PageRank or even BookRank. However, its greater predictive power suggests that bookmarks, tabbed browsing, and topicality are salient features in interpreting how we browse the Web. In addition to the descriptive and explanatory power of an agentbased model with these ingredients, our results may lead the way to more sophisticated, realistic, and hence more effective ranking and crawling algorithms.
The ABC model relies on several key parameters, and while we have attempted to make reasonable, realistic choices for some of these parameters and explored the sensitivity of our model with re-spect to some others, further work is needed to achieve a complete picture of the combined effect of the multiple parameters. We already know, for example, that some parameters such as network size, costs, and topical locality play a key role in modulating the balance between individual diversity (entropy) and session size.
While, in its current incarnation, the ABC model is a clear step in the right direction, it still shares some of the limitations present in previous efforts. The most notable example is the uniform choice among outgoing links from a page, which may be responsible for the imperfect match between the individual entropy values of our model agents and those of actual users.
Future work can also explore intrinsic, node-dependent jump probabilities to model the varying intrinsic relevance that users attribute to sites; for example, well-known sites such as CNN or Wikipedia are likely to be seen as more reliable or credible than unknown personal blogs. Restrictions on the subset of nodes reachable by each user, in the form of disconnected components for individual sessions, can be used to model different areas of interest.


Improving Corpus Comparability for Bilingual Lexicon Extraction from Comparable Corpora

Previous work on bilingual lexicon extraction from comparable corpora aimed at finding a good representation for the usage patterns of source and target words and at comparing these patterns efficiently. In this paper, we try to work it out in another way: improving the quality of the comparable corpus from which the bilingual lexicon has to be extracted. To do so, we propose a measure of comparability and a strategy to improve the quality of a given corpus through an iterative construction process. Our approach, being general, can be used with any existing bilingual lexicon extraction method. We show here that it leads to a significant improvement over standard bilingual lexicon extraction methods.

Introduction
Bilingual dictionaries are an essential resource in many multilingual natural language processing (NLP) tasks such as machine translation (Och and Ney, 2003) and cross-language information retrieval (CLIR) (Ballesteros and Croft, 1997). Hand-coded dictionaries are of high quality, but expensive to build and researchers have tried, since the end of the 1980s, to automatically extract bilingual lexicons from parallel corpora (see (Chen, 1993;Kay and Röscheisen, 1993;Melamed, 1997a;Melamed, 1997b) for early work). Parallel corpora are however difficult to get at in several domains, and the majority of bilingual collections are comparable and not parallel. Due to their low cost of acquisition, sev-eral researchers have tried to exploit such comparable corpora for bilingual lexicon extraction (Fung and McKeown, 1997;Fung and Yee, 1998;Rapp, 1999;Déjean et al., 2002;Gaussier et al., 2004;Robitaille et al., 2006;Morin et al., 2007;Yu and Tsujii, 2009). The notion of comparability is however a loose one, and comparable corpora range from lowly comparable ones to highly comparable ones and parallel ones. For data-driven NLP techniques, using better corpora often leads to better results, a fact which should be true for the task of bilingual lexicon extraction. This point has largely been ignored in previous work on the subject. In this paper, we develop a well-founded strategy to improve the quality of a comparable corpus, so as to improve in turn the quality of the bilingual lexicon extracted. To do so, we first propose a measure of comparability which we then use in a method to improve the quality of the existing corpus.
The remainder of the paper is organized as follows: Section 2 introduces the experimental materials used for the different evaluations; comparability measures are then presented and evaluated in Section 3; in Section 4, we detail and evaluate a strategy to improve the quality of a given corpus while preserving its vocabulary; the method used for bilingual lexicon extraction is then described and evaluated in Section 5. Section 6 is then devoted to a discussion, prior to the conclusion given in Section 7.

Experimental Materials
For the experiments reported here, several corpora were used: the parallel English-French Europarl corpus (Koehn, 2005), the TREC (http://trec.nist.gov/) Associated Press corpus (AP, English) and the corpora used in the multilingual track of CLEF (http://www.clefcampaign.org) which includes the Los Angeles Times (LAT94, English), Glasgow Herald (GH95, English), Le Monde (MON94, French), SDA French 94 (SDA94, French) and SDA French 95 (SDA95, French). In addition to these existing corpora, two monolingual corpora from the Wikipedia dump 1 were built. For English, all the articles below the root category Society with a depth less than 4 2 were retained. For French, all the articles with a depth less than 7 below the category Société are extracted. As a result, the English corpus Wiki-En consists of 367,918 documents and the French one Wiki-Fr consists of 378,297 documents.
The bilingual dictionary used in our experiments is constructed from an online dictionary. It consists of 33,372 distinct English words and 27,733 distinct French words, which constitutes 75,845 translation pairs. Standard preprocessing steps: tokenization, POS-tagging and lemmatization are performed on all the linguistic resources. We will directly work on lemmatized forms of content words (nouns, verbs, adjectives, adverbs).

Measuring Comparability
As far as we can tell, there are no practical measures with which we can judge the degree of comparability of a bilingual corpus. In this paper, we propose a comparability measure based on the expectation of finding the translation for each word in the corpus. The measure is light-weighted and does not depend on complex resources like the machine translation system. For convenience, the following discussions will be made in the context of the English-French comparable corpus.

The Comparability Measure
For the comparable corpus C, if we consider the translation process from the English part C e to the 1 The Wikipedia dump files can be downloaded at http://download.wikimedia.org. In this paper, we use the English dump file on July 13, 2009 and the French dump file on July 7, 2009. 2 There are several cycles in the category tree of Wikipedia. It is thus necessary to define a threshold on the depth to make the iterative process feasible.
French part C f , a comparability measure M ef can be defined on the basis of the expectation of finding, for each English word w e in the vocabulary C v e of C e , its translation in the vocabulary C v f of C f . Let σ be a function indicating whether a translation from the translation set T w of w is found in the vocabulary C v of a corpus C, i.e.: M ef is then defined as: where D v e is the English part of a given, independent bilingual dictionary D, and where the last equality is based on the fact that, the comparable corpus and the bilingual dictionary being independent of one another, the probability of finding the translation in C v f of a word w is the same for w is in C v e ∩ D v e and in C v e \D v e 3 . Furthermore, the presence of common words suggests that one should rely on a presence/absence criterion rather than on the number of occurrences to avoid a bias towards common words. Given the natural language text, our evaluation will show that the simple presence/absence criterion can perform very well. This leads to P r(w ∈ C v e ) = 1/|C v e |, and finally to: This formula shows that M ef is actually the proportion of English words translated in the French part of the comparable corpus. Similarly, the counterpart of M ef , M f e , is defined as: and measures the proportion of French words in C v f translated in the English part of the comparable corpus. A symmetric version of these measures is obtained by considering the proportion of the words (both English and French) for which a translation can be found in the corpus: We now present an evaluation of these measures on artificial test corpora.

Validation
In order to test the comparability measures, we developed gold-standard comparability scores from the Europarl and AP corpora. We start from the parallel corpus, Europarl, of which we degrade the comparability by gradually importing some documents from either Europarl or AP. Three groups (G a , G b , G c ) of comparable corpora are built in this fashion. Each group consists of test corpora with a gold-standard comparability ranging, arbitrarily, from 0 to 1 and corresponding to the proportion of documents in "parallel" translation. The first group G a is built from Europarl only. First, the Europarl corpus is split into 10 equal parts, leading to 10 parallel corpora (P 1 , P 2 , . . . , P 10 ) with a gold-standard comparability arbitrarily set to 1. Then for each parallel corpus, e.g. P i , we replace a certain proportion p of the English part with documents of the same size from another parallel corpus P j (j = i), producing the new corpus P i with less comparability which is the gold-standard comparability 1 − p. For each P i , as p increases, we obtain several comparable corpora with a decreasing gold-standard comparability score. All the P i and their descendant corpora constitute the group G a . The only difference between G b and G a is that, in G b , the replacement in P i is done with documents from the AP corpus and not from Europarl. In G c , we start with 10 final, comparable corpora P i from G a . These corpora have a gold-standard comparability of 0 in G a , and of 1 in G c . Then each P i is further degraded by replacing certain portions with documents from the AP corpus. We then computed, for each comparable corpus in each group, its comparability according to one of the comparability measures. Figure 1 plots the measure M for ten comparable corpora and their descendants from G c , according to their gold-standard comparability scores. As one can note, the measure M is able to capture almost all the differences in comparability and is strongly correlated with the gold-standard. The correlation between the different measures and the goldstandard is finally computed with Pearson correlation coefficient. The results obtained are listed in Table 1. As one can note, M f e performs worst among the three measures, the reason being that the process to construct G b and G c yields unbalanced bilingual corpora, the English section being larger than the French one. Translations of French words are still likely to be found in the English corpus, even though the corpora are not comparable. On all the 3 groups, M performs best and correlates very well with the gold standard, meaning that M was able to capture all the differences in comparability artificially introduced in the degradation process we have considered. This is the measure we will retain in the following parts.  Having established a measure for the degree of comparability of bilingual corpora, we now turn to the problem of improving the quality of comparable corpora.

Improving Corpus Quality
We here try to improve the quality of a given corpus C, which we will refer to as the base corpus, by extracting the highly comparable subpart C H which is above a certain degree of comparability η (Step 1), and by enriching the lowly comparable part C L with texts from other sources (Step 2). As we are interested in extracting information related to the vocabulary of the base corpus, we want the newly built corpus to contain a substantial part of the base corpus. This can be achieved by preserving in Step 1 as many documents from the base corpus as possible (e.g. by considering low values of η), and by using in step 2 sources close to the base corpus.

Step 1: Extracting C H
The strategy consisting of building all the possible sub-corpora of a given size from a given comparable corpora is not realistic as soon as the number of documents making up the corpora is larger than a few thousands. In such cases, better ways for extracting subparts have to be designed. The strategy we have adopted here aims at efficiently extracting a subpart of C above a certain degree of comparability and is based on the following property. Property 1. Let d 1 e and d 2 e (resp. d 1 f and d 2 f ) be two English (resp. French) documents from a bilingual corpus C. We consider, as before, that the bilingual dictionary D is independent from C.
. One can show, by exploiting condition (ii), that: and similarly that: Then exploiting condition (i), and the independence between the corpus and the dictionary, one arrives at: Property 1 shows that one can incrementally extract from a bilingual corpus a subpart with a guaranteed minimum degree of comparability η by iteratively adding new elements, provided (a) that the new elements have a degree of comparability of at least η and (b) that they are less comparable than the currently extracted subpart (conditions (ii)). This strategy is described in Algorithm 1. Since the degree of comparability is always above a certain threshold and since the new documents selected (d 2 e , d 2 f ) are the most comparable among the remaining documents, condition (i) is likely to be satisfied, as this condition states that the increase in the vocabulary from the second documents to the union of the two is the same in both languages. Similarly, considering new elements by decreasing comparability scores is a necessary step for the satisfaction of condition (ii), which states that the current subpart should be uniformly more comparable than the element to be added. Hence, the conditions for property 1 to hold are met in Algorithm 1, which finally yields a corpus with a degree of comparability of at least η.

4.2
Step 2: Enriching C L This step tries to absorb knowledge from other resources, which will be called external corpus,

Algorithm 1 Input:
English document set C d e of C French document set C d f of C Threshold η Output: C H , consisting of the English document set S e and the French document set S f 1: Initialize S e = ∅, S f = ∅, temp = 0; 2: repeat 3: if temp ≥ η then 6: Add d e into S e and add d f into S f ; 7: to enrich the lowly comparable part C L which is the left part in C during the creation of C H . One choice for obtaining the external corpus C T is to fetch documents which are likely to be comparable from the Internet. In this case, we first extract representative words for each document in C L , translate them using the bilingual dictionary and retrieve associated documents via a search engine. An alternative approach is of course to use existing bilingual corpora. Once C T has been constructed, the lowly comparable part C L can be enriched in exactly the same way as in section 4.1: First, Algorithm 1 is used on the English part of C L and the French part of C T to get the highquality document pairs. Then the French part of C L is enriched with the English part of C T by the same algorithm. All the high-quality document pairs are then added to C H to constitute the final result.

Validation
We use here GH95 and SDA95 as the base corpus C 0 . In order to illustrate that the efficiency of the proposed algorithm is not confined to a specific external resource, we consider two external resources: (a) C 1 T made of LAT94, MON94 and SDA94, and (b) C 2 T consisting of Wiki-En and Wiki-Fr. The number of documents in all the corpora after elimination of short documents (< 30 words) is listed in Table 2.  For the extraction of the highly comparable part C H from the base corpus C 0 , we set η to 0.3 so as to extract a substantial subpart of C 0 . After this step, corresponding to Algorithm 1, we have 20,124 English-French document pairs in C H . The second step is to enrich the lowly comparable part C L of the base corpus documents from the external resources C 1 T and C 2 T . The final corpora we obtain consist of 46,996 document pairs for C 1 (with C 1 T ) and of 54,402 document pairs for C 2 (with C 2 T ), size similar to the one of C 0 . The proportion of documents (columns "D-e" and "Df"), sentences (columns "S-e" and "S-f") and vocabulary (columns "V-e" and "V-f") of C 0 found in C 1 and C 2 is given in Table 3. As one can note, the final corpora obtained through the method presented above preserve most of the information from the base corpus. Especially for the vocabulary, the final corpora cover nearly all the vocabulary of the base corpus. Considering the comparability scores, the comparability of C 1 is 0.912 and the one of C 2 is 0.916. Both of them are more comparable than the base corpus of which the comparability is 0.882.
From these results of the intrinsic evaluation, one can conclude that the strategy developed to improve the corpus quality while preserving most of its information is efficient: The corpora obtained here, C 1 and C 2 , are more comparable than the base corpus C 0 and preserve most of its information. We now turn to the problem of extracting bilingual lexicons from these corpora.

Bilingual Lexicon Extraction
Following standard practice in bilingual lexicon extraction from comparable corpora, we rely on the approach proposed by Fung and Yee (1998). In this approach, each word w is represented as a

Using Algorithm 1 pseudo-Alignments
The process we have defined in the previous section to improve the quality of a given corpus while preserving its vocabulary makes use of highly comparable document pairs, and thus provides some loose alignments between the two corpora. One can thus try to leverage the above approach to bilingual lexicon extraction by re-weighting s c (w e , w f ) by a quantity which is large if w e and w f appear in many document pairs with a high comparability score, and small otherwise. In this section, we can not use the alignments in algorithm 1 directly because the alignments in the comparable corpus should not be 1 to 1 and we did not try to find the precise 1 to 1 alignments in algorithm 1. Let η be the threshold used in algorithm 1 to construct the improved corpus and let φ(d e , d f ) be defined as: Let H e (resp. H f ) be the set of documents containing word w e (resp. w f ). We define the joint probability of w e and w f as being proportional to the number of comparable document pairs they belong to, where two documents are comparable if their comparability score is above η, that is: The marginal probability p(w e ) can then be written as: Assuming that all d f in C d f have roughly the same vocabulary size and all d e have the same number of comparable counterparts in C d f , then the marginal probability can be simplified as: p(w e ) ∝ |H e |. By resorting to the exponential of the point-wise mutual information, one finally obtains the following weight: which has the desired property: It is large if the two words appear in comparable document pairs more often than chance would predict, and small otherwise. We thus obtain the revised similarity score for w e and w f :

Validation
In order to measure the performance of the bilingual lexicon extraction method presented above, we divided the original dictionary into 2 parts: 10% of the English words (3,338 words) together with their translations are randomly chosen and used as the evaluation set, the remaining words (30,034 words) being used to compute context vectors and similarity between them. In this study, the weight a(w c ) used in the context vectors (see above) are taken to be the tf-idf score of w c : a(w c ) = tf-idf(w c ). English words not present in C v e or with no translation in C v f are excluded from the evaluation set. For each English word in the evaluation set, all the French words in C v f are then ranked according to their similarity with the English word (using either equation 1 or 2). To evaluate the quality of the lexicons extracted, we first retain for each English word its N first translations, and then measure the precision of the lists obtained, which amounts in this case to the proportion of lists containing the correct translation (in case of multiple translations, a list is deemed to contain the correct translation as soon as one of the possible translations is present). This evaluation procedure has been used in previous work (e.g. (Gaussier et al., 2004)) and is now standard for the evaluation of lexicons extracted from comparable corpora. In this study, N is set to 20. Furthermore, several studies have shown that it is easier to find the correct translations for frequent words than for infrequent ones (Pekar et al., 2006). To take this fact into account, we distinguished different frequency ranges to assess the validity of our approach for all frequency ranges. Words with frequency less than 100 are defined as low-frequency words (W L ), whereas words with frequency larger than 400 are highfrequency words (W H ), and words with frequency in between are medium-frequency words (W M ).
We then tested the standard method based on the cosine similarity (equation 1) on the corpora C 0 , C H , C H , C 1 and C 2 . The results obtained are displayed in Table 4, and correspond to columns 2-6. They show that the standard approach performs significantly better on the improved corpora C 1 /C 2 than on the base corpus C 0 . The overall precision is increased by 5.3% on C 1 (corresponding to a relative increase of 26%) and 9.5% on C 2 (corresponding to a relative increase of 51%), even though the low-frequency words, which dominate the overall precision, account for a higher proportion in C 1 (61.3%) and C 2 (61.3%) than in C 0 (56.2%). For the medium and high frequency words, the precision is increased by over 11% on C 1 and 16% on C 2 . As pointed out in other studies, the performance for the low-frequency words is usually bad due to the lack of context information. This explains the relatively small improvement obtained here (only 2.2% on C 1 and 6.7% on C 2 ). It should also be noticed that the performance of the standard approach is better on C 2 than on C 1 , which may be due to the fact that C 2 is slightly larger than C 1 and thus provides more information or to the actual content of these corpora. Lastly, if we consider the results on the corpus C H which is produced by only choosing the highly comparable part from C 0 , the overall precision is increased by only 1.9%, which might come from the fact that the size of C H is less than half the size of C 0 . We also notice the better results on C H than on C H of the same size which consists of randomly choosing documents from C 0 .
The results obtained with the refined approach making use of the comparable document pairs found in the improved corpus (equation 2) are also displayed in Table 4 (columns "C 1 new" and "C 2 new"). From these results, one can see that the overall precision is further improved by 2.0% on C 1 and 2.3% on C 2 , compared with the standard approach. For all the low, medium and high-frequency words, the precision has been improved, which demonstrates that the information obtained through the corpus enrichment process contributes to improve the quality of the extracted bilingual lexicons. Compared with the original base corpus C 0 , the overall improvement of the precision on both C 1 and C 2 with the refined approach is significant and important (respectively corresponding to a relative improvement of 35% and 62%), which also demonstrates that the efficiency of the refined approach is not confined to a specific external corpus.

Discussion
It is in a way useless to deploy bilingual lexicon extraction techniques if translation equivalents are not present in the corpus. This simple fact is at the basis of our approach which consists in constructing comparable corpora close to the original corpus and which are more likely to contain translation equivalents as they have a guaranteed degree of comparability. The pseudo-alignments identified in the construction process are then used to leverage state-of-the-art bilingual lexicon extraction methods. This approach to bilingual lexicon extraction from comparable corpora radically differs, to our knowledge, from previous approaches   (Fung and Yee, 1998) and (Rapp, 1999). For example, the method developed in (Déjean et al., 2002) and (Chiao and Zweigenbaum, 2002) involves a representation of dictionary entries with context vectors onto which new words are mapped. Pekar et al. (2006) smooth the context vectors used in the standard approach in order to better deal with low frequency words. A nice geometric interpretation of these processes is proposed in (Gaussier et al., 2004), which furthermore introduces variants based on Fisher kernels, Canonical Correlation Analysis and a combination of them, leading to an improvement of the F1-score of 2% (from 0.14 to 0.16) when considering the top 20 candidates. In contrast, the approach we have developed yields an improvement of 7% (from 0.13 to 0.20) of the F-1 score on C 2 , again considering the top 20 candidates. More important, however, is the fact that the approach we have developed can be used in conjunction with any existing bilingual extraction method, as the strategies for improving the corpus quality and the re-weighting formula (equation 2) are general. We will assess in the future whether substantial gains are also attained with other methods.
Some studies have tried to extract subparts of comparable corpora to complement existing parallel corpora. Munteanu (2004) thus developed a maximum entropy classifier aiming at extracting those sentence pairs which can be deemed parallel. The step for choosing similar document pairs in this work resembles some of our steps. However their work focuses on high quality and specific documents pairs, as opposed to the entire corpus of guaranteed quality we want to build. In this latter case, the cross-interaction between documents impacts the overall comparability score, and new methods, as the one we have introduced, need to be proposed. Similarly, Munteanu and Marcu (2006) propose a method to extract subsentential fragments from non-parallel corpora. Again, the targeted elements are very specific (parallel sentences or sub-sentences) and limited, and the focus is put on a few sentences which can be considered parallel. As already mentioned, we rather focus here on building a new corpus which preserves most of the information in the original corpus. The construction process we have presented is theoretically justified and allows one to preserve ca. 95% of the original vocabulary.

Conclusion
We have first introduced in this paper a comparability measure based on the expectation of finding translation word pairs in the corpus. We have then designed a strategy to construct an improved comparable corpus by (a) extracting a subpart of the original corpus with a guaranteed comparability level, and (b) by completing the remaining subpart with external resources, in our case other existing bilingual corpora. We have then shown how the information obtained during the construction process could be used to improve state-ofthe-art bilingual lexicon extraction methods. We have furthermore assessed the various steps of our approach and shown: (a) that the comparability measure we introduced captures variations in the degree of comparability between corpora, (b) that the construction process we introduced leads to an improved corpus preserving most of the original vocabulary, and (c) that the use of pseudo-alignments through simple re-weighting yields bilingual lexicons of higher quality.