Kristof Ostir

Ziga Kokalj

Laure Nuninger

CONFIDENCE MAPS: A TOOL TO EVALUATE DATA'S RELEVANCE IN SPATIAL ANALYSIS

Keywords: Krištof Oštir, Ziga Kokalj, Laure confidence maps, spatial analysis, modelling. Confidence

INTRODUCTION

Inventory data used in archaeology are often incomplete and heterogeneous, making their interpretation, dating and localization a difficult task. They represent in fact a sample of a more complex reality. The analysis of archaeological data using spatial analysis tools therefore requires great caution in the interpretation that is drawn from them. The issue is to avoid the identification of spatial trends that are just a consequence of the degree of archaeological investigation. In the framework of the ArchaeDyn program, a method has been proposed to evaluate and give a spatial insight on the heterogeneity in archaeological inventories. ArchaeDyn is combining the efforts of several archaeologists working on various topics, ranging from the diffusion of manufactured objects in pre-and protohistorical times, to the use of land through the study of settlements, parcels and manuring during the antiquity (Nuninger and Favory 2008). A great diversity in analysis scales and studied objects led to different inventory protocols such as systematic field walking, bibliography studies, museum researches, etc. The variety of available data raised questions on the validity of spatial results based on archaeological material of different nature, temporality and spatial extent. The purpose of this preliminary study is to create a control tool that will be used for the interpretation of results in trying to extract the most valuable information to the archaeological interpretation. This tool is expressed spatially through what was called "confidence maps", a data layer produced by combining reliability and representation of the data.

REPRESENTATION MAPS

Evidence for data dispersion/location over separate study areas is symbolized with representation maps. They were designed with the aim of being standardised in respect to the theoretical mean of the individual study area (i.e. variations to the average). Therefore they allow the quantification and visualization of spatial heterogeneity in the sampling and the inventory of the different datasets. The number of archaeological items in each predefined grid cell is computed and this value is compared to the expected (usually mean) value in the study area, which gives an idea of the over-or under-representation of data.

First the analysis grid size has to be defined for each individual study area. The proposed optimal cell size calculation is based on the assumption that archaeological data is approximately evenly distributed, which means that each data object is assigned the same area, defined by the cell. The cell size is therefore "unique" for each study area because it is directly related to the area of investigation and the number of observations -in effect it is an average distance among observations (Sánchez 2006). In our case we have computed the optimal cell size as cell_size = sqrt(total_area/N observations ). This empirical method is based on the assumption that if the objects are normally distibuted, then a similar area should approximately belong to every object. Therefore, the average area of an object can be computed by dividing the whole area of interest by the number of objects. This average area is square shaped when working with a regular grid, thus the cell size of the grid can be computed by square rooting the average area. This number is then rounded and represents the optimal resolution. A similar approach is mentioned by Shary et al. (2002). However, data is rarely evenly distributed. In order to improve the statistical significance we have chosen the first larger grid size, fitting the "standard" resolution system used in ArchaeDyn, i.e. 1, 2.5, 5, 10, 25, 50, 100, 250 km … This produces grids that are both optimal and well populated that is containing a significant number of points. In order to simplify the process of data transformations and comparison of different datasets further, the common point of origin has been defined for all the grids, meaning the cell boundaries of different resolutions and study areas overlap at the same coordinates. This means that even different scale phenomena can be processed as imagery in order to combine their information over the same or different areas when it is relevant. Representation classes were defined to stand for no data, normal, over and extreme representation (see fig. 1). It was found that these types of classes correspond to the nature of archaeological data, whose frequency is typically exponentially distributed and hardly ever normal. In case of being so, the classes would be under, normal, and over representation. The approach is different from the previous work done by the group (Nuninger and Favory 2008). Some not completely resolved issues remaining are the automatic or semiautomatic selection of thresholds for classes and the no-data phenomenon. Even though the process was designed with the aim of being non subjective and based solemnly on statistics, a uniform automatic statistical division of classes based on average proved to be unreasonable because of the extreme data heterogeneity, including different distributions, differences in absolute values, no data phenomenon, and the use of integer values. According to our tests, the classification process has to be done (semi)manually and individually for every dataset with the help of statistical and mathematical tools. The usual procedure is based on histogram analysis and its modification using a logarithmic function, and defining the natural breaks in the data. The latter are especially difficult to define if absolute frequencies (representations) are low. This implies the importance of selecting the optimal grid size.

The problem of handling no data values has not been solved satisfactory, but rather bypassed. The statistics can be significantly altered with the inclusion of cells with no data values in the calculation. The argument for including such values is the fact that the space is continuous and areas cannot be left out, however in cases where data is highly concentrated this can lead to dramatic decrease of the average and as a result even the areas with only one object can be classified as over represented. Increasing the cell size by one "standard" step and manual delimitation of classes evaded this problem as with the latter the interpreter can manually classify such areas as normally represented and with the first the number of no data cells is effectively decreased anyhow. A problem which arises is further concentration of extreme values and resulting reduction of "contrast", but if this is not the primary concern it is well supplemented with improved overall legibility and accuracy of the final map.

RELIABILITY MAPS

Reliability maps express the settings (and limitations) of inventory exploration (i.e. how the archaeological sources were explored) in terms of common indicators such as survey level -sampling, visibility level, the quality of references etc., about a specific dataset. A reliability map gives information on the intensity of research and exploration (reliability of the inventory), and is not primarily concerned with the quality of data's location. It can therefore also be interpreted as a correlation between intensity of research and actually identified sites or archaeological evidence. In our case a reliability map covers the entire study area and distinguishes three reliability levels: reliable, fairly reliable and not reliable. It has been defined by the providers of individual datasets and has been mostly drawn by hand according to a predefined set of rules. The rules were defined by each workgroup or even by each archaeological team. Indeed, such rules are depending on the kind of investigation. Nonetheless, each set of rules is written with respect to the three predefined degrees allowing comparison. The definition of reliability levels is adjusted according to the nature of data. For example, instead of field walking, data availability in museums or publications can be considered (Tab.1). The identification of individual levels is based on an empirical method because its foundation is the knowledge on data, and is therefore inherently biased. It is also highly dependent on the phase of studies and of course directly connected to the state of the studied database. The ArchaeDyn's databases are, from now on, fixed at the present state of the investigation in order to provide analysis. New discoveries or new development of the database will be used by the end of the project during the step of validation and for final interpretations.

