Camille Roth
email: roth@cmb.hu-berlin.de

Antoine Mazieres
email: mazieres@cmb.hu-berlin.de

Telmo Menezes
email: menezes@cmb.hu-berlin.de

Antoine Mazières

Tubes & Bubbles Topological confinement of YouTube recommendations

Introduction

The effect of algorithms in the filtering of information and interactions in online platforms is currently at heart of a very active debate. The question of whether algorithmic recommendation fosters the serendipity of contact and content discovery or not is of particular interest. On the one hand, a growing literature aims at empirically comparing what happens when users do rely, at least in part, on the output of some recommendation algorithm vs. when they do not. This kind of scientific endeavor generally need not venture into knowing or reverse-engineering which principles drive these algorithms. Contrarily, perhaps, to intuitions related to the popularization of so-called "filter bubbles", several recent studies appear to show that algorithmic suggestions do not necessarily contribute to restrict the horizon of users.

Be it in terms of interaction or information consumption, users do not seem to be proposed less diversity content in regard to what would happen in the absence of recommendation [START_REF] Nguyen | Exploring the filter bubble: the effect of using recommender systems on content diversity in Proceedings of the 23rd international conference on World wide web[END_REF][START_REF] Bakshy | Exposure to ideologically diverse news and opinion on facebook[END_REF][START_REF] Aiello | Evolution of ego-networks in social media with link recommendations[END_REF][START_REF] Datta | Changing their tune: How consumers' adoption of online streaming affects music consumption and discovery[END_REF][START_REF] Roth | Algorithmic distortion of informational landscapes[END_REF][START_REF] Haim | Burst of the filter bubble? effects of personalization on the diversity of google news[END_REF] or using distinct recommendation approaches [START_REF] Bessi | Users polarization on facebook and youtube[END_REF][START_REF] Möller | Do not blame it on the algorithm: an empirical assessment of multiple recommender systems and their impact on content diversity[END_REF], except for what stems from explicit personalization (i.e. explicitly chosen [START_REF] Thurman | The future of personalization at news websites[END_REF], or self-selected [START_REF] Borgesius | Should we worry about filter bubbles?[END_REF], by users [START_REF] Dylko | The dark side of technology: An experimental investigation of the influence of customizability technology on online political selective exposure[END_REF]). Put shortly, the picture that seems to emerge is that filter bubbles, and possibly echo chambers, mostly occur when platforms recommend content based on explicit personal preferences (e.g., by subscribing to channels, specifying lists of interests, etc.) rather than implicit traces (either at the user-level or aggregated from the activities of all users).

On the other hand, at a more downstream level, user reactions to algorithmic curation are an equally important issue. The current state of the art exhibits mixed results and user populations may not be deemed to be homogeneous. For one, users may variously seek diversity [START_REF] Munson | Presenting diverse political opinions: how and how much in Proc[END_REF], be variously responsive to recommendation [START_REF] Nguyen | Exploring the filter bubble: the effect of using recommender systems on content diversity in Proceedings of the 23rd international conference on World wide web[END_REF], use it for various purposes [START_REF] Chen | Speak little and well: Recommending conversations in online social systems[END_REF] or have various expectations about it [START_REF] Rader | Understanding user beliefs about algorithmic curation in the facebook news feed in[END_REF] -in these respects, the "average user" does not really exist. Users however seem to be generally sensitive to social signals and goaded by the indication that some content is popular or appreciated [START_REF] Salganik | Experimental study of inequality and unpredictability in an artificial cultural market[END_REF][START_REF] Steck | Item popularity and recommendation accuracy in[END_REF][START_REF] Messing | Selective exposure in the age of social media: Endorsements trump partisan source affiliation when selecting news online[END_REF] whereas they are weakly sensitive to content-based signals, for instance if they are informed of the diversity of what they are currently consuming [START_REF] Munson | Encouraging reading of diverse political viewpoints with a browser widget in[END_REF]. Such studies generally require the design of sophisticated experimental protocols or privileged access to private company data. On the whole, there appears to be no blanket answer to the complex interplay between the structure of proposed recommendations and user attitudes towards them.

