Alexis Guyot
email: alexis.guyot@u-bourgogne.fr

Annabelle Gillet
email: annabelle.gillet@u-bourgogne.fr

Éric Leclercq
email: eric.leclercq@u-bourgogne.fr

Nadine Cullot
email: nadine.cullot@u-bourgogne.fr

ERIS: an Approach Based on Community Boundaries to Assess Polarization in Online Social Networks

Keywords: social networks, polarization, community boundaries, community structure, graph mining

Detection and characterization of polarization are of major interest in Social Network Analysis, especially to identify conflictual topics that animate the interactions between users. As gatekeepers of their community, users in the boundaries significantly contribute to its polarization. We propose ERIS, a formal graph approach relying on community boundaries and users' interactions to compute two metrics: the community antagonism and the porosity of boundaries. These values assess the degree of opposition between communities and their aversion to external exposure, allowing an understanding of the overall polarization through the behaviors of the different communities. We also present an implementation based on matrix computations, freely available online. Our experiments show a significant improvement in terms of efficiency in comparison to existing solutions. Finally, we apply our proposal on real data harvested from Twitter with a case study about the vaccines and the COVID-19.

Introduction

Online Social Networks (OSN) are large scale environments of exchanges and debates. Social Network Analysis (SNA) has diverse and numerous applications in domains such as sociology, politics, marketing, health, etc. The intrinsic characteristics of the large volume of data generated in OSN [START_REF] Barabási | Network science[END_REF], such as the power law distribution, entail analysts to use algorithmic approaches to extract value.

SNA can benefit from the graph theory since graph structures are natural representations for OSN, where users can be represented by vertices and their interactions by edges. Communities of individuals form dense areas of nodes and can therefore be detected by algorithms like Louvain, Walktrap or Infomap for non-overlapping communities and SLPA, OSLOM or Game for overlapping ones [START_REF] Fortunato | Community detection in graphs[END_REF].

Discussions about hot topics can lead to the creation of mutually antagonistic communities, with few individuals remaining neutral or holding an intermediate position. In social sciences, this phenomenon is called polarization [START_REF] Isenberg | Group polarization: A critical review and meta-analysis[END_REF]. Polarized communities negatively impact OSN by fostering social division, ideological isolation and misinformation spreading [START_REF] Baumann | Modeling echo chambers and polarization dynamics in social networks[END_REF]. Detecting such communities is of major interest to proactively assist moderation and therefore avoid further escalation between users. Journalists could also benefit from this feature to identify areas in the network where fact checking could be needed. Moreover, detecting polarization allows a more precise understanding of individuals through their relationships. Domains such as politics or business intelligence could benefit from it to adapt their decision making and communication strategies.

In the literature, echo chambers are usually considered as the consequence of polarization [START_REF] Cinelli | The echo chamber effect on social media[END_REF]. However, only showing that a community is an echo chamber does not allow to conclude about its polarization. An echo chamber is a configuration in which one is exposed only to opinions that agree with their own [START_REF] Garimella | Political discourse on social media: Echo chambers, gatekeepers, and the price of bipartisanship[END_REF]. So this phenomenon describes a global behavior within a community whereas polarization is also about relationships between communities [START_REF] Baumann | Modeling echo chambers and polarization dynamics in social networks[END_REF]. Thus, the polarization is also carried by community members exposed to other communities and exposing the main topic of their community to the outside through their interactions. These members form the community boundaries. More formally, we can define a community boundary as the set of nodes having edges directed toward both the inside and the outside of the community [START_REF] Clauset | Finding local community structure in networks[END_REF]. In the literature, boundaries are fairly unexplored parts of communities. Nevertheless, the behaviors of boundary users have a significant impact on the strength of the polarization but also on the fragility of the echo chamber [START_REF] Donkers | The Dual Echo Chamber: Modeling Social Media Polarization for Interventional Recommending[END_REF] as they contribute to the porosity of the boundary.

The major contributions of our work are: 1) a formal graph approach relying on community boundaries to unveil the polarization of networks created from the interactions between individuals; 2) two metrics to characterize the level of polarization and the porosity of boundaries; 3) an efficient algorithm based on matrix computations suitable for large volumes of data, and; 4) a case study on real data extracted from Twitter to experimentally validate our proposal.

The remainder of this paper is structured as follows. First, our method is positioned in relation to the state of the art in section 2. In section 3 we formally define the ERIS approach and propose an efficient algorithm to compute polarization metrics. The case study led on real data and validated by domain experts is described in section 4. Finally, we draw conclusions of our work and open up perspectives for the future in section 6.

Related Work

The problem of polarization in OSN was addressed back in 2011 [START_REF] Conover | Political polarization on twitter[END_REF]. The authors consider that echo chambers and polarized communities are the same.

But with this assumption, interactions and relationships between communities, carried by community boundaries, are ignored. Moreover, the approach is an applied methodology which cannot be included in an automatic analytical workflow ready-to-use for domain experts.

Many works on social polarization use exploratory analyzes combining metrics from the graph theory with interpretations provided by Natural Language Processing (NLP) tools like sentiment analysis based on Naïves Bayes [START_REF] Alamsyah | Hybrid sentiment and network analysis of social opinion polarization[END_REF]20] or sentence embedding models based on Retweet-BERT [START_REF] Jiang | Social media polarization and echo chambers: A case study of covid-19[END_REF]. These approaches best capture the semantics of discussions but require heavy involvement from the analyst, especially during the preprocessing step. Indeed, to set the stage for the NLP algorithms, many difficulties must be manually addressed like spelling approximations, abbreviations, slang, or ambiguities caused by humor, sarcasm or irony as discussed in [START_REF] González-Ibánez | Identifying sarcasm in twitter: a closer look[END_REF][START_REF] Joshi | Automatic sarcasm detection: A survey[END_REF][START_REF] Mcglone | Contextomy: the art of quoting out of context[END_REF]. Thus, they leave a large area for subjectivity and lack automatism.

Other approaches focus on the network structure with weakly-supervised strategies where just a limited amount of extra knowledge is used to initialize algorithms. In [START_REF] Morales | Measuring political polarization: Twitter shows the two sides of venezuela[END_REF] an opinion score is manually assigned to seed users (elites) and then propagated to the other nodes of the network (listeners) in order to create two opposing groups and to assess their polarization degree. In [START_REF] Al Amin | Unveiling polarization in social networks: A matrix factorization approach[END_REF], a similarity measure must be wisely chosen to create clusters of tweets (assertions) with the aim of unveiling polarized groups inside a network. To do so, they use a matrix factorization and an ensemble based gradient descent algorithm applied on the adjacency matrices of a bipartite source-assertion graph and a social influence graph. In any case the relevance of the results depends a lot on the extra knowledge brought, which must be revised for each dataset studied. Therefore, their automatism is limited. Moreover, they do not consider the relationships between polarized communities, meaning that two communities behaving as echo chambers but never interacting because they do not know each other could be considered as polarized.

Boundaries have a major impact on the polarization of their community by defining both how the community is exposed to the outside and how the outside is exposed to the community. A first non-supervised approach based on community boundaries was described by Guerra et al. in [START_REF] Guerra | A measure of polarization on social media networks based on community boundaries[END_REF] with the aim of computing complementary metrics to be used besides cohesion and homophily metrics such as modularity. Antagonism between communities is assessed by measuring the involvement of users interacting with both the inside and the outside of their community. This approach does not need any a priori knowledge on the graph or on the individuals represented and can therefore be included in automatic analytical workflows designed for domain experts. However, the main limitation of this method is its specification on undirected and unweighted graphs whereas social interaction graphs usually are directed and weighted. Furthermore, only non-overlapping communities are handled whereas users of social networks more naturally belong to multiple communities [START_REF] Xie | Overlapping community detection in networks: The state-of-the-art and comparative study[END_REF].

As a conclusion, fully automatic methods are the best option to detect polarization. This property is indeed very important in SNA to allow domain experts like sociologists or decision-makers to use a method and to permit comparisons between datasets. Furthermore, the polarization of a community can be misinterpreted when interactions between communities are not considered, which can be avoided by examining the behavior of community boundaries.

The ERIS Method

In this section, we formally introduce the ERIS method and its metrics, i.e., the community antagonism and the porosity of boundaries. Our approach relies on edge weighting and direction and handles overlapping communities. We also propose an efficient algorithm based on matrix computations to assess the metrics.

Formal Definitions

In the following definitions, a graph G = (V, E) is composed of a set of vertices V and of a set of directed edges E ⊆ V × V . An edge e a,b ∈ E connects a source a ∈ V and a destination b ∈ V with a weight w(e a,b ) ∈ R. Communities are locally dense connected subsets of V .

Two communities (C i , C j ) are polarized if they are mutually antagonistic. According to [START_REF] Guerra | A measure of polarization on social media networks based on community boundaries[END_REF] and [START_REF] Baumann | Modeling echo chambers and polarization dynamics in social networks[END_REF], a strong involvement from a boundary individual within the community, especially expressed by numerous interactions with the internal members, reveals a substantial emotional attachment to the community and its main topics. This attachment could easily lead to the expression of antagonism in response to a criticism, an attack or the broadcast of a negative opinion or information about these topics by another community.

The ERIS method consists in identifying, for each pair of communities (C i , C j ): 1) the internal area I i,j of C i , that is the set of vertices in C i without any edge directed toward C j , and; 2) the boundary area B i,j of C i , that is the set of vertices in C i with at least one edge directed toward I i,j and another one toward C j . The method assesses the average antagonism expressed by the community C i to the community C j by measuring the involvement of the vertices in B ij .

From the previous intuitive descriptions, we have established the following formal definitions:

I i,j = {v : v ∈ C i , e v,n | n ∈ C j , i = j} (1)
B i,j = {v : v ∈ C i , ∃e v,n1 | n 1 ∈ C j , ∃e v,n2 | n 2 ∈ I i,j , i = j} (2)
For each boundary, we consider the set of outgoing edges directed toward the other community (external edges or EE i,j ) as well as the set of edges directed toward the internal area I i,j of C i (internal edges or IE i,j ):

EE i,j = {e s,d : s ∈ B i,j ∧ d ∈ C j } (3)
IE i,j = {e s,d : s ∈ B i,j ∧ d ∈ I i,j } (4)
We also consider EE v i,j the external and IE v i,j the internal edges of a vertex v as the subsets of edges, respectively included in EE i,j and EI i,j , where v is the source of the edge:

EE v i,j = {e v,d : e v,d ∈ EE i,j } (5)
IE v i,j = {e v,d : e v,d ∈ IE i,j } (6)
The antagonism A v i,j expressed by a vertex v is assessed as the weighted ratio of its internal edges' weights with the sum of its internal and external edges' weights. This value is compared to a null hypothesis, i.e., each node spreads its edges equally between internal nodes and nodes from the other community [START_REF] Guerra | A measure of polarization on social media networks based on community boundaries[END_REF]:

A v i,j = e∈IE v i,j
w(e)

e∈IE v i,j w(e) + e∈EE v i,j
w(e) -0.5 [START_REF] Cinelli | The echo chamber effect on social media[END_REF] Finally, the antagonism A i,j expressed by a boundary B i,j is the average antagonism expressed by its members:

A i,j = 1 |B i,j | v∈Bi,j A v i,j (8)
By assessing the antagonism values for each possible pair of communities in a graph, we obtain an asymmetrical matrix called the antagonism matrix, containing values ranging from -0.5 to 0.5. A community boundary with a value close to 0.5 should be considered as likely to be antagonistic toward the other community of the pair. Values on the lines of the antagonism matrix express how much the community heading the line is likely to express antagonism toward the communities heading the columns. Conversely, values on the columns indicate how much the community heading the column is likely to receive antagonism from the communities heading the lines.

Boundary vertices with negative antagonism values weaken the polarization of their community. Indeed, by interacting more with the outside than with the inside, they reduce the isolation of the community that leads to the creation of an echo chamber. As fellow members, they also seem more credible in the eyes of the others when they share more nuanced opinions about the main topics of the community [START_REF] Donkers | The Dual Echo Chamber: Modeling Social Media Polarization for Interventional Recommending[END_REF]. Based on these ascertainments, we propose a novel metrics P i,j called the porosity of the boundary B i,j , measuring the fragility of the boundary of C i with C j :

P i,j = |N B i,j | |B i,j | × 100 (9)
with N B i,j = v : v ∈ B i,j , A v i,j < 0 the subset of B i,j including all the vertices having negative antagonism values. Porosity values also can be represented inside an asymmetrical matrix called the porosity matrix.

We now illustrate the different sets and values presented in this subsection by applying the definitions on the toy example of figure 1. We focus our explanation In figure 2c, the porosity value P 1,2 is equal to 100, meaning that B 1,2 is very porous as its members interact more with C 2 than with I 1,2 .

Algorithm

The adjacency matrix of a graph is at the core of the algorithm designed for ERIS, which uses a series of matrix computations to get the antagonism (M AN T ) and the porosity (M P OR ) matrices. Naming conventions used in following paragraphs are listed in table 1. We define ! as an operator computing element-wise multiplication between a vector of size N and each column of a matrix of size N × M , resulting in a new matrix of size N × M . The initialization part of the algorithm consists in computing M EE , an aggregated version of M A grouped by community (line 1). The matrix contains the sum of the edges' weights whose source is the vertex heading the row and the destination is a vertex belonging to the community heading the column. This matrix is then used to extract M I , a binary mask of M EE in which the vertices belonging to at least one internal area of their communities are identified (line 2).

Symbol

From these two common matrices, the main part of the algorithm computes for each community the antagonism and porosity values of its boundaries through four main steps:

the detection of the internal areas of the current community c for each pair involving c (line 4) ; An open source implementation of this algorithm in R is available on GitHub1 to allow the use of ERIS on graphs built from real datasets.

Experimentations

We want to experimentally show the suitability of our method on real data from OSN. First, we verify its applicability on large graphs through an analysis of the algorithmic complexity in time achieved by our matrix computation based algorithm. Then, we explore the validity of our polarization metrics through a case study led on real data harvested from Twitter with the help of domain experts validating our results and interpretations.

Execution on Large Graphs

We compare the execution times of 3 algorithms aiming to measure the polarization of communities in graphs built from interactions between individuals:

the matrix computation based algorithm of ERIS presented in the previous section (implemented in R) ; an iterative algorithm of ERIS proposed in a previous work [START_REF] Guyot | Frontières des communautés polarisées: application à l'étude des théories complotistes autour des vaccins 20[END_REF] (implemented in R) ;

the only algorithm of Guerra et al.'s method available online2 , not developed by the authors (implemented in Python).

We chose to compare ERIS with Guerra et al.'s method because both share a lot of common characteristics (no supervision needed, based on graph mining, etc.).

We have generated artificial graphs with decreasing sizes, ranging from 1 million to 500 vertices, based on a real graph extracted from a dataset harvested from Twitter. In this subsection, we do not take into consideration the semantics of the computed metrics, only the impact of the graph structure on the execution time.

For each algorithm, we have measured the elapsed time between the call of the function computing the antagonism matrices (the common metrics) and the return of a result3 . For the algorithm 1, this interval corresponds to lines 1 to 10. The three algorithms were run on a Dell PowerEdge R440 server with the following characteristics: Intel(R) Xeon(R) Bronze 3204 CPU @ 1.92GHz, 6 cores, 128Go RAM. 3a. Figure 3b focuses on the execution times of the algorithm 1 described in the last section. We can see that the matrix computation based algorithm of ERIS outperforms all the other implementations. For our biggest graph, the one with 1 million vertices directly extracted from the real corpus that we have harvested from Twitter, the matrix computation based version of ERIS took 2.5 seconds to compute the metrics. It is 12,828 times faster than the iterative version (32,070 seconds or almost 9 hours) and 592,399 times faster than the algorithm of Guerra et al.'s method [START_REF] Al Amin | Unveiling polarization in social networks: A matrix factorization approach[END_REF]528,389 seconds or more than 17 days).

Theoretically, the computational complexity for assessing both polarization metrics with the algorithm based on matrix computations is O(|V | 2 |C| 2 ), as long as |C| < |V | 3 . Beyond this value, the order reaches O(|V ||C| 3 ). However, in most of practical analyzes, the number of significant communities in a graph remains relatively small due to the resolution limit. Furthermore, domain experts also only require a small number of communities to left results open to interpretation. In these cases, |C| |V | and thus the computational complexity can be considered as O(|V | 2 ).

According to the previous theoretical and practical analyzes of the algorithmic complexity of our proposal, we can conclude that the matrix computation based algorithm of ERIS achieves our goals of applicability on large graphs and outperforms of several orders of magnitude the other algorithms available online to automatically assess polarization on graphs extracted from OSN.

Case Study on Real Data

We experimentally illustrate the interest of our approach on a real dataset about COVID-19 vaccines, which includes more than 18 millions tweets harvested in the context of the interdisciplinary project Cocktail4 by the architecture Hydre [START_REF] Gillet | Évolution et formalisation de la Lambda Architecture pour des analyses à hautes performances -Application aux données de Twitter[END_REF] from December 1, 2020 to March 31, 2021 (120 days).

From this dataset, a directed graph of quotes5 G Q is extracted, in which the vertex representing an individual u has an outgoing edge directed toward the vertex representing the user n if u has already quoted at least twice the tweets of n. The weight w of an edge indicates the exact number of times u quoted n. Following [START_REF] Garimella | Quantifying controversy on social media[END_REF], we do not consider isolated quotes as they can be random noise. The characteristics of G Q are presented in table 3 We chose the quote as type of interaction to be consistent with the previous works led on polarization on Twitter. Indeed, the literature mainly agrees that retweets often imply endorsement [START_REF] Boyd | Tweet, tweet, retweet: Conversational aspects of retweeting on twitter[END_REF] and thus not antagonism, and that the mention network is usually not polarized [START_REF] Conover | Political polarization on twitter[END_REF]. However, quotes are often used to twist a message out of its original context for humor and criticism purposes, leading to antagonistic responses [START_REF] Guerra | Antagonism also flows through retweets: The impact of out-of-context quotes in opinion polarization analysis[END_REF]. Thus, quotes are the best type of interactions for community boundary approaches like ERIS to assess polarization.

G Q is a scale-free network as the degree distribution of its vertices follows a power law of exponent 2 < 2.27 < 3 [START_REF] Barabási | Network science[END_REF]. As a result, modularity can be computed and therefore community detection algorithms based on the optimization of modularity, like Louvain [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF], can be run. On G Q , the previous algorithm revealed 8 significant communities, i.e., having a largest size than the resolution limit of the graph [START_REF] Goldstein | Problems with fitting to the power-law distribution[END_REF] (table 3). The overall modularity of G Q is 0.59.

To better understand the communities and their relationships, the domain experts of the interdisciplinary project have manually assigned to each community a label related to its main topics by analyzing, for each, its 30 most used hashtags (top-hashtags). This labeling step revealed that the two biggest communities of G Q gather respectively pro and anti-vaccine individuals. Table 4 lists the elements among the 30 top-hashtags of these last two communities used to infer the labels.

Community

Top-hashtags (translated from French) Pro-vaccines Mutation,

