Emmanuel Hadoux

Aurélie Beynier

Paul Weng

Sequential Decision-Making under Non-stationary Environments via Sequential Change-point Detection

Reinforcement Learning (RL) has been mainly interested in computing an optimal policy for an agent acting in a stationary environment. However, in many real world decision problems the assumption on the stationarity does not hold. One can view a non-stationary environment as a set of contexts (also called modes or modules) where a context corresponds to a possible stationary dynamics of the environment. Even most approaches assume that the number of modes is known, a RL method -Reinforcement Learning with Context Detection (RLCD)-has been recently proposed to learn an a pirori unknown set of contexts and detect context changes. In this paper, we propose a new approach by adapting the tools developed in statistics and more precisely in sequential analysis for detecting an environmental change. Our approach is thus more theoretically founded and necessitates less parameters than RLCD. We also show that our parameters are easier to interpret and therefore easier to tune. Finally, we show experimentally that our approach outperforms the current methods on several application problems.

Introduction

Reinforcement learning (RL) [START_REF] Sutton | Reinforcement learning: An introduction[END_REF] is a powerful framework for sequential decisionmaking. It can be seen as an extension of the Markov Decision Process (MDP) model [START_REF] Puterman | Markov decision processes: discrete stochastic dynamic programming[END_REF] when the environment (i.e., transitions and rewards) is not known. The aim in RL is for an agent to learn an optimal policy (e.g., how to act in order to maximize the expected discounted sum of rewards) while interacting with the unknown environment.

In RL, the environment is generally assumed to be stationary (e.g., transitions and rewards do not evolve with time). Without this assumption, the standard RL algorithms may not perform very well. However, one may argue that in practice, the encountered problems are often characterized by non-stationary environments.

As non-stationary environments come in many flavors, tackling the general case is very difficult, if not impossible. In this paper, we restrict ourselves to the situation where the environment changes rarely and somewhat abruptly. The slow rate of change allows learning and the abrupt change allows easier detection. A typical example of such non-stationary problem is that of control of traffic lights. Depending on the time of the day, the traffic follows different "patterns" (e.g., rush hours v.s. non-rush hours).

In the literature, such kind of non-stationary environments has already been actively investigated [START_REF] Choi | Hidden-mode markov decision processes for nonstationary sequential decision making[END_REF][START_REF] Doya | Multiple model-based reinforcement learning[END_REF][START_REF] Da Silva | Dealing with nonstationary environments using context detection[END_REF] in the RL setting. Depending on authors and domains, the pattern followed by the environment, which constitutes a temporary stationary environment, is called mode, context, module or model. [START_REF] Choi | Hidden-mode markov decision processes for nonstationary sequential decision making[END_REF] proposed Hidden-Mode MDPs (HM-MDPs) as an extension of MDPs where the non-stationarity is modeled as a hidden Markov chain, assumed to be known. [START_REF] Choi | An environment model for nonstationary reinforcement learning[END_REF] learns the HM-MDP in a RL setting using the Baum-Welch algorithm. The drawback of this approach is that it assumes the number of modes is known. [START_REF] Doya | Multiple model-based reinforcement learning[END_REF] applies ideas from adaptive control [START_REF] Narendra | Adaptation and learning using multiple models, switching, and tuning[END_REF] to RL, which consists in learning multiple models, computing a "responsibility signal" to evaluate the goodness of each models and averaging the models using this signal. Here, again, the number of models is a priori fixed. More recently, [START_REF] Da Silva | Dealing with nonstationary environments using context detection[END_REF] also proposed to learn several models in RL where an error score is computed for all models in order to select the best current model as the one minimizing this error score. Interestingly, their work allows tackling the case where the number of models is not a priori known. When all learned models has a poor error score, a new model is learned. However, their approach requires multiple parameters to be tuned, depending on the problem at hand. This may be a difficult task as they are not always easy to interpret and their interplay can be subtle and difficult to predict. Besides, their error score seems to be ad-hoc and not very theoretically founded.

In this paper, we propose a new approach for solving this sequential decisionmaking problem under non-stationary environments. Our main idea is to adapt the tools developped in statistics and more precisely in sequential analysis [START_REF] Ghosh | Handbook of Sequential Analysis[END_REF] for detecting an environmental change [START_REF] Basseville | Detection of Abrupt Changes: Theory and Application[END_REF]. This research domain started with the seminal work of [START_REF] Wald | Sequential tests of statistical hypotheses[END_REF] that has been actively developed [START_REF] Lai | Sequential analysis: Some classical problems and new challenges[END_REF] ever since. One of the main problems studied in sequential analysis is that of change point detection, which consists in detecting a change in the statistical property of a random variable that is repeatedly observed. This research has many applications (seismic detection, industrial quality control, signal segmentation. . . ). Although the works of [START_REF] Da Silva | Dealing with nonstationary environments using context detection[END_REF] and [START_REF] Doya | Multiple model-based reinforcement learning[END_REF] could somehow be reinterpreted in the sequential analysis framework, to the best of our knowledge, our paper presents the first work that explicitly exploits those statistical tools. In doing so, our approach is more theoretically founded and necessitates less parameters than that of [START_REF] Da Silva | Dealing with nonstationary environments using context detection[END_REF]. We argue that those parameters are easier to interpret and therefore easier to set a priori for solving new problems. We show experimentally that our approach outperforms the current methods.

Background

MDP and RL

A Markov Decision Process (MDP) is a common model to represent sequential decision-making problems. It is characterized by a tuple S, A, T, R with S the set of states, A the set of actions, T the transition function S × A → Pr(S) and R the reward function S × A → R. Solving a problem modeled by an MDP consists in finding a policy π that is a mapping of A over S.

When all the components of the MDP are known, one can use algorithms such as value iteration [START_REF] Bellman | Dynamic programming[END_REF] or policy iteration [START_REF] Howard | Dynamic Programming and Markov Processes[END_REF]. However, when T and/or R are unknown, reinforcement learning (RL) methods can be used. Indeed, the optimal policy is learned using reward feedbacks from the environment. The policy learned by RL is guaranteed to converge towards an optimal policy if the environment is stationary and the number of experiences is infinite. In practice, the policy learned is -optimal if the number of experiences is high enough.

The problems we try to solve in this paper are non-stationary. Therefore, we cannot directly use either MDP model or RL methods. However, as we restrict ourselves to the situation where the environment changes rarely, we can make the hypothesis that the environment is stationary during a timeframe and changes at the end of the current timeframe.

HM-MDP

Recent works propose to formalize non-stationary environments as a set of contexts (also called modes or modules) where a context corresponds to a possible stationary dynamics of the environments [START_REF] Choi | Hidden-mode markov decision processes for nonstationary sequential decision making[END_REF][START_REF] Doya | Multiple model-based reinforcement learning[END_REF][START_REF] Da Silva | Dealing with nonstationary environments using context detection[END_REF]. Hidden-Mode Markov Decision Processes have been proposed by Choi et al. [START_REF] Choi | Hidden-mode markov decision processes for nonstationary sequential decision making[END_REF] to formalize this idea.

An HM-MDP is characterized by a pair M, C where M is a set of modes {m 1 , . . . , m n } with n the number of possible modes and C : M × M → [0, 1] is a transition function over modes. For all i ∈ {1, . . . , n}, m i = S, A, T i , R i is an MDP. Note that S and A are shared by all m i 's and that an HM-MDP with n = 1 is a standard MDP. In HM-MDPs, the only observable information is the current state s ∈ S, the current mode m ∈ M is not observable.

Recently this model has also been described in the context of MOMDPs [START_REF] Ong | Planning under uncertainty for robotic tasks with mixed observability[END_REF][START_REF] Chadès | MOMDPs: A solution for modelling adaptive management problems[END_REF].

Choi et al. proposed a variant of the Baum-Welch algorithm to learn an HM-MDP. However, one major limitation of this approach is that the number of contexts (or modes) is assumed to be known in advance. Da Silva et al. [START_REF] Da Silva | Dealing with nonstationary environments using context detection[END_REF] have thus proposed a reinforcement learning method for context detection to incrementally build possible models. Their approach allows for an automatic definition and detection of models. da Silva et al. define quality signals for each partial model. When the quality of the current model becomes worse than the quality of another model (already defined), the system detects a context change and switches to the other partial model. If the quality of all the models becomes too poor, a new model is built. However, this approach requires several parameters to be tuned for each decision-problem. These parameters are not easy to interpreted and their interactions are difficult to predict thus leading to an even more difficult tuning.

Detecting an Environmental Change

Let M 0 = (S, A, T 0 , R 0 ) and M 1 = (S, A, T 1 , R 1 ) be two modes or MDPs that are both assumed to be known. We assume the environment is currently represented by M 0 and at some unknown time step, the environment changes from mode M 0 to mode M 1 . The problem we want to tackle here is that of detecting as soon as possible this environmental change. To that aim, a natural idea is to use statistical hypothesis tests for such detections, i.e., given an observed history, a null hypothesis "the current mode is M 0 " is tested against an alternative hypothesis "the current mode is M 1 ". When performing such tests, one wants to minimize the probabilities of two contradictory errors:

type I error: reject the null hypothesis when it is true, type II error: accept the null hypothesis when it is false.

In the online setting, sequential statistical tests are preferred: they perform repeated tests as observations becomes available and permit detections with smaller size samples in expectation [START_REF] Wald | Sequential tests of statistical hypotheses[END_REF] compared to standard statistical tests. Viewing detections as statistical tests highlights the contradiction between fast detection (type I error) and false detection (type II error).

A simple approach to implement those sequential statistical tests for change point detection is to recourse to cumulative sums (CUSUM) [START_REF] Basseville | Detection of Abrupt Changes: Theory and Application[END_REF]. We present the CUSUM approach adapted for our purposes below.

Detecting a Change in Transition Distributions

In our setting, CUSUM can be specified as follows for detecting a change in the transition distributions. Let (s 0 , a 1 , s 1 , a 2 , s 2 , . . . , s t-1 , a t , s t , . . .) denote the observed history and define S T 0 = 0. At each time step t ≥ 1, compute:

S T t = max(0, S T t-1 + ln( T 1 (s t , a t , s t+1 ) T 0 (s t , a t , s t+1 ) )) (1)
and compare S T t to a threshold c T > 0. If S T t ≥ c T , then a change in the transition function is detected. The intuitive idea of CUSUM is quite simple: If M 1 is more likely than M 0 to have generated the recent history, then decide that the environment has changed.

Detecting a Change in Reward Distributions

As in the general case, the observed rewards are stochastic, we assume that R 0 and R 1 are functions from S×A to probability distributions over numerical values (actual obtained rewards). We denote R i (s, a, r) the probability of obtaining numerical reward r when choosing action a in state s in mode M i . Moreover, to simplify the presentation, we assume that the possible numerical rewards are finite and known. This is generally not a very restrictive assumption as we are considering finite-state MDPs.

To detect a change in the reward function, the same procedure as for the transitions can then be applied. Let (r 1 , r 2 , . . . , r t , . . .) be the sequence of obtained rewards and S R 0 = 0. At each time step t ≥ 1, compute:

S R t = max(0, S R t-1 + ln( R 1 (s t , a t , r t ) R 0 (s t , a t , r t ) )) (2)
If S R t is greater than a threshold c R , then a change of the reward function is detected.

Joint Detection

The two previous sums can be combined by computing at each time step t ≥ 1:

S t = max(0, S t-1 + ln( T 1 (s t , a t , s t+1 )R 1 (s t , a t , r t ) T 0 (s t , a t , s t+1 )R 0 (s t , a t , r t ) )) (3)
with S 0 = 0. Sum S t is to be compared with a threshold c to detect a change of mode.

Computing S T t and S R t separately can be advantageous in some situations as this makes it possible to detect a change in the transition function or in the reward function alone. Indeed, in some domains, the non-stationarity is only limited to one of the functions and/or they can evolve in a non synchronous manner. The advantage of using S T R t is that it may allow a faster detection of the environmental change because of the combined effects of the simultaneous change of the transition function and the reward function. For ease of exposition, we will focus in the remainder of the paper on the joint detection of changes in the reward and transition functions.

Detecting Changes with Multiples Models