In this context, while YouTube has become a key content provider (being the second most popular site as of 2019), the influence of its recommendation system on user navigation dynamics and exploration diversity has been little studied (even though it is already a current news topic, see e.g., [START_REF] Nicas | How youtube drives people to the internet's darkest corners[END_REF][START_REF] Tufekci | Youtube, the great radicalizer[END_REF]). The present contribution intends to bridge this gap by focusing on the global, platform-level and thus non-personalized recommendations of YouTube. Indeed, irrespective of the personalized, user-centric adjustments to recommendation, studying platform-level suggestions shall provide an overview of the forces that are susceptible to apply globally to all users. As such, characterizing a possible confinement on these recommendation landscape constitutes a primary step toward characterizing confinement as a whole.

On content-sharing platforms, a model of user behavior toward recommendations may be construed as the navigation on a recommendation graph where nodes are items (such as videos) and links are recommendation suggestions, which users may or may not follow. Understanding the heterogeneity of the subsequent navigation topologies is crucial to appraise possible confinement processes. The issue of potential navigation topology has already generated several key studies in other platforms such as Twitter or Facebook, especially with respect to polarization and fragmentation, yielding convincing graph typologies (see, inter alia, [START_REF] Conover | Political polarization on twitter in Fifth international AAAI conference on weblogs and social media[END_REF][START_REF] Barberá | Tweeting from left to right: Is online political communication more than an echo chamber?[END_REF][START_REF] Jacobson | Open media or echo chamber: the use of links in audience discussions on the facebook pages of partisan news organizations[END_REF][START_REF] Vicario | Mapping social dynamics on facebook: The brexit debate[END_REF][START_REF] Garimella | Quantifying controversy on social media[END_REF]). By contrast, the state of the art relevant to YouTube's algorithms appears to have essentially focused on their technical underpinnings [START_REF] Davidson | The youtube video recommendation system in Proceedings of the fourth ACM conference on Recommender systems[END_REF], their improvement [START_REF] Covington | Deep neural networks for youtube recommendations in Proceedings of the 10th ACM conference on recommender systems[END_REF] or their impact on consumption and audience statistics [START_REF] Zhou | The impact of YouTube recommendation system on video views in Proceedings of the 10th[END_REF][START_REF] Park | A data-driven study of view duration on youtube in Tenth International AAAI Conference on Web and Social Media[END_REF][START_REF] Zhou | How youtube videos are discovered and its impact on video views[END_REF]. To our knowledge, very few academic works appear to focus on the general structure of the browsing network: for instance, [START_REF] Cheng | Statistics and social network of youtube videos in 2008 16th Interntional Workshop on Quality of Service[END_REF] describes the potential navigation dynamics in relation to audience or macro-level features, while [START_REF] Airoldia | Follow the algorithm: An exploratory investigation of music on youtube[END_REF] principally use the recommendation graph as a data source for extracting crowdsourced content taxonomies.

The paper is broadly organized as follows. We first carry out an instrumental step by exploring how video recommendation sets are being provided by the platform in the absence of personalization. This enables us to devise a robust protocol of collection of node-centric recommendation graphs. We then analyze the shape of the graphs that are thus generated and their various confinement features. Most importantly, we discuss them in relation to various intrinsic properties of videos (especially in terms of popularity, consensus, or topics), both in a static and longitudinal manner.

Node-centric analysis of recommendations

Most YouTube videos include a tab featuring a list of suggested videos. How user-specific these suggestions are depends on whether users are logged in or share cookies and other identification information. While some suggestions seem to be clearly user-centric and depend on user navigation history (generally labeled by YouTube as Recommended for you), others appear to be node-centric, i.e. stemming from a pool of suggestions attached to the video itself, independently of the user history. In this latter case, suggested videos most likely depend on inferences made from platform-level behavioral traces accumulated over an unknown pool of users and an unknown period of time. This engenders a dichotomy between user-specific suggestions and what may be called a "mean field" of user-independent suggestions. We aim at characterizing this mean field, while leaving personalized recommendation outside of the scope of this paper. We do not aim at all at reverse-engineering the way node-centric suggestions are being computed by the platform, but rather wish to understanding the navigation landscape that YouTube algorithms contribute to shape. In other words, we take for granted how these recommendations are built and focus on characterizing this landscape. Users are admittedly exposed to both types of suggestions, yet we contend that the analysis of the mean recommendation field is already likely to shed light on the attraction forces that are due to node-centric suggestions, all other things being equal.

Data

In practice, we thus study user-independent suggestion lists attached to videos by creating non-persistent, anonymous sessions with simple HTTPS requests on a given page from a set of about a hundred IP addresses located in the region of Paris, France. We first define a diverse set of YouTube videos by arbitrarily selecting five distinct sets of sources which feature links to such videos. Two of these sets aim to capture mainstream use by focusing on "Top" videos listed on Reddit and Wikipedia. The first set, denoted as "Reddit top" consists of the YouTube URLs contained in the most votedup posts of 20 of the most subscribed subreddits (i.e., forums) listed on redditlist.com. The second set gathers the 5 most viewed videos from the 50 YouTube channels listed on the "List of most-subscribed YouTube channels" Wikipedia page [START_REF]List of most-subscribed YouTube channels[END_REF], which we denote as "Wikipedia Top". This yields a diverse range of popular content mainly categorized by YouTube as "Music", "Entertainment", "Howto & Style" or "Science & Technology". The remaining sets focus on the activity surrounding the 2019 European Parliament election. While not as popular or representative of the use of YouTube, focusing on this context also contributes to reach political and election-related content. More precisely, the third set, denoted as "Twitter", consists of the most shared YouTube video links found on the micro-blogging platform over the 3 weeks leading to the 2019 European Parliament Elections and associated with a set of 22 hashtags that were manually selected to cover discussions related to the elections in 4 European languages: English, French, German and Italian (such as #EuropeanElections2019, #Europeennes2019, #Europawahl2019, #elezionieuropee, among others). The fourth and fifth sets are based on channels of political parties engaged in the 2019 European elections in France and in Germany. In Germany, we focus on the 13 political parties that obtained a seat after the vote. In France, we equivalently consider the 13 main parties in descending order of obtained votes. In both cases, we identify the ten most viewed videos on each channel. We denote these seed sets respectively as "Political DE" and "Political FR". This political selection yields a more homogeneous set of videos than the mainstream ones: the three subsets consist of content that is principally categorized by YouTube as "News & Politics".

Table 1 gathers basic statistics for these seed sets. Server errors, videos deleted during the data acquisition process and a handful unidentified crawling and parsing errors explain the discrepancy between the number of videos targeted for each set and the number of actually extracted seeds. While selecting IDs in a purely random manner across the platform could yield a more uniform sampling of video IDs on YouTube, it could bear the potential risk of overemphasizing insignificant videos with an extremely limited audience (using a protocol similar to [START_REF] Park | A data-driven study of view duration on youtube in Tenth International AAAI Conference on Web and Social Media[END_REF], we verify that this would indeed be the case: a selection of 50 such random videos yields a median number of views of 115, far below the seed categories considered here).

Each HTTP request for the recommendations attached to a YouTube video returns a set of a maximum of 20 suggestions (in practice, exactly 20 suggestions four fifth of the time, and 19 about a fifth of the time). Our first conception of a model of a user navigating through these node-centric recommendations would thus consist of a walk in a directed recommendation graph whose nodes all have an out-degree of 19-20. However, for a given video, this set appears to fluctuate significantly from a request to the other, bearing the risk of exploring a very unstable and thus unreliable recommendation graph: examining the temporal features of these suggestions is thus a prerequisite to construct such a graph.

To this end, we proceed with a long crawl centered on seeds and aimed at understanding the variation and potential evolution of suggestion sets across successive requests. Along the way, we also collect video metadata such as the number of views and appreciation statistics: number of thumbs up (likes), down (dislikes). For each seed, we carry out a total of 2,000 requests at a regular average interval of about 10 minutes, thus covering a bit less than two weeks of sampling. This yields a node-centric time series of sets of suggestions.

Stability of a recommendation plateau

We first compute the frequency of occurrence and recurrence aggregated over a certain number of requests R in order to appraise the stability of suggestions and thus of the related network. Irrespective of the sampling duration, yet even more so for shorter time spans, a "plateau" of consistently highly frequently suggested videos quickly emerges (several of them are often recommended nearly 100% of the time), beyond which occurrence frequencies decrease steeply. The size of this plateau may be dynamically determined through a simple change-point analysis restricted to suggestions appearing at least, say, 1% of the time. This lower bound does not significantly change the position of the detected change point but is needed to prevent the very flat long tail of the distribution to interfere with the detection process. The plateau is generally found to feature between around 20 and 30 videos (µ = 23.6, σ = 5.15). Nonetheless, its erosion over time suggests the existence of a slow renewal process. In the longer term, the ordered distribution of occurrence frequencies progressively takes the shape of an heterogeneous distribution apparently exhibiting a power-law-like tail with a cut-off. In figure 1b, we gather the frequency of occurrence of videos with respect to their rank, for various durations of aggregation. For instance, we see that the tenth most frequent suggestion after R = 200 requests (i.e. over about 33.3 hours, red curve) appears about 70% of the time. For all sampling durations R = 20, 200 and 2000, and all the more for the shorter ones, occurrence frequency is relatively high up to the ∼20th most frequent suggestion and then markedly decreases afterwards. This suggests that exit routes leaving from a given seed and, thus, the recommendation graph induced by mean-field suggestions, are rather stable when observed on a relatively short time span of a couple of days.

To further qualify this observation, we turn to the study of the lifespan of suggestions. For a given seed video, we define the occurrence frequency of a suggested video s over a sliding window of r sampling requests as θ(s). We fix r = 20, consistently with the above-observed minimal amount of requests needed to observe a robust plateau. We then denote as T (s) the lifespan of s, defined as the difference between the first and the last moment where its average occurrence frequency θ(s) goes above a certain threshold. Put simply, the lifespan of a suggestion is such that it appeared above this threshold frequency at two moments separated by such a length of time. This does not mean, however, that it appeared consistently above this threshold over that length of time. We plot the numbers of suggestions having a lifespan of at least T (instead of exactly T , since we ignore what happens before or after we started collecting data). Figure 1a shows the distribution of lifespans for various thresholds: θ ≥ 0% corresponds to suggestions appearing at least once (i.e. at all), whereas θ ≥ 90% focuses on very dominant suggestions which appear at least 90% of the time over their lifespan and thus principally belong to the plateau. While this graph exhibits a relatively large number of short-lived suggestions, it also demonstrates that the plateau videos Figure 1: (a). Number of recommendations with a lifespan T ≥ R for various thresholds θ ≥ 0%, θ ≥ 50% and θ ≥ 90%} (averages are central lines, along with their 95%-confidence intervals). A lifespan of T means that a recommendation appeared at least θ% of the time over a sliding window of r = 20 successive requests, at two distinct moments at least T requests apart. Inset: average presence of a suggestion over its lifespan as a function of the lifespan (again for the three thresholds). (b). Recommendation lifespans after R sampling requests, ordered by rank, averaged over all seeds. Inset: zoom on the inflection area typically occurring around the 20 th suggestion for R = 20. are likely to be present for a significant time. This is all the more as suggestions with higher lifespans also appear more frequently across their lifespan and not just at its extremities, as demonstrated by the inset in figure 1a.

This bears two conclusions when considering the recommendation graph induced by suggestions. First, focusing on the plateau would suffice as it concentrates most of the density of suggestion occurrence. This plateau has a modal distribution size and thus entails a network with a modal, homogeneous degree distribution -a quite peculiar object with respect to classical web topologies, which are generally heterogeneous. Second, this graph should be relatively stable in the short term, which substantiates the idea that a graph exploration protocol spanning over a short period would plausibly approximate well the recommendation graph faced by users during a navigation session.

Induced recommendation graphs

For each seed video, we now recursively crawl suggestions belonging to the above-evoked plateau computed by changepoint analysis for 20 requests. We repeat this until reaching a depth of 3, which constitutes the horizon we consider for recommendation graphs. In other words, the graph induced by a seed video contains its direct suggestions and two levels of indirect suggestions, as well as all the links between these nodes. See an illustration in figure 2. Choosing an arbitrary depth of 3 is a trade-off between sampling frequency (to keep a reasonable bandwidth with YouTube servers) and sufficiently deep exploration of the various graphs. They are each collected in about 58.2hr (±13.6) which roughly remains within the plateau stability window (this corresponds to the time elapsed after about 350 requests in figure 1a). Graphs contain an average of 3179 ± 1258 nodes and 7263 ± 2233 edges. We crawled plateaus from nodes up to depth 2 (i.e., for around 89.0k videos) and thus visited nodes up to depth 3 (reaching a total of 540k videos).

Graph entropy, diversity and confinement

We are specifically interested in exploring confinement within recommendation graphs. To this end, we devised two metrics. The first one is based on random walks, which play the role of a very simple and abstract model of user navigation (e.g., [START_REF] Garimella | Quantifying controversy on social media[END_REF], to describe graph families). Random walks always start from ego (the seed video of the induced recommendation graph), and terminate when they reach a length of 20. Results were not very sensitive to this constant, unless it is so small that meaningful walks can no longer be captured (< 5). Other plausible random walk strategies include a restart once revisiting a node, or a restart once revisiting ego. Again, we found very similar results under such strategies, so we settled for the simplest one. We measure the diversity of visited nodes by computing the information entropy of the set of frequencies of visits. For one random walk, we refer to this measure as η. For each graph we perform 100, 000 random walks -again, a value chosen to be high enough so that the results are stable across runs. The mean random walk entropy (η) gives us an estimation of the confinement of an idealized user exploring the recommendation graph from ego. The lower the entropy / diversity, the higher the confinement. Another metric that we consider is the number of nodes in a recommendation graph (N ). This configures a direct measure of the number of video recommendations that can be accessed from ego while not exceeding our maximal depth, independently of the probability of a user reaching a given node. Given that all out-degrees are This process is repeated for all nodes at depth 1 in parallel, thus defining depth 2, and again with nodes at depth 2. In the end, the recommendation graph induced by the seed contains nodes at depths 1 and 2 and potentially includes links towards already explored nodes, i.e. at depth 0 (seed), 1 (seed's direct neighbors) and 2 (seed's indirect neighbors). There are on average 23.6 nodes at depth 1 (σ = 5.15), 325 nodes at depth 2 (σ = 98.23) and 2830 nodes at depth 3 (σ = 1160). Some elements are shaded simply to indicate that we do not represent all nodes and links on this figure for the sake of clarity.

roughly equal to 20 and maximal depth is 3 for all graphs, N becomes indeed smaller when the set of targets accessible from the graph exhibits redundancy. To summarize, the first metric measures the propensity for diversity from the perspective of an idealized user following recommendations, and is determined by the topology of the graph. The second metric measures the global potential for diversity of the graph, independently of user behavior, and is simply determined by the size of the set of recommendations up to a certain depth.

In figure 3 we show that the two metrics are negatively correlated (ρ = -0.71). This is somewhat counterintuitive: it means that the more diverse the mean random walk is, the less diverse the graph is, overall. The dots in the scatter plot are colored according to the number of views of ego on a log scale. The darker the dot, the more views ego has. This helps illustrate another interesting fact: number of views are positively correlated with mean random walk entropy (ρ = 0.36) and negatively correlated with the number of nodes in the graph (ρ = -0.44). All of these correlations have a p-value < 0.0001. It appears that, as videos receive views, their overall recommendation graphs contract, becoming significantly smaller in number of nodes, while the diversity of the mean random walk increases. We first provide illustrative visualizations of three sample graphs, corresponding to the closest graphs to the two extremes and the middle point of the regression line. These sample graphs provide a preliminary intuition of how topology changes across the spectrum defined by the correlation line.

Higher random walk entropy thus corresponds to smaller graphs, as well as denser graphs: there is a strong correlation between η and 〈k〉, the average degree of the graph (ρ = 0.82). Graph contraction goes with increased connectivity -in the sense that everywhere is more accessible from everywhere else: even if the number of potentially accessible videos gets smaller (as graph size N decreases), the number of actually accessible videos increases (as further exemplified by the very strong correlation between N V and η). Put differently, graph contraction nevertheless results in more isotropy in a smaller space: graphs with higher entropy lead to more videos being visited on average (higher N V ) whereas they stem from a smaller potential selection (smaller N ).

Furthermore, we could confirm that graphs with higher η (i.e., more diverse random walks while having a smaller N ) do also qualitatively appear to users to be more confined semantically. To substantiate this empirically, we designed a simple human-based protocol. We produced three sets of 20 seed videos which are closest respectively to each extreme and the middle point, similarly to the above procedure. We recruited six participants: each of them received plateau recommendations for 20 seed videos randomly selected among the 60, without knowing anything about them. We then asked them to tell us, for each seed, whether plateau videos are similar to one another or not, on a scale of 5 stars, from most similar (*****) to least similar (*). We gathered the aggregation of their subjective evaluation of the semantic confinement of plateau videos in figure 4. We see that region 1 videos were perceived as most confined, while region 3 videos were seen as least similar, thus confirming a link between η and semantic confinement.

Confinement and seed properties

To expand our empirical exploration of confinement, we consider a number of other metrics. For the seed videos, we consider their age in seconds (a), their number of likes (l ) and dislikes (d ), and the number of subscribers (s) of the channel that they belong to. For the recommendation graphs, we apply the same random walk strategy to measure confinement or diversity in terms of video authors (η a ) and categories (η c ), as provided by YouTube.

In figure 5 we present the correlations found between the above-mentioned metrics as well as the two original diversity metrics (η and N ) and the number of views (v). It can be observed that all metrics that correspond to explicit user actions (v, l and d ) are highly inter-correlated, and also highly correlated with the number of subscribers (s) of the channel of the seed video, hinting at an audience effect. To evaluate consensus around a video, we also derive from l and d a contentment index (c), computed as the log of the ratio of the number of likes (plus one, for consistency reasons regarding the log) over the ). There are generally more likes than dislikes and the opposite happens in about only 0.6% of the cases. Interestingly, this index is at best weakly correlated with explicit actions, thus denoting an intrinsic property of videos. As for the two extra random walk entropy measures, we find that unlike η, η c is positively correlated with N (ρ = 0.45), and that η a is only very weakly correlated with N (ρ = 0.14). The mild positive correlation between η c and N is already hinted at by the category coloring of the sample graphs in the lower panel in figure 3. As already mentioned, mean number of distinct visited nodes per random walk (N v ) and mean degree (〈k〉) are very strongly correlated with η. Finally, we see that age shows close to no correlation with any of the metrics, except for a weak correlation with v (ρ = 0.27).

