Cristian Ionut

Mihai Paraschiv
email: ionut.paraschiv@cti.pub.ro

Stefan Dascalu

Trausan-Matu

Philippe Dessus
email: philippe.dessus@upmf-grenoble.fr

Automated Paper Annotation with ReaderBench

Keywords: Scientometrics, paper recommendation system, time analysis, discourse analysis, semantic similarity. ACM Classification Keywords I.2.7 [Natural Language Processing]: Discourse, Language parsing and understanding, Text analysis

The annotation of articles from a given domain and the generation of semantic metadata can be considered a reliable foundation for creating a paper recommender system. Within this paper, the models from other previous researches are extended with the capability of visualizing articles and the most important concepts from a domain within imposed timeframes. This can be very useful for researchers to check out the most important publications from a given period, to view which are the trends and how a domain has evolved. Our previous analyses used the articles to build a paper graph and to suggest the most relevant articles, given a user defined query in natural language. This research contains a use case and creates visual graph representations to enhance the overall perception of the evolution of a domain.

INTRODUCTION

A researcher's daily activities usually involve the study of new papers, as to use the information in building solutions and observing how the domain evolves. Since the retrieval of documents from the Internet can lead to large data flows, it is important to consider other approaches for a more comprehensive analysis of the domain. In this context, a paper annotation system that automatically retrieves papers on a given topic and tags them can be critical and can make the exploration phase of the research literature easier.

We propose a model that takes a large set of paper abstracts and tags them, later on annotating the results within a semantic database. The database can be queried for user defined texts, and can enable the researcher to explore the resulting graphs using different timeframes, as to retrieve the most important articles and concepts within a period. Moreover, a list of similar topics with the user's query is shown with the intention of stimulating the user in his/her research tasks.

The initial part from this paper will concentrate more on similar studies that discuss on how to build network graphs for scientific papers. We continue with the methods used behind the current model that demonstrate its potential and extensibility, as well as how they are used, and we finish with possible future improvements of our system.

RELATED WORK

A paper annotation system can be built with database software that uses keyword matching such as Mendelev or DevonThink, or other complex methods [START_REF] Joeran | Research Paper Recommender System Evaluation: A Quantitative Literature Survey[END_REF]. However, the current model does not rely on information retrieval [START_REF] Manning | Introduction to Information Retrieval[END_REF] as we describe an alternative of annotating a dataset of documents. A different, older approach of indexing papers relies on co-citation analysis [6; 7], but that method is out of scope in terms of the current research.

Information Retrieval

Information Retrieval [START_REF] Manning | Introduction to Information Retrieval[END_REF] techniques aim at finding materials of an unstructured nature, usually text, that satisfy information needs from within large textual collections. This process is usually concerned on how to store and structure data in such a manner that it will facilitate the retrieval of information based on a given query and in a relatively small amount of time. Being a text recognition tool, the query, consisting of a Boolean combination of keywords, is usually mapped with the collection; therefore, no semantic meaning is associated to the query or to the set of documents. In this way, the more complicated or complex the query is, the smaller are the chances of finding relevant results.

Semantic Similarity Analysis of Paper Abstracts

Our paper annotation model relies on two widely used methods. The first one, Latent Semantic Analysis [6; 7], is a natural language processing method that is used for analyzing relationships between documents and their terms, in our particular case -abstracts [START_REF] Gordon | Using Latent Semantic Indexing for literature based discovery[END_REF]. The method builds a document-term matrix that basically assigns for every word its corresponding number of occurrences within the document. After applying a Singular Value Decomposition, the dimensionality of the matrix is reduced, while keeping its similarity structure with a marginal error. At the end, the documents are compared by computing the cosine similarity between their associated vectors within the semantic space.

The second method, Latent Dirichlet Allocation [START_REF] Blei | Latent Dirichlet Allocation[END_REF], uses topic distributions among documents, and in combination with LSA can give an aggregated cohesion scores [START_REF] Dascalu | Analyzing discourse and text complexity for learning and collaborating[END_REF] that can be more accurate for computing semantic distances. In the end, in order to compute the semantic distance between two words, our model also relies on semantic distances extracted from the lexicalized ontology WordNet, together with LSA and LDA semantic models [START_REF] Budanitsky | Evaluating WordNet-based Measures of Lexical Semantic Relatedness[END_REF].

SYSTEM'S IMPLEMENTATION

Using the approaches described in previous subsections, the papers from the initial dataset were tagged using the content from their abstracts, that usually contains the main ideas [START_REF] Ding | Content-based citation analysis: The next generation of citation analysis[END_REF], as seen in our previous research [START_REF] Paraschiv | Analyzing the Semantic Relatedness of Paper Abstracts -An Application to the Educational Research Field[END_REF]. In this manner, three different views on the dataset of articles have been built. The first one, the document similarity view [START_REF] Paraschiv | Analyzing the Semantic Relatedness of Paper Abstracts -An Application to the Educational Research Field[END_REF], generates a graph with the papers which are connected if their semantic similarity exceeds a threshold. The second one, the concept map view [START_REF] Paraschiv | Analyzing the Semantic Relatedness of Paper Abstracts -An Application to the Educational Research Field[END_REF], extracts the most important concepts from the subset of papers, and builds a graph where the words are connected using their relevancies [START_REF] Dascalu | Analyzing discourse and text complexity for learning and collaborating[END_REF]. In both these two views, the nodes are sized depending on their centrality, and the links between them are enforced based on the similarity. In this way, the user will see at the end which are the most important words and documents from the set of papers. The third view displays the document space for a particular paper [START_REF] Paraschiv | Analyzing the Semantic Relatedness of Paper Abstracts -An Application to the Educational Research Field[END_REF], and can help researchers when they want to read semantically related articles. After this first implementation phase which was previously presented [START_REF] Paraschiv | Analyzing the Semantic Relatedness of Paper Abstracts -An Application to the Educational Research Field[END_REF], the improvements presented in this paper are focused on enabling the user to define his/her own queries. In the end, similar graphs to the document similarity view [START_REF] Paraschiv | Analyzing the Semantic Relatedness of Paper Abstracts -An Application to the Educational Research Field[END_REF] are displayed, but with the papers that have a high semantic cohesion with the text introduced by the user. Moreover, the user can also check semantically related concepts with the query terms (concepts that do not specifically appear inside the query), thus stimulating his/her imagination with ideas for new queries. This is the first exploratory extension of our system.

The text given by the user enters inside the same pipeline as the abstracts: text preprocessing, lemmatization, partof-speech tagging, syntactic dependency analysis and topic extraction [4; 12]. The next step is to represent the query using LSA and LDA vectors, and to compute its distance with every document from the dataset. The LSA query vector is obtained by summing up normalized occurrences of each constituent lemma vector representation, whereas for LDA the Gibbs inference tools is applied on the query in order to deduce the topic distributions based on pre-trained models. In order to increase the user's control, the final view shown in Figure 1 also contains a threshold used for displaying the links between the papers and the query, which can be manually adjusted. The documents are also shown inside a table, ordered by their similarity with the input query.