Level

CONFIDENCE MAPS

Confidence maps offer a tool to evaluate the relevance of archaeological data in spatial analysis. They give an impression about the confidence a user can have on the final results that is based on input data. The representation and reliability layers are combined using map algebra in order to obtain confidence maps. The logic behind lies in joining two spaces: location-based density (representation) and intensity on inventory (reliability). Results allow for the comparison and analysis of data confidence and thus the evaluation of the trustworthiness of the interpretation and spatial modelling, also give information on the correlation between data representation reliability. The map can be used to eliminate "spurious" zones for space-time analysis over long-term (according to the comparison of each study area with their chronology and the interpretation key of the representation map).

Fig. 3: Confidence map processing model.

The proposed process is essentially based on simple algebraic operations and "binary" logic. The confidence was coded into two digit numbers, with one digit reserved for representation and the other for reliability. To technically enable the addition, the representation map has to have "denary" classes, 10, 20, 30, and 40, being extreme representation, over representation, normal representation and no data, respectively, and the reliability map was used with values of 1, 2, and 3, ranging from highly, moderate to low reliability. Another technical issue is an accurate rasterization of the reliability map. Normal rasterization omits border areas with less than half cell occupancy. Consequently a 3/4 cell size buffered layer with preserved attributes has to be created and rasterized. Its outer buffer is then added to the rasterized reliability and the result combined with the representation map. An ArcGIS tool was designed to speed up and enable batch processing.

The ensuing confidence map is in effect an overlay of both maps (see fig. 3). By inspecting the map one can immediately find areas of different representation but also areas with low data reliability. The strongly coloured areas are more reliable than the light coloured areas but both can and should be included in the analyses with a different level of caution. The proposed process can also be applied to analyse and compare other spatial phenomena, and tests are underway to evaluate it for the effectiveness in representing temporal changes. Some hard to manage issues still remain in this approach. Questions, such as how to discretize representation maps and how to interpret areas with no data will have to be addressed in the future.

CONCLUSIONS

To represent the level of trust of the spatial analysis and modelling results we have defined a tool called confidence maps. Confidence maps provide the user a spatial impression about the representation and the reliability of the input data in the same time, giving him the opportunity to detect "artefacts" in the data. The same methodology has been defined for different scales and for different observed phenomena. Despite the fact that the data used can be very dissimilar the interpretation of confidence maps is the same. This is an innovation especially considering the extent of the ArchaeDyn project.

There are still some problems that have to be solved though. Confidence maps are not suitable for all databases. They suit better databases containing "noise" -they perform better with large amount of statistically well represented data. We have also found a rather strong scale dependence of the results. Different tests have shown that the tool does perform better with small scale (big area), large quantity of points (often it will be studies of objects and not sites or settlements), and a low positional accuracy (studies about the diffusion of material, circulation of artefacts).

The method was developed and successfully applied to various archaeological dataset (Oštir et al. 2007, Nuninger, Favory dir. 2008, Saligny et al. 2008). In the presented paper, our purpose is to show a first example of the methodology applied to data obtained and used in human and social studies in the framework of the Caenti project. While the methodology is still under development, it can be used effectively to map the reliability of the spatial modelling results.

Fig. 1 :

 1 Fig. 1: A representation map of dated archaeological bronze objects in France (map: Z. Kokalj, data: F. Pennors).

  Fig. 2: A reliability map of dated archaeological bronze objects in France (map: Ž. Kokalj, reliability zones and data: F. Pennors).

Fig. 4 :

 4 Fig. 4: A Confidence map of dated archaeological bronze objects in France (map: Z. Kokalj, data: F. Pennors).

ACKNOWLEDGEMENTS

Archaeological data used in the study was obtained in the frame of ArchaeDyn project. Part of the work has been performed within the ModeLTER (European Laboratory for Modelling of Landscapes and Territories over the Long Term), institute founded by ZRC SAZU and CNRS. Laure Saligny, Florian Tolle, Françoise Pennors and Klemen Zakšek have contributed to the preparation of this paper.

BIBLIOGRAPHY

Nuninger L., Favory F., 2008. ArchaeDyn 2005-2007: ambitions, achievements and accomplishments. In 7 millennia of territorial dynamics : settlement pattern, production and trades, from Neolithic to Middle Ages, preproceedings of the ArchaeDyn 2008 conference, Dijon 23-25 June. Oštir K., Kokalj Ž., Saligny L., Tolle F., Nuninger L., 2007. Confidence maps: a tool to evaluate archaeological data's relevance in spatial analysis, Layers of Perception. Proceedings of the 35th Computer Applications and Quantitative Methods in Archaeology Conference, Berlin, Germany, April 2-6, 2007, (Kolloquien zur Vor-und Frühgeschichte, vol. 10). Bonn (Germany): Habelt. Saligny L., Nuninger L., Oštir K., Poirier N., Fovet E., Gandini C., Gauthier Es., Kokalj Z., Tolle F., 2008. Models for territorial dynamic studies (Programme ArchaeDyn) In 7 millennia of territorial dynamics: settlement pattern, production and trades, from Neolithic to Middle Ages, pre-proceedings of the ArchaeDyn 2008 conference, Dijon 23-25 June. Sánchez, J., 2006. The accuracy of grid digital elevation models linearly constructed from scattered sample data, International Journal of Geographical Information Science 20 (2): 169-192. Shary, P., Sharaya, L., Mitusov, A., 2002. Fundamental quantitative methods of land surface analysis, Geoderma, 107: 1-32.