, Ethics, BeBraveWHO, IWillNotGetVaccinated Table 4: Top-hashtags highlighting the main topics of the pro and anti-vaccine communities Since these two main topics are opposite, we expect polarization between the communities. Thus, the anti and pro-vaccine communities should be cohesive and closed communities and their mutual relationship should be antagonistic. To experimentally confirm this expectation, we apply our implementation of the algorithm 1 on G Q . The computed results are shown in figures 5 and 6. Figure 4 gives supplementary information about the sizes of the boundaries.

Values on the lines of the antagonism matrix (figure 5) express how much the community heading the line is likely to express antagonism toward the communities heading the columns. Conversely, values on the columns indicate how much the community heading the column is likely to receive antagonism from the communities heading the lines.

Columns related to the pro and anti-vaccine communities show that both do not receive much antagonism from the other communities. The community the most likely to be antagonistic with the pro-vaccine community is the anti-vaccine community (0.278) and vice versa (0.152). Lines related to these two communities show however that both are pretty likely to have antagonistic behaviors with all the communities. Two hypotheses might explain the lower values between Fig. 4: Size of boundaries of G Q the two communities in comparison with the others: 1) the anti and pro-vaccine boundaries are not very antagonistic with each other ; 2) the lively debates between these communities lead some boundary members to communicate more with the outside than with the inside.

The matrix representing the porosity of boundaries (figure 6) allows to decide between the two previous hypotheses and shows that the second one is the more likely. Indeed, we see that 10% of the boundary members of the pro-vaccine community interact more with the anti-vaccine community than with the core members of their own community. For the anti-vaccine community, the equivalent value is around 5%. Thus, these contributions to the debates cause the decrease of the antagonism values for both boundaries. A possible interpretation for this observation is a need for these boundary users to convince their opponents to change their mind.

A deeper understanding of the behavior and roles of these two communities can also be achieved through the lines and columns of the porosity matrix. First, from a broader perspective, we can see that the values on the lines related to both communities are pretty low in comparison with the other ones, meaning that their boundaries do not interact much with the outside. So, anti and pro-vaccine communities are fairly closed communities. Furthermore, on the line related to the anti-vaccine community only, we can see that, even if the values are low, all the boundaries are nearly as porous. Therefore, the anti-vaccine community is almost equally exposed everywhere, which could reveal an additional need to control the debate and the image of the community.

Columns related to these two communities show that they both have a significant impact on the porosity of the other communities, pointing out the general interest of the individuals forming our corpus for the vaccination topic. Higher values in the column related to the anti-vaccine community reveal a trend for this community to trigger a lot of reactions from the boundaries of the other communities. Because we are working with quotes, these reactions could be sarcastic, ironic or humorous, and therefore rather negative.

In brief, the metrics of the ERIS method describe a relationship likely to be antagonistic between two fairly closed communities. From this observation, we can conclude that, as expected, the pro and anti-vaccine communities are polarized in our corpus. The ERIS method successfully highlights the traces of polarization within a graph built from interactions between individuals in OSN.

Discussions

In this section, we discuss about threats to validity for our method and ideas to improve the interpretability of our metrics.

Before using ERIS, a well informed user should be careful about some points that could threaten its interpretations. First, one should make sure of the objectivity of the data harvesting process, to avoid bias in the data. The longer the time period covered by the dataset is, the more the information is diluted because of higher probabilities to find random or one-time interactions between individuals. There also may be a shift of attention to subjects. ERIS needs well defined communities, so the user should pay a close attention to the chosen algorithm. For example, the modularity of the graph should be high enough to ensure the realness of detected communities with methods like Louvain. Some communities also could be too small to be significant, so the resolution limit of the graph should be respected. Finally, some relationships do not carry antagonism. For example, sharing features like retweets usually imply endorsement. The user should therefore be well aware of the usual meaning of the chosen interaction before drawing any conclusion with the computed metrics.

If the results are not threatened by the previous points, further analytics can be led to achieve a better understanding of the detected polarization. First of all, keywords or hashtags can be used to characterize the source of the disagreement, for example by looking at the main topics of the boundaries. The impact of the different boundary users on the overall polarization of their community can be further investigated by computing their centrality inside the community and inside the whole graph. Finally, the detected polarization could be contextualized in time to gain insights on its first appearance and its evolution.

Conclusion

Social Network Analysis allows the extraction of value from interactions between individuals and communities of individuals. Discussions and debates about controversial topics can lead to the polarization of the communities of individuals, i.e., their isolation inside closed and mutually antagonistic groups.

In this article, we propose ERIS, an automatic approach to assess polarization between pairs of communities inside graphs built from social interactions. The method analyzes the behavior of community boundaries, individuals acting as intermediaries between the inside and the outside of their community, to compute two metrics called the community antagonism and the porosity of boundaries.

Our formal definition of ERIS takes into consideration three major characteristics of graphs built from social interactions: the weighting, the edge direction and the possible presence of overlapping communities. We also propose an efficient algorithm based on matrix computations as well as an open source implementation in R freely available online.

By allowing a more precise description of the roles inside communities through the concepts of internal and boundary areas, the method could also be used to achieve several other objectives in future works. For example, a possible evolution of ERIS could improve discourse analyzes by exploiting these areas to comment the diffusion of topics from and toward the outside of a community.

Finally, boundary members of communities were identified as key elements to get rid of ideological echo chambers, created from the rejection of contradictory opinions [START_REF] Donkers | The Dual Echo Chamber: Modeling Social Media Polarization for Interventional Recommending[END_REF]. As the ERIS method allows to detect both polarized pairs of communities and the individuals leading to the porosity of boundaries, we would like to investigate how ERIS could be used to build a tool to favor the depolarization of some targeted OSN communities.

Fig. 1 :

 1 Fig. 1: Toy example with 3 communities C 1 (blue), C 2 (red) and C 3 (purple). Communities C 2 and C 3 overlap on vertex 6. For edges, solid lines are internal edges, dotted lines are external edges, thin lines are edges neither internal nor external. Note that e 4,6 is both internal and external. For areas, internal areas are surrounded by solid lines, boundary areas by dotted lines. on the community C 1 . Both internal areas of C 1 with C 2 and C 3 include the same vertices, that is I 1,2 = I 1,3 = {3}. The same observation can be made with its boundary areas, B 1,2 = B 1,3 = {1, 2}. External and internal edges of the pair (C 1 , C 2 ) are EE 1,2 = {e 1,4 , e 1,6 , e 2,6 } and IE 1,2 = {e 1,3 , e 2,3 }.

Fig. 2 :

 2 Fig. 2: Values calculated from the toy example Figure 2 shows the antagonism and the porosity matrices obtained on the graph of the toy example. Figure 2a expresses the sizes of the different boundary areas as a percentage of community members belonging to the boundary. In figure 2b, the antagonism value A 1,2 expressed by the boundary of the community C 1 toward the community C 2 is equal to -0.338 and therefore does not reveal an antagonistic behavior. However, the boundary of the community C 2 is pretty likely to be antagonistic toward the community C 1 since its antagonism value A 2,1 is equal to 0.4. The matrix of figure 2a reveals that all the values equal to 0 in the antagonism matrix are default values resulting from empty boundaries.In figure2c, the porosity value P 1,2 is equal to 100, meaning that B 1,2 is very porous as its members interact more with C 2 than with I 1,2 .