In the case where there are many possible models M 0 , M 1 , . . . , M k (with k ≥ 2), all assumed to be known, the previous procedures can be adapted as follows. We assume that M 0 is the current model and when a change occurs at an unknown time step, the new model can be any of M i with 1 ≥ i ≥ k. Now, we need to compute k scores at each time step t ≥ 1:

S i,t = max(0, S i,t-1 + ln( T i (s t , a t , s t+1 )R i (s t , a t , r t ) T 0 (s t , a t , s t+1 )R 0 (s t , a t , r t ) )) (4)
with S i,0 = 0 and i = 1, . . . , k. Then an environmental change is detected if max i=1,...,k S i,t ≥ c and the current environment M j is chosen to be S j,t = max i=1,...,k S i,t .

Detecting Changes in practice

In practice, in the RL setting, the number of models and their specifications are generally unknown. In that case, we simply use in the CUSUM procedure the empirical estimates learned from the observed history in place of the unknown models M 0 , M 1 , . . . , M k . We always add among the estimated models, a "uniform" model where all transition and reward probabilities are uniform. This "uniform" model allows new models to be learned. The exact method is explained in details in Section 4.

Concerning the choice of the threshold c in the CUSUM procedure, one possibility is to use the heuristic proposed by [START_REF] Wald | Sequential tests of statistical hypotheses[END_REF] (although in a different simpler setting):

c = ln 1 -β α ( 5
)
where β is the probability of a type II error and α is that of a type I error. Although this choice of the threshold value may not be optimal, this heuristics allows for some interpretation of the parameter. Besides, in our experiments, this choice seems to be reasonable and leads to good performance.

RL with Context Detection

Da Silva et al. developed the Reinforcement Learning with Context Detection algorithm (RLCD) to simultaneously learn and act in a non-stationnary environment. At each time step, a quality measure of each already learned model is calculated, depending on the last seen transition and reward. The model maximizing the measure is chosen as the next current model and is updated. However, if the maximum quality is below a given threshold, a new model is added to the list of known models, uniformly initialized and selected as the next current model. With this method, RLCD is able to tackle problems without the prior knowledge of the number of models to learn. Unfortunately, RLCD requires a set of parameters to be tuned accordingly to the problem. Moreover, this quality mesure seems to be ad-hoc and also depend on a hand-tuned threshold.

We propose an adaptation of RLCD, replacing the quality measure by the approach previously presented. Algorithm 1 presents our adaptation of RLCD using the detection on the transitions distributions. The solving part (given by π mcur (s)) and the learning part are exactly the same as in the original RLCD algorithm.

In this version of RLCD, we calculate S m for each model and detect a change if this value is above c. Moreover, a new model is created if the model maximizing the value is the uniform model. This detection method is not only more theoretically founded, but is also more efficient.

Ball Catching

The first problem is taken from [START_REF] Da Silva | Dealing with nonstationary environments using context detection[END_REF]. In this environment, a cat has to catch a ball moving on a toroidal grid. The direction towards which the ball moves is given by the context of the environment. This problem has 15 × 15 states (the size of the grid), 5 actions (4 possible direction for the cat with a no move choice) and 4 contexts (one for each possible direction for the ball). The reward is set to -1 for each move and 10 when the cat catches the ball. We compare our method to the classic RLCD algorithm, using the same algorithm (Prioritized-Sweeping) to calculate the optimal policy for the currently learned policy. In that way, the differences in the results can only be explained by the efficiency of the context switching detection. As we said, the original RLCD algorithm needs some extra parameters to be set. We used those involving the best results we could find, which were equals to those given in [START_REF] Da Silva | Dealing with nonstationary environments using context detection[END_REF]. Figure 1 shows the results obtained using the following protocol:

a step is the minimum between the number of movements the cat needs to catch the ball and 100 an episode is 100 steps we choose a starting context and run 5 episodes in this context and calculate the mean step for each episode The purpose of this protocol is to study the behaviour of the algorithms with switching to either a learned and an unknown context. Figure 1 shows that for each episode where the context is already known (the 4 last of each 5 episodes), RLCD and our adaptation perform equally. The difference is on the episodes where the context has been switched (the first of each 5 episodes). It takes less movements in mean to catch the ball, meaning the switching has been detected earlier.

Traffic

This problem is composed by 9 independent traffic lights (nodes) controlling the passage of cars one a 3 × 3 grid. The nodes on the edges of the grid are linked to 6 sources (3 at the north and 3 at the east) and 6 sinks (3 at the south and 3 at the west). Cars enter the grid by the sources and go in a straight line to the corresponding sink. Each traffic light can select a plan amongst 3, defining the amount of time it lets pass the cars at the north and the east: the first signal plan gives equal green times for both vertical and horizontal directions, the second signal plan gives priority to the vertical direction and the third signal plan gives priority to the horizontal direction. The environment can be in 3 different contexts conditioning the rate of arrival of the cars at each sources (north or east): low insertion rates from north and east, high insertion rate from north sources and average insertion rate from east, high insertion rates from east sources and average insertion rate from north. The context defined by high insertion rates from both north and east sources is not considered since even an optimal policy does not prevent from saturating the network. We can see that our method performs better than the original RLCD, especially when the environment is running an unknown model (e.g., iteration 400). This means that our adaptation is able to detect the change, create a new model and thus adapt the policy earlier, involving better results.

Conclusion

In this paper we presented a preliminary work using sequential change-point detection to detect context switching and learn the underlying model. We adapted the RLCD algorithm which is able to learn a model without knowing a priori the number of contexts. We showed that this adaptation is able to enhance the detection ability of the original RLCD, thus involving better results.

We will extend this method in a future work in order to learn the transitions between the contexts in a stochastic setting. We will then be able to learn HM-MDPs without fixing the number of modes and thus bypass a requirement of the Baum-Welch adaptation proposed by Choi et al.

An other interesting application of this work is learning HS3MDPs, an extension of the HM-MDP where the transitions between the modes are semimarkovian [START_REF] Hadoux | Solving hidden-semi-markov-mode markov decision problems[END_REF]. It will requires to not only learn the transitions between the contexts but also the time the environment stays in each context.

Fig. 1 .

 1 Fig. 1. Results for the ballcatching problem

Fig. 2 .

 2 Fig. 2. Result for the traffic problem

Figure 2

 2 Figure2presents the results for the traffic problem. It shows the number of stopped cars in the grid, depending on the iteration. The environment starts with a low rate of insertion and changes to the next context every 200 iterations. We can see that our method performs better than the original RLCD, especially when the environment is running an unknown model (e.g., iteration 400). This means that our adaptation is able to detect the change, create a new model and thus adapt the policy earlier, involving better results.

  Algorithm 1 RLCD with Sequential Change-Point Detection

	mcur ← newmodel()
	M ← mcur
	s ← s0, any starting state
	loop
	Let a be the action indicated by πm cur (s)
	Observe next state s and reward r
	for all m ∈ M \ mcur do
	Sm ← max(0, Sm + ln Tm(s,a,s ) T mcur (s,a,s )	)
	end for
	mmax ← arg maxm Sm
	if Sm max > c then S unif orm ← max(0, S unif orm + ln	1/|S| Tm cur (s,a,s ) )
	if S unif orm > c and S unif orm > Sm max then
	mcur ← newmodel()
	M ← mcur
	else
	mcur ← mmax
	end if
	end if
	Update mcur with original RLCD equations
	end loop
	5 Experimental Results


Christophe Crespelle
email: christophe.crespelle@inria.fr

Matthieu Latapy
email: matthieu.latapy@lip6.fr

Thi Ha

Duong Phan
email: phanhaduong@math.ac.vn

On the Termination of Some Biclique Operators on Multipartite Graphs $,$$

Keywords: Clean-factor Graph, Multipartite Graphs, Graph Series, Complex Network Modelling

We define a new graph operator, called the weak-factor graph, which comes from the context of complex network modelling. The weak-factor operator is close to the well-known clique-graph operator but it rather operates in terms of bicliques in a multipartite graph. We address the problem of the termination of the series of graphs obtained by iteratively applying the weak-factor operator starting from a given input graph. As for the clique-graph operator, it turns out that some graphs give rise to series that do not terminate. Therefore, we design a slight variation of the weak-factor operator, called clean-factor, and prove that its associated series terminates for all input graphs. In addition, we show that the multipartite graph on which the series terminates has a very nice combinatorial structure: we exhibit a bijection between its vertices and the chains of the inclusion order on the intersections of the maximal cliques of the input graph.

Introduction

The clique-graph operator [START_REF] Szwarcfiter | A survey on clique graphs[END_REF] is a well-known graph operator which, given a graph G, consists of building the graph G whose vertices are maximal cliques of G and such that there is an edge between two distinct vertices of G iff the corresponding cliques of G share at least one common vertex. The clique-graph series, obtained by iteratively applying the clique-graph operator starting from G, has been widely studied (see e.g. [START_REF] Prisner | Convergence of iterated clique graphs[END_REF][START_REF] Bornstein | On clique convergent graphs[END_REF]). This series is said to be convergent (in the sense of [START_REF] Bornstein | On clique convergent graphs[END_REF]) if one of the graphs of the series is the graph with one single vertex 1 . Then, all the graphs obtained in the following iterations are the same (i.e. reduced to a single vertex).

Here we consider a new operator, called weak-factor graph, which comes from the context of complex network modelling and which operates in terms of bicliques in multipartite graphs rather than cliques in graphs. One of the interest of this operator is that it keeps an explicit and complete track of the original graph at all step of the series: given an arbitrary graph of the series it generates, one can univocally retrieve the original graph which gave rise to the series. Given a k-partite graph G = (V 0 , . . . , V k-1 , E) (see Section 1.2 for a definition), where k ≥ 2, the weak-factor graph G of G is defined as follows (see Definition 5 for a more formal definition): G is the graph G augmented with a new level V k of vertices, each of which corresponds to one non-simple maximal biclique of the bipartite graph which is formed by the edges between the upper level of G, i.e. V k-1 , and the rest of the vertices of G, i.e. 0≤i≤k-2 V i . Note that we do not add a new vertex at level V k for all maximal bicliques but only for the non-simple ones, i.e. those maximal bicliques that have at least two vertices in V k-1 and two vertices in 0≤i≤k-2 V i . For each new vertex x at level V k corresponding to a non-simple maximal biclique B, we define its neighbourhood in G as being the vertices of B. The weak-factor series of a graph G is defined as the series obtained by iteratively applying the weak-factor operator starting from the vertex-clique-incidence bipartite graph of G (see Figure 1), where the vertices of G are at level V 0 and the maximal cliques of G are at level V 1 . This series is said to terminate iff, at some point, no new vertices are created. Then, the series is finite and the following graphs are undefined. For example, the series depicted on Figure 1 terminates since no new vertices are created when applying the weak-factor operator on graph G 3 of the series.

As we will show in Section 2, the weak-factor series does not always terminate. Then, the interest of the multipartite structure of the weak-factor graph is that it will allow us to restrict the definition of the non-simple bicliques we use in the weak-factor operator, taking into account the different levels of the multipartite graphs. In this way, we will be able to devise a refined version of the weak-factor graph, which we call the clean-factor graph, whose associated series terminates for all graphs.

G 0 = G G 1 = B(G) G 2 G 3
Figure 1: Example of the weak-factor series of some graph G. From left to right: the original graph G = G 0 , its vertex-clique-incidence bipartite graph B(G) = G 1 , the tripartite graph G 2 of the series, and the quadripartite graph G 3 on which the series terminates. The dashed edges are those belonging to some non-simple maximal biclique used in the factorisation steps. Note that even if those edges were removed, the multipartite graph obtained at termination of the series would still constitute an unambiguous encoding of the original graph, as these edges are encoded by the presence of some vertices in the levels above them.

Our contribution

In this paper, we study a new graph operator called the weak-factor operator which naturally arises in complex network modelling (see Section 1.1). We show that there are graphs for which the weak-factor series, obtained by iteratively applying the weak-factor operator, does not terminate. Therefore, our main contribution is to define a refinement of the operator, called the clean-factor graph, whose series terminates for all graphs, thereby defining an object suitable for modelling purposes. The difference between our approach and the one followed by previous works is that we do not try to determine on which graphs the weak-factor series terminates, but we rather look for minimal constraints to impose to the operator in order to obtain termination for all graphs. The solution we present here obtains termination by imposing constraints to only a bounded number of levels (namely 3) of the multipartite graph on which the operator is applied.