The second extension presented in this paper consists of enabling the user to select a timeframe for the displayed papers and concepts. In this manner, a researcher can check the evolution of a domain, the most important articles in a period and the most central concepts. As many domains evolve in a dynamic manner, this is definitely the way to check past and current trends, as well as concepts that become more important.

From a technical point of view, the paper annotation system uses the core components from ReaderBench [4; 5], a versatile tool for text and discourse processing. With a fully functional natural language processing pipeline incorporated, LDA and LSA semantic pre-trained models, WordNet and semantic distances, as well as Social Network Analysis [START_REF] Bastian | Gephi: An open source software for exploring and manipulating networks[END_REF], ReaderBench is an extensible tool for most of the undergone text processing steps.

These two extensions have the purpose of stimulating a researcher in his daily tasks by suggesting papers, similar concepts, as well as the modeling of the evolution of a domain within a period of time. Together, they can definitely support anyone interested in learning a domain. The next section is centered on specific use cases of how the system can be used with a real dataset of paper abstracts.

USE CASE

Dataset Description

The used dataset of abstracts consists of papers extracted from the citation index Web of Science, from the Education and Educational Research [START_REF] Grauwin | Mapping scientific institutions[END_REF] domain, taken between the years 2000-2004. From this dataset, a subset of paper which contained within their abstracts the keywords "IT", "technology" or "computer science" was extracted.

User Queries

Given the database of annotated abstracts, the user inputs an initial query "electronic learning and information technology", with the intention of finding papers related to informational systems that implement learning facilities. Using a threshold value of 70%, Figure 1 displays a sub-graph with the most related articles with the query. Table 1 displays what is the content of these articles.

Figure 1. Semantically related articles to the input query

From Table 1, we can observe that the most related abstracts with the user's query are semantically related, and unlike standard information retrieval systems, the results don't necessarily have common words with the query. This can impact the retrieval of enhanced search results, and can definitely help anyone in finding documents about a subject.

For the example query in this subsection, the researcher could be interested to check some related concepts with his/her query. The system is capable of displaying the related keywords in a graph, which can be explored by the user. In this context, the model suggests words such as "learner", "teacher", "science", "curriculum", "research", "process", and "development" (see Figure 2), which are quite relevant given the input query. Moreover, we can check the underscored words as being from the input query, while the others are being automatically introduced as semantically related to them. All the words with a threshold over .5 in terms of semantic similarity are shown, and they are grouped together using the same stem; in the end, the shortest lemma is being displayed.

Paper title and abstract Relevance

Trajectories and tensions in the theory of information and communication technology in education "For largely historical reasons, information and communication technology in education has been heavily influenced by a form of constructivism based on the transmission and transformation of information. This approach has implications for both learning and teaching in the field. The assumptions underlying the approach are explored and a critique offered...."

.78

Information technology and education in the information age "This paper attempts to gain an understanding of current and potential impact of information technology (IT) on education in the information age. First, it attempts to highlight that integration of information technology in teaching is a central matter in ensuring quality in the educational system. ..."

.74

Hippias Major, version 1.0: Software for post-colonial, multicultural technology systems "The first half of Plato's Hippias Major exhibits the interfacing of the first teacher (Socrates) with the first version of a postcolonial, multicultural information technology system (Hippias). In this interface the purposes, results and values of two contradictory types of operating system for educational servicing units are exhibited to.." .72

Table 1. Samples from the related papers

Unlike standard information retrieval systems, this model performs better when it comes to user queries, as in this case, more complex queries usually mean richer semantic content, and thus more accurate results.

Timeframe View

Although not a computationally demanding task, the ability to filter articles and important concepts using different timeframes can be very appealing to researchers, as they can check the trends and the evolution in time of a specific domain. In Figure 3, a subgraph from the article similarity view from the year 2002 is shown, displaying the central article having a relevance of 0.81.

Paper title and abstract

A collaborative, investigative recombinant DNA technology course with laboratory

"A recombinant DNA technology course was designed to promote contextual, collaborative, inquiry-based learning of science where students learn from one another and have a sense of ownership of their education. The class stressed group presentations and critical reading and discussion of scientific articles. The laboratory consisted of two research projects: random cDNA …."

Technology in the first two years of collegiate mathematics "We present several roles of technology and suggest various ways that technology could have a lasting and significant impact upon the quality of mathematics courses being taught in the first two years of collegiate mathematics. Overcoming some mathematicians' anxiety and reluctance to address applied problem solving so as to take full advantage of the opportunities remains a challenge for the future…"

Maximising the educational affordances of a technology supported learning environment for introductory undergraduate phonetics

"New technologies afford a range of opportunities that can transform teaching techniques and offer enhanced possibilities for learning. This potential is often not grasped by the technologist or the educationalist when introducing new technologies into the learning situation and a situation arises which can be described as 'New technology, no new pedagogy.'…" The graph of the most important concepts from 2002 is displayed in Figure 4. Overall, it becomes clear that there is a difference in terms of semantic meaning between the central articles from 2002 and the ones in 2004. As technology has evolved in that period, the central articles are more related to information technology applied inside learning environments, which supports the idea that the user can check using our system how the domain has evolved in time.

Figure 6. Central concepts in 2004

To sustain this idea, Figure 6 displays some of the most important concepts from 2004, where the most preeminent lemmas are "technology", "education", "teacher", "study", "learning", "science" and "computer". They demonstrate the idea that the domain has evolved as new technologies appeared and were applied inside the educational research domain.

Another interesting experiment on the two datasets of papers was to find out which are the most similar concepts. In this manner, we have extracted the most important 100 concepts from the papers written in 2002, Dataset 1 (DS1), and from those written in 2004 (DS2). Every concept from DS1 was compared with every concept from DS2, and This paper focuses on the use of multimediabased predict-observe-explain (POE) tasks to facilitate small group learning conversations. Although the tasks were given to pairs of students as a diagnostic tool to elicit their preinstructional physics conceptions, they also provided a peer learning opportunity for students. The study adopted a social constructivist perspective... .913

3.a Conditions for classroom technology innovations (2002)

This article reports on a study of the complex and messy process of classroom technology integration, The main purpose of the study was to empirically address the large question of "why don't teachers innovate when they are given computers?" rather than whether computers can improve student learning. Specifically, we were interested in understanding the conditions …

3.b. New teaching and learning techniques facilitated by information technology (2004)

A wide variety of classroom techniques are being advocated to increase learning: active learning, collaboration, integration of assessment and feedback, and the use of concrete physical manipulatives. These techniques must be transformed into practical tools and be infused with content from the subject area. At the same time, the information technology revolution has provided new tools … .898

Table 5. Most similar articles from the subsets

This section presented in detail a generalizable use case that can be easily extrapolated on any dataset of papers and can enable researchers to better understand a domain. Moreover, the results clearly indicate that the evolution of a domain can be better understood by analyzing the semantic content of the articles within certain timeframes.

CONCLUSIONS