Algorithm 1 9 :

 19 Matrix computations to assess the metrics of ERIS Require: MA, MC Ensure: MANT , MP OR 1: MEE ← MA × MC 2: MI ← (MEE == 0) 3: for c = 1, . . . , |C| do 4:MIC ← MC [, c] ! (MI • ¬MC ) 5: MIE ← (MC [, c] ! (MA × MIC )) • ¬MI 6: MBIE ← (MIE! = 0) 7: MV AN T ← ((MIE/(MIE + MEE)) -0.5) • MBIE 8: MANT [c, ] ← (M T C × MV AN T )/(M T C × MBIE) MP OR[c, ] ← 100 * (M T C × (MV AN T < 0))/( end forthe aggregation of M A to sum the weights of the edges directed toward the internal areas of c (line 5) ; the computation of the antagonism values for the vertices belonging to the boundaries of c (line 6) ; the computation of the antagonism and porosity values for the boundaries of c (lines 8-9).

Fig. 3 :

 3 Fig. 3: Execution times of the algorithms

Fig. 5 :Fig. 6 :

 56 Fig. 5: Antagonism Matrix of G Q

Table 1 :

 1 Naming ConventionsThe inputs of the algorithm are the adjacency matrix M A of G and a community membership matrix called M C . M A is a square matrix of size |V | × |V | containing in each cell the weight of the edge whose source is the vertex heading the row and the destination is the vertex heading the column. M C is a binary matrix of size |V | × |C| in which the value 1 means that the vertex heading the row belongs to the community heading the column, and 0 if not.

			Definition	Symbol	Definition
	G	The graph to analyze	C	The set of communities in G
	V	The set of vertices in G	|V |	The number of vertices in G
	E	The set of edges in G	|C|	The number of communities in G
		Symbol Size Type		Name
		MA	|V | × |V | Int	Adjacency Matrix
		MC	|V | × |C| Bin Community Membership Matrix
		MEE |V | × |C| Int External Edges Weight Matrix
		MI	|V | × |C| Bin	Internals Matrix
		MIC |V | × |C| Bin	Current Internals Matrix
		MIE |V | × |C| Int	Internal Edges Weight Matrix
		MBIE |V | × |C| Bin	Binary Internal Edges Matrix
		MV AN T |V | × |C| Real	Vertices Antagonism Matrix
		MANT |C| × |C| Real	Antagonism Matrix
		MP OR |C| × |C| Real	Porosity Matrix

Table 2 :

 2 Matrices used in Algorithm 1

  .

	Vertices count	24,591
	Edges count	55,703
	Average Strength	4.46
	Diameter	338
	Power Law Exponent γ	2.27
	Resolution Limit	333
	Significant Community count	8
	Modularity	0.59

Table 3 :

 3 Characteristics of G Q

https://github.com/AlexisGuyot/ERIS

https://github.com/rachel-bastos/boundaries-polarization

See https://github.com/AlexisGuyot/ERIS/tree/main/experiment complexity for more detailed explanations on the experiment.

https://projet-cocktail.fr/

Quotes are retweets with additional comments.

Acknowledgment

This work is supported by ISITE-BFC (ANR-15-IDEX-0003) coordinated by G. Brachotte, CIMEOS Laboratory (EA 4177), University of Burgundy.


Alexis Guyot
email: alexis.guyot@u-bourgogne.fr

Annabelle Gillet
email: annabelle.gillet@u-bourgogne.fr

Éric Leclercq
email: eric.leclercq@u-bourgogne.fr

Nadine Cullot
email: nadine.cullot@u-bourgogne.fr

A Formal Framework for Data Lakes Based on Category Theory

Keywords: Information systems → Decision support systems, Business intelligence, Data management systems, Information storage systems, • Software and its engineering → Architecture description languages, • Computer systems organization → Architectures, Data Lakes, Category Theory, Architecture Pattern

The management of Big Data requires flexible systems to handle the heterogeneity of data models as well as the complexity of analytical workflows. Traditional systems like data warehouses have reached their limits due to their rigid schema-on-write paradigm, that requires well identified and defined use cases to ingest data. Data lakes, with their schema-on-read paradigm, have been proposed as more flexible systems in which raw data are directly stored in their original format associated with metadata, to be accessed and transformed only when users need to process or analyze them. Thus, it is necessary to define and control the different levels of abstraction and the dependencies among functionalities of a data lake to use it efficiently. In this article, we present a formal framework aiming to define a data lake pattern and to unify the interactions among the functionalities. We use the category theory as theoretical foundations to benefit from its high level of abstraction and its compositionality. By relying on different categories and functors, we ensure the navigation among the functionalities and allow the composition of multiples operations, while keeping track of the entire lineage of data. We also show how our framework can be applied on a simple example of data lake.

INTRODUCTION

Changes in the way of producing and consuming data have led to the emergence of new issues for information systems. Big Data are especially tied to 5 main concerns, usually referred to 5V: Volume, Variety, Velocity, Veracity and Value. Management of such data requires appropriate environments offering enough flexibility to support heterogeneous data with different models, but also multiple data analysis tools and complex pipelines or workflows. Traditional systems like data warehouses have thereby reached their limits due to their schema-on-write paradigm. Indeed, when using Extract-Transform-Load (ETL) processes to ingest data, the time-consuming and difficult data integration and cleaning steps require well known use cases, that hinder the flexibility of such systems.

Data lakes have been proposed as flexible environments for storing and analyzing Big Data [START_REF] Dixon | Pentaho, Hadoop, and data lakes[END_REF] with a schema-on-read paradigm. In other words, raw data are usually directly stored in their original format and only processed when needed, but at the cost of complex model transformations that are supported by users. Different kind of metadata are proposed to help users to navigate, select, validate and transform data according to their needs. To a certain extent, it prevents from turning data lakes into data swamps [START_REF] Gartner | Gartner Says Beware of the Data Lake Fallacy[END_REF], whose usability is reduced because of the difficulty to localize data. Data lakes have been described multiple times in the literature [START_REF] Couto | A Mapping Study about Data Lakes: An Improved Definition and Possible Architectures[END_REF][START_REF] Ravat | Data lakes: Trends and perspectives[END_REF][START_REF] Sawadogo | On data lake architectures and metadata management[END_REF]], but we follow Hai et al. 's definition [START_REF] Hai | Data lake concept and systems: a survey[END_REF]:

A data lake is a flexible, scalable data storage and management system, which ingests and stores raw data from heterogeneous sources in their original format, and provides query processing and data analytics in an on-the-fly manner. This definition is fairly complete. It presents the data lake as an integrated system from the user's perspective (for example a data engineer), exposing multiple functionalities. At a technical level, a data lake is in fact an architecture that brings together specialized components.

Despite being defined as systems for both storing and processing data with management and analytical processes, few architectures of data lakes take all these aspects into consideration in a unified manner [START_REF] Sawadogo | On data lake architectures and metadata management[END_REF]. This has led to the creation of alternative systems like Delta Lakes [START_REF] Armbrust | Delta lake: high-performance ACID table storage over cloud object stores[END_REF], Lakehouses [START_REF] Armbrust | Lakehouse: a new generation of open platforms that unify data warehousing and advanced analytics[END_REF] and Data Mesh [START_REF] Dehghani | How to move beyond a monolithic data lake to a distributed data mesh[END_REF], that focus on improving a subset of functionalities of data lakes. As a result, these systems have major drawbacks: they do not necessarily meet the functional requirements and they lack robustness. One of the main causes is that they are built as an assembly of isolated components having different behavioral properties, and thus it is difficult to ensure the validity of the expected properties for the whole system. However, the use of multiple components to support all the functionalities of the data lake is inevitable. Thus, the notion of data lake is in fact an architecture pattern in which the functionalities are well-defined. To avoid the data lake construction issues, some works narrow their system for a specific use case according to different domains [START_REF] Liu | Ar-chaeoDAL: A Data Lake for Archaeological Data Management and Analytics[END_REF][START_REF] Mcpadden | A scalable data science platform for healthcare and precision medicine research[END_REF][START_REF] Amr | Data lake lambda architecture for smart grids big data analytics[END_REF][START_REF] Sarathkumar Rangarajan | Scalable architecture for personalized healthcare service recommendation using big data lake[END_REF][START_REF] Sarramia | CEBA: A Data Lake for Data Sharing and Environmental Monitoring[END_REF]. We adopt a more abstract point of view, and aim to define a framework allowing to generalize the data lake pattern and to unify the component interactions.

The greater control offered by robust systems is usually obtained through solid theoretical foundations [START_REF] Broy | Can practitioners neglect theory and theoreticians neglect practice[END_REF][START_REF] Johnson | Where's the theory for software engineering[END_REF], such as Codd's relational model [START_REF] Frank | A relational model of data for large shared data banks[END_REF] and algebra for database management systems, which can provide formal frameworks for studying different properties and their preservation or for building optimization processes. Data lakes, as pragmatic solutions originally designed to resolve industrial issues, were not defined at the time with strong theoretical foundations to describe and validate their functionalities, or to control their uses. Nevertheless, they could benefit from such framework.

Category theory [START_REF] Eilenberg | General theory of natural equivalences[END_REF] is a meta-mathematical formalism introduced in the 1940s by Saunders MacLane and Samuel Eilenberg. It has already been successfully used for building formal frameworks in various domains of computer science like functional programming or software architectures. These domains especially benefit from the high level of abstraction and compositionality of this theory. Data lakes can greatly take advantage of these characteristics, as data and functions need to be represented altogether. Indeed, the schema-on-read paradigm requires enough expressivity to allow all kind of processing, but it also necessitates constraints in order to control data and metadata organization as well as their transformations and analysis. Category theory can provide all of these requirements.

In this article, we propose to use category theory to build a formal framework allowing the interconnections among the different functionalities of a data lake, and unifying the levels of abstraction. It allows to compose the functionalities, and thus to keep track of the lineage of data, in order to give a formal structure to data lakes while coping with their need for flexibility. We also show the usability of the framework by applying it to an example of simple data lake.

The remainder of this paper is structured as follows. First, we describe in section 2 the main functionalities of data lakes according to the literature, we present other formalisms previously proposed for data lakes and we show how the category theory can contribute to the formalization of these systems. In section 3, we introduce the main concepts of the category theory and our formal framework. We then use it to model a small example of data lake in section 3.3. Finally, we draw conclusions of our work and open up perspectives for the future in section 4.

STATE OF THE ART AND DISCUSSION

In this section, after describing the main functionalities of data lakes, we argue that various levels of abstraction and dependencies among functionalities justify the need of a formalism allowing both abstraction and composition. In a second part, we study the major works regarding the formalization of data lake components and we show how category theory can be used in this context.

Main Functionalities of Data Lakes

Reviews of the literature [START_REF] Couto | A Mapping Study about Data Lakes: An Improved Definition and Possible Architectures[END_REF][START_REF] Hai | Data lake concept and systems: a survey[END_REF][START_REF] Ravat | Data lakes: Trends and perspectives[END_REF][START_REF] Sawadogo | On data lake architectures and metadata management[END_REF] agree on 4 main functionalities for data lakes, namely Data Storage, Data Ingestion, Data Maintenance and Data Exploration.

Data Storage can take several forms in data lakes, from single systems handling data heterogeneity with generic models [START_REF] Farid | CLAMS: bringing quality to data lakes[END_REF][START_REF] Raghu Ramakrishnan | Azure data lake store: a hyperscale distributed file service for big data analytics[END_REF] to polystores built as an assembly of specialized database management systems [START_REF] Beheshti | CoreKG: a knowledge lake service[END_REF][START_REF] Hai | Constance: An intelligent data lake system[END_REF][START_REF] Alon Y Halevy | Managing Google's data lake: an overview of the Goods system[END_REF]. As datasets must be properly and accurately annotated with metadata so that the data lake does not become a data swamp [START_REF] Gartner | Gartner Says Beware of the Data Lake Fallacy[END_REF], the data storage functionality also includes the storage of metadata.