Alexandru Tatar
email: tatar@npa.lip6.fr

Panayotis Antoniadis
email: antoniadis@tik.ee.ethz.ch

Marcelo Dias De Amorim

Serge Fdida

From Popularity Prediction to Ranking Online News

Keywords:

Introduction

The widespread adoption of smart phones and the rise of social networking sites has accelerated the consumption of online news in the latest years. This is a type of content that can be easily produced and has a small size, short lifespan, and low cost -properties that places it in a top position to be consumed on mobile or social sharing platforms. As a result, a significant amount of research has been centered on understanding the world of online news and many research problems have been addressed within this space, such as: tracking the propagation of topics across the web [START_REF] Leskovec | Meme-tracking and the dynamics of the news cycle[END_REF], describing the decay of interest over time (Dezso et al. 2006), detecting online communities [START_REF] Adamic | The political blogosphere and the 2004 us election: divided they blog[END_REF], and prediction of popularity [START_REF] Tsagkias | News comments: Exploring, modeling, and online prediction[END_REF]. It is the last one, however, that gained most of the research focus both because this problem is very challenging and because of its immediate practical implications. Indeed, predicting the popularity of online content is valuable for different stakeholders: news sites and news aggregators can better highlight the most popular content, online advertisers can propose more profitable monetization strategies, and online readers can filter the huge amount of information more easily.

There are different ways of expressing the notion of popularity. For example, the classical way of defin-This paper is a significant extension of our previous work, "Ranking news articles based on popularity prediction", published at ASONAM 2012.

ing it is through the click-through rate. However, this information is seldom available to external observers and, when available, it is difficult to estimate the actual number of times that a page was requested by users or due to web crawlers and search engines. Nevertheless, as reading news has become a social experience, there are other metrics that capture readers' interest. These metrics are based on user participation activities such as comments, votes, or shares through social media or email services. In this paper we focus solely on one dimension of the content popularity -comments -and consider the number of comments as an implicit indicator of the interest generated by a news article.

Predicting the popularity of news articles is a complex and difficult task and different prediction methods and strategies have been proposed in several recent studies [START_REF] Lee | An approach to model and predict the popularity of online contents with explanatory factors[END_REF]; Lerman et al. 2010;[START_REF] Szabo | Predicting the popularity of online content[END_REF][START_REF] Tsagkias | News comments: Exploring, modeling, and online prediction[END_REF]. Most previous efforts have focused on predicting the exact amount of attention that online content will generate at a future moment in time. This information can indeed prove valuable in online advertising, where new revenue models could be designed to charge advertisers for the (future) amount of attention that a content will generate. However, in another practical situation, a news platform may want to use this information to rank news stories in realtime and highlight the most popular ones. For example, imagine an online newspaper that publishes news stories and at random moments of the day it promotes some of its articles on the social networks accounts. The decision of which content to promote can be done by human raters or through an automatic operation that ranks news stories and selects the most important ones.

In this paper, we focus on the latter option, by studying the feasibility of using popularity prediction methods for automatic online news ranking. To this end, we compare the ranking effectiveness of two prediction methods: a linear model on a logarithmic scale and constant scaling model. In order to properly evaluate the ranking performance, we propose a general setting that takes into consideration two important properties of the articles: lifetime and distribution of popularity. We validate the effectiveness of these methods by using two news sources and compare them with various baseline methods and dedicated learning to rank algorithms. As a summary, the main contributions of this work are:

-We analyze two important online news platforms from France and Netherlands and provide valuable insights on how users post comments on news articles. By exploring these data sets we observe that news stories have a very short lifespan and that the volume of comments per article can be described by a power-law distribution. -In the context of automatic online news ranking we evaluate the ranking effectiveness of two popularity prediction methods and show that a linear model on a logarithmic scale is an effective method for online news ranking. -We compare the performance of these methods with learning to rank algorithms and show that for this ranking problem, popularity prediction methods could successfully replace more complex ranking algorithms.

The rest of the paper is organized as follows. In Section 2 we give a brief overview of our ranking approach and present the two data collections. We explore the properties of these data sets in Section 3 and describe the evaluation strategy in Section 4. We evaluate the ranking performance of our proposed methods and compare them with several baseline methods (Section 5) and learning to rank algorithms (Section 6). We conclude with a presentation of the related work in Section 7 and present future perspectives in Section 8.

Methodology and data sets

Methodology

We tackle the problem of ranking online news by using a two-phase procedure. The first step consists in understanding two underlying properties of news articles that are relevant to our ranking problem: articles' lifetime and distribution of popularity. Then, based on these observations, we recommend a more rigorous evaluation strategy adapted to the characteristics of news.

The entire ranking process, through model training, article scoring, and actual ordering can add a significant overhead to a system if the number of items is large. News platforms are particularly affected by this problem as a large corpus of articles accumulates over time. But news stories have a short lifetime and only few items continue to catch readers attention over a longer period of time. It is thus important to study the lifetime of articles and use this information to reduce the pool of articles considered for ranking.

The second relevant information for this ranking problem is the distribution of popularity. News articles, similar to most of the content found over the Internet, depict a very skewed distribution of interest. Understanding how readers' attention is distributed between articles can be exploited to conduct a more focused ranking evaluation where a ranking method should be particularly accurate in identifying the top most important articles. [START_REF] Tsagkias | News comments: Exploring, modeling, and online prediction[END_REF]). We present a summary of the data sets in Table 1.