As more and more research communities appear and they are more dynamic than ever, it is becoming quite hard for a researcher to keep up-to-date with this fast growing information. In this context, a paper annotation model and viewer can be a good alternative to better visualize the papers from a certain dataset. Moreover, the support for user defined queries, graphical visual representations and timeframe filtering increase the overall understanding of a domain and, in the end, the productivity of researchers.

As future developments, the timeframe snapshot will be displayed in an interactive and animated manner, not just as a static graph within a period of time. Moreover, a current drawback must be addressed: the long preprocessing time due to the NLP processing pipeline, and a relatively small number of possible papers that can be loaded directly into the system's memory. Therefore, some improvements must be done for our model in terms of memory and CPU consumption. In order to address these issues, clusters of papers will be created and the search will be conducted within a multi-hierarchical structure of documents..

Figure 2

 2 Figure 2 Semantically related concepts

Figure 3 .

 3 Figure 3. Subgraph of the article similarity view -Year 2002

Figure 4 .

 4 Figure 4. Central concepts in 2002 As displayed in Figure 4, the most important concepts from the dataset in 2002 are educational, classroom, training and instruction. It will be very interesting to check how the central article's topics and the corresponding concept graph have changed in 2004.

Figure 5 .

 5 Figure 5. Subgraph of the article similarity view -Year 2004

Table 2 . Central article summaries in 2002

 2

Table 3 . Central articles summaries in 2004

 3

Table 4 . Concept similarities from the subsets

 4 Table 4 displays the most similar pairs from the two subsets. In this manner, the researcher can get additional information regarding the domain and how it has evolved.

	Concept from 2002	Concept from 2004	Sim.
	Classroom	Student	.92
	Educator	Student	.86
	Design	Engineering	.75
	Knowledge	Experience	.71
	Educational	Student	.71
	Professional	Practice	.66
	Further on, Table 5 depicts the most similar abstracts
	between the two subsets, being a good metric to see how
	the content has evolved in the two years. The idea of the
	table is that, by checking on the articles that are
	semantically related in different periods, a researcher can
	observe a domain's trends and what emerging solutions
	have appeared regarding certain problems.

Article pairs (marked as X.a and X.b) Score

						in urban middle schools. The effort was one
						component of systemic reform efforts …
						2.a Integrating algorithm visualization
						technology into an undergraduate algorithms
						course: ethnographic studies of a social
						constructivist approach (2002)
						Algorithm visualization (AV) software
						graphically illustrates how algorithms work.
						Traditionally, computer science instructors
						have used the software as a visual aid in
						lectures, or as the basis for interactive
						laboratories. An alternative approach, inspired
						by Social Constructivist learning theory …
						2.b. Classroom use of multimedia-supported
						predict-observe-explain tasks in a social
						constructivist learning environment (2004)
	1.a Introduction of CAA into a mathematics
	course for technology students to address a
	change in curriculum requirements (2002)
	The	mathematical	requirements	for
	engineering, science and technology students
	has been debated for many years and concern
	has been expressed about the mathematical
	preparedness of students entering higher
	education.	This	paper	considers	a
	mathematics course that has been specifically
	designed to address some of these issues for	.955
	technology education students …
	1.b Standardized test outcomes of urban
	students participating in standards and
	project based science curricula (2004)
	Considerable effort has been made over the
	past decade to address the needs of learners in
	large urban districts through scaleable reform
	initiatives. We examine the effects of a
	multifaceted scaling reform which focuses on
	supporting standards based science teaching

ACKNOWLEDGMENTS

The work presented in this paper was partially funded by the FP7 2008-212578 LTfLL project and by the Sectorial Operational Programme Human Resources Development 2007-2013 of the Ministry of European Funds through the Financial Agreements POSDRU/159/1.5/S/134398 and POSDRU/187/1.5/S/155420. We also thank Pablo Jensen and Sebastian Grauwin for providing the initial corpus of paper abstracts.


Alexandre Reiffers Masson

Eitan Altman

Yezekael Hayel

Controlling the Katz-Bonacich Centrality in Social Network: Application to gossip in Online Social Networks

Recent papers studied the control of spectral centrality measures of a network by manipulating the topology of the network. We extend these works by focusing on a specific spectral centrality measure, the Katz-Bonacich centrality. The optimization of the Katz-Bonacich centrality using a topological control is called the Katz-Bonacich optimization problem. We first prove that this problem is equivalent to a linear optimization problem. Thus, in the context of large graphs, we can use state of the art algorithms. We provide a specific applications of the Katz-Bonacich centrality minimization problem based on the minimization of gossip propagation and make some experiments on real networks.

I. INTRODUCTION

Centrality measures are valuable key measures to understand Social Networks. The most famous ones are the degree centrality, the betweenness centrality, the closeness centrality and finally the eigenvector centrality (see [START_REF] Jackson | Social and economic networks[END_REF]). The popularity of these measures comes from the fact that they are concerned with links between a given node to the overall network (a micro perspective) as opposed to the diameter of a graph, the small world property, etc. (macro perspective). In particular spectral centrality measures of a node depends on the whole topology of the network. This is one of the main differences between spectral centrality measures and the others. Among the huge number of applications of spectral centralities, we will mention two works as example. In [START_REF] Bimpikis | Competing over networks[END_REF], the authors characterize the optimal targeted marketing strategies in a Social Network by a spectral centrality measure. The second recent example of application is [START_REF] Ballester | Delinquent networks[END_REF], where authors use a spectral centrality measure to find the delinquent who, once sent in jail, decreases to the maximum the population of delinquency profiles.

The control of the spectral centrality score associated to each node, by modifying the graph topology, is a recent problem. To the best of our knowledge the very first paper on this topic, concerns the maximization of the PageRank, where a webmaster controls multiple pages and hyperlinks between them (see related work of [START_REF] Fercoq | Ergodic control and polyhedral approaches to pagerank optimization[END_REF]). In the framework of delinquency, the paper [START_REF] Ballester | Delinquent networks[END_REF] proposes to model a network of delinquents with communications between them and design an algorithm to characterize the link to remove that will minimize the overall rate of delinquency. In [START_REF] Nicosia | Controlling centrality in complex networks[END_REF] the authors try to find the minimum set such as the vector of score is fully controlled.