A plausible interpretation for the interplay between random walk diversities (especially η and η c ), recommendation graph size (N ) and number of views (v), arises from modeling the recommendation engine as a knowledgediscovery process. By viewing a video, the user provides empirical data on the probability of relatedness of the video being watched and all the videos the user has watched before. Of course, there are certainly myriad implementation details on how different signals and pieces of information about the user and the video are taken into account to tweak the recommendation process. Here we are not interested in reverse-engineering a given recommendation engine, but instead in using empirical data to try to uncover more general dynamics from a user's perspective. This is of particular interest to understand how a generic recommendation engine may mediate the exploration of a given cultural space by human actors. Independently of the details, it appears trivial to assume that users viewing videos also provide a connection between this video and the videos previously seen by them. The observation that the age of a video has almost no correlation with any of the other metrics goes in favor of this interpretation: the dynamics of the system appears to be dominantly driven by the actions of its users.

This standpoint invites us to take the number of nodes in the recommendation graph as an expression of uncertainty. The user is given more choices, but these choices lead to more constrained paths. As a video receives views, and so knowledge about relatedness of this video to other videos in the system increases, recommendations become possibly more focused: smaller in overall number, but more inter-related between themselves, and thus further constraining the user in a general sense, while providing a more diverse navigation path, in terms of distinct video IDs, within this more constrained realm. This interpretation is given further credence by the fact that, even though random walk video diversity η increases with N , random walk category diversity η c decreases. In other words, the user is exposed to a higher diversity of unique videos on a less diverse set of topics.

Confinement and transitions

We dig further this notion of topical confinement by focusing on the node level and especially the navigations induced by jumping from a video to another one. More precisely, for each node that appears in any crawl, we compute the outgoing transition probabilities for immediate recommendations i.e., we examine dyadic directed links from a node to the members of the plateau found for that node. We distinguish three types of features related to topics, on the one hand, and to explicit user actions, on the other hand; all of which are linked to some intrinsic property of a seed video (semantics, popularity, consensus):