3 News properties

Lifetime of an article

A common characteristic of online content is that it suffers from a decay of interest over time and, depending on the type of content, this decay can be steep or gradual. News articles incur a very steep decay compared to videos [START_REF] Cha | I tube, you tube, everybody tubes: analyzing the world's largest user generated content video system[END_REF] or photos [START_REF] Cha | A measurement-driven analysis of information propagation in the flickr social network[END_REF]), as they refer to a recent type of information that by its nature has a very short life cycle (Dezso et al. 2006).

We provide a coarse representation of articles' lifetime by analyzing the timestamp of the last comment received by an article. 3 . The results are presented in Figure 1 by means of a complementary cumulative distribution function of the duration between the publication time of an article and its last comment. For both news sources we observe that the majority of articles (72% for telegraaf and 61% for 20minutes) acquire all comments within the first day after the publication. There are indeed articles that stimulate user interest for a longer period of time, but this interest is sparse and not constant as observed for other type of online content [START_REF] Cha | I tube, you tube, everybody tubes: analyzing the world's largest user generated content video system[END_REF]). This can be seen in Figure 2 by means of a probability density function of the comments publication time relative to articles publication time. As it can be observed, users react very fast to the publication of news articles, but their interest drops quickly after six hours and only a negligible amount of comments are received after one day. Comparing the two news sources, we observe that, while the drop of interest over time is similar in the first day for both sites, articles published on 20minutes engage users in a commenting activity for a longer period of time than those published on telegraaf. This difference can be explained by the different lifespan of the data sets, one covering more than four years and the other one only eight months. To isolate this effect we analyze a reduced version of the 20minutes data set, one that covers the same period of time as telegraaf (Figure 1b). Even after this adjustment we can observe that, in general, 20minutes articles receive comments for a longer period of time than telegraaf. There are several factors that could explain this difference. One of them is that 20minutes news have a greater exposure than telegraaf news, as indicated by the traffic statistics of the two web sites (5.5 million unique visitors per month for 20minutes.fr compared to 3.8 million for telegraaf.nl4 ). The result is that 20minutes articles may seize a greater amount of attention in the early stages after the publication, which could further impact the popularity and smoothen the decay of interest over time. Other explanations, which unfortunately cannot be deduced from the information found in our data sets, could be related to the tone of the articles (a more personal and subjective voice may be more captivating to online readers) or the topic of the news (it has been observed that certain topics have a longer life cycle [START_REF] Leskovec | Meme-tracking and the dynamics of the news cycle[END_REF])).

Distribution of popularity

A common question addressed by scientists that study the properties of online content is whether the data under observation exhibits heavy-tail characteristics or not. While this is interesting from a scientific point of view, where a mathematical model can summarize empirical data, this information also has practical implications. For example, it has been shown that understanding the underlying distribution of popularity for web content can have important consequences in the design of caching algorithms [START_REF] Breslau | Web caching and zipf-like distributions: Evidence and implications[END_REF] In the case of social media content, recent work, on different sources of online content and using various popularity metrics, indicates that content popularity can be described by heavy-tail distributions and the log-normal distribution appears to give the most consistent description [START_REF] Tsagkias | News comments: Exploring, modeling, and online prediction[END_REF][START_REF] Van Mieghem | Lognormal distribution in the digg online social network[END_REF][START_REF] Wu | Novelty and collective attention[END_REF]). Our data sets make no exceptions from this observation. This can visually be observed in Figure 3, where we illustrate the complementary cumulative distribution of the number of comments per article and the power-law fit. The power-law behavior appears in the tail of the distribution and has been confirmed by rigorous power-law tests proposed by Clauset et al. (Clauset et al. 2007). 5 There is, however, a difference between the two news sources as observed in Table 2. Our results indicate that while a power-law provides the most accurate description for 20minutes articles, a power-law with exponential cut-off gives a more precise solution for telegraaf data set.

It is out of the scope of this paper to debate over which distribution is the most adequate one for describing the popularity of online news and we encourage the reader to follow the enriching discussion presented in [START_REF] Mitzenmacher | A brief history of generative models for power law and lognormal distributions[END_REF]). One possible explanation of why the power-law provides a more precise description for 20minutes articles can be given by the web site recommendation strategy. The site highlights the most commented articles in a dedicated section and twice a day it delivers to its subscribers a short electronic edition with the most commented articles. This creates a rich-get-richer effect, which is one of the reasons why power-law appears so often on the Internet [START_REF] Easley | Networks, Crowds, and Markets: Reasoning About a Highly Connected World[END_REF]). The recommendation mechanism can also explain why the power-law fails to appear in the beginning of the distribution and could also account for the difference in articles' lifetime observed in Section 3.1. Articles that are unpopular in the beginning do not benefit from any recommendation mechanism and the probability of 5 Statistical techniques based on maximum-likelihood methods and Kolmogorov-Smirnov statistics. receiving any kind of attention drops even more as they lose their position on the web site [START_REF] Simkin | Why does attention to web articles fall with time?[END_REF]).

The heavy-tail property has important implications in the ranking evaluation. Indeed, given that the distribution is so heavily skewed, a ranking algorithm should perform particularly well in identifying the top most important articles. We explore in Figure 4 the daily distribution of comments for the top most commented articles. On the x-axis we order articles based on their popularity (in a decreasing way) and normalize the ranks from 0 to 100. On the y-axis we consider the proportion of daily comments received by the top-k most important articles. As we can observe in Figure 4, for both data sets, on a daily basis the top 10% most commented articles gather 50% of the total number of comments and around 20% of the articles receive 80% of all the comments published that day.

Experimental setting

Methodology. To evaluate the ranking performance we propose the following methodology:

1. We break the corpus of articles of each data set in small subsets, where each subset contains all articles published during a certain period of time before a specific reference hour h. We set the duration of the period to one day given our previous observations of how readers significantly lose their interest in articles after one day. 2. We rank each subset of articles based on the number of comments that articles receive after the reference hour and consider this ranking as the ground truth. We then apply the different methods (heuristics, popularity prediction methods, and learning to rank algorithms) to estimate the ranking of articles and assess the ranking effectiveness using NDCG evaluation measure.

In the following, we explain the ranking and the evaluation strategies in more detail.

Ranking strategy. Let A be the corpus of articles published by a news platform during a period of time T, with a ∈ A being one specific article. We discretize time on an hourly basis and consider h a precise hour of the day according to a 24-hour clock. Let t h be the absolute time in hours and denote d as a one-day period. According to this time description and relative to an hour h we split A in k subsets, with k = ⌈T /d⌉. Denote A i h the ith subset of articles created relative to an hour h, with A = k i=1 A i h . Please note that as h varies from 0 to 23 there are 24 ways of separating the corpus of articles. This separation allows us to further measure how the ranking performance is influenced by the hour we perform the ranking.

For every article a we refer to a t0 as the article's publication time and define N a (t) the number of comments received by article a from a t0 to certain time t. We also consider N a (t h , t r ) the number of comments received by an article from t h to t r .

For our specific ranking task, given a set of articles A i h and a ranking time t h , our goal is to accurately rank articles by the number of comments they will receive from t h until a future time t r , with t r > t h . We set t r to 30 days to catch only the relevant comments and remove possible sources of spam. Under this description the ground truth ranking for A i h is given by N a (t h , t r ). We consider this value the relevance of an article, and note

rel(a t h ,tr ) = N a (t h , t r )• (1)
Evaluation measure. We assess the ranking performance of the different strategies using the normal discounted cumulative gain (NDCG) (Jarvelin et al. 2002).

To compute NDCG for a set of q articles we first determine DCG as

DCG = rel 1 + q i=2 2 reli -1 log 2 (i + 1) , (2)
where rel i is the relevance of an article found at position i in the ranked list. From this value we compute NDCG as

NDCG = DCG IDCG , ( 3
)
where IDCG is the ideal DCG, the DCG of the perfectly ranked list of articles (ground truth ranking). We report the results using 10-fold cross-validation. That is, after splitting the corpus of articles in k subsets we randomly divide these subsets in 10 folds. We use 9 folds to train the models and assess their performance on the remaining fold; we repeat the process 10 times, using a different fold at each step, and report the average value.

Ranking methods

Each ranking method rates the relevance of an article using a certain criterion and one method is considered adequate if the estimated ranked list is close to the ground truth ranking. We analyze the ranking effectiveness of two methods based on content popularity prediction and compare them with several baselines.

Popularity predictions methods

We consider the following two popularity prediction methods:

- The choice of the prediction model is justified by the properties of our data, where the linear model on a logarithmic scale is particularly well adapted to data with heavy-tail characteristics. We also consider the constant scaling model in our analysis following the observations that this model outperforms the linear log model when minimizing the relative squared error (Szabo et al. 2008).

These two models are regression functions where the dependent variable is the total number of comments received by an article until time t r and the independent variable is the number of comments received t i hours after its publication. The goal of the prediction method is thus to estimate the number of comments t r hours after an article a is published using the information received in the first t i hours.

The estimated popularity for the linear log model is described by the following equation:

N LN a (t i , t r ) = exp ln(N a (t i )) + β 0 (t i , t r ) + σ 2 0 (t i , t r ) 2 • (4)
For the parameters of Equation 4, β 0 is computed on the training set using maximum likelihood parameter estimation on the regression function ln N a (t r ) = β 0 (t i , t r ) + ln N a (t i ) and σ 2 0 is the estimate of the variance of the residuals on a logarithmic scale.

The constant scaling model is expressed as

N CS a (t i , t r ) = α 2 (t i , t r ) × N a (t i ), (5)
where we estimate α 2 using the following expression:

α(t i , t r ) = a Na(ti) Na(tr) a Na(ti) Na(tr ) 2 • (6)
We assess the performance of these methods in predicting the exact popularity of the articles using the absolute squared error (QSE):

QSE(a, t i , t r ) = N a (t i , t r ) -N a (t r ) 2 • ( 7
)
We analyze the predictive performance of these models as a function of the observation period (t i ) in Figure 5. The results indicate that the prediction error for both models is significantly high for an observation period of less than 6 hours and it rapidly decreases after that. Comparing the two data sets, we observe that telegraaf articles have very low predictive performance in the beginning and a negligible one after 20 hours. On the other hand, 20minutes articles show a better overall predictive performance but the error prevails even after one day. The different performance of these models can, however, be explained by the different dynamics of the comment arrival rate presented in Section 3. As observed in Figure 2, the most significant share of comments is received in the first 6 hours, which explains the high prediction error for short observation periods. Similar, the low error for telegraaf news stories after 20 hours is explained by the saturation of articles' popularity in less than one day.

Baselines

We compare the effectiveness of these methods with three baseline strategies: -Live: rank articles by the number of comments received until the prediction moment, N a (t h ). -Recency: rank articles by the time of publication, a t0 , with the most recent first. -Weighted : rank articles by the number of comments but weight the volume of comments per hour giving importance to more recent information.

The first two methods are simple heuristics often used by news portals to highlight their popular content, where live is oblivious to the temporal information and recency considers the time of the publication as the only factor that matters in the ranking decision. The third baseline method is similar 6 ). This method combines the partial popularity and recency of articles in the ranking decision by weighting the popularity relative to its closeness to t h . By using this method, the score S assigned to an article a at time t h is given by the following formula:

S(a t h ) = t h t=at 0 f (t h -t)N a (t)• ( 8
)
where f is a probability density function that describes how much weight we should assign to past popularity on an hourly basis. In our case, we observed in Figure 2 that the decay of interest over time follows a log-normal behavior. As a result, we express f as log-normal probability density function:

f (δ; µ, σ) = 1 δσ √ 2π exp (-ln(δ) -µ) 2 2σ 2 , ( 9
)
where we obtain the values of µ and σ by fitting the log-normal distribution on the empirical data.

Results

Using the experimental setting described in Section 4 we compare the ranking performance of the two popularity prediction models with the baseline strategies (Figure 6). We report the mean value and a 95% confidence interval over all prediction hours and for various levels of precision: NDCG@1, NDCG@5, NDCG@10, NDCG@20, and NDCG@100. One can observe from the results that the simplest baseline models, live and recency, have limited ranking capabilities. This suggests that news ranking based on the submission timerecency heuristic -or one based on static view of the popularitylive heuristic -are inefficient solutions for this ranking task. The performance can however be improved using popularity prediction methods or a weighted solution. For a precision level of NDCG@100 (that allows us to capture on average 98% of the daily comments -Figure 4) the linear log model shows 50% improvement compared to live solution (for both data sets) and a 40% improvement for telegraaf -and 75% for 20minutes -compared to the recency solution. From the top three performing algorithms, the linear log model shows the overall highest performance; the only exception is observed for NDCG@1, where the weighted model is equally effective. The gain of linear log model, compared to the second best solution (weighted model ) for NDCG@100, is of 2% for 20minutes and 10% for telegraaf. If the benefit brought by the linear log model over the other top two models is important for telegraaf (with an increase between 10% and 14% for precision levels greater than NDCG@5), for 20minutes the top three methods show a similar performance suggesting that they are equally fit for this ranking task. These results depict the average performance over all hours of the day. However, in our previous analysis [START_REF] Tatar | Predicting the popularity of online articles based on user comments[END_REF]) and other similar studies [START_REF] Szabo | Predicting the popularity of online content[END_REF][START_REF] Tsagkias | News comments: Exploring, modeling, and online prediction[END_REF], it has been observed that articles and comments are published at a different rate during the day. As a consequence, articles may be more popular or exhaust their interest more quickly depending on the publication hour, an effect that can influence the ranking accuracy. To capture the impact of this observation, we illustrate in Figure 7 the ranking performance as a function of different prediction hours (to ease the presentation of the figure we report only the even hours of a day). We take as example the case of NDCG@100, but we observed that the relative performance of the ranking methods is equivalent for the other levels of precision. One can notice that, in general, the top three algorithms show a consistent improvement over the simple heuristics live and recency. The improvement of the linear log model over the other two methods is insignificant for 20minutes -suggesting that the top three ranking solutions are equally effective -but has an important impact for telegraaf data set where the improvement is notable for some specific hours (e.g. the improvement for 10 a.m. is 12%.)

Comparison with learning to rank algorithms

A different approach to this ranking problem is to automatically construct a ranking model using learning to rank algorithms. These algorithms propose a straightforward approach to the ranking problem and provide higher adaptability to include more features into the ranking model. We compare our approach with several learning to rank algorithms.

Depending on how they address the ranking problem, there are three main classes of learning to rank algorithms: pointwise, pairwise, and listwise [START_REF] Liu | Learning to rank for information retrieval[END_REF]. We consider a representative model from each category:

-Multiple additive regression trees (MART)pointwise approach based on the gradient boosting technique proposed in [START_REF] Friedman | Greedy function approximation: a gradient boosting machine.(english summary)[END_REF]). -RankBoostpairwise approach based on a boosting algorithm and multiple weak rankers [START_REF] Freund | An efficient boosting algorithm for combining preferences[END_REF]). -LambdaMARTpairwise and listwise approach using boosted regression trees and designed to optimize NDCG [START_REF] Wu | Adapting boosting for information retrieval measures[END_REF]). -AdaRanklistwise approach also based on a boosting algorithm that minimizes an exponential loss function [START_REF] Xu | Adarank: a boosting algorithm for information retrieval[END_REF]).

Using the same evaluation strategy (10-fold crossvalidation) we deploy and assess the performance of these algorithms for our specific ranking task. 7 While the format of the previous models is not adapted to be used with a large number of features, this can easily be done using learning to rank algorithms. We thus compare the performance of dedicated learning to rank algorithms using the same amount of information as the previous models, with models that include other features into the ranking decision (e.g. section, author, mean inter-comment time). As a result, we train and evaluate these algorithms using two different set of features:

-basic set of features: partial popularity, time since publication, publication hour. -enhanced set of features: basic features + (section, author, time of the first comment, mean and median inter-comment time, weekday, and week). 8 We report the performance of these models in Table 3 and compare them with the best performing model from our previous analysis, the linear log model. Overall, one can observe that the linear log method is more effective than most of the learning to rank solutions, being surpassed only by the MART model with an enhanced set of features for NDCG@100. From the learning to rank algorithms, MART exhibits effective performances (very close to linear log method) across all levels of prediction. This is likely due to the underlying structure of the model that solves the ranking problem through a set of regression trees. Using the basic set of features, the other learning to rank solutions generally do not perform as well as the previous two, which suggest that they are not able to solve the pairwise and listwise constrains for this ranking problem. In general, we observe that adding more features in the model improves the ranking performance except for AdaRank applied to 20minutes data set, which shows a reduced performance. These results suggest that popularity prediction methods can accurately identify the top most commented articles and could be used as a valuable solution to automatic online news ranking.

Related Work