There are several spectral centrality measures: the eigenvector centrality, the alpha centrality, the Katz-Bonacich centrality, the PageRank1 and the subgraph centrality (see [START_REF] Estrada | Subgraph centrality in complex networks[END_REF]). We propose to restrict ourselves to the Katz-Bonacich centrality. Indeed in this case we are able to derive an efficient algorithm to control this centrality by choosing which nodes to remove. The score given by the Katz-Bonacich centrality to a node is based on a discounted sum of the walks that initially has starting from it. There are applications in Social Network that use it. For instance, in the gossip in social network described, the authors use the Katz-Bonacich centrality to characterize the key node. In other contexts, the Katz-Bonacich centrality has been used in a pricing context [START_REF] Bloch | Pricing with local network externalities[END_REF], to characterize the Nash equilibrium of a Cournot competition over a network [START_REF] Bimpikis | Cournot competition in networked markets[END_REF] and in other economic and social network applications (see [START_REF] Banerjee | The diffusion of microfinance[END_REF], [START_REF] Banerjee | Gossip: Identifying central individuals in a social network[END_REF], [START_REF] Jackson | Social and economic networks[END_REF] and [START_REF] Temurshoev | Who's who in networks-wanted: The key group[END_REF]).

The focus in this paper is on deriving an efficient algorithm to optimize the Katz-Bonacich centrality by removing nodes. We prove that it is equivalent to a linear programming formulation and that there is a polynomial solution algorithm. Thus algorithms from [START_REF] Bunch | Sparse matrix computations[END_REF] can be used in the context of large graphs. Once the linear programming characterization is provided our goal is to propose an application of the control of the Katz-Bonacich Centrality based on the minimization of a gossip process over an online Social Network.

After a short state-of-the-art section, we introduce in section III the Katz-Bonacich centrality optimization problem. We recall the mathematical definition of Katz-Bonacich centrality. We then prove the equivalence between with a linear programming problem. In section IV, we apply the Katz-Bonacich centrality minimization problem to control of a gossip process over a Online Social Network [START_REF] Ballester | Delinquent networks[END_REF]. Finally we compute the solution the Katz-Bonacich centrality minimization problem on real networks in section V.

II. RELATED WORKS

The control of the spectral centrality has been studied from different points of view: Topology Control. Lately, the question of how to modify the topology of the network in order to control the centrality score of nodes became a subject of interest. In [START_REF] Nicosia | Controlling centrality in complex networks[END_REF], an algorithm is proposed to find the minimum controlling centrality subset of nodes in a complex network in the particular case of the eigenvector centrality. The authors propose to only control interactions generated by nodes inside this subset. In [START_REF] Fercoq | Ergodic control and polyhedral approaches to pagerank optimization[END_REF] the authors noticed the links between the optimization of the PageRank and the ergodic Markov decision problem. Based on it, they provide an efficient algorithm to optimize the PageRank.

Key node. Another question has been also investigated on how does the centrality score of nodes evolve when a node is removed from the network. In [START_REF] Ballester | Delinquent networks[END_REF], [START_REF] Ballester | Who's who in crime network. wanted the key player[END_REF], the authors highlight the equivalence between the delinquency effort level and the Katz-Bonacich centrality. Then they propose to find which delinquent has to be in jail in order that the global delinquent profile decreases to the maximum. In [START_REF] Liu | Control centrality and hierarchical structure in complex networks[END_REF], [START_REF] Pan | Power of individuals-controlling centrality of temporal networks[END_REF], the authors investigate the control of the eigenvalue centrality. Their study is based on the theory of control of linear system and the well-known Kalman's controllability rank condition (see [START_REF] Kalman | Contributions to the theory of optimal control[END_REF]). They propose to find which node can control the whole system based on results from [START_REF] Hosoe | On the irreducibility condition in the structural controllability theorem[END_REF].

III. CONTROL OF THE KATZ-BONACICH CENTRALITY

As previously mentioned, the focus of this study is to provide an efficient algorithm to solve the Katz-Bonacich centrality optimization problem. We first recall the definition of the Katz-Bonacich centrality measure. We then, formally, describe the Katz-Bonacich centrality optimization problem.

A. The Katz-Bonacich centrality optimization problem

We begin our analysis by recalling the definition of the Katz-Bonacich centrality. In one of his work [START_REF] Katz | A new status index derived from sociometric analysis[END_REF], made during the 50s, Katz proposed to model the centrality or the prestige of a node in a network in the following manner: the score associated to a node is based on a discounted sum of the walks that initially has started from it. Nowadays, this centrality measure is called Katz-Bonacich centrality because Bonacich proposed in [START_REF] Bonacich | Power and centrality: A family of measures[END_REF] a similar spectral centrality measure. We next provide a formal definition of it.

The social network G (I , E) is composed of a set I := {1, . . . , I} of nodes and the interactions between them is described by an communication matrix E. The variable e i j ∈ [0, 1] denotes the i j th entry of E and represents the relative frequency of interaction between node i ∈ I and node j ∈ I . Moreover, for each i, we assume that ∑ j e i j = 1 expect when a node does not communicate with any other nodes and so ∑ j e i j = 0. The definition of the Katz-Bonacich centrality [START_REF] Katz | A new status index derived from sociometric analysis[END_REF], is given by:

Definition 1: Let ρ ∈ [0, 1]. The Katz-Bonacich centrality associated to G (I , E), denoted by x * (E, ρ) ∈ R I +
, is given by:

x * (E, ρ) := ∞ ∑ n=0 (ρE) n 1 I , (1)
where 1 I is the all ones vector of size I. Thus the Katz-Bonacich centrality is the limit, as t goes to infinity (whenever it exists), of the following deterministic process, where for each t ∈ N * :

x i (t + 1) = 1 + ∑ j ρe i j x j (t), ∀i. (2)
Moreover if the Perron Frobenius eigenvalue (see [START_REF] Meyer | Matrix analysis and applied linear algebra[END_REF]), λ max (ρE), associated to the matrix ρE is smaller than one, then:

x * (E, ρ) = (Id I -ρE) -1 1 I , (3)
where Id I is the identity matrix of size I × I.

The problem we are interested in is the minimization (or the maximization) of the Katz-Bonacich centrality by removing nodes, in other words by controlling the communication matrix E. The variable p i ∈ [p i , p i ] denotes the probability to not remove a node i and (1p i ) the probability to remove it. Thus the Katz-Bonacich centrality is now in expectation, for each i, the limit lim t→∞ E[x i (t)] (which exists if λ max (ρE) < 1) of the following dynamical system:

E[x i (t + 1)] = E[1 + ∑ j ρe i j x j (t)] (4)
= p i (1 + ∑ j ρe i j E[x j (t)]). (5)
Moreover we assume that the Katz-Bonacich cannot be lower that a certain level in some regions of the graph. Let c ∈ {1, . . . ,C} denote a particular region of the graph. Let N(c) ⊂ I the subset of nodes that belongs to the region c. For each c and c , we assume that N(c) ∩ N(c ) = / 0. For each region c, the constraint over Katz-Bonacich centrality is:

∑ j∈N(c) x * j ≥ φ c , (6)
where φ c ≥ 0. These region constraints comes from the fact it is not possible to remove all the nodes of the graph. The Katz-Bonacich centrality minimization problem is therefore defined below: Definition 2: For each i, let p i ∈ [p i , p i ] denotes the probability to remove node i and p := (p 1 , . . . , p I ) the associated vector. Let P := Π i [p i , p i ] the set of constraints. Let ρ ∈ [0, 1]. Let E a sub-stochastic matrix and λ max (ρE) < 1. Let φ := (φ 1 , . . . , φ C ) the region constraints. The Katz-Bonacich centrality minimization problem associated to (E, ρ) is defined as:

min p∈P ∑ i x * i (p), (7)
where for each i, x * i is the unique solution of:

x * i (p) = p i (1 + ∑ j ρe i j x * j (p)), (8)
such that for each c,

∑ j∈N(c) x * j (p) ≥ φ c . (9)

B. Characterization by a linear program

Our main result is to provide an equivalence between the Katz-Bonacich centrality minimization problem and a linear program. Our goal is to first compute, for a given centrality, a closed form of the control that allows us to reach it. Then given a particular matrix E and a scalar ρ we will describe the set of feasible centralities. Finally we will prove the equivalence between the Katz-Bonacich centrality minimization with a linear program. The region constraints will only appear in the formulation of the linear program. We will not use it before.

Proposition 1: Let k ∈ R I
+ , E and ρ. If for each i,

p i ≤ k i 1 + ∑ j ρe i j k j ≤ p i , (10)
let us define

p * i = k i 1 + ∑ j ρe i j k j , ∀i (11)
then x * i = k i for all i, where x * i is solution of (8) for each i. Proof: If

p i ≤ k i 1 + ∑ j ρe i j k j ≤ p i , (12)
then p * i ∈ [p i , p i ]. This is the reason why p * i exists. Moreover for each i

x * i = p * j (1 + ∑ j ρe i j x * j ) (13)
x * i = k i 1 + ∑ j ρe i j k j (1 + ∑ j ρe i j x * j ). (14)
This linear system admit a unique solution. And it is easy to check that the unique solution is x * i = k i :

x * i = k i 1 + ∑ j ρe i j k j (1 + ∑ j ρe i j k j ) = k i . (15)
Now we are interested to undersand the set of feasible centralities, in other word to characterize the following set:

F := k ∈ R I + | ∃p ∈ P such that k sol. of (8) . (16)
The next proposition characterize this set: Proposition 2: Let E and ρ.

F = k | ∀i, k i ≥ 0, p i ≤ k i 1 + ∑ j ρe i j k j ≤ p i , . (17)
Proof: According to the proposition 1, it exists p such that x * i = k i if for each i:

p i ≤ k i 1 + ∑ j ρe i j k j ≤ p i . (18)
Now according to the two previous propositions we can deduce that the Katz-Bonacich centrality minimization problem is equivalent to: min

k ∑ i k i (19)
subject to for each i and each c:

p i 1 + ∑ j ρe i j k j ≤ k i , (20)
p i 1 + ∑ j ρe i j k j ≥ k i , (21)
∑ j∈N(c) k j ≥ φ c , (22)
0

≤ k i . (23)
Once this linear program is solved the associated control is the one proposed in proposition 1. Because it exists a linear program equivalent to the Katz-Bonacich centrality minimization problem, we can use algorithm proposed in [START_REF] Bunch | Sparse matrix computations[END_REF] for large graphs.

IV. WHICH NODES TO REMOVE IN A GOSSIP PROCESS

The problem we are interested in is the minimization of the propagation of a gossip by removing nodes. We call this problem the Gossip Minimization problem. As proposed in [START_REF] Banerjee | Gossip: Identifying central individuals in a social network[END_REF] the owner of the Online Social Network (the controller) can block some nodes in the Social Network. For instance, by sending a warning to the friends of a user, the control can disturb communication between users. A more precise exemple, still in the context of Online Social Networks, messages that appear in subscribers' News Feed2 are control by a content curation algorithm [START_REF] Eslami | Feedvis: A path for exploring news feed curation algorithms[END_REF], thus the controller can reduce interactions between users. We propose to generalize the model proposed in [START_REF] Banerjee | Gossip: Identifying central individuals in a social network[END_REF], under realistic considerations.

A. Interest of Users: A first model

Let I := {1, . . . , I} the set of users and i ∈ I is a user index. A user i of a social network gets news, about the gossip according to a Poisson point process of intensity λ i ∈ R + . Thus when an news arrival occurs, concerning the gossip, the probability that it is for user i is:

λ i ∑ j λ j .
Let t n ∈ R + the arrival rate of the n-th message. When a user i receives a news, its increases his belief in the gossip. Thus the interest of an average user about the gossip at time t n , is described by a random variable

Y i (n) ∈ R + . Let x i (n) := Y i (n) n
the time average interest of user i at time t n . A user i updates his interest in the following way: When he receives a news about the gossip at time t n , he increases of one the interest related to it. Thus, for each i the evolution of Y i is described by:

Y i (n + 1) = Y i,c (n) + ζ i (n),
where the interest update is modeled by:

ζ i (n) :=        1 w.p λ i ∑ j λ j , 0 w.p 1 - λ i ∑ j λ j . (24)

B. Imitation between users: a network extension

As an extension of the previous model, we consider that interests imitation can occurs between users. Let P ∈ [0, 1] I×I the imitation matrix, where the i j-entry of P, p i, j , is the probability that a user i imitates interest of user j. For each i, assume ∑ j p i, j = 1. The time instant when user i decides to imitate one of his neighbors is modeled by a Poisson point process of intensity α i ∈ R + . An event is now the arrival of messages or the activation of a user who wants to imitate someone. When an event occurs, the probability that it is the imitation phase of user i is α i ∑ j λ j +α j . At event n, when user i imitates user j, he will add one to Y i (n) with probability x j (n). Thus the new version of ζ (n

) := [ζ 1 (n), . . . , ζ I (n)], associated to the evolution of Y = [Y 1 , . . . ,Y I ], is described below: ζ i (n) =    1 w.p P i (x(n)) := λ i ∑ j λ j + α j + α i ∑ j p i, j x j (n) ∑ j λ j + α j 0 w.p 1 -P i (x(n)). (25)

C. Stability Analysis

Following the theory developped in [START_REF] Borkar | Stochastic approximation[END_REF], the next theorem provides a sufficient condition about the convergence of the sequence {x n }.

Theorem 1: [9] Let x 0 ∈ [0, 1] C×I denote the initial conditions. If the matrix A defined as follows,

a i, j := α i p i, j ∑ i ,c λ i ,c + α i -1 i= j ,
is irreducible then the sequence {x(n)} converges almost surely to an unique rest point x * ∈ [0, 1] C×I . Moreover

x * c = BΛλ c ∀c, (26)
where Λλ c := [Λλ 1,c , . . . , Λλ I,c ], Λ := 1 ∑ j,c λ j,c +α j and B := A -1 . It is interesting to note that the rest point of the stochastic approximation ( 25) is the Katz Bonacich centrality of the graph defined by the following matrix C, where the i j-entry is given by c i, j := α i p i, j ∑ i λ i + α i . Control description. In the Gossip minimization problem, the controller can decide which users to block. More precisely, he can reduce the impact of user i over his neighbors using a control p i ∈ [p i , p i ], such that the interest of each user i is solution of the following linear system:

x * i = p i ( λ i ∑ j λ j + α j + α i ∑ j p i, j x * j ∑ j λ j + α j ). (27)
Moreover because the controller cannot fully control the interest of each user, the sum of the interests of each user cannot be lower that a certain level:

∑ j x * j ≥ φ , (28)
where φ > 0.

Utility description. In the present paper, we assume that the controller wishes to minimize a utility vector depending on the interest of each user. Then the Gossip minimization problem is:

min p∈P U(x * ). (29)
where for each i, x * i is the unique solution of:

x * i = p i ( λ i ∑ j λ j + α j + α i ∑ j p i, j x * j ∑ j λ j + α j ), (30)
subject to

∑ j x * j ≥ φ . ( 31
)
We shall be interested in reducing the overall interest, in other words:

U(x) := ∑ i x * i . (32)
Finally according the previous section III-B, the Gossip minimization problem is equivalent to the following linear programming: min

k ∑ i k i ( 33
) Network I d ∑ i x * i ∑ i x * i (p)
p i λ i ∑ j λ j + α j + α i ∑ j p i, j k j ∑ j λ j + α j ≤ k i , (34)
p i λ i ∑ j λ j + α j + α i ∑ j p i, j k j ∑ j λ j + α j ≥ k i , (35)
∑ j k j ≥ φ , (36) 0
≤ k i . (37)
It is easy to generalize to a convex utility function. Indeed, as U(x i * ) is convex in x i * , we can use classical convex optimization algorithm [START_REF] Boyd | Convex optimization[END_REF] to solve this problem.

V. SIMULATIONS

In this section we propose to compute over different networks the solution of the Katz-Bonacich centrality minimization problem. We study it over 4 different topologies depicted in fig. 1. The summary of experimental results are described in table I. The first column provides the number of nodes, the second column the average degree (d). We propose to study each network with its normalized adjacency matrix E, where the i j-entry is given by: e i j := a i j ∑ j a i j , where A is the real adjacency matrix. For each network, the Katz-Bonacich centrality is computed with ρ = 0.1. The centrality average value of each network is given in the third column. We applied the Katz-Bonacich centrality minimization problem with, C = 1, φ C = 20 and for each i, p i = 0.1 and p i = 1. The fourth column describes the utility of the Katz-Bonacich centrality minimization problem. The first observation is that for each network, the constraint ∑ i x * i ≥ 20, is saturated. It follows from the fact that, for each network, the aggregated Katz-Bonacich centrality is bigger than 20. We expect that if we increase p i this constraint will not be saturated anymore. When we look at fig. 1, where the size of the node is proportional to the solution of the Katz-Bonacich centrality minimization problem (x * i for each i), we remark that we do not have a trivial solution like only one node is active or each node has the same centrality.

VI. CONCLUSION AND PERSPECTIVES

The main result of this paper is the equivalence between a linear programming problem and the Katz-Bonacich centrality minimization problem. Once this equivalence is proved, we also describe an application to the control of gossip on Online Social Network.

There is one major follow-up of this work. The extension is to study the Katz-Bonacich centrality minimization problem in an online context, in other words when the structure of the social network changes over the time. The formulation of the problem could be the following: The evolution of the interaction occurs each unit time t ∈ N. Let E(t) the interaction matrix at time t. For each t we assume that E(t) a substochastic matrix. The index p i (t) ∈ [0, 1] denotes the node that the controller will perturbates at time t between node i. The online version of the Katz-Bonacich centrality minimization problem is defined as follow: Known parameters:. Set of nodes I . For each round t = 1, 2, . . .

1) The controller removes nodes by using a control p(t) := (p 1 (t), . . . , p I (t)), 2) simultaneously, the adversary select a matrix E(t) of interaction, ρ(t) and α(t),