• topical categories, found in the meta data of the respective videos. We focus on the six top categories in the whole data set (News & politics, Entertainment, Music, People & Blogs, Science & technology, Howto & Style). YouTube provides for many other possible categories which each appear less than a dozen times here, so we gathered them as "[Other]".

• contentment indices, defined as before as the log of the ratio of likes over dislikes. Since negative values are rare, we gather them into a single category denoted as "negative". Integer ranges strictly above 4 are also strongly underpopulated (less than a dozen of occurrences each) and are, again, gathered as "[Other]".

• number of views, binned as quartiles whose boundaries are {143k, 960k, 5.31m} views.

In figure 6, we show the likelihood of jumping from a video with some property to a recommended video of the plateau with some property as transition matrices. Results are aggregated over all nodes appearing in the various seed-centric crawls. For one, it appears that topical categories are also generally topological categories, even though we observe large variations across topics: from "Music" which is massively self-reinforcing, to "People & blogs" which rather redistribute users toward other topics, especially "Entertainment". The effect of "contentment" displays a quite different picture. There are few negatively rated videos and contentment typically ranges between 1 and 3. Yet, there is also a tendency to redistribute users toward videos which are more positively rated so, in a sense, the recommendation landscape does not confine users into controversial areas.

Views follow a rather automorphic tendency where, irrespective of the origin quartile, recommended videos generally exhibit the same order of magnitude as the origin video. This effect is particularly strong for the most viewed videos. As such, the recommendation landscape does not seem to push viewers of less viewed videos towards most viewed videos. Furthermore and similarly, mainstream videos do not appear to forward users towards less viewed videos, which seems to be likely to induce a reinforcement mechanism in these areas, opposite to the conclusions of [START_REF] Zhou | The impact of YouTube recommendation system on video views in Proceedings of the 10th[END_REF]. One may suggest that we just observe here the result of an a posteriori redistribution mechanisms where videos recommended from the most viewed ones incidentally garner views and end up in the highest quartile as well. This possibility is however invalidated by the computation of these transition matrices restrained to newly appearing videos only i.e., videos that were not part of the plateau when collecting recommendation graphs (see below): these matrices do exhibit exactly the same patterns as the ones shown on figure 6.

In other words and to summarize, following meanfield recommendations, users are incited (1) to navigate within the same topical category, especially so for musical and political/news videos, (2) to remain in sets of videos which have rather comparable numbers of views, especially so for mainstream videos, and (3) to go towards more consensual videos, to a lesser extent when videos are moderately consensual.

Evolution of recommendation graphs and origin of novelty

We previously observed that recommendation sets attached to a seed video slowly evolve with time. New suggestions appear in the plateau over time. We may ask in which direction does the introduction of novelty in recommendation sets alter the picture that we sketched so far and, in particular, where do new suggestions come from and what percentage of them stems from inside vs. outside the known recommendation graph. Put differently, is novelty really novel? To check this, we consider as novelty the new plateau suggestions for seed videos appearing at the end of the long crawl i.e., R = 2000 requests after the recommendation graph has been collected. We first notice that percentages vary greatly across seed videos, as shown on the left panel in figure 7: most plateaus nevertheless exhibit at least a third of novel videos, with an average of about 58%. However, many of these novel recommendations can be found not far in the recommendation graph, at depth 2 or 3. In other words, a significant portion of suggestions at R = 2000 come from inside the known graph at R = 0 (almost four in five): reinforcement is also at work here, in the sense that new suggestions are either direct or indirect neighbors.

Similarly, we could also verify that transitions matrices restricted to novel recommendations are of the same nature as those which were observed in figure 6: the aggregated matrices look almost indistinguishable from the original matrices (we thus do not shown them here).

Concluding remarks

This work was focused on recommendation graphs extracted from YouTube. Two types of findings were attained: firstly about the temporal dynamics of the mean- field recommendations provided by the platform for a given seed video, and secondly about the configuration of local recommendation graphs centered around seed videos, especially in regard to confinement and diversity. The former does not aim at reverse-engineering: it is purely instrumental to the purpose of the latter. In this respect, we could exhibit a plateau of highly frequently suggested videos and characterized this phenomenon statistically, both in terms of size and duration. This led to an exploration and retrieval protocol that is both computationally feasible and leads to observables -the recommendation graphs -with well-justified and empirically grounded boundaries. Recommendation graphs are, for one, a peculiar sort of networks, with a modal degree distribution.

In turn, the analysis of these graphs according to several metrics, notably measures of confinement, led to a better understanding of recommendation dynamics, including its interaction with users. In a nutshell, be it in topological, topical or temporal terms, the landscape of what we call mean-field YouTube recommendations generally exhibits confinement. However, we could also show that this claim must be nuanced in various directions.

• First, recommendation graphs exhibit a wide range of values of entropies: some graphs are more confined or confining than others. Counter-intuitively, higher entropies (in terms of navigation) are associated with lower diversity (in terms of distinct number of accessible videos). This hints at a dichotomy where some seed videos are at the root of an isotropic navigation (higher entropy) in a more limited space of videos (lower size).

• Second, we could demonstrate that higher entropies are found for seed videos with a higher number of views. We hypothesized that a higher popularity means that more information could be collected and thus plausibly enabled the platform to refine and in passing contract the associated recommendation graph. This contributes to hint at a dynamic of increasing confinement driven by user activity.

• Third, we exhibited the existence of confinement in topical terms (categories are endogenous), temporal terms (seemingly new recommendations are not to be found too far in the recommendation graph), popularity terms (high view videos transition to high view videos, keeping in mind the correlation between the number of views and topological confinement), but not in contentment terms.

Future work should certainly appraise a variety of other modes of recommendation (such as personalized suggestions), other types of behavior (such as organic navigation, whereby users search for videos by themselves) and a mix thereof (such as browsing on subscription-based channels). On the whole, the analysis of the graphs we extracted nonetheless demonstrate the diversity of navigation anisotropy on YouTube in a variety of dimensions. They also suggest that the most confined graphs i.e., potential bubbles, are organized around videos that garner the highest audience and plausibly viewing time. Admittedly, our work could help devise algorithms that make users aware of their possible confinement, in line with [START_REF] Resnick | Bursting your (filter) bubble: Strategies for promoting diverse exposure in CSCW '13 Companion[END_REF] and [START_REF] Ekstrand | Letting users choose recommender algorithms: An experimental study in[END_REF]. While our results further indicate that it is difficult to provide a binary answer to the question of confinement on this platform, they appear to nuance the emerging picture in the literature that implicit recommendation has a neutral or even horizon-expanding role.

3 Figure 2 :

 32 Figure2: Illustration of the recursive crawl focused on a given seed video. Recommendations are crawled for the seed until a plateau may be estimated, which defines the direct neighbors of the seed and a set of nodes at depth 1. This process is repeated for all nodes at depth 1 in parallel, thus defining depth 2, and again with nodes at depth 2. In the end, the recommendation graph induced by the seed contains nodes at depths 1 and 2 and potentially includes links towards already explored nodes, i.e. at depth 0 (seed), 1 (seed's direct neighbors) and 2 (seed's indirect neighbors). There are on average 23.6 nodes at depth 1 (σ = 5.15), 325 nodes at depth 2 (σ = 98.23) and 2830 nodes at depth 3 (σ = 1160). Some elements are shaded simply to indicate that we do not represent all nodes and links on this figure for the sake of clarity.

3 Figure 3 :

 33 Figure 3: Induced recommendation graphs and sample visualizations. The three sample graphs (b), (c) and (d) are the closest ones to the three points indicated in the regression line of plot (a). Nodes (and adjacent edges) are colored according to the category of the video they correspond to.

Figure 4 :

 4 Figure 4: Human evaluation of confinement. Plateau recommendations for seed videos stemming from region 1 (largest entropy η) are generally perceived as most similar (five stars), while the opposite holds for region 3. Region 2 appears as a middle way.

Figure 5 :

 5 Figure 5: Pearson correlations between various recommendation graph metrics. Asterisks indicate significance: *** for P < 0.0001, ** for P < 0.001, * for P < 0.01.

Figure 6 :

 6 Figure 6: Recommendation transition matrices for all nodes, with respect to topical categories (left), contentment index (middle) and quartiles of numbers of views (right).