Data Ingestion provides tools for connecting the system to data sources, loading the data in streaming and/or batch manner and retrieving or producing basic metadata [START_REF] Gao | Navigating the data lake with datamaran: Automatically extracting structure from log datasets[END_REF][START_REF] Quix | Metadata extraction and management in data lakes with GEMMS[END_REF]. Some data may require to only store aggregated insights to reduce their important volume, as it is the case for data streams of sensor data with high velocity.

Data Maintenance ensures: 1) the usability of the data by organizing the lake [START_REF] Alserafi | Towards information profiling: data lake content metadata management[END_REF][START_REF] Maccioni | KAYAK: a framework for justin-time data preparation in a data lake[END_REF] and by extracting more advanced metadata [START_REF] Beheshti | CoreKG: a knowledge lake service[END_REF][START_REF] Castro Fernandez | Aurum: A data discovery system[END_REF][START_REF] Alon Y Halevy | Managing Google's data lake: an overview of the Goods system[END_REF], for example through profiling or through the discovery of relationships among datasets; 2) the quality of data [START_REF] Farid | CLAMS: bringing quality to data lakes[END_REF][START_REF] Hai | Relaxed functional dependency discovery in heterogeneous data lakes[END_REF], by guarantying or improving it, for example through the application of integrity constraints; and 3) the ease of use of the system by providing functionalities that make schema-on-read simpler and more efficient such as schema pre-integration [START_REF] Hai | Constance: An intelligent data lake system[END_REF].

Finally, Data Exploration functionality allows the discovery of content in data lakes through unified query interfaces [START_REF] Beheshti | CoreKG: a knowledge lake service[END_REF][START_REF] Hai | Constance: An intelligent data lake system[END_REF] or navigational algorithms based on measures of relatedness [START_REF] Castro Fernandez | Aurum: A data discovery system[END_REF] or faceted search [START_REF] Alon Y Halevy | Managing Google's data lake: an overview of the Goods system[END_REF]. During the exploration phase, datasets are retrieved and integrated in an on-the-fly manner. Queries and algorithms can be applied on them in order to obtain results according to the case study.

The description of the functionalities extracted from the literature reveals two major characteristics of data lakes. Firstly, it brings to light different levels of abstraction related to: 1) data, including various models, formats and metadata; 2) software architectures, with different strategies and components that can be used to store and process data; and finally 3) functionalities themselves, composed to implement other higher level services. Secondly, the definitions also reveal existing dependencies among the main functionalities. Data exploration depends on data maintenance and on data storage, data storage depends on data ingestion and finally data maintenance depends on data storage.

The higher complexity induced by abstractions and dependencies is a strong motivation for building a formal framework able to ensure the robustness of data lakes and to control the interactions among components.

On Formalization of Data Lakes

Only few proposals have been made to provide such formal framework for data lakes. Most of previous works have focused on the formalization of mostly isolated aspects of data lakes such as metadata models, data storage, analytical queries, etc.

Several models have been proposed for metadata modeling using UML, entity relationship or graph theory. In [START_REF] Scholly | Coining goldMEDAL: a new contribution to data lake generic metadata modeling[END_REF] the authors state that existing metadata models are either tailored for a specific use case or not generic enough to be used in different contexts. They extend their previous model called MEDAL (MEtadata model for DAta Lakes) to build a more generic one called goldMEDAL, defined on three levels: conceptual, logical and physical. The conceptual level is formalized through set theory and describes data entities and groupings, as well as hierarchy and lineage relationships. The logical level puts together the previous elements through graph theory concepts, especially nodes, edges and hyperedges. The physical level is finally implemented with the metadata framework Apache Atlas. The overall proposal of goldMEDAL is synthesized in a UML class diagram.

In [START_REF] Ravat | Metadata management for data lakes[END_REF], a classification of metadata in two groups is proposed, with a special attention given to metadata related to data governance concerns such as data access, quality and security. Metadata describing various relationships among datasets are classified as inter-metadata and metadata describing datasets themselves are classified as intra-metadata. The conceptual metadata model is represented with a UML class diagram. A data lake architecture based on three zones is also represented but not formalized. This proposal has been later extended by the authors in [START_REF] Zhao | A Zone-Based Data Lake Architecture for IoT, Small and Big Data[END_REF] with a new analysisoriented metadata model, also conceptualized through a UML class diagram.

Finally for metadata models, ensemble modeling and more precisely data vaults are used in [START_REF] Iuri D Nogueira | Modeling data lake metadata with a data vault[END_REF] to create a model allowing better evolutivity for data and schema. At the conceptual level, datasets are classified inside satellites, logically abstracted inside hubs and finally associated inside links. The proposal is represented with a graph.

The storage layer of semantic data lakes has been formalized with set theory in [START_REF] Diamantini | A Semantic Data Lake Model for Analytic Query-Driven Discovery[END_REF] as a tuple containing a set of data sources (datasets), a set of metadata catalogs describing the datasets with directed graphs, a global knowledge graph and a mapping function relating metadata to knowledge concepts in the global graph. In the same article, the authors also propose a set-theoretical formalization of analytical queries. They are defined as sets of indicators of interest measured along sets of dimensions of analysis. A response to such query is a set of metadata and transformation rules allowing the discovery of relevant data.

In [START_REF] Hai | Data lake concept and systems: a survey[END_REF], the authors compare four formal schema mapping languages based on tuple-generating dependencies (tgds), namely simple tgds, nested tgds, second-order tgds (SO tgds) and plain SO tgds, as potential formal frameworks for integration tasks in data lakes. The different tgds are compared depending on their expressiveness as well as on the set of structural or reasoning properties they can ensure among the existence of universal solutions, closure under target homomorphism and allowing conjunctive query rewriting. SO tgds languages are identified as more expressive than the other two but also less reliable on the properties due to their higher time complexity for model checking.

Despite existing attempts to formalize parts of data lakes, a formal framework allowing a unified and complete representation of all the functionalities and levels of abstraction of such systems is still missing. Moreover, existing pieces of formal definitions are mainly based on semi-formal and descriptive models like UML or labeled graphs, which are not restrictive enough to guarantee mathematical, structural and/or reasoning properties to the proposed model and to ensure their preservation in any subsequent concrete implementation [START_REF] Broy | UML formal semantics: lessons learned[END_REF].

Contributions of Category Theory to Data Lakes

Category theory is an abstract meta-mathematical theory. It helps to reconcile the expressiveness of descriptive models and the restrictiveness of mathematical ones. This formalism has already been successfully used to address some challenges of computer science, for example to build a general framework for the specification of concurrent systems [START_REF] Ehrig | Applications of category theory to the area of algebraic specification in computer science[END_REF] or to allow the compositionality of machine learning components [START_REF] Shiebler | Category theory in machine learning[END_REF]. To the best of our knowledge, it has never been studied as foundation for a complete formal framework for data lakes. Nevertheless, some works tackle relevant issues to these systems with category theory. Related to the data storage functionality, schemas and data instances in relational databases have been modeled with small categories and set-valued functors in [START_REF] Spivak | Categorical Information Theory[END_REF], and constraints with functors and natural transformations later in [START_REF] David | Database queries and constraints via lifting problems[END_REF]. Frameworks for objectoriented databases have been proposed in [START_REF] Kolencık | Categorical Framework for Object-Oriented Database Model[END_REF] and for documentoriented databases in [START_REF] Toth | Database engineering from the category theory viewpoint[END_REF]. The management of multi-model data and data integration issues are studied in [START_REF] Holubova | Categorical Management of Multi-Model Data[END_REF][START_REF] Liu | Multi-model database management systems-a look forward[END_REF][START_REF] Uotila | A Formal Category Theoretical Framework for Multi-model Data Transformations[END_REF] with some basic categorical tools like categories and functors as well as with more advanced one like pullbacks, pushforwards and kan lifts. Finally, metadata models based on category theory have been proposed in [START_REF] Cafezeiro | Semantic Interoperability via Category Theory[END_REF][START_REF] Diskin | The Arrow Logic of Metadata Environment: A Formalised Graph-Based Framework for Structuring Metadata Repositories[END_REF].

On data maintenance, category theory has been mostly used to ensure data quality, through a metamodel adapted for geographic information systems in [START_REF] Andrew | Metamodels for data quality description[END_REF] and through a framework for variability models of software engineering in [START_REF] Munoz | Category Theory Framework for Variability Models with Non-functional Requirements[END_REF].

Finally, on data exploration, most of the existing works using category theory focus on query processing. In [START_REF] Gottlob | Monadic queries over tree-structured data[END_REF][START_REF] Grust | Monad comprehensions: a versatile representation for queries[END_REF], monads have been proposed as representation for queries, and monad comprehension is used for query processing. A query language implemented with the functional programming language Haskell, based on functors and using natural transformations for optimization is presented in [START_REF] Thiry | Categories for (Big) Data models and optimization[END_REF]. Category theory also serves as basis for a framework of a search meta-engine in [START_REF] Varoutas | Using category theory as a basis for a heterogeneous data source search meta-engine: the Prométhée framework[END_REF]. Other issues related to the data exploration fonctionality of data lakes include data and schema integration, which has been tackled in [START_REF] David | Functorial data migration[END_REF] with functorial data migration operations, and the creation of data visualization, which has been formalized in [START_REF] Vickers | Understanding visualization: A formal approach using category theory and semiotics[END_REF].

Synthesis

Data lakes have been detailed several times in terms of functionalities, but a formal definition expressed through a theoretical framework is still missing, and existing proposals either lack expressiveness or restrictiveness. Category theory is a promising candidate as foundation for such framework and has already been used in several relevant contexts for data lakes. A categorical definition unifying all the main functionalities of data lakes should provide the formal framework needed to improve them with mathematical properties and theorems, while creating a bridge with the previous works using the same formalism.