Several works have addressed the problem of predicting the popularity of online content. One of the first models, used to predict the popularity of Slashdot stories, was proposed by Kaltenbrunner et al. (2007). This solution considers that, depending on the publication hour, the popularity of news stories follows a constant growth. Sz 2012) who use a learning to rank algorithm and Twitter posts to rank news articles based on the future number of clicks. The study shows that micro blogging activity can successfully be used to detect the important news stories. In our study we share the same general objective of ranking news articles, but our work differs both in the ranking technique, notion of article relevance, and input used for the ranking methods.

Summary and outlook

In this paper, we analyzed the efficiency of popularity prediction methods in the context of automatic online news ranking. We conducted our study using a large corpus of articles and comments from a French and a Dutch online news platforms and performed an evaluation centered on two fundamental characteristics of online content: the distribution of popularity and the lifetime of articles. In this context, we analyzed the ranking effectiveness of two content popularity prediction methods and compared them with several baselines methods and learning to rank algorithms. Our results indicate that a linear log popularity prediction model is an effective solution to online news ranking, with a performance that can evenly match more customized learning to rank algorithms.

The quality of the prediction, even under the most accurate ranking method, shows a moderate performance. One way to boost the ranking performance is to include more information in the ranking decision. During our analysis, we observed that some learning to rank algorithms improve their performance by including more features in the model. The improvement is, nevertheless, modest and other sources of information should be considered in the future work. We believe that an interesting direction would be to study how news articles spread in social networks [START_REF] Li | Modeling and evaluating information propagation in a microblogging social network[END_REF] or blogs [START_REF] Cha | The spread of media content through blogs[END_REF]) and to understand how this process influences articles' popularity. As it has already been observed that the blogosphere (Mc-Creadie et al. 2010) and online social networks (Morales et al. 2012) provide reliable signals for content popularity, an appealing extension of this work is to create a ranking model that puts toghether evidence from all these sources. An additional source of information lies in the profile of the users that comment on news articles. Blogging is often a social activity and user communities may form around certain topics [START_REF] Macskassy | Contextual linking behavior of bloggers: leveraging text mining to enable topicbased analysis[END_REF]) which can animate the discussions and increase news articles popularity.

The popularity prediction models studied in this paper are designed to predict the popularity at a specific future time and are oblivious to how the popularity is spread over the entire lifetime of an article. While most articles share a similar temporal trend -fast decay of user interest -more complex temporal dynamics have been observed with online content (Crane and Sornette 2008, [START_REF] Leskovec | Meme-tracking and the dynamics of the news cycle[END_REF]). Uncovering the different temporal evolution patterns could refine the quality of the prediction and further improve the ranking accuracy.

Finally, in future work we will propose strategies that are more adequate for an online evaluation of the ranking methods. In our work, we use an offline evaluation strategy that makes abstraction of how the outcome of the ranking influences the commenting activity. In reality, the prediction outcome, used for content recommendation or front page ordering, may play a critical role in the future popularity of a content [START_REF] Zhou | The impact of youtube recommendation system on video views[END_REF]. Future work should focus on the design of more adequate assessment tools based on an internal feedback loop between the web platform and user reaction to ranking outcome.

Fig. 1 :

 1 Fig.1: Complementary cumulative distribution function corresponding to the articles' lifetime (time elapsed between article publication time and the last comment time). The labels on the x-axis correspond to one hour, day, week, month, and year. We represent two versions of 20minutes data: one over the entire data set and a reduced version that covers the same period of time as telegraaf data set.

Fig. 2 :

 2 Fig.2: Probability distribution function of the comments time relative to the articles publication time. We represent the histogram covering a one-day period along with the best probability fit, which in our case is described by a log-normal distribution.

Fig. 3 :

 3 Fig. 3: The complementary cumulative distribution function of the articles' popularity and the corresponding power-law fit.

Fig. 4 :

 4 Fig.4: Normalized article ranks and the cumulative of proportion of comments received on a daily basis. We present the average value and one standard deviation (shaded area).

Fig. 5 :

 5 Fig.5: The prediction error in terms of QSE for the two popularity prediction methods. On the x -axis we vary the observation period from 1 to 24 hours. On the y-axis we represent the mean error -depicted in the top figures -and the mean along with one standard deviation (SD) represented by the shaded area in the bottom figures.

  Linear regression on a logarithmic scale (linear log) model proposed by Szabo and Huberman (Szabo et al. 2008) and previously evaluated on Digg news, YouTube videos, and Dutch news articles (Tsagkias et al. 2010).-constant scaling model also described bySzabo and Huberman and evaluated on Digg news and YouTube videos[START_REF] Szabo | Predicting the popularity of online content[END_REF]).

Fig. 6 :

 6 Fig.6: NDCG at different levels of precision. @n corresponds to the NDCG score for the top most important n articles. We present the mean over all prediction hours h (n=24) along with a 95% confidence interval.

  to the algorithm proposed by McCreadie et al. that showed one of the most accurate performance on TREC 2009 blog collection (McCreadie et al. 2010

Fig. 7 :

 7 Fig.7: Ranking accuracy in terms of NDCG@100 per hourly basis. The outer numbers correspond to different reference hours h (only the even hours of the day). The inner numbers correspond to the different ranking methods, with 1 -linear log, 2weighted, 3 -constant scaling, 4 -recency, 5 -live.

Table 1 :

 1 Summary of the data sets analyzed in this paper.

	Data set	20minutes	telegraaf
	Lifespan:
	-start	3/2/2007	18/8/2008
	-end	6/5/2011	21/4/2009
	Total articles	231,120	40,287
	Total comments	2,635,489	731,395
	Articles per day
	-mean	157	176
	-median	136	153
	Comments per day
	-mean	1,255	3,086
	-median	1,231	3,052
	2.2 Data collections
	In this study we use data from two news platforms,
	20minutes 1 and telegraaf 2 . Both news sources are
	popular daily newspapers that complement the hard
	copy editions with online sites that allow users to read
	news stories and express their opinions through com-
	ments. The sites' content is news oriented, starting with
	the main articles from the printed version and being
	periodically updated with the latest news. These news-
	papers target a broad audience and cover diverse topics
	from national and international politics, sports, econ-
	omy, or lifestyle.
	The two data collections differ in size and lifespan:
	20minutes contains 231,120 articles and 2,635,489 com-
	ments published from February 2007 until May 2011 (Tatar
	et al. 2011); telegraaf data set contains 40,287 arti-
	cles and 731,395 comments published from August 2008
	until April 2009

  [START_REF] Simkin | Why does attention to web articles fall with time?[END_REF][START_REF] Wu | Novelty and collective attention[END_REF]), but for the scope of our work, this coarse characterization provides us with sufficient information.

			20minutes
		0.002	Data
	Density	0.001	Log-normal fit: µ=5.74, σ= 1.22
		0
		6	12	18	24
			telegraaf
		0.003	Data
	Density	0.0015	Log-normal fit: µ=5.63, σ= 0.8
		0
		6	12	18	24
		Time since article publication(hours)