In addition to our termination result, we show that the multipartite graph on which the clean-factor series terminates has a remarkable combinatorial structure. Namely, its vertices are in bijection with the chains of the inclusion order on the non-simple intersections of maximal cliques of the graph (Theorem 1), denoted L in the rest of the paper. We believe that this link between the termination of the series and the structure of the cliques of the original graph is worth in itself and may be used to study termination of other similarly defined graph operators. Finally, we give an upper bound on the size and computation time of the graph on which the iterated clean-factor series of G terminates, under reasonable hypotheses on the degree distributions of the vertex-clique-incidence bipartite graph of G (which hold for most real-world complex networks), therefore showing that this multipartite graph can be used in practice for complex network modelling.

Let us mention that this work is an improved and complete version of the extended abstract that appeared in [START_REF] Latapy | Termination of multipartite graph series arising from complex network modelling[END_REF]. In [START_REF] Latapy | Termination of multipartite graph series arising from complex network modelling[END_REF], the notion of clean-factor is slightly different from the one we use here. As a consequence, we could not prove that imposing constraints only to a bounded number of levels is enough to guarantee the termination of the series, and we did not have a real bijection between the multipartite graph obtained at termination and the vertices of L.

Related works

The weak-factor operator we study here operates on multipartite graphs and is defined using the bicliques between the upper level and the rest of the multipartite graph. For graphs, closely related operators have been defined using the cliques or the bicliques of the graph, and many works addressed the question of convergence of the series obtained by iteratively applying these operators to an input graph. There exists several definitions of convergence in the literature. The notion of termination we use here for the multipartite graph series is somehow equivalent to the convergence notion used in [START_REF] Bornstein | On clique convergent graphs[END_REF] in the context of graph series, and is a particular case of convergence of the definition used in [START_REF] Prisner | Convergence of iterated clique graphs[END_REF].

For the well-known clique graph operator (see [START_REF] Szwarcfiter | A survey on clique graphs[END_REF] for a survey) the question of convergence has received a lot of attention [START_REF] Prisner | Convergence of iterated clique graphs[END_REF][START_REF] Bornstein | On clique convergent graphs[END_REF]. Most of the efforts focussed on obtaining convergence results, or divergence results, for some particular graphs or graph classes [START_REF] Larrión | The clique operator on cographs and serial graphs[END_REF][START_REF] Larrión | Clique divergent clockwork graphs and partial orders[END_REF][START_REF] Larrión | Contractibility and the clique graph operator[END_REF][START_REF] Lin | The clique operator on circular-arc graphs[END_REF]. Similar questions have been addressed recently for the biclique graph operator [START_REF] Groshaus | The number of convergent graphs under the biclique operator with no twin vertices is finite[END_REF][START_REF] Groshaus | On the iterated biclique operator[END_REF], which also operates on graphs2 but using bicliques instead of cliques. It is worth noticing that the clique graph and the biclique graph are defined as intersection graphs while this is not the case of the operators we study in this paper. Let us mention, that another closely related graph operator called edge-clique-graph operator has been studied (see e.g. [START_REF] Chartrand | Edge-clique graphs[END_REF][START_REF] Cerioli | Clique graphs and edge-clique graphs[END_REF]) but, to the best of our knowledge, the question of the convergence of its iterated series has not been investigated.

It must be clear that none of these three operators, clique graphs, biclique graphs and edge-clique graphs, which are defined on graphs, is equivalent to one of the multipartite-graph operators we consider here. And the convergence or divergence results obtained previously for these graph operators do not imply the termination and non-termination results we present here.

Moreover, it is worth noticing that the question we address in this paper is orthogonal, and complementary, to the one addressed in all the previously cited works. Indeed, we do not intend to characterise the graphs for which the iteration of the weak-factor operator terminates or does not terminate. Instead, we aim at determining minimal constraints that can be imposed to this operator in order to obtain termination for all graphs.

Finally, we note that recently [START_REF] Evans | Clique graphs and overlapping communities[END_REF] showed the interest of clique graphs to study communities in complex networks. However, their approach and results are not equivalent to ours. In particular, they do not consider the series obtained by iterating the operator, which is our main concern here in the case of the weakfactor operator.

Outline of the paper

In Section 1.1, we detail further the context where the practical motivation of our work comes from. Then, Section 1.2 gives a few notations and basic definitions, useful in the whole paper, including the definition of a fundamental notion, the factorisation, which plays a key role in the following. In Section 2, we formally define the weak-factor operator and a natural variation of this operator, called the factor operator, both of which giving rise to some infinite series. In Section 3 we propose a deeper refinement of the operator, called the clean-factor operator, for which we prove termination for all graphs and give a structural characterisation of the multipartite graph obtained at termination. Finally, in Section 4, we address the question of efficiently computing and storing the representation provided by the clean-factor series.

Motivation

It is worth to mention that we did not come to the study of the termination of the weak-factor series only for theoretic motivations: this question is of key interest in complex network modelling. Complex networks are those graphs encountered in practice in various domains such as computer science, biology, social sciences and others. In the last decade, they were shown to share some nontrivial common properties [START_REF] Watts | Collective dynamics of small-world networks[END_REF][START_REF] Albert | Statistical mechanics of complex networks[END_REF], independently from the context they come from. A lot of efforts have been done to design models able to capture these properties while staying general enough. One of the difficulty of the domain is to encompass in a same model the two major properties of these networks, namely their heterogeneous degree distribution and their high local density (clustering coefficient, see [START_REF] Barrat | Dynamical processes on complex networks[END_REF] for a formal definition).

Among the most promising approaches, [START_REF] Guillaume | Bipartite structure of all complex networks[END_REF][START_REF] Guillaume | Bipartite graphs as models of complex networks[END_REF] propose to model complex networks based on the properties of their vertex-clique-incidence bipartite graph. Their idea is to use prescribed-degree-graph generation, which is a powerful and well understood technique since the works of [START_REF] Bender | The asymptotic number of labeled graphs with given degree sequences[END_REF][START_REF] Molloy | A critical point for random graphs with a given degree sequence[END_REF], for the vertex-cliqueincidence bipartite graph instead of the graph itself. In other words, they advocate for the generation of complex networks by their cliques rather than by their edges. They show that, in this way, one obtains graphs having a high local density (thanks to the clique structure) and a heterogeneous degree distribution that is controlled by the degrees of the vertices in the vertex-clique-incidence bipartite graph. However, the bipartite model suffers from a severe limitation: when generating the edges of the bipartite graph at random, the obtained neighbourhoods of the upper vertices intersect only on one (or zero) vertex with a very high probability (see [START_REF] Guillaume | Bipartite structure of all complex networks[END_REF][START_REF] Guillaume | Bipartite graphs as models of complex networks[END_REF]). This is not the case in real world networks, where most of the maximal cliques have non-simple overlaps with some others (i.e. overlaps of cardinality at least two). Thus, even though it gives the desired properties concerning degree distribution and local density, the bipartite model results in graphs having a caricaturistic structure.

The weak-factor graph (see Section 2) was introduced in [START_REF] Latapy | Termination of multipartite graph series arising from complex network modelling[END_REF] in order to correct this drawback. The idea is to define an object that encodes the nonsimple intersections of maximal cliques of a graph G by the neighbourhoods of vertices in some other suitably defined graph, so that such objects can be randomly generated using the prescribed-degree generation technique of [START_REF] Bender | The asymptotic number of labeled graphs with given degree sequences[END_REF][START_REF] Molloy | A critical point for random graphs with a given degree sequence[END_REF]. In order to define such an encoding of a graph G, we can proceed as follows. We start from the vertex-clique-incidence bipartite graph B(G) = (V 0 , V 1 , E) of G and we create a new level V 2 where each vertex x corresponds to a non-simple maximal biclique B of B(G). Then, we can delete the edges of B as they are now encoded by the presence of x. Doing so simultaneously for all non-simple maximal bicliques of B(G) gives a tripartite graph in which the neighbourhoods on V 0 of vertices at level V 1 have no non-simple intersections anymore. Then, we can iteratively repeat the operation by considering, at each stage of the process, the maximal bicliques between the vertices on the uppermost level and the rest of the vertices of the multipartite graph, until the process hopefully terminates. In this case, we obtain a multipartite graph3 without any non-simple intersection of neighbourhoods. We can therefore generate similar structures at random using the prescribed-degree generation method without bumping into the problem raised by [START_REF] Guillaume | Bipartite structure of all complex networks[END_REF][START_REF] Guillaume | Bipartite graphs as models of complex networks[END_REF]. Of course, in order to obtain a multipartite graph that has no non-simple neighbourhood intersections, it is mandatory that the iterative factorising process terminates. This is the reason why we came to study the termination of the weak-factor series.

Note that, opposite to the process described above, in the definition of the weak-factor operator we do not delete edges of the bicliques involved in one factorisation step. This has no impact on the set of nodes created in the rest of the process, as those edges are not involved in further factorisation steps. On the other hand, keeping those edges helps to describe the structure of the graphs of the weak-factor series (Definition 2 below) and this is the reason why we keep them in the rest of the paper.

Notations and preliminary definitions

All graphs considered here are finite, undirected and simple (no loops and no multiple edges). A graph G having vertex set V and edge set E will be denoted by G = (V, E). We also denote by V (G) the vertex set of G. The edge between vertices x and y will be indifferently denoted by xy or yx. K(G) denotes the set of maximal cliques of a graph G, and N (x) the neighbourhood of a vertex x in G.

An ordered k-partition P of a set V is a partition of V into k parts (non empty and pairwise disjoint, from the classical definition of partition) which are numbered from 0 to k -1. It is denoted as a k-tuple: P = (V 0 , . . . , V k-1 ). In this paper, a k-partite graph is always given together with a partition of its vertices as in the following definition.

Definition 1 (k-partite graph). A k-partite graph is a couple (G, P) where G = (V, E) is a graph and P = (V 0 , . . . , V k-1 ) is an ordered k-partition of its vertex set V such that all edges of G are between vertices in different parts of P. It is denoted by G = (V 0 , . . . , V k-1 , E).

A multipartite graph is a k-partite graph with k ≥ 2. For a k-partite graph G = (V 0 , . . . , V k-1 , E), the vertices of V i , for any i, are called the i-th level of G, and the vertices of V k-1 are called its upper vertices. We denote by N i (x), where 0 ≤ i ≤ k -1, the set of neighbours of x at level i: N i (x) = N (x)∩V i . A biclique of a graph is a set of vertices of the graph inducing a complete bipartite graph. We denote by B(G) the vertex-clique-incidence bipartite graph of G = (V, E):

B(G) = (V, K(G), E ) where E = {vc | c ∈ K(G), v ∈ c}.
A non-simple biclique of a bipartite graph is a biclique having at least two vertices in the upper level and at least two vertices in the bottom level. Two sets have a nonsimple intersection if they share at least two elements. In the whole paper, we denote L the inclusion order of the non-simple intersections of maximal cliques of a graph G (there will be no confusion on the graph G referred to when we use this notation).

For two non-negative integers a, b ∈ N, we use the notation a, b for the set

{p ∈ N | a ≤ p ≤ b}, with the convention a, b = ∅ if a > b.
In the sequel, an operation will play a key role, we name it factorisation and define it generically as follows.

Definition 2 (factorisation with respect to

V k (G)). Given a k-partite graph G = (V 0 , . . . , V k-1 , E) with k ≥ 2 and a set V k (G) of subsets of V (G), we de- fine the factorisation of G with respect to V k (G) as the (k + 1)-partite graph G = (V 0 , . . . , V k , E ∪ E + ) where: • V k is the set of maximal (with respect to inclusion) elements of V k (G), • E + = {Xy | X ∈ V k and y ∈ X}.
When V k = ∅, the factorisation is said to be effective.

Provided that the set V k (G) is properly defined for all multipartite graphs G, such a factorisation operation defines a multipartite graph operator, the iteration of which gives rise to a series of multipartite graphs as defined below.

Definition 3 (series associated to a factorisation operation). Given a factorisation operation that associates any