Figure 7 :

 7 Figure 7: Provenance of new suggestions for seed videos. Left: Distribution of the percentage of novelty: percentage of plateau recommendations which are new at the end of the long crawl (after R = 2000 requests) vs. its beginning. Middle: Distribution of the percentage of such novelty which could already be found deeper in the recommendation graph at the beginning of the crawl. Right: Average, over all seeds, of the provenance of plateau recommendations, with respect to their position in the recommendation graph. Error bars indicate standard deviations.

Table 1 : Seed categories and basic statistics.

 1

	Seed set	Seeds		Views		Top categories ≥ 10%
			min median	max	(using YouTube labels)
	Reddit Top	178	2,102	1,595k	228m Entertainment (15.7%), Science & Technology (12.9%), Peo-
						ple & Blogs (12.9%), Howto & Style (11.8%), Music (10.1%)
	Wikipedia Top	161	528,159 91,430k 4,242m Music (34.8%), Entertainment (22.4%)
	Political DE	73	299	111k	1.25m News & Politics (100%)
	Political FR	88	116	33k	0.8m News & Politics (86.4%)
	Twitter Top	184	20	10k	34m News & Politics (68.5%)

Acknowledgements

We are grateful to Katharina Tittel for her participation in the Twitter data set perimeter definition, and to Lucie Lamy, Serge Reubi and Ayşe Yuva for their kind contribution to the humanbased confinement evaluation step. This paper has been partially realized in the framework of the "Algodiv" grant (ANR-15-CE38-0001) funded by the ANR (French National Agency of Research) and the "Socsemics" Consolidator grant funded by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No. 772743).


Jean N Éraud
email: jean.neraud@univ-rouen.fr

Complete Variable-Length Codes: An Excursion into Word Edit Operations

Keywords: closed, code, complete, deletion, dependent, detection, distribution, edition, embedding, independent, insertion, Levenshtein, maximal, string, substitution, substring, subword, variable-length, word

Given an alphabet A and a binary relation

The language X is complete if any word over A is a factor of some concatenation of words in X. Given a family of languages F containing X, X is maximal in F if no other set of F can stricly contain X. A language X ⊆ A * is a variable-length code if any equation among the words of X is necessarily trivial. The study discusses the relationship between maximality and completeness in the case of τ -independent or τ -closed variable-length codes. We focus to the binary relations by which the images of words are computed by deleting, inserting, or substituting some characters.

Introduction

In formal language theory, given a property F, the embedding problem with respect to F consists in examining whether a language X satisfying F can be included into some language X that is maximal with respect to F, in the sense that no language satisfying F can strictly contain X. In the literature, maximality is often connected to completeness: a language X over the alphabet A is complete if any string in the free monoid A * (the set of the words over A) is a factor of some word of X * (the submonoid of all concatenations of words in X). Such connection takes on special importance for codes: a language X over the alphabet A is a variable-length code (for short, a code) if every equation among the words (i.e. strings) of X is necessarily trivial.

A famous result due to M.P. Schützenberger states that, for the family of the so-called thin codes (which contains regular codes and therefore also finite ones), being maximal is equivalent to being complete. In connection with these two concepts lots of challenging theoretical questions have been stated. For instance, to this day the problem of the existence of a finite maximal code containing a given finite one is not known to be decidable. From this latter point of view, in [START_REF] Restivo | On codes having no finite completion[END_REF] the author asked the question of the existence of a regular complete code containing a given finite one: a positive answer was brought in [START_REF] Ehrenfeucht | Each regular code is included in a regular maximal one[END_REF], where was provided a now classical formula for embedding a given regular code into some complete regular one. Famous families of codes have also been concerned by those studies: we mention prefix and bifix codes [2, Theorem 3.3.8, Proposition 6.2.1], codes with a finite deciphering delay [START_REF] Bruyère | On completion of codes with finite deciphering delay[END_REF], infix [START_REF] Lam | Finite maximal infix codes[END_REF], solid [START_REF] Lam | Finite maximal solid codes[END_REF], or circular [START_REF] Néraud | Completing circular codes in regular submonoids[END_REF].

Actually, with each of those families, a so-called dependence system can be associated. Formally, such a system is a family F of languages constituted by those sets X that contain a non-empty finite subset in F. Languages in F are F-dependent, the other ones being F-independent. A special case corresponds to binary words relations τ ⊆ A * × A * , where a dependence systems is constituted by those sets X satisfying τ ∩ (X × X) = ∅: X is τ -independent if we have τ (X) ∩ X = ∅ (with τ (X) = {y : ∃x ∈ X, (x, y) ∈ τ }). Prefix codes certainly constitute the best known example: they constitute those codes that are independent with respect to the relation obtained by removing each pair (x, x) from the famous prefix order. Bifix, infix or solid codes can be similarly characterized.

As regards to dependence, some extremal condition corresponds to the so-called closed sets: given a word relation τ ⊆ A * × A * , a language X is closed under τ (τ -closed, for short) if we have τ (X) ⊆ X. Lots of topics are concerned by the notion. We mention the framework of prefix order where a one-to-one correspondence between independent and closed sets is provided in [2, Proposition 3.1.3] (cf. also [START_REF] Berstel | Bifix codes and sturmian words[END_REF][START_REF] Rudi | The infimal prefix-closed and observable superlanguage of a given language[END_REF]). Congruences in the free monoid are also concerned [START_REF] Nivat | Congruences parfaites et quasi-parfaites[END_REF], as well as their connections to DNA computing [START_REF] Kari | At the crossroads of linguistic, DNA computing and formal languages: characterizing RE using insertion-deletion systems[END_REF]. With respect to morphisms, involved topics are also provided by the famous L-systems [START_REF] Rozenberg | The Mathematical Theory of L-Systems[END_REF] and, in the case of one-to-one (anti)-automorphisms, the so-called invariant sets [START_REF] Néraud | Embedding a θ-invariant code into a complete one[END_REF].

As commented in [START_REF] Jürgensen | Codes. In Handbook of Formal Languages[END_REF], maximality and completeness concern the economy of a code. If X is a complete code then every word occurs as part of a message, hence no part of X * is potentially useless. The present paper emphasizes the following questions: given a regular binary relation τ ⊆ A * × A * , in the family of regular τ -independent (-closed) codes, are maximality and completeness equivalent notions? Given a non-complete regular τ -independent (-closed) code, is it embeddable into some complete one? Independence has some peculiar importance in the framework of coding theory. Informally, given some concatenation of words in X, each codeword x ∈ X is transmitted via a channel into a corresponding y ∈ A * . According to the combinatorial structure of X, and the type of channel, one has to make use of codes with prescribed error-detecting constraints: some minimum-distance restraint is generally applied. In this paper, where we consider variable-length codewords, we address to the Levenshtein metric [START_REF] Levenshtein | Binary codes capable of correcting deletions, insertion and reversals[END_REF]: given two different words x, y, their distance is the minimal total number of elementary edit operations that can transform x into y, such operation consisting in a one character deletion, insertion, or substitution. Formally, it is the smallest integer p such that we have y ∈ Λ p (x), with Λ p = 1≤k≤p (δ 1 ∪ ι 1 ∪ σ 1 ) k , where δ k , ι k , σ k are further defined below. From the point of view of error detection, X being Λ p -independent guarantees that y ∈ Λ p (x) implies y = x. In addition, a code satisfies the property of error correction if its elements are such that Λ p (x)∩Λ p (y) = ∅ unless x = y: according to [9, chap. 6], the existence of such codes is decidable. Denote by Subw(x) the set of the subsequences of x:

-δ k , the k-character deletion, associates with every word x ∈ A * , all the words y ∈ Subw(x) whose length is |x| -k. The at most p-character deletion is ∆ p = 1≤k≤p δ k ; -ι k , the k-character insertion, is the converse relation of δ k and we set I p = 1≤k≤p ι k (at most p-character insertion); -σ k , the k-character substitution, associates with every x ∈ A * , all y ∈ A * with length |x| such that y i (the letter of position i in y), differs of x i in exactly k positions i ∈ [1, |x|]; we set Σ p = 1≤k≤p σ k ; -We denote by Λ p the antireflexive relation obtained by removing all pairs (x, x) from Λ p (we have Λ 1 = Λ 1 ).

For short, we will refer the preceding relations to edit relations. For reasons of consistency, in the whole paper we assume |A| ≥ 2 and k ≥ 1. In what follows, we draw the main contributions of the study:

Firstly, we prove that, given a positive integer k, the two families of languages that are independent with respect to δ k or ι k are identical. In addition, for k ≥ 2, no set can be Λ k -independent. We establish the following result:

Theorem A. Let A be a finite alphabet, k ≥ 1, and τ ∈ {δ k , ι k , σ k , ∆ k , I k , Σ k , Λ k }.
Given a regular τ -independent code X ⊆ A * , X is complete if, and only if, it is maximal in the family of τ -independent codes.

A code X is Λ k -independent if the Levenshtein distance between two distinct words of X is always larger than k: from this point of view, Theorem A states some noticeable characterization of maximal k-error detecting codes in the framework of the Levenshtein metric.

Secondly, we explore the domain of closed codes. A noticeable fact is that for any k, there are only finitely many δ k -closed codes and they have finite cardinality. Furthermore, one can decide whether a given non-complete δ k -closed code can be embedded into some complete one. We also prove that no closed code can exist with respect to the relations ι k , ∆ k , I k .

As regard to substitutions, beforehand, we focus to the structure of the set σ * k (w) = i∈N σ i k . Actually, excepted for two special cases (that is, k = 1 [START_REF] Ehrlich | Loopless algorithms for generating permutations, combinations, and other combinatorial configurations[END_REF][START_REF] Savage | A survey of combinatorial gray codes[END_REF], or k = 2 with |A| = 2 [8, ex. 8, p.77]), to our best knowledge, in the literature no general description is provided. In any event we provide such a description; furthermore we establish the following result: Theorem B. Let A be a finite alphabet and k ≥ 1. Given a complete σ k -closed code X ⊆ A * , either every word in X has length not greater than k, or a unique integer n ≥ k + 1 exists such that X = A n . In addition for every Σ k (Λ k )-closed code X, some positive integer n exists such that X = A n .

In other words, no σ k -closed code can simultaneously possess words in A ≤k and words in A ≥k+1 . As a consequence, one can decide whether a given non-complete σ k -closed code X ⊆ A * is embeddable into some complete one.

Preliminaries

We adopt the notation of the free monoid theory. Given a word w, we denote by |w| its length; for a ∈ A, |w| a denotes the number of occurrences of the letter a in w. The set of the words whose length is not greater (not smaller) than n is denoted by A ≤n (A ≥n ). Given x ∈ A * and w ∈ A + , we say that x is a factor of w if words u, v exist such that w = uxv; a subword of w consists in any (perhaps empty) subsequence

w i 1 • • • w in of w = w 1 • • • w |w| .
We denote by F(X) (Subw(X)) the set of the words that are factor (subword) of some word in X (we have X ⊆ F(X) ⊆ Subw(X)). A pair of words w, w is overlapping-free if no pair u, v exist such that uw = wv or

w u = vw, with 1 ≤ |u| ≤ |w| -1 and 1 ≤ |v| ≤ |w | -1; if w = w , we say that w itself is overlapping-free.
It is assumed that the reader has a fundamental understanding with the main concepts of the theory of variable-length codes: we suggest, if necessary, that he (she) report to [START_REF] Berstel | Codes and Automata[END_REF]. A set X is a variable-length code (a code for short) if for any pair of sequences of words in X, say (x i ) 1≤i≤n , (y j ) 1≤j≤p , the equation

x 1 • • • x n = y 1 • • • y p implies n = p,
and x i = y i for each integer i (equivalently the submonoid X * is free). The two following results are famous ones from the variable-length code theory: Theorem 2.1 Schützenberger [2, Theorem 2.5.16] Let X ⊆ A * be a regular code. Then the following properties are equivalent:

(i) X is complete;

(ii) X is a maximal code;

(iii) a positive Bernoulli distribution π exists such that π(X) = 1;

(iv) for every positive Bernoulli distribution π we have π(X) = 1.

Theorem 2.2 [4]

Given a non-complete code X, let y ∈ A * \F(X * ) be an overlappingfree word and

U = A * \ (X * ∪ A * yA * ). Then Y = X ∪ y(U y) * is a complete code.
With regard to word relations, the following statement comes from the definitions:

Lemma 2.3 Let τ ∈ A * × A * and X ⊆ A * .
Each of the following properties holds: (i) X is τ -independent if, and only if, it is τ -1 -independent (τ -1 denotes the converse relation of τ ).

(ii) X is δ k (∆ k )-independent if, and only if, it is ι k (I k )-independent.

(iii) X is τ -closed if, and only if, it is τ * -closed.

Complete independent codes

We start by providing a few examples:

Example 3.1 For A = {a, b}, k = 1, the prefix code X = a * b is not δ k -independent (we have a n-1 b ∈ δ k (a n b))
, whereas the following codes are δ 1 -independent:

-the regular (prefix) code: Y = {a 2 } + {b, aba, abb}. Note that since it contains

{a 2 } + , δ 1 (Y ) is not a code.
-the complete (non-regular) context-free Dyck bifix code D 1 , which generates the Dyck free submonoid

D * 1 = {w ∈ A * : |w| a = |w b |} (for every word w ∈ D 1 we have |δ 1 (w)| a = |δ 1 (w)| b ). Note that δ 1 (D 1
) contains the empty word, ε, thus it cannot be a code; however δ 1 (D 1 ) \ A remains a (non-complete) bifix code -the non-complete finite bifix code Z = {ab 2 , ba 2 }: actually, δ 1 (Z) is the complete uniform code A 2 .

-for every pair of different integers n, p ≥ 2, the prefix code T = aA n ∪ bA p . We have δ 1 (T ) = A n ∪ A p , which is not a code, although it is complete.

In view of establishing the main result of Section 3, we will construct some peculiar word:

Lemma 3.2 Let k ≥ 1, i ∈ [1, k], τ ∈ {δ i , ι i , σ i }.
Given a a non-complete code X ⊆ A * some overlapping-free word y ∈ A * \ F(X * ) exists such that τ (y) does not intersect X and y / ∈ τ (X).

Proof. Let X be a non-complete code, and let w ∈ A * \ F(X * ). Trivially, we have w k+1 / ∈ F(X * ). Moreover, in a classical way a word u ∈ A * exists such that y = w k+1 u is overlapping-free (eg. [2, Proposition 1.3.6]). Since we assume i ∈ [1, k], each word in τ (y) is constructed by deleting (inserting, substituting) at most k letters from y, hence by construction it contains at least one occurrence of w as a factor. This implies τ (y) ∩ F(X * ) = ∅, thus τ (y) does not intersect X.

By contradiction, assume that a word x ∈ X exists such that y ∈ τ (x). It follows from δ -1 k = ι k and σ -1 k = σ k that y = w k+1 u is obtained by deleting (inserting, substituting) at most k letters from x: consequently at least one occurrence of w appears as a factor of x ∈ X ⊆ F(X * ): this contradicts w / ∈ F(X * ), therefore we obtain y / ∈ τ (X) (cf. Figure 1). As a consequence, we obtain the following result:

Theorem 3.3 Let k ≥ 1 and τ ∈ {δ k , ι k , σ k }.
Given a regular τ -independent code X ⊆ A * , X is complete if, and only if, it is maximal as a τ -independent codes.

Proof. According to Theorem 2.1, every complete τ -independent code is a maximal code, hence it is maximal in the family of τ -independent codes. For proving the converse, we make use of the contrapositive. Let X be a non-complete τ -independent code, and let y ∈ A * \ F(X * ) satisfying the conditions of Lemma 3.2. With the notation of Theorem 2.2, necessarily X ∪ {y}, which is a subset of Y = X ∪ y(U y) * , is a code. According to Lemma 3.2, we have τ (y) ∩ X = τ (X) ∩ {y} = ∅. Since X is τ -independent and τ antireflexive, this implies τ (X ∪ {y}) ∩ (X ∪ {y}) = ∅, thus X non-maximal as a τ -independent code.

We notice that for k ≥ 2 no Λ k -independent set can exist (indeed, we have

x ∈ σ 2 1 (x) ⊆ Λ k (x)
). However, the following result holds:

Corollary 3.4 Let τ ∈ {∆ k , I k , Σ k , Λ k }.
Given a regular τ -independent code X ⊆ A * , X is complete if, and only if, it is maximal as a τ -independent code.