Table 2 :

 2 Comparing the power-law fit against other alternative distributions. For each alternative distribution, we provide the p-value and the likelihood ratio test (LR). We consider a significance level of 0.1 for the p-value and display the significant values in bold. Positive values of the log-likelihood indicate that the power-law is a better fit model than the alternative distributions.

	Data set	Exponential LR p	Power + cut-off Log-normal LR p LR p
	20minutes 34.42 0.07 -1.24	0.11	-2.5	0.31
	telegraaf	13.40	0.12	-5.6	0.00	-4.6 0.05

; Guo et al. 2008) or in the improvement of search engines (Fortunato et al. 2006).

  abo et al. proposed two other prediction methods that have shown good results in predicting the popularity of YouTube videos and Digg stories (Szabo et al. 2008). Tsagkias et al. showed that the linear log method is also reliable for predicting the popularity of news articles (Tsagkias et al. 2010). Lerman et al. propose a different approach to the prediction problem and present a model built on the social influence and web platform characteristics in the prediction process (Lerman et al. 2010). A different approach was proposed by Lee et al. Information about section and author are available only for 20minutes data set.

8

Table 3 :

 3 Ranking accuracy in terms of NDCG for different levels of precision. We compare the linear log model and the learning to rank algorithms using different set of features: basic and enhanced. The bold value indicates the best performing algorithm for a specific precision level.

		(a) 20minutes
	Method	@1	@5	NDCG @10	@20 @100
	Linear log	0.35 0.52 0.56 0.58	0.61
	MART-b	0.3	0.48	0.52	0.54	0.57
	MART -e	0.33	0.50	0.54	0.56	0.59
	RankBoost -b	0.07	0.12	0.13	0.14	0.26
	RankBoost -e	0.24	0.36	0.39	0.43	0.48
	LambdaMART -b 0.06	0.17	0.22	0.25	0.32
	LambdaMART -e	0.05	0.16	0.22	0.26	0.32
	AdaRank -b	0.13	0.23	0.28	0.31	0.38
	AdaRank -e	0.07	0.19	0.24	0.29	0.35
		(b) telegraaf
	Method	@1	@5	NDCG @10	@20 @100
	Linear log	0.36 0.50 0.55 0.59	0.60
	MART-b	0.31	0.48	0.52	0.56	0.59
	MART -e	0.32	0.49	0.54	0.59	0.61
	RankBoost -b	0.19	0.24	0.28	0.32	0.40
	RankBoost -e	0.27	0.46	0.49	0.52	0.56
	LambdaMART -b 0.13	0.20	0.24	0.30	0.39
	LambdaMART -e	0.14	0.21	0.25	0.29	0.40
	AdaRank -b	0.15	0.22	0.24	0.24	0.37
	AdaRank -e	0.16	0.26	0.41	0.41	0.51
	where, instead of predicting the exact value, the au-
	thors are interested in predicting the probability that a
	content will continue to receive comments after a cer-
	tain period of time (Lee et al. 2010). More recent results
	(Bandari et al. 2012), which use the number of tweets as
	the popularity metric, show that it is possible to classify
	articles in four classes of popularity, but that it is still
	difficult to predict the exact amount of attention. We
	place ourselves in this context of popularity prediction.
	In our work we analyze the predictive characteristics of
	news articles, on an unexplored data set (20minutes),
	using methods that have shown good results in previ-
	ous works. We make a step further in our research and
	analyze the ranking capabilities of these methods by
	taking into consideration the dynamic nature of news
	generation.
	The feasibility of ranking online news has been ad-
	dressed in (Morales et al. 2012; McCreadie et al. 2010).
	McCreadie et al. propose a ranking method based on
	relevant blog posts and show that the blogosphere activ-
	ity is a reliable indicator of news stories importance (Mc-
	Creadie et al. 2010). A different approach was proposed
	by Morales et al. (

http://www.20minutes.fr/

http://www.telegraaf.nl/

We are aware that there are other fine-grained methods of evaluating the decay of attention over time[START_REF] Lee | An approach to model and predict the popularity of online contents with explanatory factors[END_REF]

According to the latest statistics of the two sites: http://corporate.tmg.nl/en/result-second-quarter-2012 (telegraaf); http://www.mediametrie.fr (20minutes)

The algorithm uses the number of blog posts to predict users' interest in articles.

We deploy these algorithms using RankLib open source library (Ranklib).

Acknowledgements

The work presented in this paper has been carried out at LINCS (www.lincs.fr) and was partially supported by the ANR project Crowd under contract ANR-08-VERS-006 and EINS, the Network of Excellence in Internet Science, FP7 grant 28802. The authors are grateful to Manos Tsagkias for sharing the telegraaf data set.