k-partite graph G = (V 0 , . . . , V k-1 , E) with k ≥ 2 to a (unique) k + 1-partite graph G ,
we define the series of multipartite graphs (G i ) i≥1 , associated to this factorisation operation and generated by a graph G 0 = (V 0 , E 0 ), by: G 1 = B(G 0 ) is the vertex-clique-incidence bipartite graph of G 0 (in which the cliques are on the upper level of B(G 0 )) and, for all i ≥ 1, G i+1 = G i when the factorisation of G i is effective, and G i+1 is undefined otherwise.

Definition 4 (termination of the series). We say that the series (G i ) 1≤i≤n associated to some factorisation operation terminates iff for some i ≥ 1 the factorisation is not effective, then all subsequent graphs of the series are undefined and the series reduces to a finite sequence.

In the rest of the paper, we will refine the notion of factorisation by using different sets V k (G) on which is based the factorisation operation. And we will study termination of the graph series resulting from each of these refinements. As, in the following, the graph G referred to is always clear from the context, we denote V k instead of V k (G). But all the sets V k we define still depend on the graph considered.

Weak-factor series and factor series

Weak-factor series

Thanks to the generic notion of factorisation, we will now formally define the weak-factor operation we introduced above.

Definition 5 (V +

k and weak-factor graph). Given a k-partite graph G = (V 0 , . . . , V k-1 , E) with k ≥ 2, we define the set V + k as:

V + k = {{x 1 , . . . , x l }∪ 1≤i≤l N (x i ) | l ≥ 2, ∀i ∈ 1, l , x i ∈ V k-1 and | 1≤i≤l N (x i )| ≥ 2}.
The weak-factor graph G + of G is the factorisation of G with respect to V + k . the input graph G, its vertex-clique-incidence bipartite graph B(G), and the tripartite graph B(G) + of its weak-factor series (note that for sake of readability of the drawing, the edges between levels V 1 and V 0 have been removed in B(G) + ). The shaded edges are the ones involving vertex e, which plays a special role: all the vertices of the upper level of the multipartite graph are linked to e. The structure of edges between vertices of V 2 and vertices of V 1 ∪ {e} in B(G) + is identical to the one between levels V 1 and V 0 in B(G), revealing that the series will not terminate.

Figure 1 gives an illustration for this definition. In this case, the weak-factor series is finite. However, it is not difficult to find examples of graphs which lead to infinite weak-factor series. Figure 2 provides such an example for which the structure of the upper level is infinitely reproduced on the further levels. Intuitively, this is due to the fact that a vertex may be the base for an infinite number of factorisation steps (vertex e in the example of Figure 2). The aim of the next sections is to avoid this case by using a more restrictive definition of factorisation.

Factor series

In this section, we examine a first restriction of the operator, called factor graph, that forbids the repeated use of the same vertex to produce infinitely many factorisations, which is the phenomenon responsible for the non termination of the series for the example of Figure 2.

Definition 6 (V • k and factor graph). Given a k-partite graph G = (V 0 , . . . , V k-1 , E) with k ≥ 2, we define the set V • k as: V • k = {X ∈ V + k such that | y∈X∩V k-1 N k-2 (y)| ≥ 2}. The factor graph G • of G is the factorisation of G with respect to V • k .
This new definition results from the restriction of the weak-factor definition by considering only sets X ∈ V + k such that the vertices of X ∩ V k-1 have at least two common neighbours at level k -2. The reason is that, in this way, a vertex cannot contribute to more than two factorising steps: once when it is on the upper level of the multipartite graph, once when it is on the level just below. Indeed, even if the vertices of levels lower than the two upper levels (i.e.

V k and V k-1 ) may be involved in a factorisation step, they are not responsible for the creation of a new vertex. Such a creation depends only on the edges between the two upper levels of the multipartite graph.

Finding examples of input graphs that generate infinite factor series is not straightforward. In particular, one natural candidate that one could have in mind, namely the graph whose vertex-clique-incidence bipartite graph is the anti-matching on 2n vertices, which generates an infinite series for the cliquegraph operator [START_REF] Neumann-Lara | On clique-divergent graphs[END_REF], actually gives rise to a finite series for the factor operator. The anti-matching is the bipartite complement of a perfect matching between the n upper vertices and the n bottom vertices (also known as the octahedron in clique-graph theory and as the crown in poset theory). The anti-matching is known for being the bipartite graph on 2n vertices that has the maximum number of bicliques. Regarding the factor series, it implies that there is a combinatorial explosion of the number of vertices on the first next levels. Despite of this, one can check that the series of the anti-matching on 2n vertices terminates.

Nevertheless, [START_REF] Phan | Termination of the iterated strong-factor operator on multipartite graphs[END_REF] recently provided an example of a graph that gives rise to an infinite factor series. This is the reason why in the next section, we constraint further the factor operation: we do not only require that the neighbourhoods of vertices at level V k-1 involved in the creation of a new vertex at level V k share at least two vertices on level V k-2 but we also require that those vertices have the same neighbourhood at level V k-3 (see Definition 7 of the clean-factor graph). This supplementary condition is not only a technical condition used to guarantee termination: we will show that the graph on which terminates the clean-factor series is a fundamental combinatorial object.

Clean-factor series

In the previous section, we studied two series of multipartite graphs based on two different factorisation operations, both of them giving rise to some infinite series. In this section, we introduce a more constrained refinement of these two factorisation operations, which we call the clean-factor operator, for which we prove that the associated series always terminates. One interesting point of our solution is that the constraints introduced in order to guarantee termination are light: they apply on only 3 levels of the multipartite graph. In addition, the multipartite graph obtained at termination has a very deep combinatorial meaning: its vertices are the chains of the inclusion order L of the non-simple intersections of maximal cliques of the input graph G.

We now give the formal definition of the clean-factor graph of a multipartite graph: the general factorisation step is the case where k ≥ 5, the construction of levels V 2 , V 3 and V 4 are subject to particular conditions. It should be clear that these particular conditions may be simplified while preserving termination. But on the other hand, those exact conditions are necessary in order to obtain the bijection with the chains of order L.

Definition 7 (V *

k and clean-factor graph). Given a k-partite graph G = (V 0 , . . . , V k-1 , E) with k ≥ 2, we define the set V * k as:

• If k ≥ 5, V * k = {X ∈ V + k | | x∈X∩V k-1 N k-2 (x)| ≥ 2 and ∀x, y ∈ X ∩ V k-1 , N k-3 (x) = N k-3 (y) and | x∈X∩V k-1 N 1 (x)| ≥ 2}. • If k = 4, V * 4 = {X ∈ V + 4 | | x∈X∩V3 N 2 (x)| ≥ 2 and | x∈X∩V3 N 1 (x)| ≥ 2 and ∀x, y ∈ X ∩ V 3 , N 0 (x) = N 0 (y)}. • If k = 3, V * 3 = {X ∈ V + 3 | | x∈X∩V2 N 1 (x)| ≥ 2 and | x∈X∩V2 N 0 (x)| ≥ 2}. • If k = 2, V * 2 = V + 2 .
The clean-factor graph G * of G is the factorisation of G with respect to V * k .

The rest of this section is devoted to proving the termination of the cleanfactor series (G i ) i≥1 generated by any graph G (Theorem 2) and the bijection between vertices of level V i of the series, with i ≥ 2, and the chains of length i -2 of L (Theorem 1). We start by proving Theorem 1 since Theorem 2 will be obtained as a direct corollary from it.

Theorem 1 gives a characterisation of V i , i ≥ 2 by associating to each of its nodes a chain of length i -2 in order L. Formally, we associate to a node x of V i a sequence S(x) of subsets of V (G) which are precisely the elements of L defining the chain associated to x. Before formally defining S(x) (Definition 10) and stating Theorem 1, we need to establish some basic definitions, notations and properties of the non-simple intersections of the maximal cliques of a graph. Note that the set A defining K(A) is not unique: there may exist A = A such that K(A ) = K(A). This is the reason why we now need to state some basic properties of sets K(A) that we will use in the following.

Remark 1. For any subsets

A, B ⊆ V (G), if A ⊆ B then K(B) ⊆ K(A). And for any subsets A ⊆ V (G) and O ∈ O , if K(O) ⊆ K(A) then A ⊆ O.
Proof: The first part of the remark is self-evident. For the second part, note that, by definition of O , O = C∈K(O) C. And on the other hand, we have

A ⊆ C∈K(A) C ⊆ C∈K(O) C = O. Remark 2. For any A, B ⊆ V (G), K(A) ∩ K(B) = K(A ∪ B). Conversely, if A 1 , . . . , A n ⊆ V (G), with n ≥ 2, and if O ∈ O and if 1≤i≤n K(A i ) = K(O), then 1≤i≤n A i ⊆ O. Proof: Let A, B ∈ V (G).
The cliques in K(A) ∩ K(B) are exactly the cliques that contain both A and B, i.e. the cliques that contain A ∪ B. Therefore

K(A) ∩ K(B) = K(A ∪ B). Let A 1 , . . . , A n ⊆ V (G), with n ≥ 2, and let O ∈ O such that 1≤i≤n K(A i ) = K(O). From what precedes, 1≤i≤n K(A i ) = K( 1≤i≤n A i ). Consequently, we have K(O) ⊆ K( 1≤i≤n A i ). And since O ∈ O , from Remark 1, we have 1≤i≤n A i ⊆ O.
O i ) = K(O). Since O ⊇ 1≤i≤k O i , we have K(O) ⊆ K( 1≤i≤k O i ) = 1≤i≤k K(O i ), from Remark 2. For the converse in- clusion, consider C ∈ K( 1≤i≤k O i ). By definition, C ∈ O and 1≤i≤k O i ⊆ C. Since 1≤i≤k O i ⊆ O, we also have 1≤i≤k O i ⊆ O ∩ C. And since O ∩ C ∈ O (as O is closed under intersection), the minimality of O implies that O ∩C = O, that is O ⊆ C. Thus, C ∈ K(O) and it follows that K( 1≤i≤k O i ) ⊆ K(O), which completes the proof.
The following lemma is the first step toward the bijection theorem (Theorem 1). It establishes the bijection between vertices of V 2 and the chains of length 0 of L. We will use it in the initialising step of the recursion of the proof of Theorem 1.

Lemma 2. In the clean-factor series,

V 0 = V (G), V 1 = K(G) and V 2 = O in the sense that the map φ defined by x → N 0 (x) is a bijection from V 2 to O. Moreover, ∀x ∈ V 2 , N 1 (x) = K(N 0 (x)).
Proof: Let us start with the second part of the lemma. Let x ∈ V 2 . By definition of V + 2 , all the elements y in N 1 (x) are such that N 0 (x) ⊆ N 0 (y). Then, y ∈ K(N 0 (x)), by identifying V 1 and K(G). On the other hand, the maximality of x in V + 2 implies that all y ∈ K(N 0 (x)) belong to N 1 (x). Thus,

N 1 (x) = K(N 0 (x))
Let us prove that the map φ is a bijection from

V 2 to O. First, if x ∈ V 2 then by definition, |N 0 (x)| ≥ 2, |N 1 (x)| ≥ 2,
and N 0 (x) = y∈N1(x) N 0 (y), hence N 0 (x) belongs to O, and the map φ is well defined.

Second, φ(x) = φ(x ) means N 0 (x) = N 0 (x ). But N 1 (x) is the set of all maximal cliques containing N 0 (x), and N 1 (x ) is the same. Then, if φ(x) = φ(x ), we have x = x : φ is injective.

We now prove that φ is surjective. Let O be an element of O, we show that the element

x = K(O) ∪ y∈K(O) N 0 (y) is an element of V 2 and φ(x) = O. It is clear that x ∩ V 0 = O, so |x ∩ V 0 | ≥ 2. Since O ∈ O, |K(O)| ≥ 2, and we have |x ∩ V 1 | ≥ 2. Then x ∈ V + 2 .
Moreover, by definition, K(O) is exactly the set of all maximal cliques containing O, then x is maximal in V + 2 . It follows that x is an element of V 2 , and φ(x) = O.

We are now ready to give the definition of the sequence S(x) that we associate to a vertex x ∈ V i with i ≥ 2.

Definition 10 (Characterising sequence S(x)). Let G be a graph and let (G i ) i≥1 be its clean-factor series. The characterising sequence