FORMALIZATION

In this section, after a brief introduction to category theory, we give a high level theoretical description of the main functionalities of a data lake presented in section 2.1. We show how composition and abstraction can be used to define different levels of representation and how different types of functors can ensure the navigation among them. We explain how our framework can be used to check the validity of an implementation of a data lake. We finally illustrate this on an example in subsection 3.3.

Category theory in a nutshell

Category Theory describes structures as categories and relations between them with functors.

A category 𝐶 is defined by a collection 𝑂𝑏 (𝐶) of objects, a collection 𝐻𝑜𝑚(𝐶) of directed relations between these objects, called morphisms, and a binary associative operation (noted •) to compose morphisms. The sub-collection of morphisms between an object 𝑥 (called domain) and an object 𝑦 (called codomain), both in 𝑂𝑏 (𝐶), can be expressed as 𝐻𝑜𝑚 𝐶 (𝑥, 𝑦), and a morphism 𝑓 between these objects is noted 𝑓 : 𝑥 → 𝑦. Each object 𝑥 ∈ 𝑂𝑏 (𝐶) is associated with an identity morphism 𝑖𝑑 𝑥 : 𝑥 → 𝑥, acting as neutral element with •.

A category 𝐶 is said to be locally small if 𝐻𝑜𝑚(𝐶) is a set, small if 𝑂𝑏 (𝐶) and 𝐻𝑜𝑚(𝐶) are both sets and large otherwise. There is also a large category Cat defined with all objects as small categories and with all morphisms as functors between them.

A functor 𝐹 : 𝐶 → 𝐷 is a structure mapping the objects and morphisms of a category 𝐶 to objects and morphisms of a category 𝐷. Functors preserve identities, that is ∀𝑥 ∈ 𝑂𝑏 (𝐶), 𝐹 (𝑖𝑑 𝑥 ) = 𝑖𝑑 𝐹 (𝑥) , and preserve composition, that is ∀𝑓 : 𝑥 → 𝑦, 𝑔 : 𝑦 → 𝑧, 𝐹 (𝑔 • 𝑓 ) = 𝐹 (𝑔) • 𝐹 (𝑓 ).

A constant functor Δ 𝐶-𝐷 : 𝐶 → 𝐷 is a special mapping that collapses every object in 𝑂𝑏 (𝐶) to a single object 𝑑 ∈ 𝑂𝑏 (𝐷) and every morphism in 𝐻𝑜𝑚(𝐶) to the identity morphism 𝑖𝑑 𝑑 . Surjective functors act on every not empty 𝐻𝑜𝑚 𝐷 (𝑥, 𝑦). A functor 𝐹 : 𝐶 → 𝐷 is said to be surjective if for every 𝑥, 𝑦 ∈ 𝑂𝑏 (𝐷) and every morphism in 𝐻𝑜𝑚 𝐷 (𝑥, 𝑦), there is at least one morphism in 𝐻𝑜𝑚 𝐶 (𝐹 -1 (𝑥), 𝐹 -1 (𝑦)) (surjective mapping on every morphism of D).

A product of two categories 𝐶1 and 𝐶2 produces a new category whose objects are all the possible pairs (𝑥, 𝑦) with 𝑥 ∈ Ob(𝐶1) and 𝑦 ∈ Ob(𝐶2) and morphisms (𝑥, 𝑦) → (𝑥 ′ , 𝑦 ′ ) are pairs (𝑓 , 𝑔) where 𝑓 : 𝑥 → 𝑥 ′ ∈ Hom 𝐶1 (𝑥, 𝑥 ′ ) and 𝑔 : 𝑦 → 𝑦 ′ ∈ Hom 𝐶2 (𝑦, 𝑦 ′ ). A bifunctor has a product of categories as domain, and a category as codomain.

Categorical Framework for Data Lakes

In this subsection, we propose a high level categorical framework for data lakes, based on the description of the main functionalities established in the literature and presented in section 2.

At the highest level of abstraction, a data lake can be seen as a large category DL. This category is more precisely defined in table 1 and is visually represented in figure 1. Its collection of objects 𝑂𝑏 (DL) includes three of the main functionalities identified in section 2, namely Data Storage, Data Ingestion and Data Exploration. These objects are themselves categories. The Data Maintenance functionality has a specific representation. As it mainly transforms data to improve their usability, it is represented by a bifunctor Storage × Storage → Storage. It allows to define maintenance operations that can have a single dataset along with its metadata as input, but also operations that take two datasets with their metadata as input (such as the discovery of relationship between entities). The Data Ingestion functionality represents the entry point for data into the data lake. To do so, its Ingestion category contains three objects: 𝑟𝑎𝑤_𝑑𝑎𝑡𝑎 for data as they are from their source, 𝑑𝑎𝑡𝑎𝑠𝑒𝑡 for data as they enter into the data lake system and 𝑚𝑒𝑡𝑎𝑑𝑎𝑡𝑎 that are extracted from 𝑑𝑎𝑡𝑎𝑠𝑒𝑡. The morphisms in this category show the different steps of data ingestion, i.e., we 𝑙𝑜𝑎𝑑 the 𝑟𝑎𝑤_𝑑𝑎𝑡𝑎 into the system to create a 𝑑𝑎𝑡𝑎𝑠𝑒𝑡, this 𝑑𝑎𝑡𝑎𝑠𝑒𝑡 can be 𝑡𝑟𝑎𝑛𝑠 𝑓 𝑜𝑟𝑚ed (for example to compute aggregated data or to add some lightweight information such as the timestamp of the entry in the data lake), and some 𝑚𝑒𝑡𝑎𝑑𝑎𝑡𝑎 can be 𝑒𝑥𝑡𝑟𝑎𝑐𝑡ed from this 𝑑𝑎𝑡𝑎𝑠𝑒𝑡.

The 𝑑𝑎𝑡𝑎𝑠𝑒𝑡 and its 𝑚𝑒𝑡𝑎𝑑𝑎𝑡𝑎 must be stored into the data lake. This functionality is supported by the Storage category. It is a category, in which objects represent data at different levels of abstraction, linked by morphisms. The different levels considered are the physical one with 𝑚𝑑_𝑠𝑦𝑠𝑡𝑒𝑚 and 𝑑_𝑠𝑦𝑠𝑡𝑒𝑚, the logical one with 𝑑𝑎𝑡𝑎𝑠𝑒𝑡, the conceptual one with 𝑚𝑒𝑡𝑎𝑑𝑎𝑡𝑎 and the structural one with 𝑚𝑑_𝑚𝑜𝑑𝑒𝑙 and 𝑑_𝑚𝑜𝑑𝑒𝑙. The morphims link a 𝑑𝑎𝑡𝑎𝑠𝑒𝑡 to its 𝑚𝑒𝑡𝑎𝑑𝑎𝑡𝑎, and the 𝑑𝑎𝑡𝑎𝑠𝑒𝑡 and 𝑚𝑒𝑡𝑎𝑑𝑎𝑡𝑎 to their respective 𝑚𝑜𝑑𝑒𝑙. The different 𝑚𝑜𝑑𝑒𝑙s are themselves linked to their storage 𝑠𝑦𝑠𝑡𝑒𝑚.

Once the data are stored, they can be accessed in order to be explored. It can be done with the Exploration category. The 𝑐𝑎𝑡𝑎𝑙𝑜𝑔𝑢𝑒 allows the 𝑙𝑜𝑐𝑎𝑙𝑖𝑧ation of a 𝑑𝑎𝑡𝑎𝑠𝑒𝑡, through its 𝑚𝑒𝑡𝑎𝑑𝑎𝑡𝑎. It is possible to run some 𝑞𝑢𝑒𝑟𝑖es or 𝑎𝑙𝑔𝑜𝑟𝑖𝑡ℎ𝑚s on the retrieved 𝑑𝑎𝑡𝑎𝑠𝑒𝑡 in order to get the desired result.

With this representation, constant functors can link different levels when lower level categories are embedded in objects of higher level categories. For example, the refinements carried by the Storage category are all embedded in one object of DL, namely 𝑆𝑡𝑜𝑟𝑎𝑔𝑒. A constant functor Δ 𝑆𝑡𝑜𝑟𝑎𝑔𝑒-𝐷𝐿 : Storage → DL can be used to link the lower level category to the higher level one. Functorial laws are satisfied because every object and every identity morphism in the domain category is mapped to the same object and its identity To use the categories of the framework with an instance of a data lake, each implementation of a functionality must be represented in a category, that must be linked to its higher-level corresponding category with a surjective functor. The surjective condition ensures the respect of the proposed framework and its structure, while allowing more complete descriptions of functionalities in the category of the implementation. Furthermore, the morphisms of the DL category add a constraint that forces the existence of functors between the categories concerned by each morphism when they are represented as objects in the DL category.

To ensure the navigation between the functionalities of the data lake, functors exist between the Ingestion and the Storage categories, and between the Storage and the Exploration categories. The defined functors and morphisms force the direction of the different transformations, and avoid the scattering of data. As the categories that will be defined for the implementation must be linked to their corresponding higher-level category, this forces also the implementation to provide these functors between the different implemented functionalities.

By relying on their constraints, such as the preservation of identities and the composition of morphisms, functors allow to keep track of data from their loading into the data lake to the production of results from a dataset in the exploration phase. Indeed, all the objects and the morphisms of the domain category must be sent to the codomain category. So, no information is lost when switching from a functionality to another.