Proof. As indicated above, if X is complete, it is maximal as a τ -independent code. For the converse, once more we argue by contrapositive that is, with the notation of Lemma 3.2, we prove that X ∪ {y} remains independent. By definition, for each τ ∈ {∆ k , I k , Σ k , Λ k }, we have τ ⊆ 1≤i≤k τ i , with τ i ∈ {δ i , ι i , σ i }.

According to Lemma 3.2, since τ i is antireflexive, for each i ∈ [1, k] we have

τ i (X ∪ {y}) ∩ (X ∪ {y}) = ∅: this implies (X ∪ {y}) ∩ 1≤i≤k τ i (X ∪ {y}) = ∅, thus X ∪ {y} τ -independent.
With regard to the relation Λ k , Corollary 3.4 expresses some interesting property in term of error detection. Indeed, as indicated in Section 1, every code is Λ k -independent if the Levenshtein distance between its (distinct) elements is always larger than k. From this point of view, Corollary 3.4 states some characterization of the maximality in the family of such codes.

It should remain to develop some method in view of embedding a given noncomplete Λ k -code into a complete one. Since the construction from the proof Theorem 2.2 does not preserve independence, this question remains open.

Complete closed codes with respect to deletion or insertion

We start with relation the δ k . A noticeable fact is that corresponding closed codes are necessarily finite, as attested by the following result:

Proposition 4.1 Given a δ k -closed code X, and x ∈ X, we have |x| ∈ [1, k 2 -k - 1] \ {k}.
Proof. It follows from ε / ∈ X and X being δ k -closed that |x| = k. By contradiction, assume |x| ≥ (k -1)k and let q, r be the unique pair of integers such that |x| = qk + r, with 0 ≤ r ≤ k -1. Since we have 0 ≤ rk ≤ (k -1)k ≤ |x|, an integer s ≥ 0 exists such that |x| = rk + s, thus words

x 1 , • • • , x k , y exist such that x = x 1 • • • x k y, with |x 1 | = • • • = |x k | =
r and |y| = s. By construction, every word t ∈ Sub(x) with |t| ∈ {r, s} belongs to δ * k (x) ⊆ X (indeed, we have r = |x| -qk and s = |x| -rk). This implies x 1 , • • • , x k , y ∈ X, thus x ∈ X k+1 ∩ X: a contradiction with X being a code.

Example 4.2 (1) According to Proposition 4.1, no code can be δ 1 -closed. This can be also drawn from the fact that, for every set X ⊆ A + we have ε ∈ δ * 1 (X). (2) Let A = {a, b} and k = 3. According to Proposition 4.1, every word in any δ k -closed code has length not greater than 5. It is straightforward to verify that X = {a 2 , ab, b 2 , a 4 b, ab 4 } is a δ k -closed code. In addition, a finite number of examinations lead to verify that X is maximal as a δ k -closed code. Taking for π the uniform distribution we have π(X) = 3/4 + 1/16 < 1: thus X is non-complete.

According to Example 4.2 (2), no result similar to Theorem 3.3 can be stated in the framework of δ k -closed codes. We also notice that, in Proposition 4.1 the bound does not depend of the size of the alphabet, but only depends of k.

Corollary 4.3 Given a finite alphabet A and a positive integer k, one can decide whether a non-complete δ k -closed code X ⊆ A * is included into some complete one. In addition there are a finite number of such complete codes, all of them being computable, if any.

Proof. According to Proposition 4.1 only a finite number of δ k -closed codes over A can exist, each of them being a subset of A ≤k 2 -k-1 \ A k .

We close the section by considering the relations ∆ k , ι k and I k :

Proposition 4.4 No code can be ι k -closed, ∆ k -closed, nor I k -closed. Proof. By contradiction assume that some ι k -closed code X ⊆ A * exists. Let x ∈ X, n = |x| and u, v ∈ A * such that x = uv. It follows from |(vu) k | = kn, that u(vu) k v ∈ ι * k (x). According to Lemma 2.3(iii), we have ι * k (X) ⊆ X, thus u(vu) k v ∈ X. Since u(vu) k v = (uv) k+1 = x k+1 ∈ X k+1 , we have X k+1 ∩ X = ∅: a contradiction with X being a code. Consequently no I k -closed codes can exist. According to Example 4.2(1), given a code X ⊆ A * , we have δ 1 (X) ⊆ X: this implies ∆ k (X) ⊆ X, thus X not ∆ k -closed.

Complete codes closed under substitutions

Beforehand, given a word w ∈ A + , we need a thorough description of the set σ * k (w). Actually, it is well known that, over a binary alphabet, all n-bit words can be computed by making use of some Gray sequence [START_REF] Ehrlich | Loopless algorithms for generating permutations, combinations, and other combinatorial configurations[END_REF]. With our notation, we have A n = σ * 1 (w). Furthermore, for every finite alphabet A, the so-called |A|-arity Gray sequences allow to generate A n [START_REF] Knuth | The art of computer programming[END_REF][START_REF] Savage | A survey of combinatorial gray codes[END_REF]: once more we have σ * 1 (w) = A n . In addition, in the special case where k = 2 and |A| = 2, it can be proved that we have |σ 2 (w)| = 2 n-1 [8, Exercise 8, p. 28]. However, except in these special cases, to the best of our knowledge no general description of the structure of σ * k (w) appears in the literature. In any event, in the next paragraph we provide an exhaustive description of σ k (w). Strictly speaking, the proofs, that we have reported in Section 5.2, are not involved in σ k -closed codes: we suggest the reader that, in a first reading, after para. 5.1 he (she) directly jumps to para. 5.3. In the case where A is a binary alphabet, we set A = {0, 1}: this allows a well-known algebraic interpretation of σ k . Indeed, denote by ⊕ the addition in the group Z/2Z with identity 0, and fix a positive integer n; given w, w ∈ A n , define w ⊕ w as the unique word of A n such that, for each i ∈ [1, n], the letter of position i in w ⊕ w is w i ⊕ w i . With this notation the sets A n and (Z/2Z) n are in one-to-one correspondence. Classically, we have w ∈ σ 1 (w) if, and only if, some u ∈ A n exists such that w = w ⊕ u with |u| 1 = 1 (thus |u| 0 = n -1). From the fact that σ k (w) ⊆ σ k 1 (w), the following property holds:

w ∈ σ k (w) ⇐⇒ ∃u ∈ A n : w = w ⊕ u, |u| 1 = k. (1)
|w| 1 + |w | 1 = |w 1 | -|w | 1 (mod 2) = |u| 1 (mod 2). (2)
Finally, for a ∈ A we denote by a its complementary letter that is, a = a ⊕ 1; for

w ∈ A n we set w = w 1 • • • w n . Lemma 5.2 Let A = {0, 1}, n ≥ k + 1. Given w, w ∈ A n the two following properties hold: (i) If k is even and w ∈ σ * k (w) then |w | 1 -|w| 1 is an even integer; (ii) If |w | 1 -|w| 1 is even then we have w ∈ σ * k (w)
, for every k ≥ 1. Given a positive integer n, we denote A n 0 (A n 1 ) the set of the words w ∈ A n such that |w| 1 is even (odd). (c)

w i 0 = c = w i 0 , (d) w i = w i = w i if i ∈ I, and: (e) w i = w i = w i if i / ∈ I ∪ {i 0 }. Since we have |I ∪ {i 0 }| = k, this implies w ∈ σ k (w ). Proof of Proposition 5.1. Let w ∈ A n \ {w}: we prove that w ∈ σ * k (w). Let I = {i 0 , • • • , i p } = {i ∈ [1, n] : w i = w i } and let (w (i j )
) 0≤j≤p be a sequence of words such that w = w (i 0 ) , w (ip) = w and, for each j ∈ [0, p -1]: w

(i j+1 ) = w (i j ) if,
and only if, = i j+1 . Since we have w (i j+1 ) ∈ σ 1 (w (i j ) ) (1 ≤ j < p), by induction over j we obtain w ∈ σ * 1 (w) thus, according to Lemma 5.4, w ∈ σ * k (w).

In view of proving Lemma 5.2 and Proposition 5.3, we need some new lemma:

Lemma 5.5 Assume |A| = 2. For every w ∈ A ≥k+1 , we have σ 2 (w) ⊆ σ 2 k (w).