S(x) = (O 1 (x), . . . , O k-1 (x)) of a vertex x ∈ V k , with k ≥ 2, is defined by: • O 1 (x) = N 0 (x), and
• for k ≥ 3, ∀j ∈ 2, k -1 , O j (x) is the unique element of O such that K(O j (x)) = y∈Nj (x) N 1 (y).
Note that O j is properly defined. Indeed, from Lemma 2, ∀y ∈ V 2 , V 1 (y) ∈ C. And since C is closed under intersection, a simple recursion shows that for all i ≥ 3 and for all y ∈ V i , N 1 (y) = z∈Vi-1 N 1 (z) ∈ C. Then, for any j ≥ 2, We will often use the following remark in the proof of Theorem 1.

Remark 3. For any x ∈ V k , with k ≥ 2, K(O k-1 (x)) = N 1 (x).
Proof: For k = 2, the remark rewrites

K(O 1 (x)) = N 1 (x). Since O 1 (x) = N 0 (x)
and since, from Lemma 2, K(N 0 (x)) = N 1 (x), then the result follows. For k > 2, the remark simply follows from the fact that y∈N k-1 (x) N 1 (y) = N 1 (x).

We will now state the bijection theorem (Theorem 1) which is our main combinatorial tool for proving the termination of the clean-factor series (Theorem 2). Its proof is rather intricate, but it gives much more information than the termination of the series. By associating a sequence of sets to each vertex in levels greater than V 2 in the multipartite graph, we show that each such vertex corresponds to a chain of the inclusion order L of the non-simple intersections of maximal cliques of G.

Theorem 1 (Bijection theorem). Let G be a graph and (G i ) i≥2 its cleanfactor series. For any k ≥ 2, the map φ defined by x → S(x) is a bijection from 3).