The maintenance functionality takes a different form in the formalization framework. As it aims at improving the quality of the datasets or the metadata in order to ease their use during the exploration phase, two major applications of a maintenance operation can be found: improving a dataset or its metadata directly from themselves or improving a dataset or its metadata by relying on another dataset along with its metadata. Within the category theory, it is possible to use bifunctors to cover both of these applications. To do so, the bifunctor 𝑚𝑎𝑖𝑛𝑡𝑒𝑛𝑎𝑛𝑐𝑒 is defined as Storage × Storage → Storage. The first Storage category corresponds to the one on which the maintenance operation is applied, the second one corresponds to the one that will bring the elements required to the improvement (it can be the same Storage category as the first one when it is used to improve itself). The last Storage category is the result of the maintenance operation, and can be seen as the evolution of the first Storage category.

The figure 3 gives an overview of this mechanism. The objects (𝑑𝑎𝑡𝑎𝑠𝑒𝑡, 𝑚𝑒𝑡𝑎𝑑𝑎𝑡𝑎) and (𝑚𝑒𝑡𝑎𝑑𝑎𝑡𝑎, 𝑑𝑎𝑡𝑎𝑠𝑒𝑡) can be mapped either on the object 𝑚𝑒𝑡𝑎𝑑𝑎𝑡𝑎 or on the object 𝑑𝑎𝑡𝑎𝑠𝑒𝑡 of the resulting Storage category depending on the effect of the maintenance operation. We detail a little more this mechanism with an example in the following section. The other associations of objects are omitted for the sake of readability. This representation allows the composition of multiple maintenance operations, while giving freedom to apply them in any order and to any data. Thus, the maintenance operations can be chosen according to the individual needs of each dataset. Furthermore, it has also constraints, as a maintenance operation can only be applied on existing datasets and metadata. This contributes to the identification of dependencies among datasets and metadata.

So, in its globality, this framework keeps track of the entire lineage of data. It is possible to know the source of data, how they have been transformed and the relationships that exist among datasets. It also imposes constraints on the validity of transformations applied on data, and on the switching from a functionality to another. Furthermore, operations can be composed, mainly with the 𝑚𝑎𝑖𝑛𝑡𝑒𝑛𝑎𝑛𝑐𝑒 functor, in order to allow a high flexibility that is essential to data lakes.

Example

We propose to show the usability of our categorical framework by defining a small data lake. We rely on the following use case: an enterprise has data about their customers, and records their online activity on the enterprise web applications.

The instances of the Ingestion and Storage categories are represented in figure 4. Regarding the data of the online activity, the enterprise is not interested by all the data, so it performs an aggregation operation in order to store only a summary of the data (category Ing_ds1). The data of the customers are easier to handle. As they are extracted from the enterprise information system, they do not need any transformation before being stored into the data lake (category Ing_ds2).

Once the data are ingested, they are stored in the data lake. For the activity data, the dataset is modeled as time series and InfluxDB is used as storage system. For the metadata, they are modeled as graphs in Neo4j (category Str_ds1). Regarding the customer data, the metadata are stored in the file system as JSON format, and the dataset in the relational PostgreSQL database (category Str_ds2).

The table 3 states the effects of functors on the objects and morphisms from the instance categories of the figure 4 to the corresponding high-level categories Ingestion and Storage. Thus, the ingestion and storage functionalities of the implemented data lake satisfy the requirements of the formalization including the surjectivity condition on functors.

Once the two datasets are stored, a maintenance operation can be applied on them (figure 5). In this operation, the dataset of the temporal activity is enriched with the data about customers (category Str_ds1_v2) in order to gain more information regarding their different characteristics, for example their country that can be used to make the typical hours of activity more precise. With this enriched dataset, an exploration is performed, first to reduce the dataset on a given period, and then to execute an anomaly detection algorithm to reveal fraudulent uses. This example demonstrates how the category theory supports the navigation across abstraction levels and how properties on functors constrain the implemented functionalities to comply to the structure defined in the corresponding higher-level categories. Moreover, the framework allows to represent all the potential functionalities of a data lake, and thus to use it to check the validity of an implementation of a data lake.

CONCLUSION

In this article, we have proposed a unified formal framework for data lakes based on category theory. The navigation between the different functionalities is controlled by functors and compositions, that allow to keep track of the lineage of data while providing the flexibility required by these systems. The levels of abstraction of the data lake are linked with constant or surjective functors, that ensure the validity of implementations of data lakes. We have shown on an example how the framework can be used.

Unlike previous works on the formalization of data lakes, our proposal considers a unified and complete view of all the main functionalities identified by the literature, namely Data Ingestion, Data Storage, Data Maintenance and Data Exploration. Thanks to the expressiveness and restrictiveness of category theory, we have also been able to represent and control the various dependencies and levels of abstraction existing in data lakes. Category theory additionally creates a bridge with existing works of the literature using the same formalism, allowing their use as refinements of some higher level aspects described in our framework.

As perspectives for future works, we plan to extend our formalism to allow the definition and control of complex and hybrid workflows for accessing and querying data in data lakes. Such workflows are indeed very important for these systems, in which a variety of operations can be executed in the same environment like for example operators of relational algebra, machine learning tasks based on linear algebra, user-defined functions, etc. These various operations could therefore be unified by expressing them through categories, functors and bifunctors and then linked to the rest of the framework. We also plan to introduce the physical level of components in the data lake architecture by mapping the implemented functionalities to their corresponding component through functors. With this configuration, we can rely on a previous work [START_REF] Gillet | Lambda+, the Renewal of the Lambda Architecture: Category Theory to the Rescue[END_REF] that allows to check the conservation or the loss of technical properties in an architecture with the category theory. We also think about exploring more the capabilities of the 𝑚𝑎𝑖𝑛𝑡𝑒𝑛𝑎𝑛𝑐𝑒 functor, that could be used to control the models of the dataset and the metadata depending on their original models with the (𝑑_𝑚𝑜𝑑𝑒𝑙, 𝑑_𝑚𝑜𝑑𝑒𝑙) object of the product of categories. It can serve to detect model transformations that will lose precision compared to the original model.

Figure 1 :

 1 Figure 1: Representation of the category DL

functor

  Effects of store on objectsEffects of explore on objects

Figure 2 :

 2 Figure 2: Representation of the categories Ingestion, Storage and Exploration, and the functors that link them

Figure 3 :

 3 Figure 3: Partial representation of the 𝑚𝑎𝑖𝑛𝑡𝑒𝑛𝑎𝑛𝑐𝑒 functor, in which the immutable parts are represented

Figure 4 :

 4 Figure 4: The ingestion and storage of the two datasets

Figure 5 :

 5 Figure 5: A maintenance operation followed by an exploration