3) The controller observe E(t), and received 1 T I (Id Iρ(t)E(t)) -1 1 I α(t), as an instantaneous vector payoffs. In order to solve this problem we can use the theory of online convex optimization techniques [START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multi-armed bandit problems[END_REF].

TABLE I :

 I Summary tableFig. 1: Visualization of the solution of the Katz-Bonacich centrality minimization problem

subject to for each i and each c:

see[START_REF] Jackson | Social and economic networks[END_REF] for definitions of the above spectral centrality measures

https://www.facebook.com/help/210346402339221


A Study of YouTube recommendation graph based on measurements and stochastic tools

Yonathan Portilla †, , Alexandre Reiffers † , Eitan Altman , Rachid El-Azouzi † Abstract-The Youtube recommendation is one the most important view source of a video. In this paper, we focus on the recommendation system in boosting the popularity of videos. We first construct a graph that captures the recommendation system in Youtube and study empirically the relationship between the number of views of a video and the average number of views of the videos in its recommendation list. We then consider a random walker on the recommendation graph, i.e. a random user that browses through videos such that the video it chooses to watch is selected randomly among the videos in the recommendation list of the previous video it watched. We study the stability properties of this random process and we show that the trajectory obtained does not contain cycles if the number of videos in the recommendation list is small (which is the case if the computer's screen is small).

Index Terms-Analysis of recommendation system, drift stability analysis, Youtube

I. INTRODUCTION

Online media constitute currently the largest share of Internet traffic. A large part of such traffic is generated by platforms that deliver user-generated content (UGC). This includes, YouTube and Vimeo for videos, Flickr and Instagram for images and all social networking platforms. Among these platforms, Youtube has become the most popular. Based on statistics available from the website Alexa.com, more than 30% of global Internet users visit Youtube.com per day. Other statistics from htt p : //www.youtube.com/t/press statistics clearly illustrate the previous fact: "Over 800 million unique users visit YouTube each month" and "72 hours of video are uploaded to YouTube every minute". Of course, not all videos posted on YouTube are equal. The key aspect is their "popularity'", broadly defined as the number of views they score (also referred to as view count). This is relevant from a twofold perspective. On the one hand, more popular content generates more traffic, so understanding popularity has a direct impact on caching and replication strategy that the provider should adopt. On the other hand, popularity has a direct economic impact. Indeed, popularity or view counts are often directly related to click-through rates of linked advertisements, which constitute the basis of the YouTube's business model. Hence the revenue model of YouTube is based on a sophisticated advertising scheme. Indeed different types of advertising methods are used in YouTube, for example, "In-video graphical and text advertisements", "post-roll advertising", etc. Extracting incomes in such business models is related to Models for predicting popularity of online content including YouTube videos and Digg stories, are proposed in [START_REF] Cha | I tube, you tube, everybody tubes: analyzing the world's largest user generated content video system[END_REF], [START_REF] Crane | Viral, quality, and junk videos on youtube: Separating content from noise in an information-rich environment[END_REF], [START_REF] Gill | YouTube traffic characterization: A view from the edge[END_REF], [START_REF] Ratkiewicz | Traffic in social media ii: Modeling bursty popularity[END_REF], [START_REF] Chatzopoulou | A first step towards understanding popularity in YouTube[END_REF], [START_REF] Cha | Analyzing the video popularity characteristics of large-scale user generated content systems[END_REF], [START_REF] Richier | Bio-inspired models for characterizing youtube viewcount[END_REF], with the aim of developing models for early-stage prediction of popularity features [START_REF] Szabo | Predicting the popularity of online content[END_REF]. Such studies have highlighted a number of phenomena that are typical of UGC delivery. This includes the fact that a significant share of content gets basically no views [START_REF] Cha | Analyzing the video popularity characteristics of large-scale user generated content systems[END_REF], as well as the fact that popularity may see some bursts, when content "goes viral" [START_REF] Ratkiewicz | Traffic in social media ii: Modeling bursty popularity[END_REF]. Visibility of content is not just of interest to Youtube. It is also of interest to the content consumers and to the content creators. There is a competition between the creators on visibility of their creations. Understanding of how view count of a video is driven by different sources of views is helpful for finding strategies for increasing the number of views of videos. For advertisers and for content providers, this is useful for strategic planning so as to increase the contents' popularity. This is often directly related to click-through rates of linked advertisement.

To achieve this, we will study properties of recommendation lists and their impact on content propagation. Several studies have showed that there exists a strong correlation of view count of a content and the average view count of the videos in its recommendation list [START_REF] Zhou | The impact of youtube recommendation system on video views[END_REF], [START_REF] Cheng | Statistics and social network of youtube videos[END_REF]. Indeed, from different measurement studies, the view count of videos in a recommendation list of a given video tends to match the view count of that video. Cheng et al. have provided different statistics of Youtube and showed that the graph of YouTube's video structure exhibits a small-world characteristic [START_REF] Cheng | Statistics and social network of youtube videos[END_REF].

Zhou et al. have showed the importance of the recommendation system on view count of a video [START_REF] Zhou | The impact of youtube recommendation system on video views[END_REF]. They found that the recommendation system is the source for 40-60% views of a video. Performing several measurement, they have discovered that the position of a video on a related video plays an important role in the click through rate of the video. They have also identified that the recommendation system improves the diversity of video views which helps a user to discover unpopular videos.

Our work compliments these works by quantifying the relationship between a video's view and its related videos (i.e. the videos in its recommendation list). To that end we focus on users that browse through videos according to some random mobility model over the recommendation graph. In this directed graph, videos are nodes, and directed edges connect that node to the videos that appear in its recommendation list. Nodes have some attributes, or weights that may correspond to the view count, or to the total time that the video was viewed, or to the number of likes etc.

We first describe the model associated the recommendation system in section II. Our first goal is to relate the attributes of a node to those of its recommendation graph. In section III, we first describe our dataset. We then study empirical properties of the sequence of weights in a random trajectory of a user in the recommendation model as a function of their mobility model. In particular, we focus on two attributes. The first is the number view count of the video, and the second is its age. To each one of these attributes and every mobility model, the sequence of consecutive attributes on the random trajectory forms a stochastic process which we model as a Markov chain and we study its stability in section IV. We then derive properties related to the stability of the sequence of videos viewed from the stability properties of the Markov chain corresponding to the attribute process. Finally in section V, we provide a theoretical result on the improvement by the recommendation system of the diversity of video views. Indeed, recommender system in Youtube is traditionally based on keyword between videos (tags, title and summary).

II. A MODEL FOR YOUTUBE RECOMMENDATION SYSTEM

We now provide some background on Youtube which has become a key international platform for socially enabled media diffusion. This platform allows not only to share videos, but also to create interaction between users (friends, creators, rating..). It becomes a most attractive and a popular media diffusion with a huge quantity of user-generated content. Our study on recommendation system in Youtube is based on the data sets crawled from Youtube. Here we describe how we collected the data sets.

A. Data on videos

A huge majority of Youtube videos are available to the general public and includes valuables data about the video (a video may not be available if its creator decided to attach to it the unlisted or the private privacy level or if there are copyright issues that do not allow to show the video at a given country). Youtube further proposes a list of recommendation from which the consumer can choose the next video to watch. We collected data sets of videos using our own software developed in JAVA. This tool allows us to collect some view statistic of videos in Youtube as views, titles, tags, ages and recommendation list. A Linear Least Squares Regression (LLSR) is used to adjust the model parameter in order to obtain the minimum error between the model and experimental data.

B. View graph

In this section we construct a graph based on Youtube recommendation. In particular, we will explore how the view of a video influences the view count of other videos through the recommendation list. Indeed, a user who views a video u may view a video v from its recommendation list. In that Fig. 1: Recommendation list in Youtube case, there is a directed edge between u and v (See figure 1).

Let us first introduce some terminology. We consider a connected network G = (V, E), where V denotes the set of nodes with |V | = n, E denotes the set of edges and w : V → R + denotes the view count of the node v. We will now describe how we construct our connected graph. We imagine a random walker on Youtube starting from a video u. After viewing the video u, he selects randomly (with uniform distribution) a video v among top N videos in its recommendation list, and moves to its neighbour. We repeat the procedure again and again. A stochastic (transition) matrix Q = [Q uv ] n×n is used to govern the transition of the random walk process where n is the number of videos in the graph. Q uv is the probability that the transition from video u to video v occurs.

III. STATISTICAL STUDY OF THE RECOMMENDATION

GRAPHS

In this section, we explain how we obtain the influence of recommendation system using our data sets in Youtube. We will study two datasets. In the first one we randomly picked 1000 videos, in the month of july 2012 in Youtube by using our random extraction software. In the second one we crawl Youtube to get NBV IDEOS videos. We focus on two elements of the data. The first element is the view count of a video and the second element is the average view count of related videos recommended by YouTube recommendation system. We believe that the number of videos that we collected for each experiment is enough to capture all information. First, we investigate the relation between the view count of a video and the average view count of its recommendation list. We consider different values of the number N of videos in the list. In practice, the larger screen is, the larger is N. We shall show later that N plays a crucial role on the properties of the excursions over the recommendation graph. A very small N corresponds to list of recommendations viewed over cellular telephones.

In our statistical study, we test two types of models that relate a function of the number x i of views of a video i and the function of views of videos in its recommendation list averaged over N:

• N-videos in which we use the linear regression between

x i and y i , i ∈ {1, . . . , I}, wher I ∈ {1000, NBV IDEOS}.

Here,

y i = 1 N N ∑ j=1 y j i
where y j i is the view count of the j th video in the recommendation list of video i. We thus identify parameters a and b so that y i will be well approximated by ax i + b. a and b are chosen in fact so as to minimize the mean square error of this approximation over all samples.

• N-videos wherein a linear regression is used between log(x i ) and log(y i ). We thus identify parameters a and b so that 1

N N ∑ j=1 log(y j i )
will be well approximated by a log(x i ) + b. a and b are chosen in fact so as to minimize the mean square error of the difference between the expressions over all samples.

A. Study of the data set

The distribution of the dataset according to age and to popularity

The measure of goodness of the linear fit is summarized by the statistical R 2 coefficient. It takes value in the unit interval [0, 1] and the better the fit is, the larger is its value.

In figure 2a, we plot the view count of one video on the X-axis, and the average view count of videos in its recommendation list. We observe that the coefficient of determination R-square is small for all values of N (see fig. 4a) . This indicates that there are important deviations from any approximation of the y i as a linear function of the x i .

On the other hand, in figures 2b-2c, we use a logarithmic scale to plot the view count of one video on the X-axis, and the averaged of the view count of videos in its recommendation list. Both figures 2b-2c show the strong correlation between the view count of a video and the view count of top N videos in its recommendation system.

The first observation is on the monotonicity: the higher the the view count of the related videos in recommendation list of a given video is, the higher the view count of that video is. Hence, Youtube recommendation system will prefer to put videos in recommendation list based on the popularity of the current video, located in the same region of the popularity.

Table 1 shows the quality of the linear regression in the logarithm scaling. The table fits a set of data for several values of N. Our experimentation thus correspond to random walkers that after watching a video, it chooses the next one to see among its N recommended ones with equal probability. This can model space limitation on the screen Fig. 3: The age of one video on the X-axis, and the average age of the top N = 3, 15 of its recommendation list or in the recommendation list which limit the number of recommendations seen by the random walker. It can also model user behaviour in which the top recommendations are preferred. Indeed, in was shown in [START_REF]Google adwords click through rates per position[END_REF] the first position in the recommendation list attracts 39 times more clicks than the 10 th position. Now we further investigate the correlation between the age of a content and the average of age of videos in its recommendation list. Figures 3a-3b show clearly the trend that the higher the average of age of the related videos, the higher the age of the video. This implies that Youtube recommendation will prefer to recommend the videos located in the same region of the age. This means that Youtube's recommendation will not significantly affect the overall videos based on the age of a video and will instead focus more on the same generation of that video. Moreover, Table 4b displays a high regression coefficient which is the additional evidence that the recommendation system has an important

IV. STABILITY AND VIDEO VIEW DIVERSITY

We shall study in this section the stochastic process X n , n ≥ 1 of the attributes of the videos encountered by the random walker. For example, X n can be taken to be the view count or the age of the nth visited video. For simplicity we shall assume that this constitutes a discrete time aperiodic communicating Markov chain (any state can be reached from any other state with positive probability), although this assumption will be relaxed later. We investigate the stability of this Markov chain defined above in order to identify the impact of Youtube recommendation system on the visibility and popularity of videos.

We briefly recall some basic notions in Markov chains. The chain is said to be recurrent if it visits every state infinitely often. It is said to be positive recurrent if for each state x, the expected time between consecutive visits of x is finite. It is said to be transient if for some state x there is a strictly positive probability never to return back to that state. Thus in a transient Markov chain, a state x is only visited finitely often, and after some finite (random) time it never returns to x again. We shall say that X n is stable if it is positive recurrent and that it is unstable if it is not.

We argue that a recommendation system tought to be designed with the objective of having X n communicating and positive recurrent for various reasons. First, it would allow a random walker to return to a video he liked. Secondly, it does not get stuck in a subset of states due to the communicating assumption. The fact that one reaches a state infinitely often guarantees in particular that any video will be discovered by any random walker that stays long enough. Finally, this property has a positive impact on increasing the page rank of the video and thus search engines based on page rank will allow one to find the video quicker.

We next recall the Foster stability conditions for communicating Markov chains. Introduce a positive and increasing function f and a finite set B. Define the drift of the chain at state x as

∆(x) := E[ f (X n+1 ) -f (X n ) | X n = x]
Note that due to the Markov property this does not depend on n. If is called a Lyapunov function.

(i) If sup x ∆(x) is finite and for some ε > 0, ∆(x) < -ε for all x / ∈ B then the Markov chain is stable. (ii) If ∆(x) > ε for all x / ∈ B then the Markov chain is unstable. A sufficient condition for instability is that

E[ f (X n+1 ) | X n = x] ≥ a f (x) + b for b > 0 and a ≥ 1.
From different experiments (see for example Table 4a), we observe that for N = {3, 4, 5} and for all n ∈ N we have

E[log(X n+1 ) | X n = x] < ∞, and E[log(X n+1 ) -log(X n ) | X n = x] > ε > 0 (1)
for some ε > 0 and for all x large enough (larger than some constant K). It follows from Theorem 3 in [START_REF] Foss | Coupling again: the renovation theory[END_REF], that the Markov chain cannot be positive recurrent.

V. DISCUSSION

The instability of the Markov chain X n for N = {3, 4, 5} (which is the case if the computer's screen is small) has several interpretations and consequences. Indeed, by the rapid adoption of smartphone, tablets and e-reader which are characterized by a small screen, our result may explain some results in [START_REF] Zhou | The impact of youtube recommendation system on video views[END_REF] which showed how Youtube recommendation can improve the view diversity and help users to discover videos.

The process X n which we studied in this paper can be interpreted as a random walk on the recommendation graph, where X n corresponds to the number of views of the nth viewed video. The n + 1 video viewed is chosen uniformly from the recommended videos of the previously viewed video. We identified in this paper instability of the process X n as a function of N (size of recommendation graph). The instability was obtained by establishing (through experiments) that the related drift is positive.

How sensitive are the results to the Markovian assumption on X n ? Note (by taking expectations in (1)) that as n → ∞, E[ f (X n )] tends to infinity. This type of instability result does not require X n to be a Markov chain. Some of the stability results of X n do hold even when X n is not a Markov chain [START_REF] Borovkov | Ergodicity and stability of stochastic processes[END_REF].

Note that both for stability as well as for instability, the drift condition is required to hold for all large enough states, i.e. for all x > K for some positive K. Instability of the process means that the number of views of the nth video tends to grow without bound. In practice however, there is some finite bound on the number of viewed videos (the bound is the number of views of the most viewed video). Thus, what instability means in practice is that the number of views grows until it is in some neighbourhood of that bound. For this to occur, we expect that it is sufficient to establish that the drift is bounded below by a positive number within some large integral x ∈ [K 1 , K 2 ].

VI. CONCLUSION

We have shown in this paper through measurements the relation between the number of views of a video and the number of views of the videos in its recommendation list averaged over the first N slots in this recommendation list. We considered not only relations between the numbers of videos viewed but also between functions of these numbers. More precisely, we established the relation between a function of the number of views of a video and the function averaged over the number of views of videos in the recommendation list of the video.

We show good fits of a linear relation between the number of views of a video and the number of views averaged over its recommended videos when considering the log-log scale. The fit was not good when considering a linear scale.

Based on this relationship we explored the evolution on number of views that a random walker sees when travelling through recommendation graph. We showed in particular that if the number of videos in the list is small, the number of views tends to increase along the trajectory of random walker. We conclude that the random trajectory is not sable which means that the trajectory doest not contain cycles.

For showing instability, we used Foster Criteria where we approximated conditional expectations by conditional averages. Note that Foster Criteria is valid independently of the value of the R 2 parameter.

This study was restricted to Youtube and based on a dataset that reflects Youtube's protocol at a given time (july 2012). However the methodology is valid for other recommendation systems as well or for newer versions of Youtube recommendation.

Fig. 2 :

 2 Fig. 2: The view count of one video on the X-axis, and the average of the logarithmic views of the top N = 1, 2, 3 of its recommendation list

Fig. 4 :

 4 Fig. 4: Regression coefficients and coefficient of determination R-square for different values of N for the age study

Table 2

 2

		regression coefficients R2
	1 videos days	0.976898	0.918683
	2 videos days	0.932103	0.882182
	3 videos days	0.931216	0.879587
	4 videos days	0.906025	0.870077
	5 videos days	0.906025	0.870077
	8 videos days	0.780917	0.776079
	10 videos days 0.742248	0.713315
	15 videos days 0.723398	0.685777