V k to {(O 1 , . . . , O k-1 ) ∈ O k-1 | O 1 . . . O k-1 } (see Figure

Proof:

The case k = 2 directly follows from Lemma 2, then, in the following, we only deal with the cases where k ≥ 3. We prove Theorem 1 by recursion, using the five recursion hypotheses below, namely H tar , H inj , H sur , H N and H E . Actually, hypotheses H tar , H inj and H sur are the targeted properties: they imply that map φ is a bijection. Hypotheses H N and H E contain the fundamental structure of the multipartite graph series. Hypothesis H N is essential, it gives a complete characterisation of the neighbourhood of a vertex on the lower levels. Hypothesis H E shows that the condition of equality of the neighbourhood at level k -3 of the children of x in Definition 7 actually induce a control of the neighbourhoods of the children of x on all the lower levels. L of the non-simple intersections of maximal cliques of G. Bottom: the multipartite graph M obtained at termination of the clean-factor series of G. M has 5 levels. Level V 0 is for the vertices of G and level V 1 for the maximal cliques of G. The bijection between the vertices of M and the chains of order L appears in the rest of the levels: each vertex x of M in levels V 2 to V 4 has been labelled with the corresponding chain of L, i.e. its characterising sequence S(x) (see Definition 10). Level V 2 is for the non-simple intersections of maximal cliques of G (i.e. the chains of L of length 0), level V 3 is for the chains of L of length 1, and level V 4 is for the chains of L of length 3, which is precisely the height of L. For sake of clarity, only a few links of M have been drawn on the figure, namely all the links between two consecutive levels higher than level V 2 . The black bold lines are for the link between a vertex x at level V i , for i ≥ 3, and the unique vertex of V i-1 whose characterising sequence is a prefix of the sequence of x (of length length(S(x)) -1, necessarily). In this way, we obtain a clearer representation of the bijection with the chains of L, as one can clearly see the four prefix trees of the chains starting at a given element of L: these prefix trees are rooted at level V 2 and two of them are reduced to one single node, labelled (abcd) and (abce).

H tar (k) : If x ∈ V k then O 1 (x) . . . O k-1 (x) and (O 1 (x), . . . , O k-1 (x)) ∈ O k-1 , H inj (k) : If x, y ∈ V k then x = y implies S(x) = S(y), H sur (k) : For any sequence (O 1 , . . . , O k-1 ) ∈ O k-1 with O 1 . . . O k-1 , there exists x ∈ V k such that S(x) = (O 1 , . . . , O k-1 ).
H N (k) : If x ∈ V k , then for all j such that 2 ≤ j < k, N j (x) = W j (x); where W j (x) is the set {y ∈ V j | (O 1 (y), . . . , O j-2 (y)) = (O 1 (x), . . . , O j-2 (x)) and O j-1 (x) ⊆ O j-1 (y) ⊆ O j (x)} (using the convention (O 1 (.), . . . , O j-2 (.)) = () for j = 2).

H E (k) , for k ≥ 4: If y 1 , y 2 ∈ V k such that N k-2 (y 1 ) = N k-2 (y 2 ) then ∀p ∈ 0, k -2 \ {1}, N p (y 1 ) = N p (y 2 ).
At each level k of recursion, we start by showing H N (k), using H E (k -1), then we use it to prove H arr (k), H inj (k), and H sur (k), and we finish by proving H E (k).

Initialisation step. We will prove that H N (3), H tar (3), H inj (3), and H sur (3) are true. We do not prove H E (3) since it is undefined. It is worth to note that we do not need H E (3) in the proof of H N (4): instead, we use Definition 7 that provide us the initialisation we need. Proof of H N (3). Since in H N (k), j varies from 2 to k -1, then in H N (3), j only takes the value 2. Then, to prove H N (3), we just have to prove that for all

x ∈ V 3 , N 2 (x) is equal to W 2 (x) = {y ∈ V 2 | O 1 (x) ⊆ O 1 (y) ⊆ O 2 (x)}. Let x ∈ V 3 ; we first show that N 2 (x) ⊆ W 2 (x)
. We denote by a 1 , . . . , a l , with l ≥ 2, the elements of the set N 2 (x). Clearly, for any

i ∈ 1, l , 1≤i≤l N 0 (a i ) ⊆ N 0 (a i ) ⊆ 1≤i≤l N 0 (a i ). From Definition 10, we have N 0 (a i ) = O 1 (a i ), O 1 (x) = N 0 (x) = 1≤i≤l N 0 (a i ), and K(O 2 (x)) = 1≤i≤l N 1 (a i ). Moreover, from Re- mark 3, N 1 (a i ) = K(O 1 (a i )), so we have K(O 2 (x)) = 1≤i≤l K(O 1 (a i )). And since, by definition, O 2 (x) ∈ O , then, from Remark 2, 1≤i≤l O 1 (a i ) ⊆ O 2 (x). Consequently, for any i ∈ 1, l , O 1 (x) ⊆ O 1 (a i ) ⊆ O 2 (x). That is N 2 (x) ⊆ W 2 (x).
Conversely, we show that if y ∈ W 2 (x), then y ∈ N 2 (x). To that purpose, we show that N 0 (x) ⊆ N 0 (y) and N 1 (x) ⊆ N 1 (y), which implies, by maximality of x in V * 3 (see Definition 2), that y ∈ N 2 (x). First, we have N 0 (x) = O 1 (x), and since y ∈ W 2 (x), we also have O 1 (x) ⊆ O 1 (y) = N 0 (y). Then, N 0 (x) ⊆ N 0 (y). Since O 1 (y) ⊆ O 2 (x), we have K(O 2 (x)) ⊆ K(O 1 (y)). And from Remark 3, we have K(O 1 (y)) = N 1 (y) and K(O 2 (x)) = N 1 (x). Thus, N 1 (x) ⊆ N 1 (y) and we conclude that y ∈ N 2 (x). Finally, we showed that N 2 (x) = W 2 (x), and so

H N (3) is true. Proof of H tar (3). Since, from H N (3), N 2 (x) = W 2 (x) and since |N 2 (x)| ≥ 2, it follows that O 1 (x) O 2 (x), otherwise W 2 (x) would contain at most one element. By definition of V * 3 , |N 0 (x)| ≥ 2. Since O 1 (x) = |N 0 (x)|, it follows that O 1 (x)
, and so O 2 (x), contains at least two elements. Moreover, from Remark 3, we have K(O 2 (x)) = N 1 (x). And from Definition 7, |N 1 (x)| ≥ 2. It follows that K(O 2 (x)) contains at least two elements, and so does

K(O 1 (x)) since K(O 2 (x)) ⊆ K(O 1 (x)). Thus O 1 (x) and O 2 (x) both belong to O: H tar (3) is true. Proof of H inj (3). For any z ∈ V 3 , N 2 (z) = W 2 (z). Thus, for any x, y ∈ V 3 , (O 1 (x), O 2 (x)) = (O 1 (y), O 2 (y)) implies that N 2 (x) = N 2 (y), which implies that x = y. So H inj (3) holds. Proof of H sur (3). Let O 1 , O 2 ∈ O such that O 1 O 2 .
We will find an element

x of V 3 such that O 1 (x) = O 1 and O 2 (x) = O 2 . Let Y = {y ∈ V 2 | O 1 ⊆ O 1 (y) ⊆ O 2 }. Let x = Y ∪ y∈Y N (y), we prove that x is the desired element.
First, to prove that x ∈ V 3 , we must prove that x

∈ V * 3 , that is |x ∩ V 2 | ≥ 2 and |x ∩ V 1 | ≥ 2 and |x ∩ V 0 | ≥ 2. From Lemma 2 , there exists two dis- tinct elements y 1 , y 2 ∈ V 2 such that O 1 (y 1 ) = O 1 and O 1 (y 2 ) = O 2 . Clearly, {y 1 , y 2 } ⊆ Y , which gives |x ∩ V 2 | ≥ 2. Furthermore, x ∩ V 1 = y∈Y N 1 (y) = y∈Y K(O 1 (y)), from Remark 3. Since, for any y ∈ Y , O 1 (y) ⊆ O 2 , we have also K(O 2 ) ⊆ K(O 1 (y)). It follows that K(O 2 ) ⊆ x ∩ V 1 , and O 2 ∈ O implies that |K(O 2 )| ≥ 2, then |x ∩ V 1 | ≥ 2. We also have x ∩ V 0 = y∈Y N 0 (y) = y∈Y O 1 (y). And since O 1 ⊆ O 1 (y) for all y ∈ Y , then O 1 ⊆ x ∩ V 0 . It follows that |x ∩ V 0 | ≥ 2.
We now show that x is maximal in

V * 3 . Let z ∈ V 2 \ Y i.e. O 1 ⊆ O 1 (z) or O 1 (z) ⊆ O 2 , we prove that x ∩ V 0 ⊆ N 0 (z) or x ∩ V 1 ⊆ N 1 (z), which implies that y∈Y ∪{z} N (y)
y∈Y N (y) and that x is maximal, since this holds for all z ∈ Finally, H sur (3) is true.

V 2 \ Y . Let us first note that x ∩ V 0 = y∈Y N 0 (y) = y∈Y O 1 (y) = O 1 , the last equality coming from the fact that ∀O ∈ O, ∃z ∈ V 2 , O 1 (z) = O (see Lemma 2). On the other hand x∩V 1 = y∈Y N 1 (y) = y∈Y K(O 1 (y)) = K( y∈Y O 1 (y)) = K(O 2 ), again using Lemma 2 for the last equality. Now, if O 1 (z) ⊆ O 2 , since O 1 (z) ∈ O , then, from Remark 1, K(O 2 ) ⊆ K(O 1 (z)). And since, from what precedes, K(O 2 ) = x ∩ V 1 and, from Remark 3, K(O 1 (z)) = N 1 (z), we obtain x∩V 1 ⊆ N 1 (z). On the other hand, if O 1 ⊆ O 1 (z), since O 1 = x∩V 0 (see above) and O 1 (z) = N 0 (z) (by definition), we obtain x ∩ V 0 ⊆ N 0 (z). Consequently, x is maximal in V *
Recursion step. Now, let us suppose that k ≥ 4 and that for all i such that 3 ≤ i < k, H tar (i), H inj (i), H sur (i) and H E (i) are true. Note that we did not prove H E (3), which is not even defined, but we don't need it. Actually, in step k of the recursion, H E (k -1) is used only in the proof of H N (k). For proving H N (4), the use of H E (3) is replaced by the use of the definition of V *

(Definition 7).

Proof of H N (k). Let x ∈ V k . We denote by a 1 , . . . , a l the elements of the set

N k-1 (x). Let i 1 , i 2 ∈ 1, l . If k ≥ 5, by hypothesis H E (k -1), we have that N p (a i1 ) = N p (a i2 ) = N p (x) for all p ∈ 0, k -3 \ {1}. If k = 4
, by Definition 7, we have that N 0 (a i1 ) = N 0 (a i2 ) = N 0 (x). Thus, independently of the value of k ≥ 4 we have N p (a i1 ) = N p (a i2 ) = N p (x) for all p ∈ 0, k -3 \ {1}. Then, using the Definition 10 of the characterising sequence, it follows that, for p = 0, we obtain

O 1 (a i ) = O 1 (a j ) and for p ∈ 2, k -3 , we obtain O p (a i ) = O p (a j ) = O p (x). Let j ∈ 2, k -3 and let i ∈ 1, l . From recursion hypothesis H N (k -1)
applied to a i , we have N j (a i ) = W j (a i ). Since for all q ∈ 1, k -3 we have O q (x) = O q (a i ), then, from the definition of W j , it follows that W j (x) = W j (a i ).

Finally, since N j (x) = N j (a i ), we obtain N j (x) = W j (x), for all 2 ≤ j ≤ k -3.

Then we just have to prove that

N k-2 (x) = W k-2 (x) and N k-1 (x) = W k-1 (x).
We start with N k-1 (x). We will first show that for any i ∈ 1, l we have

a i ∈ W k-1 (x), that is N k-1 (x) ⊆ W k-1 (x).
As explained above, we already know that, for all q ∈ 1, k -3 , O q (x) = O q (a i ). Then, we only need to show

that O k-2 (x) ⊆ O k-2 (a i ) ⊆ O k-1 (x).
Let us show the first inclusion:

O k-2 (x) ⊆ O k-2 (a i ). By definition, N k-2 (x) = t∈ 1,l N k-2 (a t ) ⊆ N k-2 (a i ). Then, we have b∈N k-2 (ai) N 1 (b) ⊆ b∈N k-2 (x) N 1 (b). And since, by definition, b∈N k-2 (ai) N 1 (b) = K(O k-2 (a i ) and b∈N k-2 (x) N 1 (b) = K(O k-2 (x), then we obtain K(O k-2 (a i )) ⊆ K(O k-2 (x)). Thus, from Remark 1, we have O k-2 (x) ⊆ O k-2 (a i ).
Let us now show the second inclusion:

O k-2 (a i ) ⊆ O k-1 (x). Since N k-2 (a i ) ⊆ t∈ 1,l N k-2 (a t ) then b∈N k-2 (ai) N 1 (b) ⊇ b∈ t∈ 1,l N k-2 (at) N 1 (b), and by definition b∈N k-2 (ai) N 1 (b) = K(O k-2 (a i ))
. In order to show the inclusion we aim at, we will show that b∈

t∈ 1,l N k-2 (at) N 1 (b) = t∈ 1,l N 1 (a t ). Since, by definition again, t∈ 1,l N 1 (a t ) = K(O 1 (x)), this will give K(O k-2 (a i )) ⊇ K(O k-2 (x)), which implies O k-2 (a i )) ⊆ O k-2 (x)
, the inclusion we aim at.

Then, let us show the equality b∈

t∈ 1,l N k-2 (at) N 1 (b) = t∈ 1,l N 1 (a t ) by a double inclusion. Let z ∈ t∈ 1,l N 1 (a t ), then for all t ∈ 1, l , z ∈ N 1 (a t ). It follows that for all b ∈ N k-2 (a t ), z ∈ N 1 (b)
. Since this holds for all t ∈ 1, l and for all b ∈ N k-2 (a t ), then we obtain z

∈ b∈ t∈ 1,l N k-2 (t) N 1 (b). Conversely, let z ∈ b∈ t∈ 1,l N k-2 (at) N 1 (b), we show that z ∈ t∈ 1,l N 1 (a t ). For all b ∈ t∈ 1,l N k-2 (a t ) we have z ∈ N 1 (b).
In particular, for any t ∈ 1, l and for any b ∈ N k-2 (a t ), we have z ∈ N 1 (b), and so z ∈ N 1 (a t ). As this holds for any t ∈ 1, l , then z

∈ t∈ 1,l N 1 (a t ), that is b∈ t∈ 1,l N k-2 (t) N 1 (b) ⊆ t∈ 1,l N 1 (a t ).
Finally, as we already showed the converse inclusion, we obtain

b∈ t∈ 1,l N k-2 (t) N 1 (b) = t∈ 1,l N 1 (a t ).
We can now finish the proof of the inclusion

N k-1 (x) ⊆ W k-1 (x). Remem- ber that b∈N k-2 (ai) N 1 (b) ⊇ b∈ t∈ 1,l N k-2 (t) N 1 (b) and that by definition b∈N k-2 (ai) N 1 (b) = K(O k-2 (a i ). In addition, we just proved that b∈ t∈ 1,l N k-2 (t) N 1 (b) = t∈ 1,l N 1 (a t ),
and, by definition again, we have t∈

1,l N 1 (a t ) = K(O k-1 (x)). We then ob- tain K(O k-2 (a i )) ⊇ K(O k-1 (x)), and Remark 1 concludes that O k-2 (a i ) ⊆ O k-1 (x), for all i ∈ 1, l . So finally, putting everything together (we proved above that O k-2 (x) ⊆ O k-2 (a i )) we get O k-2 (x) ⊆ O k-2 (a i ) ⊆ O k-1 (x), for all i ∈ 1, l , which completes our proof of a i ∈ W k-1 (x), for all i ∈ 1, l , that is N k-1 (x) ⊆ W k-1 (x).
Let us now prove the converse inclusion:

W k-1 (x) ⊆ N k-1 (x). Let y ∈ W k-3 (z) and W k-3 (y), we obtain that t 2 ∈ W k-3 (z) = N k-3 (z) but, since O k-3 (z) ⊆ O k-3 (y), we have t 2 ∈ W k-3 (y) = N k-3 (y). Thus, in all cases where k ≥ 5, if there exists some j ∈ 1, k -3 such that O j (z) = O j , then N k-3 (z) = N k-3 (y).
Let us now deal with the particular case where k = 4. In this case, necessarily the index j ∈ 1, k -3 such that O j (z) = O j is j = 1. We immediately obtain that N 0 (z) = O 1 (z) = O 1 (y) = N 0 (y). Then, from Definition 7 (case k = 4), there is no element B ∈ V * k containing both y and z. Finally, we conclude that, regardless of the value of k ≥ 4, if for some

j ∈ 1, k -3 , O j (z) = O j then there is no element B ∈ V * k containing Y ∪ {z}. Thus, to show that x is maximal in V * k we only need to show that for any z ∈ V k-1 such that (O 1 (z), . . . , O k-3 (z)) = (O 1 , . . . , O k-3 ), if O k-2 ⊆ O k-2 (z) or O k-2 (z) ⊆ O k-1 , then we have y∈Y N (y) ⊆ N (z).
We first treat the case where

O k-2 (z) ⊆ O k-1 . In this case, from Remark 1, K(O k-1 ) ⊆ K(O k-2 (z)). From Remark 3, we have K(O k-2 (z)) = N 1 (z). We now show that K(O k-1 ) = y∈X∩V k-1 N 1 (y), which will give us the desired result: y∈x∩V k-1 N 1 (y) ⊆ N 1 (z). From Remark 3, for any y ∈ V k-1 , N 1 (y) = K(O k-2 (y)). It follows that y∈x∩V k-1 N 1 (y) = y∈x∩V k-1 K(O k-2 (y)) and we also have y∈x∩V k-1 K(O k-2 (y)) = P ∈O and O k-2 ⊆P ⊆O k-1 K(P ), from H sur (k- 1
) and the definition of x. From Lemma 2, we get

P ∈O and O k-2 ⊆P ⊆O k-1 K(P ) = K( P ∈O and O k-2 ⊆P ⊆O k-1 P ), which is clearly equal to K(O k-1 ). And so we have y∈x∩V k-1 N 1 (y) = K(O k-1
). As a consequence, we obtain y∈x∩V k-1 N 1 (y) ⊆ N 1 (z). Then, adding z to x ∩ V k-1 would strictly decrease y∈x∩V k-1 N 1 (y).

Let us now consider the case where

O k-2 ⊆ O k-2 (z). Using recursion hy- pothesis H N (k-1), for all y ∈ x∩V k-1 we have N k-2 (y) = {t ∈ V k-2 | O k-3 (y) ⊆ O k-3 (t) ⊆ O k-2 (y) and (O 1 (t), . . . , O k-4 (t)) = (O 1 , . . . , O k-4 )}. Let us denote Z = {t ∈ V k-2 | y∈x∩V k-1 O k-3 (y) ⊆ O k-3 (t) ⊆ y∈x∩V k-1 O k-2 (y) and (O 1 (t), . . . , O k-4 (t)) = (O 1 , . . . , O k-4 )} (as usual, we use the convention (O 1 , . . . , O k-4 ) = () when k = 4). We show that y∈x∩V k-1 N k-2 (y) = Z. Let t ∈ y∈x∩V k-1 N k-2 (y), then for all y ∈ x∩V k-1 , O k-3 (y) ⊆ O k-3 (t) ⊆ O k-2 (y) and so y∈x∩V k-1 O k-3 (y) ⊆ O k-3 (t) ⊆ y∈x∩V k-1 O k-2 (y), that is t ∈ Z. Conversely, if t ∈ Z then we have y∈x∩V k-1 O k-3 (y) ⊆ O k-3 (t) ⊆ y∈x∩V k-1 O k-2 (y) and so O k-3 (y) ⊆ O k-3 (t) ⊆ O k-2 (y) for all y ∈ x ∩ V k-1 , that is t ∈ y∈x∩V k-1 N k-2 (y). Thus, y∈x∩V k-1 N k-2 (y) = Z. By definition, for all y ∈ x ∩ V k-1 , O k-3 (y) = O k-3 and O k-2 ⊆ O k-2 (y). It follows that y∈x∩V k-1 O k-3 (y) = O k-3 and O k-2 ⊆ y∈x∩V k-1 O k-2 (y). Moreover, from recursion hypothesis H sur , there exists t ∈ V k-2 such that O k-3 (t ) = O k-2 and (O 1 (t ), . . . , O k-4 (t )) = (O 1 , . . . , O k-4 ). From what precedes, since O k-3 ⊆ O k-2 ⊆ y∈x∩V k-1 O k-2 (y), then t ∈ Z. On the other hand, from recursion hypothesis H N (k -1), we have N k-2 (z) = {t ∈ V k-2 | O k-3 ⊆ O k-3 (t) ⊆ O k-2 (z) and (O 1 (t), . . . , O k-4 (t)) = (O 1 , . . . , O k-4 )}. And since O k-2 ⊆ O k-2 (z), it follows that t ∈ N k-2 (z), while t ∈ Z = y∈x∩V k-1 N k-2 (y). Thus, y∈x∩V k-1 N k-2 (y) ⊆ N k-2 (z) and adding z to x ∩ V k-1 would strictly decrease y∈x∩V k-1 N k-2 (y). Finally, x is maximal in V *
k and is therefore an element of V k .

In order to conclude the proof of H sur (k), let us now show that the element x of V k has the desired characterising sequence (O 1 , . . . , O k-1 ). First, from H N (k), which we already proved, we know that (O 1 (x), . . . , O k-3 (x)) = (O 1 (y), . . . , O k-3 (y)) for any y ∈ N k-1 (x), which gives (O 1 (x), . . . , O k-3 (x)) = (O 1 , . . . , O k-3 ), from the definition of x = Y y∈Y N (y). Second, from Remark 3, we have K(O k-1 (x)) = N 1 (x) and we already know that |N 1 (x)| ≥ 2 (see beginning of the proof of H sur (k)). This gives |K(O k-1 (x))| ≥ 2, and as we have

|O 1 (x)| ≥ 2 and O 1 (x) ⊆ . . . ⊆ O k-2 (x) ⊆ O k-1 (x), we obtain that O k-2 (x), O k-1 (x) ∈ O. Now, from H N (k), we know that the couple (O k-2 (x), O k-1 (x)) is such that N k-1 (x) = {y ∈ V k-1 | O k-2 (x) ⊆ O k-2 (y) ⊆ O k-1 (x)
O k-2 (x), O k-1 (x)), we have O k-1 ⊆ O k-1 (x). Similarly, for P = O k-1 (x) we obtain O k-1 (x) ⊆ O k-1 , and it follows that O k-1 (x) = O k-1 . Analogously, choosing P = O k-2 and then P = O k-2 (x) shows that O k-2 (x) = O k-2 . Thus, H sur (k) is true. Proof of H E (k).
Let k ≥ 4, and let y 1 , y 2 ∈ V k such that N k-2 (y 1 ) = N k-2 (y 2 ). We will show that for all p ∈ 0, k -2 \ {1}, N p (y 1 ) = N p (y 2 ). From H N (k) applied to y 1 and y 2 , we get:

N k-2 (y 1 ) = W k-2 (y 1 ) = {t ∈ V k-2 | (O 1 (t), . . . , O k-4 (t)) = (O 1 (y 1 ), . . . , O k-4 (y 1 )) and O k-3 (y 1 ) ⊆ O k-3 (t) ⊆ O k-2 (y 1 )}, and N k-2 (y 2 ) = W k-2 (y 2 ). Since N k-2 (y 1 ) = N k-2 (y 2 )
, then by considering a common element t of these two sets (which are non empty since O k-2 (y 1 ) ∈ O), we have (O 1 (y 1 ), . . . , O k-4 (y 1 )) = (O 1 (y 2 ), . . . , O k-4 (y 2 )) (using the usual convention on empty sequences). We now prove that O k-3 (y 1 ) = O k-3 (y 2 ). From recursion hypothesis H sur (k), we know that there exists t 1 ∈ V k-2 such that S(t 1 ) = (O 1 (y 1 ), . . . , O k-3 (y 1 )). This element t 1 is clearly an element of N k-2 (y 1 ), and then is an element of N k-2 (y 2 ). Then, we have This shows that H E (k) is true, which ends the recursion step and the proof of Theorem 1.

O k-3 (y 2 ) ⊆ O k-3 (t 1 ) = O k-3 (y 1 ). Symmetrically, by considering an element t 2 ∈ V k-2 such that S(t 2 ) = (O 1 (y 2 ), . . . , O k-3 (y 2 )), we obtain O k-3 (y 1 ) ⊆ O k-3 (y 2 ).
The termination of the series directly follows from the bijection theorem (Theorem 1 above) between the vertices of the multipartite graph and the chains of L.

Theorem 2 (Termination theorem). For any graph G, the clean-factor series (G i ) i≥1 generated by G terminates.

Proof: Theorem 1 states that the characterising sequence (O 1 (x), . . . , O k-1 (x)) of any node x at level k is such that O 1 (x)

. . . O k-1 (x). The strict inclusions imply that the length of the characterising sequence, which is equal to k -1, cannot exceed h + 1, where h is the height of L. Since h ≤ n -2, necessarily V n+1 is empty. It follows that the clean-factor series terminates and that the multipartite graph on which it terminates has at most n + 1 levels, that is the upper level has index at most n.

In our definition of the clean-factor series, the first bipartite graph of the series is always the vertex-clique-incidence bipartite graph of some graph. It is worth to note that our result of termination is actually more general: the iteration of the clean-factor operator starting from an arbitrary bipartite graph always terminates too.

Corollary 1. For any bipartite graph H, the series of multipartite graphs obtained by iteratively applying the clean-factor operator starting from H terminates.

Proof: Let H = (V 0 , V 1 , E) be an arbitrary bipartite graph. Now, consider the vertex-clique-incidence bipartite graph H = (V 0 , V 1 , E ) built from H in the following way: for each vertex y ∈ V 1 , add a particularising vertex x ∈ V 0 linked only to y. Then, in H , the sets of neighbours on V 0 of vertices of V 1 are not pairwise included and it follows that H is the vertex-clique-incidence bipartite graph of some graph4 G . Moreover, since the vertices we added on level V 0 are included in only one maximal clique of G , then the vertices at level V 2 in the clean-factor graph of H and H are the same and have the same neighbourhoods. And this holds for all other levels of the series as well: from level V 1 and above, the series of H is identical to the one of H. And since from Theorem 2, the series of H terminates, so does the series of H.

Practical utility of the model

In addition to the theoretic questions we addressed, our work was motivated by designing a model of complex networks that, while remaining very general, encompass both the local density and the heterogeneous degree distribution of those graphs encountered in practice. In this section, we emphasise on the fact that our modelling object, the multipartite graph on which the clean factor series terminates, which we call the clean-factor decomposition, is suitable for practical use, with regard to size and time of computation. This allowed us to compute the clean-factor decomposition of very large graphs having hundreds of thousands of vertices and millions of edges. These practical results are not presented here since they are far beyond the scope of this work. But, in the following, we give theoretic evidence of why the clean-factor decomposition is a suitable model to manipulate large real-world instances of graphs, based on common properties of those graphs.

The size of the multipartite graph M obtained at termination of the cleanfactor series can be exponential in theory, as the number of maximal cliques itself may be exponential. But in practice, its size is quite reasonable and it can be computed efficiently. Indeed, the size of M mainly depends on the complexity of imbrication of maximal cliques, namely on the number of chains of L (Theorem 1). Theorem 3 below shows that under reasonable hypotheses, this number is linearly bounded and the size of M only linearly depends on the number of vertices of G.

It must be clear that our hypotheses imply that the number of maximal cliques of G is linearly bounded, as the vertices on level V 1 of M are precisely the maximal cliques of G. But on the other hand, note that this bound on the number of maximal cliques is not sufficient to guarantee a polynomial bound on the number of vertices of M : there may still be an exponential number of vertices on the upper levels of M . Theorem 3 below shows that this does not happen under our hypotheses.

. , O i ) such that O 1 , . . . , O i-1 ∈ O.
First, we use the fact that all such sequences are sub-sequences of those obtained starting from a clique O i and recursively removing one vertex at each step until one obtains a pair O 1 . The number of such sequences starting with a fixed clique is at most the number of orders on the c vertices of the clique, that is c!. And the number of sub-sequences of a sequence of length c is 2 c . Finally, since each vertex is included in at most k maximal cliques, the number of maximal cliques is at most k n. Then, there are at most k 2 c c! n increasing sequences made of elements of O, which are in bijection with the vertices of M of level at least 2. Moreover, note that our counting also includes the sequences made of one single maximal clique of G and the sequences made of one single set O which is a singleton. Those particular sequences are in bijection with the vertices of M at level 1 and 0 respectively. Then, we obtain

|V (M )| ≤ k 2 c c! n.
Clearly, since O ⊆ O , the number of strictly increasing sequences made of elements of O is at most the number of strictly increasing sequences made of elements of O . Another way to count those latter sequences is to count those starting with a fixed minimal set O min ∈ O \ {∅}. Since O is closed under intersection, minimal elements of O \ {∅} are pairwise disjoint and therefore their number is at most n. The sequences having O min as first set can be formed by starting from a clique containing O min and iteratively intersecting it with another clique containing O min . By hypothesis, there are at most k cliques containing a given O min , and therefore k! orders on these k cliques. Each order gives rise to a sequence of elements of O , which contains 2 k sub-sequences. Thus, there are at most k! 2 k strictly decreasing sequences of elements of O having O min as first element. Note that the counting we made actually also comprises the sequences made of one single maximal clique of G. Consequently, the number of vertices in M at level at least 1 is at most k! 2 k n, and adding the n vertices at level 0 to this count we obtain the bound |V (M )| ≤ (2 k k! + 1) × n, which completes the proof.

In practice, parameters k and c are quite small, as they are often constrained by the context where the graphs come from (e.g. social networks, computer networks, citation networks) independently from the size of the graph. Then, the size of M is reasonable in practice, namely O(n) for class of graphs where k and c are bounded. An important consequence is that for those graphs it is possible to compute M in low polynomial time. For example, under those hypotheses, the algorithm of [START_REF] Wan | A new algorithm for enumerating all maximal cliques in complex network[END_REF] enumerates all maximal cliques of graph G in linear time with regard to the number of maximal cliques, that is O(n) time in this case. Moreover, [START_REF] Gély | Enumeration aspects of maximal cliques and bicliques[END_REF] shows that, for general bipartite graphs on |B| vertices, it is possible to enumerate their maximal bicliques in O(|B| 2 ) time per biclique (see also [START_REF] Alexe | Consensus algorithms for the generation of all maximal bicliques[END_REF] for a survey on maximal bicliques enumeration). In the computation of M , at any stage we have to compute the maximal bicliques of the bipartite graph between the uppermost level and the rest of the levels. Since, from Theorem 3, under our hypotheses, the size of M is O(n), then the time needed to compute one maximal biclique is O(n 2 ). And as we need to compute at most O(n) bicliques along the algorithm, it follows that the total time spent by the algorithm for computing the maximal bicliques involved in the construction of M is O(n 3 ). Finally, as the rest of the treatments needed for the construction of M can be achieved in polynomial time, it turns out that, under the hypotheses of Theorem 3, M can be computed in polynomial time.

These facts explain that, in practice, using as black boxes the implementation [START_REF] Uno | Implementation of Tomita et al.'s algorithm[END_REF] of [START_REF] Tomita | The worst-case time complexity for generating all maximal cliques and computational experiments[END_REF]'s algorithm for enumeration of maximal cliques and the implementation [START_REF] Uno | Lcm program (linear time closed itemset miner)[END_REF] of [START_REF] Uno | An efficient algorithm for enumerating closed patterns in transaction databases[END_REF]'s algorithm for enumeration of maximal bicliques, we could compute the clean-factor decomposition of graphs with thousands and even hundred of thousands of nodes. Indeed, we did so for a protein interaction network of 1 458 vertices and 1 948 edges, a movie actors network of 392 340 vertices and 15 038 083 edges, and a piece of the world-wide-web graph of 325 740 nodes and 1 090 108 edges (all can be found at [START_REF] Barabási | Ccnr network databases[END_REF]).

This shows that, even though the problem of computing the maximal cliques and bicliques is NP-hard for arbitrary graphs, for graphs encountered in practice, since this computation can be done in polynomial time (under the hypotheses of Theorem 3), it is possible to efficiently compute the clean-factor series. This makes the clean-factor model a very promising tool for modelling complex networks.

Conclusion

In this paper, we studied the termination of the weak-factor operator, which is a multipartite graph operator appeared in the context of complex network modelling. One key issue in this context is that the series obtained by iteratively applying the operator terminates, as this is mandatory in order to obtain an object suitable for modelling. Since the weak-factor series does not always terminate, we designed a refinement of this operator, called the clean-factor graph, whose series terminates for all input graphs. And we showed that this modelling approach is practically efficient in the sense that the clean-factor series can be computed even for large graphs, under reasonable assumptions on their structure.

The first question arising from our work is to find minimal restrictions of the weak-factor operator that guarantee termination for all graphs. Indeed, it is crucial in practice to introduce constraints as light as possible, since those constraints, that have to be respected during the random generation process, makes this process more intricate to design and less efficient. In particular we ask whether the condition requiring equality of the neighbourhoods at level V k-3 in the definition of the clean-factor graph can be replaced by a condition requiring only that these neighbourhoods share at least two common vertices.

Moreover, the use of multipartite graphs as models of complex networks, in the spirit of the bipartite decomposition [START_REF] Guillaume | Bipartite structure of all complex networks[END_REF][START_REF] Guillaume | Bipartite graphs as models of complex networks[END_REF], asks for some other important questions. In this context, the key issue is to generate a random multipartite graph while preserving the properties of the original graph. To do so, one has to express the properties to preserve as functions of basic multipartite properties (like degrees, for instance) and to generate random multipartite graphs satisfying these properties. This is a very promising direction for complex network modelling, but much remains to be done.

Figure 2 :

 2 Figure 2: An example graph for which the weak-factor series is infinite. From left to right:the input graph G, its vertex-clique-incidence bipartite graph B(G), and the tripartite graph B(G) + of its weak-factor series (note that for sake of readability of the drawing, the edges between levels V 1 and V 0 have been removed in B(G) + ). The shaded edges are the ones involving vertex e, which plays a special role: all the vertices of the upper level of the multipartite graph are linked to e. The structure of edges between vertices of V 2 and vertices of V 1 ∪ {e} in B(G) + is identical to the one between levels V 1 and V 0 in B(G), revealing that the series will not terminate.

Definition 8 .Definition 9 .

 89 We denote by O the set of intersections of maximal cliques of G (possibly only one clique or none), that is O = {O ⊆ V (G) | ∃P c ⊆ K(G), O = C∈Pc C}, using the convention that C∈∅ C = V (G). And we denote by O the subset of O formed by the elements that contain at least two vertices of G and that are obtained as the intersection of at least two distinct maximal cliques of G, that is O = {O ∈ O | |O| ≥ 2 and ∃k ≥ 2, ∃C 1 , . . . , C k ∈ K(G), (∀j, l ∈ 1, k , j = l ⇒ C j = C l ) and O = 1≤i≤k C i }. For any subset A ⊆ V (G) of vertices of G, we denote by K(A) the set of maximal cliques of G containing A, that is K(A) = {C ∈ K(G) | A ⊆ C}. And we denote by C the family of subsets of K(G) defined by C = {K(O) | O ∈ O }.

Lemma 1 .

 1 O and C are closed under intersection. Proof: The fact that O is closed under intersection is clear from the definition. Let us show that C is closed under intersection. Let k ≥ 2 and let O 1 , . . . , O k ∈ O . We prove that 1≤i≤k K(O i ) ∈ C. For that purpose, consider a set O ∈ O such that O ⊇ 1≤i≤k O i and which is minimal under inclusion. We will show that 1≤i≤k K(

  y∈Nj (x) N 1 (y) is in C and there exists some O j in O satisfying the condition. The fact that such an O j ∈ O is unique comes from the fact that for any set O ∈ O , we have O = C∈K(O) C. Then, if there exists some O such that K(O) = K(O j ), necessarily O = O j . Consequently, O j is unique and properly defined.

Figure 3 :

 3 Figure3: Top left: a graph G. Top center: its maximal cliques. Top right: the inclusion order L of the non-simple intersections of maximal cliques of G. Bottom: the multipartite graph M obtained at termination of the clean-factor series of G. M has 5 levels. Level V 0 is for the vertices of G and level V 1 for the maximal cliques of G. The bijection between the vertices of M and the chains of order L appears in the rest of the levels: each vertex x of M in levels V 2 to V 4 has been labelled with the corresponding chain of L, i.e. its characterising sequence S(x) (seeDefinition 10). Level V 2 is for the non-simple intersections of maximal cliques of G (i.e. the chains of L of length 0), level V 3 is for the chains of L of length 1, and level V 4 is for the chains of L of length 3, which is precisely the height of L. For sake of clarity, only a few links of M have been drawn on the figure, namely all the links between two consecutive levels higher than level V 2 . The black bold lines are for the link between a vertex x at level V i , for i ≥ 3, and the unique vertex of V i-1 whose characterising sequence is a prefix of the sequence of x (of length length(S(x)) -1, necessarily). In this way, we obtain a clearer representation of the bijection with the chains of L, as one can clearly see the four prefix trees of the chains starting at a given element of L: these prefix trees are rooted at level V 2 and two of them are reduced to one single node, labelled (abcd) and (abce).

3 and then x ∈ V 3 .

 3 The last condition we have to check for proving H sur[START_REF] Barabási | Ccnr network databases[END_REF] is that O 1 (x) = O 1 and O 2 (x) = O 2 . We already have O 1 = N 0 (x) = O 1 (x).Moreover by definition, O 2 (x) is the unique element of O such that K(O 2 (x)) = y∈Y N 1 (y), and we also have from above that K(O 2 ) = y∈Y N 1 (y), then O 2 (x) = O 2 .

  and (O 1 (y), . . . , O k-3 (y)) = (O 1 , . . . , O k-3 )}. And by definition of x, the couple (O k-2 , O k-1 ) also satisfies this condition. But sinceO k-2 , O k-1 , O k-2 (x), O k-1 (x) all belong to O, then, from recursion hypothesis H sur (k -1), for any P ∈ {O k-2 , O k-1 , O k-2 (x), O k-1 (x)} there exists y ∈ V k-1 such that S(y) = (O 1 , . . . , O k-3 , P ). Then, for P = O k-1 , using the definition of N k-1 (x) based on the couple (O k-2 , O k-1 ), we obtain that y ∈ N k-1 (x), and consequently, using the definition of N k-1 (x) based on the couple (

  And finally, we have O k-3 (y 1 ) = O k-3 (y 2 ). Then, regardless of the value of k ≥ 4, we have N 0 (y 1 ) = O 1 (y 1 ) = O 1 (y 2 ) = N 0 (y 2 ), which is enough to prove H E (k) when k = 4. Let us complete the general case where k ≥ 5 by considering some p ∈ 2, k -3 and showing that N p (y 1 ) = N p (y 2 ). From recursion hypothesis H N (k), we have N p (y 1 ) = {t ∈ V p | (O 1 (t), . . . , O p-2 (t)) = (O 1 (y 1 ), . . . , O p-2 (y 1 )) and O p-1 (y 1 ) ⊆ O p-1 (t) ⊆ O p (y 1 )}. And since p ≤ k -3, (O 1 (y 1 ), . . . , O p (y 1 )) = (O 1 (y 2 ), . . . , O p (y 2 )), which implies N p (y 1 ) = N p (y 2 ). Thus, for all p ∈ 0, k -2 \ {1}, N p (y 1 ) = N p (y 2 ).

Theorem 3 .

 3 If every vertex of G is involved in at most k maximal cliques and if every maximal clique of G contains at most c vertices, then we have |V (M )| ≤ min(k 2 c c! , 2 k k! + 1) × n Proof: Thanks to Theorem 1, we obtain an upper bound on |V (M )| by bounding the number of strictly increasing sequences of the form (O 1 , . .

Note that[START_REF] Prisner | Convergence of iterated clique graphs[END_REF] uses a different definition of convergence which includes the one of[START_REF] Bornstein | On clique convergent graphs[END_REF] as a particular case, and also includes periodic behaviours. The notion of termination we use throughout the article is somehow equivalent to the one of[START_REF] Bornstein | On clique convergent graphs[END_REF].

Note that the bicliques we use in the definition of the weak-factor operator are bicliques in a bipartite graph and not in a general graph as in the definition of the biclique graph operator.

Note that this multipartite graph is an encoding of the original graph, as the factorising operation is reversible.

Graph G is simply the graph whose vertex set is V 0 and whose maximal cliques are the neighbourhoods in H of the vertices of V 1 .

Acknowledgements. We warmly thank Thanh Qui Nguyen and The Hung Tran for helpful discussions on the subject, as well as Clémence Magnien and Stéphan Thomassé for their comments on the writing of the article.

$ This work was partially supported by the PICS program of CNRS (France), by the Vietnam National Foundation for Science and Technology Development (NAFOSTED) and by the Vietnam Institute for Advanced Study in Mathematics (VIASM).

W k-1 (x), we have O q (y) = O q (x) for all q ∈ 1, k -3 . Moreover, as we showed at the beginning of the proof of H N (k), for all i ∈ 1, l , and all q ∈ 1, k -3 we have O q (a i ) = O q (x) and so O q (a i ) = O q (y). For q = 1, from the definition of O 1 , this gives N 0 (a i ) = N 0 (y). For q ≥ 2 (which occurs only for k ≥ 5), using recursion hypothesis H N (k -1) that characterises, for any z ∈ V k-1 and any q ≥ 2, N q (z) as a function of only O 1 (z), . . . , O q (z), we then obtain that since y and a i have the same sequence O 1 (y), . . . , O k-3 (y) = O 1 (a i ), . . . , O k-3 (a i ), they necessarily have the same neighbourhood N q (y) = N q (a i ), for all q ∈ 2, k -3 . Since we showed that y and a i also have the same neighbourhood on V 0 , and since we showed at the beginning of the proof of H N (k) that N p (a i ) = N p (x) for all p ∈ 0, k -3 \ {1}, it follows that for all p ∈ 0, k -3 \ {1}, we have N p (y) = N p (x). Then, in order to show that y ∈ N k-1 (x), we only need to show that N 1 (x) ⊆ N 1 (y) and N k-2 (x) ⊆ N k-2 (y), which implies, by maximality of x (see Definition 2), that y ∈ N k-1 (x). First, let us show that

And since we already showed that O q (a i ) = O q (x), then we obtain O q (z) = O q (x) for all q ∈ 1, k -4 . On the other hand, since y ∈ W k-1 (x), then O q (y) = O q (x) for all q ∈ 1, k -4 , which finally gives that O q (y) = O q (z) for all q ∈ 1, k -4 .

Let us now show that

. We state this fact as a proposition as we use it further in the proof:

And by recursion hypothesis H

In summary, we showed that for any y ∈ W k-1 (x), we have

As we also showed the converse inclusion, we obtain

In order to achieve the proof of H N (k), we still have to show that

As we already mentioned several times, we have

. And for the same reason, we also have

Then, the only thing left we have to show in order to prove that z ∈ W k-2 (x), which is our goal, is to prove that O k-3 (z) ⊆ O k-2 (x). In fact, we already proved this proposition in the proof of W k-1 (x) ⊆ N k-1 (x) above, referred as (Prop. A) in the text. So we finally obtain that N k-2 (x) ⊆ W k-2 (x), and since we already proved the converse inclusion, we obtain the equality between the two sets, N k-2 (x) = W k-2 (x), which completes our proof of H N (k).

Proof of H tar (k). From H N (k) we know that for any i ∈ 1, l , (O 1 (a i ), . . . , O k-3 (a i )) = (O 1 (x), . . . , O k-3 (x)). Then, from recursion hypothesis H tar (k -1), we have O 1 (x) . . . O k-3 (x) and, in particular, we have O 1 (x) ∈ O and so

From recursion hypothesis H sur (k -1), for any P ∈ O such that O k-3 P , there exists y P ∈ V k-1 such that S(y P ) = (O 1 , . . . , O k-3 , P ). We denote by Y the set

k and that the corresponding element of V k has the desired sequence S(x) = (O 1 , . . . , O k-1 ).

Let us start by showing that

), which do exist from recursion hypothesis H sur . Since this is true for all y ∈ N k-2 (x), then x itself has these two elements as neighbours on level

And since O k-1 ∈ O, O k-1 contains at least two elements and so does x ∩ V 1 . In order to complete the proof of x ∈ V * k , we need to show that for all y, y ∈ Y , we have N k-3 (y) = N k-3 (y ). First, note that, by definition, (O 1 (y), . . . , O k-3 (y)) = (O 1 (y ), . . . , O k-3 (y )) = (O 1 , . . . , O k-3 ). Moreover, recursion hypothesis H N (k -1) gives that the neighbourhood at level V k-3 of any vertex z ∈ V k-1 only depends on the piece of sequence (O 1 (z), . . . , O k-3 (z)). And since y and y have the same such pieces of sequence, it follows that N k-3 (y) = N k-3 (y ). Thus x ∈ V * k . We will now show that x is maximal in V * k . Let z ∈ V k-1 \Y , we show that if for some j ∈ 1, k -3 , O j (z) = O j then there is no element B ∈ V * k containing Y ∪{z}. We denote y ∈ Y an arbitrary element of Y and we distinguish between the case where k = 4 and the case where k ≥ 5.

Let us start with the general case where k ≥ 5, we show that N k-3 (z) = N k-3 (y), which implies, from Definition 7, that there is no element of V * k containing both y and z. So let j ∈ 1, k -3 , such that O j (z) = O j . Since O j (y) = O j , then we have O j (z) = O j (y). Moreover, from recursion hypothesis H N (k -1), we have N k-3 (z) = W k-3 (z) and N k-3 (y) = W k-3 (y). We again distinguish several cases depending on the value of j. If j ≤ k -5 (which may occur only when k ≥ 6), from recursion hypothesis H sur (k -3), there exists t 1 ∈ V k-3 such that S(t 1 ) = (O 1 (z), . . . , O k-4 (z)). Clearly, from the definition of W j (z), we have t 1 ∈ W k-3 (z) = N k-3 (z). On the opposite, from the definition of W j (y), and since O j (z) = O j (y) with j ≤ k -5, we obtain t 1 ∈ W k-3 (y) = N k-3 (y) and it follows that