Table 1 :

 1 High level categories of the framework

	Name		Objects	Morphisms (without identity morphisms)
	DL		storage, ingestion,	𝑠𝑡𝑜𝑟𝑒 : 𝐼𝑛𝑔𝑒𝑠𝑡𝑖𝑜𝑛 → 𝑆𝑡𝑜𝑟𝑎𝑔𝑒
			exploration	𝑒𝑥𝑝𝑙𝑜𝑟𝑒 : 𝑆𝑡𝑜𝑟𝑎𝑔𝑒 → 𝐸𝑥𝑝𝑙𝑜𝑟𝑎𝑡𝑖𝑜𝑛
				𝑚𝑎𝑖𝑛𝑡𝑒𝑛𝑎𝑛𝑐𝑒 : 𝑆𝑡𝑜𝑟𝑎𝑔𝑒 × 𝑆𝑡𝑜𝑟𝑎𝑔𝑒 → 𝑆𝑡𝑜𝑟𝑎𝑔𝑒
	Ingestion		raw_data, dataset,	𝑙𝑜𝑎𝑑 : 𝑟𝑎𝑤_𝑑𝑎𝑡𝑎 → 𝑑𝑎𝑡𝑎𝑠𝑒𝑡
			metadata	𝑡𝑟𝑎𝑛𝑠 𝑓 𝑜𝑟𝑚 : 𝑑𝑎𝑡𝑎𝑠𝑒𝑡 → 𝑑𝑎𝑡𝑎𝑠𝑒𝑡
				𝑒𝑥𝑡𝑟𝑎𝑐𝑡 : 𝑑𝑎𝑡𝑎𝑠𝑒𝑡 → 𝑚𝑒𝑡𝑎𝑑𝑎𝑡𝑎
	Storage		metadata, dataset,	𝑑𝑒𝑠𝑐𝑟𝑖𝑏𝑒𝑑_𝑏𝑦 : 𝑑𝑎𝑡𝑎𝑠𝑒𝑡 → 𝑚𝑒𝑡𝑎𝑑𝑎𝑡𝑎
			d_model, d_system	𝑚𝑑_𝑚𝑜𝑑𝑒𝑙𝑒𝑑_𝑏𝑦 : 𝑚𝑒𝑡𝑎𝑑𝑎𝑡𝑎 → 𝑚𝑑_𝑚𝑜𝑑𝑒𝑙
			md_model, md_system	𝑚𝑑_𝑠𝑡𝑜𝑟𝑒𝑑_𝑖𝑛 : 𝑚𝑑_𝑚𝑜𝑑𝑒𝑙 → 𝑚𝑑_𝑠𝑦𝑠𝑡𝑒𝑚
				𝑑_𝑚𝑜𝑑𝑒𝑙𝑒𝑑_𝑏𝑦 : 𝑑𝑎𝑡𝑎𝑠𝑒𝑡 → 𝑑_𝑚𝑜𝑑𝑒𝑙
				𝑑_𝑠𝑡𝑜𝑟𝑒𝑑_𝑖𝑛 : 𝑑_𝑚𝑜𝑑𝑒𝑙 → 𝑑_𝑠𝑦𝑠𝑡𝑒𝑚
	Exploration	catalogue, dataset	𝑙𝑜𝑐𝑎𝑙𝑖𝑧𝑒 : 𝑐𝑎𝑡𝑎𝑙𝑜𝑔𝑢𝑒 → 𝑑𝑎𝑡𝑎𝑠𝑒𝑡
			metadata	𝑞𝑢𝑒𝑟 𝑦 : 𝑑𝑎𝑡𝑎𝑠𝑒𝑡 → 𝑑𝑎𝑡𝑎𝑠𝑒𝑡
				𝑎𝑙𝑔𝑜𝑟𝑖𝑡ℎ𝑚 : 𝑑𝑎𝑡𝑎𝑠𝑒𝑡 → 𝑑𝑎𝑡𝑎𝑠𝑒𝑡
				𝑑𝑒𝑠𝑐𝑟𝑖𝑏𝑒𝑑_𝑏𝑦 : 𝑑𝑎𝑡𝑎𝑠𝑒𝑡 → 𝑚𝑒𝑡𝑎𝑑𝑎𝑡𝑎
	Name		Type	Elements in Domain Elements in Codomain
	𝑠𝑡𝑜𝑟𝑒	𝐼𝑛𝑔𝑒𝑠𝑡𝑖𝑜𝑛 → 𝑆𝑡𝑜𝑟𝑎𝑔𝑒	𝑟𝑎𝑤_𝑑𝑎𝑡𝑎	𝑑𝑎𝑡𝑎𝑠𝑒𝑡
				𝑑𝑎𝑡𝑎𝑠𝑒𝑡	𝑑𝑎𝑡𝑎𝑠𝑒𝑡
				𝑚𝑒𝑡𝑎𝑑𝑎𝑡𝑎	𝑚𝑒𝑡𝑎𝑑𝑎𝑡𝑎
				𝑙𝑜𝑎𝑑	𝑖𝑑 𝑑𝑎𝑡𝑎𝑠𝑒𝑡
				𝑡𝑟𝑎𝑛𝑠 𝑓 𝑜𝑟𝑚	𝑖𝑑 𝑑𝑎𝑡𝑎𝑠𝑒𝑡
				𝑒𝑥𝑡𝑟𝑎𝑐𝑡	𝑑𝑒𝑠𝑐𝑟𝑖𝑏𝑒𝑑_𝑏𝑦
	𝑒𝑥𝑝𝑙𝑜𝑟𝑒 𝑆𝑡𝑜𝑟𝑎𝑔𝑒 → 𝐸𝑥𝑝𝑙𝑜𝑟𝑎𝑡𝑖𝑜𝑛	𝑑𝑎𝑡𝑎𝑠𝑒𝑡	𝑑𝑎𝑡𝑎𝑠𝑒𝑡
				𝑑_𝑚𝑜𝑑𝑒𝑙	𝑑𝑎𝑡𝑎𝑠𝑒𝑡
				𝑑_𝑠𝑦𝑠𝑡𝑒𝑚	𝑑𝑎𝑡𝑎𝑠𝑒𝑡
				𝑚𝑒𝑡𝑎𝑑𝑎𝑡𝑎	𝑚𝑒𝑡𝑎𝑑𝑎𝑡𝑎
				𝑚𝑑_𝑚𝑜𝑑𝑒𝑙	𝑚𝑒𝑡𝑎𝑑𝑎𝑡𝑎
				𝑑_𝑠𝑦𝑠𝑡𝑒𝑚	𝑚𝑒𝑡𝑎𝑑𝑎𝑡𝑎
				𝑑𝑒𝑠𝑐𝑟𝑖𝑏𝑒𝑑_𝑏𝑦	𝑑𝑒𝑠𝑐𝑟𝑖𝑏𝑒𝑑_𝑏𝑦
				𝑑_𝑚𝑜𝑑𝑒𝑙𝑒𝑑_𝑏𝑦	𝑖𝑑 𝑑𝑎𝑡𝑎𝑠𝑒𝑡
				𝑑_𝑠𝑡𝑜𝑟𝑒𝑑_𝑖𝑛	𝑖𝑑 𝑑𝑎𝑡𝑎𝑠𝑒𝑡
				𝑚𝑑_𝑚𝑜𝑑𝑒𝑙𝑒𝑑_𝑏𝑦	𝑖𝑑 𝑚𝑒𝑡𝑎𝑑𝑎𝑡𝑎
				𝑚𝑑_𝑠𝑡𝑜𝑟𝑒𝑑_𝑖𝑛	𝑖𝑑 𝑚𝑒𝑡𝑎𝑑𝑎𝑡𝑎

Table 2 :

 2 Functors used in the framework

	morphism in the codomain category (identity preservation) and be-
	cause identity morphisms can always be composed with themselves
	(composition preservation).

Table 3 :

 3 Functors used in the example, between the category representing the instance of a functionality and the highlevel category of the functionality


Rather surprisingly, this is the first dedicated monograph to be published on the northern French peasant revolt of 1358 known as the Jacquerie since Siméon Luce's École des chartes thesis of 1859. Luce's foundational research in both chronicle and archival material was revisited and expanded in the later twentieth century by Raymond Cazelles and Françoise Autrand, amongst others, but in the form either of articles, or of studies whose focus lead them to be classed as exclusively political history. Douglas Aiton's 2007 thesis remains unpublished. The result has been a slippage in interpretation amongst historians both leftleaning and conservative, who tend to follow the 'anti-explanation' advanced by Jules Flammermont in 1879 in which the revolt is the nihilistic act of 'rude peasants, without education or direction, dazed by poverty and drink'. Thus even Michel Mollat and Philippe Wolff saw the revolt as being as 'incoherent as it was spontaneous', an amorphous outpouring of long-held social animus fundamentally explained by poverty. Historians from Jonathan Sumption to David Green concur. In the light of recent research which stresses the rationality

and structure underlying medieval revolts, the time seems ripe to reconsider how Cazelles' emphatically political interpretation, in which the Jacquerie is 'remote-controlled' from Paris by Étienne Marcel and the reformers, might be tweaked to give due prominence to peasant priorities and modes of action.

A monographic approach enables Justine Firnhaber-Baker to show how the political was dominant in this revolt, yet not as something controlled by political professionals in Paris.

Instead the Jacquerie took form through peasant initiatives based on their knowledge of events and the structures of peasant social organisation. Numerous subtle but essential revisions make it possible to fill in this new picture. This is a cumulative process, based on a thorough analysis of lettres de remission (pardons accompanied by narratives that both detail their recipients' crimes and justify them, granted both to rebels and to the nobles who violently suppressed them), Parlement litigation, more miscellaneous sources in provincial archives, and a thorough re-reading of the chronicle material. To start with, Firnhaber-Baker shows that the Jacquerie was not a revolt against lords, but against nobles, the second estate which had so badly failed at Poitiers, and especially those who resisted reform. Ecclesiastical lords, for example, were not attacked, and only two churchmen were victimised, and not because they were clerics. The interpersonal violence which the chronicles put centre-stage was a relatively minor aspect of the revolt next to the destruction of noble castles, fortresses or houses which were often more markers of noble status than military redouts. Only 27 identified individuals were killed by the rebels, 9 of these, including the probable heir of the marshal of Normandy recently murdered by the Parisians, in the incident at Saint-Leu-d'Esserent on 28 May 1358 that marked the beginning of the Jacquerie. Meanwhile, some 32 castles, 2 fortresses, 1 tower and over 27 manor-houses can be identified as destroyed in the documentation, and this is surely the tip of the iceberg. The action at Saint-Leu should be seen as an attempt to stop Charles, duke of Normandy, the king's eldest son, from cutting off Paris' supply lines via the river Oise by garrisoning the castle of Creil, as he had done on the Seine at Montereau and on the Marne at Meaux. So this was a pro-Parisian action, but the initiative was local, and the Parisians were not aware of it in advance. The rebel captains of whom the most famous was Guillaume Calle were home-grown leaders, from the immediate vicinity, although they later joined forces with troops sent from Paris. These were the Jacques Bonhommes mobilised by the summons of the arrière-ban in 1355 and 1356, but whom the king had, fatally, not taken with him against the Black Prince. Moreover, their action was more pre-emptive than reactive. The region north and east of Paris where the Jacquerie broke out had not yet suffered from post-Poitiers military violence, and later activity further east in Champagne seems to have consisted entirely in tentative peasant self-defence initiatives, interpreted by nobles as sedition and violently suppressed as such.

The analysis of the lettres de remission enables Firnhaber-Baker to reject the chroniclerderived clichés which portray the Jacques as impoverished marginals without accepting Cazelles' picture of a revolt of educated officials and well-off artisans. She identifies 498 rebels in the remissions, 27.8% of which include a clause specifying that the pardon will enable the recipient to return to their agricultural occupations, and many of the 15.5% identified as artisans would likely also have pursued agricultural trades. This was thus emphatically a peasants' revolt, although it involved cooperation with towns, both Paris and, more effectively, with locally active towns such as Senlis. Communal mechanisms for information circulation, assembly and mobilisation were its sinews, made effective and legitimate by their frequent use in the cause both of the community and the king. Arguably, however, this ordinariness or normality was also one of the rebels' weaknesses, for the sense it gave of legitimacy was decidedly not shared by the nobles. It seems likely that news circulating from Paris and elsewhere made Charles of Navarre seem a potential ally, convincing Guillaume Calle to parley with him at Mello and Clermont without asking for hostages. Their leader captured, the Jacques were cut down by Navarre's forces, and Calle was murdered soon after. A quarter-century later, Wat Tyler had still not learned the lesson that you can never trust a noble.

Christopher Fletcher

IRHiS (UMR 8529), CNRS/Université de Lille, France