Proof. Set A = {0, 1}. It follows from σ 2 ⊆ σ 2 1 that the result holds for k = 1. Assume k ≥ 2 and let n = |w|, w ∈ σ 2 (w). By construction, there are distinct integers i 0 , j 0 ∈ [1, n] such that the following holds:

(a) w i = w i if, and only if, i ∈ {i 0 , j 0 }. Since some (k -1)-element set I ⊆ [1, n] \ {i 0 , j 0 } exists, words w , w ∈ A n such that:

(b) w i = w i if, and only if, i ∈ {i 0 } ∪ I, and: (c) w i = w i if, and only if, i ∈ {j 0 } ∪ I. By construction, we have w ∈ σ k (w) and w ∈ σ k (w ), thus w ∈ σ 2 k (w). Moreover, the fact that we have w = w is attested by the following equations:

(d) w j 0 = w j 0 = w j 0 = w j 0 , (e) w i 0 = w i 0 = w i 0 = w i 0 , and: (f) for i / ∈ {i 0 , j 0 }: w i = w i = w i = w i if, and only if, i ∈ I.

Proof of Lemma 5.2. Assume k even. According to Property (1) we have w = w ⊕ u with |u| 1 = k. According to (2), |w | 1 -|w| 1 is even: hence (i) follows.

is σ k -closed. Since every σ k -closed code is finite, no complete σ k -closed code can contain X.

Proposition 5.10 Let X be a (finite) non-complete σ k -closed code. Then one can decide whether some complete σ k -closed code containing X exists. More precisely, there is only a finite number of such codes, each of them being computable, if any.

Proof sketch. We draw the scheme of an algorithm that allows to compute every complete σ k -closed code X containing X. In a first step, we compute Y = X ∩ A ≤k . If Y = X, according to Theorem 5.9, we have X ⊆ A ≤k : X, if any, can be computed in a finite number of steps. Otherwise, X exists if, and only if, for some n ≥ k + 1 we have X ⊆ A n : this can be straightforwardly checked.

Fig. 1 :

 1 Fig. 1: Proof of Lemma 3.2: y ∈ τ (X) implies w ∈ F(X); for i = k = 3 and y = w 4 u, the action of the substitution τ = σ3 is represented by the arrows, in some extremal condition.

5. 1

 1 Basic results concerning σ * k (w) Proposition 5.1 Assume |A| ≥ 3. For each w ∈ A ≥k , we have σ * k (w) = A |w| .

  In additionw ⊕ u = w is equivalent to u = w ⊕ w . Let d = |{i ∈ [1, n] : w i = w i = 1}|. The following property comes from |u| 1 = (|w| 1 -d) + (|w | 1 -d) and |w| 1 + |w | 1 = |w 1 | + |w | 1 -2|w | 1 (mod 2) :

Proposition 5 . 3

 53 Assume |A| = 2. Given w ∈ A ≥k exactly one of the following conditions holds: (i) |w| ≥ k + 1, k is even, and σ * k (w) ∈ {A |w| 0 , A |w| 1 }; (ii) |w| ≥ k + 1, k is odd, and σ * k (w) = A |w| ; (iii) |w| = k and σ * k (w) = {w, w}.

5. 2 Lemma 5 . 4

 254 Proofs of the statements 5.1, 5.2 and 5.3Actually, Proposition 5.1 is a consequence of the following property: Assume |A| ≥ 3. For every word w ∈ A ≥k we have σ 1 (w) ⊆ σ 2 k (w).Proof. Let w ∈ σ 1 (w) and n = |w| = |w | ≥ k. We prove that w ∈ A * exists with w ∈ σ k (w) and w ∈ σ k (w ). By construction, i 0 ∈ [1, n] exists such that: (a) w i = w i if, and only if, i = i 0 . It follows from k ≤ n that some (k -1)-element subset I ⊆ [1, n] \ {i 0 } exists. Since we have |A| ≥ 3, some letter c ∈ A \ {w i 0 , w i 0 } exists. Let w ∈ A n such that:(b) w i 0 = c and, for each i = i 0 : w i = w i if, and only if, i ∈ I. By construction we have w ∈ σ k (w), moreover c = w i 0 implies w i 0 = w i 0 . According to (a) and (b), we obtain:

Conversely, assume |w | 1 -|w| 1 even and let u = w ⊕ w . According to [START_REF] Berstel | Codes and Automata[END_REF], |u| 1 is also even, moreover according to [START_REF] Berstel | Bifix codes and sturmian words[END_REF] we obtain w = σ |u| 1 (w): this implies w ∈ σ * 2 (w). According to Lemma 5.5, we have w ∈ σ * k (w): this establishes (ii).

Proof of Proposition 5.3. Let w ∈ A ≥k and n = |w|. (iii) is trivial and (i) follows from Lemma 5.2(i): indeed, since k is even, σ * k (w) is the set of the words w ∈ A n such that |w | 1 -|w| 1 is even. Assume k odd, n ≥ k +1 and let w ∈ A n \{w}; we will prove that

this completes the proof.

The consequences for σ-closed codes

Given a σ k -closed code X ⊆ A * , we say that the tuple (k, A, X) satisfies Condition (3) if each of the three following properties holds:

We start by proving the following technical result:

Lemma 5.6 Assume |A| = 2 and k even. Given a pair of words v, w ∈ A + , if |w| ≥ max{|v| + 1, k + 1} then the set σ * k (w) ∪ {v} cannot be a code.

Proof. Let v, w ∈ A + , and

it follows from |v| ≤ n -1 that a (perhaps empty) word s exists such that vs ∈ A n-1 . On another hand, it follows from

As a consequence of Lemma 5.6, we obtain the following result:

Proof. Firstly, consider two words v, w ∈ X ∩ A ≥k+1 and by contradiction, assume |v| = |w| that is, without loss of generality |v| + 1 ≤ |w|. Since X is σ k -closed, we have σ * k (w) ⊆ X, whence the set σ * k (w) ∪ {v}, which a subset of X is a code: this contradicts the result of Lemma 5.6. Consequently, we have X ⊆ A ≤k ∪ A n , with n = |v| = |w| ≥ k + 1. Secondly, once more by contradiction assume that words v ∈ X ∩ A ≤k , w ∈ X ∩ A ≥k+1 exist. As indicated above, since X is σ k -closed, σ * k (w) ∪ {v} is a code: since we have |w| ≥ k + 1 and |w| ≥ |v| + 1, once more this contradicts the result of Lemma 5.6. As a consequence, necessarily we have X ⊆ A n , for some n ≥ k + 1. With such a condition, according to Proposition 5.3 for each pair of words v, w ∈ X, we have

According to Lemma 5.7, with Condition (3) no σ k -closed code can simultaneously possess words in A ≤k and words in A ≥k+1 .

Lemma 5.8 Given a σ k -closed code X ⊆ A * , if (k, A, X) does not satisfy Condition (3) then either we have X ⊆ A ≤k , or we have X = A n , with n ≥ k + 1.

Proof. If Condition (3) doesn't hold then exactly one of the three following conditions holds:

(c) X ⊆ A ≤k with |A| = 2 and k odd. With each of the two last conditions, let w ∈ X ∩ A ≥k+1 . Since X is σ k -closed, according to the propositions 5.1 and 5.3(ii), we have

As a consequence, every σ k -closed code is finite. In addition, we state: Theorem 5.9 Given a complete σ k (Σ k , Λ k )-closed code X, exactly one of the following conditions holds:

(i) X is a subset of A ≤k ;

(ii) a unique integer n ≥ k + 1 exists such that X = A n . In addition, every Σ k (Λ k )-closed code is equal to A n , for some n ≥ 1.

Proof. Let X be a complete σ k -closed code. If Condition (3) does not hold, the result is expressed by Lemma 5.8. Assume that Condition (3) holds. According to Lemma 5.7, in any case some integer n ≥ k + 1 exists such that X ∈ {A n 0 , A n 1 , A n }. Taking for π the uniform distribution, we have π(A n 0 ) = π(A n 1 ) = 1/2 and π(A n ) = 1 thus, according to Theorem 2.1:

As a corollary, in the family of Σ k (Λ k )-closed codes, maximality and completeness are equivalent notions. With regard to σ k -closed codes, things are otherwise: indeed, as shown in [START_REF] Restivo | On codes having no finite completion[END_REF], there are finite codes that have no finite completion. Let X be one of them, and k = max{|x| : x ∈ X}. By definition X