Marina Bruneau
email: marina.bruneau@utc.fr

Alexandre Durupt
email: alexandre.durupt@utc.fr

Laurent Vallet
email: laurent.vallet@ensam.eu

Lionel Roucoules
email: lionel.roucoules@ensam.eu

Jean-Philippe Pernot
email: jean-philippe.pernot@ensam.eu

A THREE-LEVEL SIGNATURE BY GRAPH FOR REVERSE ENGINEERING OF MECHANICAL ASSEMBLIES

Keywords: Reverse Engineering, CAD, signature, shape descriptor, graph comparison

Several approaches exist to provide Reverse

Engineering solutions on mechanical parts. Mechanical assemblies and the expertise information retrieved at the same time with the model geometry are not really taken into account in the literature. Thus, the main challenge of this contribution is to propose a methodology to retrieve the Digital Mock-Up of a mechanical assembly from its meshed data (from digitalization). The output DMU consists of expertise information and parameterized CAD models. The methodology proposed relies on a signature by a three-level graph. It enables to provide an adequate level of details by identifying the corresponding functional surfaces in meshed data. The first-level graph is a connectivity graph; the intermediate level is the same as the first with the geometric type of face added to each node (plane, cylinder and sphere) and the deepest level corresponds to a precedence graph. This one provides information such as functional surfaces and position between them (perpendicularity, coaxiality etc.). The solutions developed and the results are presented in this paper. The methodology is illustrated thanks to an industrial use-case with a scan of an assembly with a connecting rod and a piston. The conclusion and perspectives will complete this paper.

INTRODUCTION

Reverse Engineering (RE) is defined as a process starting from a physical product and ending to digital representation in two or three dimensions. It can be used at several steps in the product lifecycle and in a routine way. Vinesh and Fernandes [START_REF] Vinesh | Reverse Engineering[END_REF] present in Figure 1 the link between CAD and CARE which is Computer-Aided Reverse Engineering. Most of CARE solutions propose to rebuild the CAD model with geometry without any possibility to change Figure 1 Reverse Engineering process from [START_REF] Vinesh | Reverse Engineering[END_REF] method by approximation of the Medial Axis Transform (MAT) of the 3D object. An inverse transform is used to retrieve the surface representation from the MAT. Approaches based on shock-graph are similar such as in Sebastian et al. [START_REF] Sebastian | Recognition of shapes by editing shock graphs[END_REF]. This shape descriptor is used in order to recognize 2D shape outlines. A third type of graph-based method is Reeb Graph (RG). The difference with skeleton lies in the way of building the graph and a ponderation criterion is used. RG principle is to cut the shape (2D or 3D data) by parallel level lines. For each section obtained, center of mass is computed, which corresponds to one node of the graph. Once all the nodes are linked, the graph is created. Instead of computing the center of mass, other criteria have been used in the literature such as [START_REF] Hilaga | Topology Matching for Fully Automatic Similarity Estimation of 3D Shapes for Topology Matching[END_REF] [START_REF] Bespalov | Reeb Graph Based Shape Retrieval for CAD[END_REF]. Tierny et al. [START_REF] Tierny | Graphes de Reeb de Haut Niveau de Maillages Polygonaux 3D[END_REF] propose a new method which is invariant to 3D shape position and mesh resolution. Biasotti et al. [START_REF] Biasotti | Sub-part correspondence by structural descriptors of 3D shapes[END_REF] compare sub-part correspondence. Their method is able to provide a global measure of the similarity between two parts but also to indicate where the similarities occur in the shapes. It is performed thank to RG which enable to couple geometrical and structural information about the shape. Model-graphs and in particular attributed graph seem to be an adequate solution for our signature process. Indeed this representation provides a higher level of details in the signature such as topological and geometrical information, which can be interesting if the user wants to retrieve a parametrized CAD model of each component of the mechanical assembly.

Signature matching and KBE application

Tangelder and Veltkamp [START_REF] Tangelder | A survey of content based 3D shape retrieval methods[END_REF] consider the matching step as a process enabling to determinate similarity between two shapes, by computing their "distance" between each other. As graph-based signatures are studied in this paper, only graph comparison will be treated. To compare the signatures, our system disposes of a knowledge database composed of signatures. Each signature is linked to a component which belongs to an mechanical assembly, a function etc. Chapman and Pinfold [START_REF] Chapman | Design engineering -a need to rethink the solution using knowledge based engineering[END_REF] define Knowledge-Based Engineering (KBE) as a method combining oriented computer programming, artificial intelligence techniques and CAD tools. KBE tools enable to capture information linked to the product, in order to reuse it in engineering activities. These systems aim to capitalize best design practices and also information expertizes and they store them in a knowledge database. Durupt et al. [START_REF] Durupt | A new reverse engineering process, the combination between the knowledge extraction and the geometrical recognition techniques[END_REF] propose a methodology called KBRE which combines RE and KBE activities. The given solution uses a functional and structural skeleton from a knowledge database. It leads their RE process by instantiating the skeleton thanks to dimensions extracted from points cloud. The skeleton is composed of two types of characteristics: design intents and manufacturing characteristics. They contain information expertizes in order to rebuild a parametrized CAD model. Recently Ali [START_REF] Ali | La rétro-conception de composants mécaniques par une approche "Concevoir pour fabriquer[END_REF] came up with a methodology called REFM (Reverse Engineering For Manufacturing). She associates information expertizes link to the manufacturing process with the RE process. A knowledge database enables to store this information whose aim is first to bring a structured method to the user for the purpose of remanufacturing the component. Then this knowledge, stored under precedence graph formalism, can be reused for RE of similar components. These KBE solutions could be useful in our context. Let us now have a look on the related works dealing with graph comparison. Through the comparison of graphs, we seek similarities between the two components. The result of comparison is used to filter (restrict) the set of nodes of each of the graphs. Then this improves the precision of the signature and it increases the percentage of matched components. Thus, we are confronted with problem of finding Maximum Common Subgraph (MCS) of two graphs. This problem is NP-hard optimization problem: there is no known polynomial solution to this problem. Several libraries and software allow comparison graphs: Boost Graph Library (BGL) [START_REF] Siek | The Boost Graph Library: User Guide and Reference Manual[END_REF], Vflib2 [START_REF] Cordella | A (sub)graph isomorphism algorithm for matching large graphs[END_REF], Simpack [START_REF] Bernstein | SimPack: A Generic Java Library for Similarity Measures in Ontologies[END_REF], Nauty [START_REF] Mckay | Practical graph isomorphism,II[END_REF], etc. Unfortunately some seem to only support directed graphs (Vflib2 and Simpack for example). In our case, the graphs are not oriented: nodes are linked by edges whereas in oriented graph, they are linked by arrows. Others solutions do not fulfill to the problem (i.e. MCS). So we opted for the BGL library in C ++. It provides the algorithm « Mc Gregor common subgraphs ». Thus, it perfectly meets the issue: it resolves MCS problem, it supports undirected graphs, it allows customizing the output display of the results (via user callback)which can be operated easily -, and finally, the vertices and edges may receive values, which allow them to compare themselves (via vertices equivalent and edges equivalent predicates). Once mappings between the two graphs were obtained, it remains to apply a criterion of similarity to mean how the two graphs are similar.

Thanks to [START_REF] Durupt | A new reverse engineering process, the combination between the knowledge extraction and the geometrical recognition techniques[END_REF][15], we can measure the advantages of KBE systems because they can help considerably the user in the RE process and accelerate the identification of the components. The combination of graph and knowledge database could permit to identify also uncompleted components inside the data.

HDI-RE : HETEROGENEOUS DATA INTEGRATION FOR REVERSE ENGINNERING

The whole methodology

HDI-RE is a global methodology which answers the main issue presented in introduction of this paper. In this section, we will explain the ins and the outs of each step (see Figure 2).

The first step concerns the data segmentation.

According to its type (2D or 3D), a technique of segmentation is applied to retrieve segments. For this paper, we consider only points cloud data (others heterogeneous data are presented in [START_REF] Bruneau | A methodology of Reverse Engineering for large mechanical assemblies products from heterogeneous data[END_REF]). The aim is to retrieve segments which can be identified topologically as planes, cylinders and sphere. The others types such as torus or cones are not studied in this work since the number of parameters of canonical surface to approximate is larger. The method used relies on hierarchical mesh segmentation. The entire methodology is described in Attene et al. [START_REF] Attene | Hierarchical mesh segmentation based on fitting primitives[END_REF].

A graph is built (second step of our methodology) and it corresponds to the signature of the data. Each cluster (segment) is associated to a node and the edges refer to the connectivity between each cluster of the segmented data. If the final aim of the RE process is to rebuild a digital mock-up with parametrized CAD models, the signature of the data (the graph) may contain an appropriate level of details such as topological information or dimensions of the main characteristics. It will be explained in the next section.

The last step concerns the signature comparison. The graph signature of the data is compared with other signatures existing in the KDB. We consider that a component signature can't be recognized if there is no existing signature of the related component in the database. A capitalization of the enterprise proper knowledge is performed at each RE process.

A three-levels geometrical signature

In this section, we present one of the signatures developed in the HDI-RE process which is dedicated to points cloud data. Another one has been presented in a previous work [START_REF] Bruneau | A methodology of Reverse Engineering for large mechanical assemblies products from heterogeneous data[END_REF].

The Figure 3 presents a global representation of our three-level signature. Depending of the level of details required to (re)build the DMU, five scenarios can be possible and they are described in [START_REF] Bruneau | Une méthodologie de Reverse Engineering à partir de données hétérogènes pour les pièces et assemblages mécaniques[END_REF]. One of them will be presented in section 4.1. From a global point of view, a segmented mesh1 is signed as follows:

• First-level signature: each node represents a cluster (also called segment) of the mesh. The edges refer to the connectivity links between the clusters. Let us consider 𝐺𝐺 1 this first-level graph; 𝑁𝑁 1 the set of nodes of 𝐺𝐺 1 and 𝐸𝐸 1 the connected edges.

• Second-level signature: the first-level signature is reused. Each cluster (graph's node) is classed as plane, cylinder, sphere or other. This information is added to each corresponding node as attribute. The second signature corresponds to a second graph 𝐺𝐺 2 with 𝑁𝑁 2 its nodes and 𝐸𝐸 2 the connected edges. We can notice that 𝐸𝐸 1 = 𝐸𝐸 2 .

• Third-level signature: this one is dependent of the second level. Let us consider 𝐺𝐺 3 this thirdlevel graph; 𝑁𝑁 3 the set of nodes of 𝐺𝐺 3 and 𝐸𝐸 3 the connected edges. It is built thanks to the intersection between a mapping (cited later) and its second-level signature. It is called precedence graph: an example is given in Figure 5.

It is a formal representation of design intents used in engineering process. It is presented in details in Ali [START_REF] Ali | La rétro-conception de composants mécaniques par une approche "Concevoir pour fabriquer[END_REF]. This type of graph is useful for the part instantiation (digital mock-up reconstruction). Its edges have labels which correspond to geometrical constraints and its nodes have the same attributes as the second-level graph. The main advantage is the limited number of nodes of this graph: only the functional surfaces of the component have a corresponding node in the graph (the number of nodes in a precedence graph is smaller than the number of faces). Thus the amount of nodes to compare is also reduced. We consider that the knowledge database contains precedence graphs previously. Moreover compared to the two previous graphs, this one is oriented. Thus the graph in Figure 5 is interpreted as follows: the node C2 (cylindrical surface) is positioned thanks to C1 by a constraint of parallelism. The plane P3 is perpendicular to C1 cylinder's axis. There are many types of constraints existing so, for our work, we consider only these ones: perpendicularity, coaxiality and parallelism.

Signature comparison

We consider that all the signatures (levels 1, 2 and 3) of the components in KDB have been created upstream to the RE activity: they have been segmented thanks to Efpisoft and then they have been signed such as in the process described in the previous section. These signatures are used as reference to identify components in our input data.

After the first-level signature, the first-level graph of our input data is compared with the first-level graphs in KDB. Let us consider 𝑆𝑆𝐺𝐺 1 , one of the maximum common subgraphs and which relies on one of the mapping. This last is a list of correspondences between 𝑁𝑁 1 and 𝑁𝑁′ 1 the set of nodes of 𝐺𝐺′ 1 , one graph of database which matched. Thus 𝑆𝑆𝐺𝐺 1 = 𝑁𝑁 1 ∩ 𝑁𝑁′ 1 . Figure 6 (step A) illustrates the comparison between 𝐺𝐺 1 , the input data signature and 𝐺𝐺′ 1 , one graph of the database. Then the mapping results are shown (step B): these are all the combinations of correspondences between the two graphs ( 𝑆𝑆𝐺𝐺 1 is equivalent to one combination). We consider that a component (reference) is identified in our input data if its similarity score with the input data is superior to zero percent. Many reference components can match with a low similarity score. Thus we will keep the highest or one of the highest similarity score (e.g. 80 %) and we will consider that our input data is 80% similar, for example, with the reference component (e.g. a connecting rod). At this stage, our input data is considered as similar to others components thanks to connectivity information.

For the second level, the graph comparison is done between 𝐺𝐺 2 and the second-level signatures of the KDB. 𝑆𝑆𝐺𝐺 2 is one of the maximum common subgraphs belonging to the mapping between 𝐺𝐺 2 , one of the graph from KDB (𝑁𝑁′ 2 its nodes). We consider that 𝐺𝐺′ 2 got the highest matching score comparing to the others graphs of KDB. At this stage, the component is identified topologically and geometrically and it is possible to determine the similarity between the meshed data and one component identified (our reference). In our example, a connecting rod has been identified in our meshed data (cf. Figure 3).

For the third level, the comparison can be processed only if there is at least one maximum common subgraph ( 𝑆𝑆𝐺𝐺 2 ) existing after the second-level comparison. Let us consider 𝐺𝐺′ 3 , the precedence graph (PG) of the connecting rod from the KDB The set of matched nodes (from 𝑇𝑇𝑇𝑇𝑇𝑇_𝐺𝐺𝐺𝐺𝑇𝑇𝐺𝐺ℎ𝐿𝐿𝐿𝐿𝐿𝐿3) is called 𝑛𝑛 3 and it corresponds to the functional surfaces inside the meshed data. As described previously, the last step of the comparison procedure consists in verification. It is performed by computing local characteristics of each node of 𝑛𝑛 3 (cluster of the meshed data). A threshold is defined by the user.

For each constraint between two segments of the mesh data computed, the relative error should be inferior to this threshold. If constraints are validated (e.g. perpendicularity between two clusters), thus each corresponding edge of the graph is generated (it corresponds to the third column of 𝑇𝑇𝑇𝑇𝑇𝑇_𝐺𝐺𝐺𝐺𝑇𝑇𝐺𝐺ℎ𝐿𝐿𝐿𝐿𝐿𝐿3). Geometrical information of 𝑁𝑁 3 (e.g. diameter and length of a cylindrical segment) could be used (in future works) to instantiate a CAD template whose functional surfaces are piloted by these parameters. To finish, 𝐺𝐺 3 is stored in the database for knowledge capitalization (𝐺𝐺 1 and 𝐺𝐺 2 are also stored).

Factor of similarity between graphs

We used the "node count" as the type of similarity (step C -Figure 6). Three similarities emerge: the similarity to the first graph S G 1 , the similarity to the second graph S G′ 1 , and the overall similarity S G 1 G′ 1 (of how much the two graphs are similar). They are displayed as a percentage. For each of the similarities, the nodes of the largest subgraph (resulting from comparison of graphs) and the nodes of the two initial graphs are used. Let us consider: N G 1 the number of nodes in the first graph, N G′ 1 the number of nodes in the second graph and N G Sub the number of nodes in the subgraph. Then the similarities are defined by:

𝑆𝑆 𝐺𝐺 1 = 𝑁𝑁 𝐺𝐺 𝑆𝑆𝑆𝑆𝑆𝑆 * 100 𝑁𝑁 𝐺𝐺 1 𝑆𝑆 𝐺𝐺′ 1 = 𝑁𝑁 𝐺𝐺 𝑆𝑆𝑆𝑆𝑆𝑆 * 100 𝑁𝑁 𝐺𝐺′ 1 𝑆𝑆 𝐺𝐺 1 𝐺𝐺′ 1 = 2 * 𝑁𝑁 𝐺𝐺 𝑆𝑆𝑆𝑆𝑆𝑆 * 100 𝑁𝑁 𝐺𝐺 1 + 𝑁𝑁 𝐺𝐺′ 1

APPLICATION

The use case presented here is a scanned assembly of a piston and a connecting rod (green cell of the Table 1). The set of data provided in the KDB is composed of three signatures (for each level) for each data. The aim is to identify the components in the input data and extract from them topological and geometrical information in order to instantiate in the future a CAD template.

The number of segments (nodes) has an influence on the graph comparison. It is not possible to predict the best number of nodes for the input data (operation realized manually by the user). So, in order to maximize our ability to match with a signature (with a defined number of nodes) in KDB, we generated a large set of signatures (in KDB) with a varying number of clusters.

Graph-based signature and comparison

Let us consider the steps presented in Figure 2. Our scenario starts when the scanned assembly (mesh) is imported. We consider that the points cloud has already been meshed by the user outside of our process.

The segmentation is performed in Efpisoft software developed by Attene et al. [START_REF] Attene | Hierarchical mesh segmentation based on fitting primitives[END_REF]. The input file is the STL file of the scanned assembly (ASCII format).

The user defines manually the number of segments (ideally this number corresponds to the sum of all the components assembly's surfaces). This can be adjusted thanks to the software's GUI. An illustration of the segmentation is given in Figure 7. The output file is saved in Open Inventor Scene format thanks to Efpisoft software. Another file is generated thanks to separate algorithm. This file is a XML file which contains the Open-Inventor-Scene's file information in a standard format. It will be used for the secondlevel signature. It gives information about each Table 1 Scanned assembly and data available in database matched at step 3 (a piston and a connecting rod). A text file which corresponds to the mapping information (similar to the first-level results) is generated automatically. Moreover, the similarity score is displayed for each comparison performed with a signature form KDB. Information given (thanks to mapping) enables to identify topologically our input data.

At step 7, the user needs to select the best matching results depending of two criteria: similarity score, and number of fitted 2 nodes inside the mapping. Indeed, the maximum common subgraph between our input data and the signature of the KDB needs to have at least one fitted node (defined as plane, sphere or cylinder). Without this condition, it is impossible to continue with the third-level signature because this graph relies only on fitted nodes.

Step 8 is performed upstream to our process: a Graphical User Interface (GUI) helps the RE user to generate 𝐺𝐺𝐺𝐺 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚 in KDB. The precedence graph is linked with the second-level graph of the corresponding component. This GUI is presented in [START_REF] Bruneau | Une méthodologie de Reverse Engineering à partir de données hétérogènes pour les pièces et assemblages mécaniques[END_REF].

For the third-level signature (step 9), the mapping results (subgraph information) of one of the signatures from step 6 is used. Contrary to the two previous levels of signature, this one is performed as many times as there are components selected by the user at step 7. In our example, that means that the signature is first performed in order to match with the precedence graph information of the connecting rod (𝐺𝐺𝐺𝐺 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚_𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑚𝑚𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑚𝑚𝐶𝐶𝐶𝐶𝐶𝐶 ) and then, it is performed again with the information from the piston (𝐺𝐺𝐺𝐺 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚_𝑃𝑃𝐶𝐶𝑃𝑃𝐶𝐶𝐶𝐶𝐶𝐶 ). Thus for the connecting rod, the inputs files for the third level are:

• XML file of signature of the third-level (𝐺𝐺𝐺𝐺 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚_𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑚𝑚𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑚𝑚𝐶𝐶𝐶𝐶𝐶𝐶 ) for the connecting rod selected in step 7. These XML file comes from the knowledge database.

• A text file containing the mapping results from the second-level comparison : it is a list of pair of matched nodes;

• A text file which contains geometrical information about each segment (e.g. normal coordinates for a plane, direction coordinates of a cylinder, cylinder diameter etc.). This 2 A fitted node is a node (cluster) which has been fitted to a canonical surface during the second-level signature.

information is extracted during the type identification in the second-level signature.

As explained previously, this process of comparison is different. Algorithm 1 is applied: it is mainly a geometrical comparison. Then the algorithm is also applied for the piston. The output of this step is the third-level signature of the scanned data. It represents the functional relationships between the segments (clusters) for the two components that compose the mechanical assembly. This signature (XML file) is saved in the database.

Thanks to the third-level signature (XML file), geometrical information extracted from the functional surfaces in the input data will be used to value the CAD templates parameters (for the digital mock-up reconstruction).

Results

In this section, we will present the results obtained for each comparison level according to the set of data available in the KDB.

The input data is segmented in Efpisoft with 20 clusters (Figure 7). This quantity has been determinate according to our capacity of computation. The experiments were conducted on a 2-way Intel Xeon machine operating at 2.40 GHz with 8.00 Go of RAM. The comparison was not possible with graphs with more than 20 nodes, in particular for the first-level comparison.

The number of nodes of the graphs (signatures) in the KDB is also limited. Indeed, it was not possible to compare graphs with more than 15 nodes in particular for the first-level comparison (infinite computing time). The results are displayed in the Table 2.

Each value corresponds to the factor of similarity 𝑆𝑆 𝐺𝐺′ 1 (presented in section 3.4) between the graph of mechanical assembly (data to identify) and the others graphs of the KDB. This similarity factor has been chosen as a mechanical assembly component is looked up in the KDB. The highest scores (with The number of clusters chosen by the user during the segmentation influences all the process and especially the results obtained in the comparison steps. The graphs comparison algorithm is limited by the computing capacity. For now, it is not possible to generate graphs with as clusters as component's faces. Thus in order to get some results, the number of clusters has been decreased: 20 nodes as a maximum for the input meshed data, 60 nodes for the graphs in database for the second-level comparison and until 15 nodes for the first-level comparison.

Several tests have been performed to measure efficiency of the first-level graph (time computing beside quality of results). The results demonstrate that the use of the first-level graph is disputable in our RE methodology. Indeed, the majority of graphs of the database which have matched have a low number of nodes (between 5 and 10). The comparison with others graphs (more than 15 nodes) exceeds computing capacity. Moreover the signatures matched in first level (with only 5 nodes) don't provide enough information to perform third-level comparison. Indeed, these five-node signatures have clusters which are faces agglomerates, thus the node's attribute given is "other". An illustration is given in Figure 10 with a connecting rod with 10 clusters. We can notice that several clusters contain plans and cylinders in the same cluster. The secondlevel signature relative to this segmentation is presented below. Each node attribute is represented by a letter before the node's number: 'P' for plan, 'S' for sphere and 'C' for cylinder. We notice that only 3 nodes are fitted with a canonical surface. It can be deduced that only 3/10 nodes can be matched during the second-level comparison. For this reason the first scenario has been aborted in order to start again our process signature and by skipping the first-level signature. Even with this improvement, the results obtained don't enable to validate our third-level signature. It is mainly due to the low number of nodes of the input data. Ideally this number should be equal to the sum of all the components assembly's surfaces (for the corresponding CAD models).

The data set used in this study involves only components with surfaces which fit only with planes, cylinders or spheres. Free form, conical and toric surfaces haven't been processed such as the second level signature algorithm requires more complex algorithms. It will be carried out in future works.

To finish, the selection of the signature(s) after each comparison needs to be automatized. A solution could be a weighted similarity score in function of the number of fitted nodes in the maximum common subgraph. In addition, uncomplete data (in input) and noise can affect the comparison results and it needs to be also studied.

CONCLUSIONS AND PERSPECTIVES

HDI-RE is a methodology which enables to retrieve a digital mock-up from a set of heterogeneous data. It relies on three steps: segmentation data, signature data and comparison of the signature with the knowledge database.

This paper deals with the signature and comparison steps. One of the signatures developed in our project research and its comparison mechanism are presented. It is a three-level signature by graph. Depending of the level, graph provides different information: connectivity between faces or segments (for the input data), surface type such as plane, cylinder or sphere and functional relationships between faces for the third level.

An applicative example is given with a scanned assembly as input data. Two components are identified: a piston and a connecting rod. The thirdlevel signature enabled to extract some geometric information that could help to instantiate a CAD template (available in the KDB) in order to rebuild the final digital mock-up.

The development work related to the third-level signature is not complete. The last comparison is run manually. The perspectives are to finish it and to perform several tests on it. The number of clusters of the segmented data has an influence on the results, thus this work will be continued in order to improve the final results (influence of the number of clusters, noise etc.). The aim is to identify as much functional surfaces as possible.

To finish, components instantiation (digital mock-up reconstruction step) will be coded in the future thanks to CAD templates also available in the knowledge database.

Figure 4

 4 Figure 4 Example of a precedence graph.

Figure 5

 5 Figure 5 Set of data used for 3rd level comparison.

Figure 10 A

 10 Figure 10 A 10 clusters segmentation and second-level signature.

Table 2

 2 Results for the first-level comparison.

We consider points cloud is meshed previously by the user in dedicated software. Figure 3 A three-level signature for meshed data.

ACKNOWLEDGMENTS

These works have been supported by the ANR (National Agency of Research) through the Numerical Model program (Project METIS -12-MONU-004).

Authors want to thank Attene et al. [18] for letting us using the software Efpisoft in our research works.

Industrial data for the application section have been provided by a French company called IFPEN (Institut Français du Pétrole et des Energies Nouvelles).They are part of the consortium project whose these works are relying on.


Monica Billio

Lorenzo Frattarolo

Hayette Gatfaoui
email: gatfaoui@univ-paris1.fr

Philippe De Peretti

46r

Lorenzo Frattarollo

Clustering in Dynamic Causal Networks as a Measure of Systemic Risk on the Euro Zone

Keywords: Causal Networks, Topology, Flickering, Desynchronisation, Phase Transitions. JEL codes: C1, C4, G1

In this paper, we analyze the dynamic relationships between ten stock exchanges of the euro zone using Granger causal networks. Considering returns for which we allow the variance to follow a Markov-Switching GARCH or a Changing-Point GARCH process, we …rst show that over di¤erent periods, the topology of the network is highly unstable. In particular dynamic relationships vanish over very recent years. Then, expanding on this idea, we analyze patterns of information transmission within the network. Using rolling windows to study networks' topology in terms of information clustering, we …nd that the nodes'state changes continually. Moreover, the system exhibits periods of ‡ickering in information transmission. During these periods of ‡ickering, the system also exhibits desynchronization in the information transmission process. These periods do precede tipping points or phase transitions on the market, especially before the global …nancial crisis, and can thus be used as early warnings.

Introduction

Consider an electronic component designed to emit a signal which is about to fail, that is about to switch from one state to an other. This component is likely to start emitting abnormal signals, or signals in an abnormal way before the failure, rather than abruptly failing. For instance, we are likely to observe a ‡ickering signal before a phase transition occurs. Consider further the component as part of an electronic device, which is connected to other components, forming then a complex interdependent dynamic system. Two questions then arise: i) What will be the impact of the component's failure on the whole system? In other words, will the electronic device fail because of the failure of one component ? and ii) Is it possible to know in advance that a failure will occur ?

One way to answer the …rst question is to look at the integrated circuit of the device (i.e. the topology) and to focus on the importance of the component in terms of centrality and/or the number of components connected to it (i.e. the degree). To answer the second question, one …rst needs to recover the topology of the system, and next to look at the information di¤usion processes (i.e. the signals) so as to identify abnormal periods prior to the failure at the individual and/or the macro level (i.e. component versus circuit level).

Turning to …nancial systems and systemic risk, the …rst question has been adressed by a number of authors using networks. Relating systemic risk to the concepts of connectedness, contagion, and therefore di¤usion of exogenous and/or endogenous shocks within and/or across …nancial sectors (see Bisias et al. 2012), [START_REF] Allen | Financial Contagion[END_REF] as well as Acemoglu et al. (2013) show that highly interconnected networks are more resilient to small shocks but not to large ones. [START_REF] Battiston | Default Cascades in Complex Networks: Topology and Systemic Risk[END_REF] focus on the frailty of nodes, and then study cascading e¤ects as [START_REF] Motter | Cascade-based attacks on complex networks[END_REF] do. In such models, the focus is set on the impact of the failure of one or several nodes on the whole system. Our paper clearly relates to the second question, that is on early warning indicators prior to a phase transition (i.e. non-crisis versus crisis periods). We consider …nancial systems as being possibly critically self-organized (Bak et al., 1987, Bianconi and[START_REF] Bianconi | Clogging and self-organized criticality in complex networks[END_REF]. In particular, local interrelations between the system's components build up a coordinated system or network. Such selforganised network/system will turn into a critical behavior (i.e. tipping point and phase transition) without the e¤ect of external forces or drivers. In this light, our main contribution is to provide early warnings of phase transitions for the whole system (or network), which is highly suggestive of systemic risk.

To detect early warnings, we adopt a two-step methodology. First, we recover the network topology using non-causality tests as suggested in Billio and al. non-causality over a given number of lags, or at a given lag. They thus allow for capturing the complex interplay such as feedbacks and spillover e¤ects, and are used to build directed and undirected, as well as weighted and binary networks here. Despite its apparent simplicity, it has been suggested by [START_REF] Zhou | Granger Causality Network Reconstruction of Conductance-Based Integrate-and-Fire Neuronal Systems[END_REF] in integrate-and-…re neuronal systems (see also [START_REF] Winterhalder | Comparison of linear signal processing techniques to infer directed interactions in multivariate neural systems[END_REF] that Granger non-causality can capture non-linear relationships.

Once the topology is recovered, we …rst propose a period-speci…c analysis of the contagion process within the network while discriminating between crisis and non-crisis periods. We mainly show that the nodes' states are highly un- stable over time. Expanding on this idea, we identify phase transitions based on the very short-term dynamic di¤usion process of information/shocks accross nodes. Such nodes' short-term di¤usion processes are interpreted as signals.

Our dynamic signal analysis relies on a six-month rolling window, and focuses on triangular clustering patterns or motifs of information di¤usion as de…ned by [START_REF] Faggiolo | Clustering in complex directed networks[END_REF], including spillover and feedback e¤ects.

Considering daily data about ten main European stock indices form 1994 to 2014, our …ndings are manyfold: i) With respect to period-speci…c analysis, correlations prevail over the data sample and are regime-dependent. Such correlations increase up to the period following the crisis, and then start decreasing, ii) Besides, the number of causal relationships as well as their strength increases up to the crisis period but vanishes after the crisis period. Over the remaining sample history, there exist very few and very weak causal relationships, iii)

Based on a rolling window analysis, we …rst show that periods of clustering precede periods of ‡ickering in clustering, which are followed by a tipping point and a phase transition. The phase transition begins with an abrupt clustering phenomenon for all stock exchanges. Such sudden phenomenon indicates a simultaneous phase transition of all stock markets (i.e. synchronized clusters).

Interestingly, ‡ickering periods also highlight times when stock exchanges exhibit desynchronized information ‡ow processes. In particular, Euro zone stock exchanges exhibit clusters'desynchronization approximately one year before the Global Financial Crisis. At last, the end-of-crisis period exhibits an exceptional and speci…c clustering phenomenon, which is followed by the sudden disappearance of clusters. Hence European stock exchanges seem to stop interacting together. To our knowledge, we are the …rst to study clustering, or equivalently, information di¤usion patterns within causal networks. Clearly, ‡ickering in clustering as well as desynchronization in information transmission patterns could serve as early warnings indicators of phase transition on the market. This paper is structured as follows. Section 2 introduces the econometric methodology. Section 3 focuses on the statistical properties of the data and ) 0 ; t 2 Zg be a set of N log-returns of a main index of a stock-exchange, observed over T periods. Assume that each component of r admits a Generalized Auto-Regressive Conditional Heteroskedastic process (GARCH) representation (Bollerslev, 1986):

r (i) t p P l=1 (i) l r (i) t l c (i) = q h (i) t (i) t (1)
(i) t = q h (i) t (i) t (2)
h (i) t = ! (i) + (i) (i)2 t 1 + (i) h (i) t 1 (3)
(i) t iid(0; 1) (4)
Moreover, as T becomes large, consider that returns might also exhibit breaks in their volatility process. Then, de…ne a more realistic Data Generating Process (DGP) as:

r (i) t p P l=1 (i) l r (i) t l c (i) = q h (i) t (i) t ( 5
) (i) t = q h (i) t (i) t (6)
h (i) t = ! (i) st + (i) st (i)2 t 1 + (i) st h (i) t 1 ( 7
) (i) t iid(0; 1) (8)
Equation [START_REF] Billio | Econometric measures of connectedness and systemic risk in the …nance and insurance sector[END_REF] where

p ij = P [s t = jjs t 1 = i];
or by:

P C = 0 B B B B B B B B B @ p 11 1 p 11 0 0 0 0 p 22 1 p 22 0 0 0 0 0 p KK 1 p KK 0 0 0 0 1 1 C C C C C C C C C A :
where P S corresponds to a Markov switching process with K +1 regimes, and P C describes a change-point process with K breaks. Then, de…ne the estimated normalized return b

(i) t = ( b h (i) t ) 1=2 b (i)
t , i = 1; 2; :::; N: Next, we build binary and weighted undirected networks (BUN, WUN) as well as binary and weighted directed networks (BDN, WDN). A binary network is described by a graph G = (N; A), where N is the number of nodes, here the number of stocks, and A = fa ij g is the N N adjacency matrix. For binary networks, nodes i and j are connected by an edge if a ij = 1. For a graph G = (N; A), de…ne the indegree, outdegree and total degree for node i as:

d in i = X j6 =i a ji = (A 0 ) i 1 (9)
d out i = X j6 =i a ij = (A) i 1 (10)
d tot i = d in i + d out i = (A 0 + A) i 1 (11)
where A 0 is the transpose of A:

Also of interest are the bilateral edges between i and j, i.e. a ij = 1 and a ji = 1:

d $ i = X j6 =i a ij a ji = A 2 ii ( 12
)
The weighted networks parallel the binary one. They are de…ned by the graph G = (N; W) where W = fw ij g is a matrix of weights ranging from 0 to 1.

C (hh) b (0) = T 1 T X i=1 b (h) t b (h)0 t ; h = 1; 2 (13)
C (12) b (k) = 8 <
:

T 1 P T i=1 b (1) t b (2)0 t k 0 k T 1 T 1 P T i=1 b (1) t b (2)0 t k 1 T k 0: (14)
the correlations and cross-correlations are de…ned as:

R (hh) b (0) = fdiag C (hh) b (0)g 1=2 C (hh) b (0)fdiag C (hh) b (0)g 1=2 (15)
and:

R (12) b (k) = fdiag C (11) b (0)g 1=2 C (12) b (k)fdiag C (22) b (0)g 1=2 (16)
Then the null of non-correlation or independence can be tested using the portmanteau statistic:

Q M = T M P k= M T T jkj vec R (12) b (k) 0 R (22) b (0) R (11)
b (0)

1 vec R (12) b (k) (17)
Under the null of non-signi…cance of cross correlations at all leads and lags, Q M is distributed as a Chi-square with (2M + 1)d1d2 degrees of freedom.

Using the above statistic,Granger non-causality tests are easy to derive by summing over f1; M g or f M; 1g. For instance, testing for Granger noncausality from X (2) to X (1) (X (2) ; X (1) ) amounts to computing the test statistic:

Q + M = T M P k=1 T T k vec R (12) b (k) 0 R (22) b (0) R (11)
b (0)

1 vec R (12) b (k) (18)
Similarly, to test for non-causality from X (1) to X (2) (X (1) ; X (2) ), one is to use:

Q M = T M P k= 1 T T jkj vec R (12) b (k) 0 R (22) b (0) R (11)
b (0)

1 vec R (12) b (k) (19)
Under the null, both tests ( 18) and ( 19) are chi-square distributed with M d1d2 degrees of freedom.

All above tests are portmanteau tests. It is also useful to look at the significance of an individual lead/lag. A natural test statistic is given by:

Q(k) = T T T jkj vec R (12) b " (k) 0 R (22) b " (0) R (11) b " (0) 1 vec R (12) b " (k) (20)
which is also chi-square distributed with d1d2 degrees of freedom.

In this paper, to build BUN and WUN we use [START_REF] Geweke | Evaluating the accuracy of sampling-based approaches to the calculation of posterior moments[END_REF] with k = 0 and M = 7 and ( 20) with k = 0. Therefore, an edge exists between two nodes, if the test is rejected at the 5% threshold. For BDN and WDN we use ( 18), ( 19) and [START_REF] Koch | A method for testing the independence between two time series that accounts for a potential pattern in the crosscorrelation function[END_REF] with k 6 = 0; M = 7 (and M = 1 for 20), and this for each pair of the set b .

Data properties and orthogonalization

t g T t=1 . Doing this for each European stock index i = 1; 2; :::; N , we build a set of N = 10

orthogonalized series b " = f(b " (1)0 t ; b " (2)0 t ; :::; b " (N )0 t
) 0 ; t 2 Zg with regard to SP500 index. In the sequel, all tests are implemented on this set.

Period-based analysis

We …rst perform our analysis over 6 di¤erent periods given by Table [START_REF] Bak | Self-organized criticality: An explanation of the 1/f noise[END_REF]. As mentioned above, three kinds of networks can be built: i) Networks where nodes are connected if the null of independence is rejected at 5%, ii) Networks where nodes are connected if non-causality is rejected at 5%, also called functional connectivity, iii) Networks where nodes are connected if for a given lead/lag the null of non-signi…cance of the individual cross-correlation is rejected.

Please insert Table (3) about here

Results are summarized by both heatmaps and networks. To build heatmaps, we use both total degrees [START_REF] Dakos | Flickering as an early warning signal[END_REF] and weights. To compute weights ranging from 0 to 1 for a single node, and as all tests of connectivity are based on sums of individual (squared) cross-correlations or on individual cross-correlations at a given lag, we proceed as follows. For independence and non-causality tests and for each period, we divide the test statistics by the maximal value obtained over one period. For individual lags, we just take the absolute value of the cross-correlations. Focusing on degrees (upper panel), all stock exchanges are highly interconnected over the …rst 5 periods whereas, over the last period, Greece disconnects from the network of Euro zone stock exchanges. Moreover, the total degree slightly decreases (i.e. less interconnections) for all stock markets except for Ireland and Portugal. As regards strength (lower panel), which ranges from 0 to 9, the main striking feature is the abrupt change in the strength of dependence among stock exchanges after the post-crisis period. During the crisis, the strength of the network increases, remains high during the post-crisis period, and then seems to vanish. As a result, the closer we get to the crisis period, the more mutually dependent stock exchanges become, due to the increasing strength of their network. All stock exchanges being connected during the crisis, connections' strength reaches their highest level by that time. However, some stock exchanges start disconnecting after the crisis period. Furthermore, Greece exhibits a weak connection to the Euro zone network of stock exchanges. Thus, even if the Greek stock exchange is risky, its has a reduced impact on other Euro zone stock exchanges. Please insert here Figures [START_REF] Bak | Self-organized criticality: An explanation of the 1/f noise[END_REF] and ( 4)

The network representations corresponding to heatmaps in Figure ( 4) are illustrated by Figures [START_REF] Bauwens | Marginal likelihood for Markov-switching and change-point GARCH models[END_REF], ( 6) and [START_REF] Billio | Econometric measures of connectedness and systemic risk in the …nance and insurance sector[END_REF]. Corresponding network representations are provided for the six periods covering the data sample (see Table 3). Such …gures emphasize the evolution of the dynamic causal network of Euro zone stock exchanges over time. Speci…cally, the network's density increases up to the crisis period, diminishes during the post-crisis period, starts increasing during the sovereign debt crisis period, and then strongly drops over the post-sovereign debt crisis period. Over the last period of the sample, there are very few causal relationships between Euro zone stock exchanges. Moreover, previous …gures display incoming and outgoing connections between the network's nodes (i.e. between stock exchanges). Thus, we observe clearly the directional propagation of shocks across stock market places over time.

Please insert here Figures [START_REF] Bauwens | Marginal likelihood for Markov-switching and change-point GARCH models[END_REF], ( 6) and ( 7)

Flickering in information transmission

One major result of the previous section is that the topology of the network changes from one period to another. Speci…cally, information transmission channels within the network are unstable over time, which leads to complex patterns of transmitted and emitted signals. It is therefore of interest to focus on such an unstability in order to: i) Check if the evolution of certain patterns of information transmission match with the di¤erent phases of the …nancial market as reported in Table (3 We use a six-month rolling window, and focus on the very short-term (K 1) information di¤usion schemes, and in particular, on speci…c triangular patterns or motifs as de…ned by [START_REF] Faggiolo | Clustering in complex directed networks[END_REF]. Table [START_REF] Battiston | Default Cascades in Complex Networks: Topology and Systemic Risk[END_REF] introduces the de…nitions for four types of clustering coe¢ cients (C j i ; j = Cyc; Out; M id; In) as well as the total clustering coe¤cient (C D i ) for BDNs and WDNs. For a node i, the cycle pattern (Cyc) corresponds to feedback e¤ects and the out pattern (Out) to spillovers. In the middleman pattern (M id), the node i appears to be a relay in the information propagation (i.e. intermediate transmitter). In the in pattern (In) , the node receives information from its neighbors (i.e. receiver). Thus, all complex interactions are well captured by the various clustering coe¢ cients under consideration.

Results are displayed in Figures [START_REF] Bisias | A survey of systemic risk analytics[END_REF], [START_REF] Hong | Testing for independence between two covariance stationary time series[END_REF] and [START_REF] Dakos | Flickering as an early warning signal[END_REF]. Figure [START_REF] Bisias | A survey of systemic risk analytics[END_REF] plots the heatmap of total clustering for BDNs (upper panel), ranging from 0 to 1. This Figure also displays an indicator of crisis (grey) and non crisis (white) periods as mentionned in Table [START_REF] Bak | Self-organized criticality: An explanation of the 1/f noise[END_REF]. Such indicator is labelled 'Regimes'. For a comparison purpose, we also plot the time-path of the density of the network (lower panel). Figure [START_REF] Hong | Testing for independence between two covariance stationary time series[END_REF] plots heatmaps for each kind of triangular patterns for BDNs. At last, we average the total clustering coe¢ cients of WDNs over each rolling window (see Figure 11).

Interpreting clustering in dynamic networks as emitted or received signals, allows to study the whole dynamics of the system. The heatmap of total clustering (Figure 8) unveils key information. Starting from the Dot.com bubble, each return series, except for Greece, does exhibit very large periods of clustering with variable intensities. Then, around March 2001, clustering abruptly stops, and the system turns into a ‡ickering period so that some nodes alternate between clustering and non-clustering states. During such periods, each node ‡ickers between being in and out the information di¤usion process. At the same time, periods of clustering become shorter. In other words, the network's nodes continually become active or inactive, emphasizing that we face an ever-changing network [START_REF] Odum | Fundamentals of Ecology[END_REF] in terms of information transmission. This rapid alternation of states does precede a phase transition, the market entering then the pre-crisis period. The beginning of the transition is characterized by a sudden rise of clustering for all stock exchanges at nearly the 13 Documents de travail du Centre d'Economie de la Sorbonne -2016.46R (Version révisée) same time. Focusing on the pre-crisis period, similar patterns are found. From the beginning of the pre-crisis period to early 2005, the whole system exhibits a high degree of clustering, especially after 2004. Then, abruptly in early 2005, the system starts to ‡icker, alternating between clustering and non-clustering states. Such feature is also re ‡ected in the density of the network in early 2006, and more speci…cally in the average clustering coe¢ cient (Figure 11). Hence, compared to [START_REF] Billio | Econometric measures of connectedness and systemic risk in the …nance and insurance sector[END_REF], the relevant information, may not be the increase in degrees before a …nancial crisis, but rather the ‡ickering in degrees, which occurs after their increase (e.g. during the pre-crisis period).

Focusing on the Global Financial Crisis period, it is interesting to notice that it begins with an abrupt change in clustering (phase transition) for the whole system, and also ends with an abrupt change. Over the post crisis period, clustering totaly disappears, which is line with our previous causality tests.

Anecdotal results show that the sovereign debt crisis period begins and ends with a sudden rise in clustering. As a consequence, our methodology's added-values are twofold. First, we are able to detect forthcoming phase transitions, and second, we are able to date crises' beginnings and ends. Such dating matches with the di¤erent market phases reported in Table [START_REF] Bak | Self-organized criticality: An explanation of the 1/f noise[END_REF]. Therefore ‡ickering precedes a phase transition and acts as an early warning.

Flickering phenomena as early warning signals have been reported in complex systems, especially in ecology (e.g. [START_REF] Dakos | Flickering as an early warning signal[END_REF] as well as in climatology [START_REF] Livina | Potential analysis reveals changing number of climate states during the last 60 kyr[END_REF]. Interestingly, [START_REF] Dakos | Flickering as an early warning signal[END_REF] noticed that ‡ickering between basins of attraction may appear far before bifurcation or tipping points, and could then be used as early warnings. To our knowledge, this is the …rst time that ‡ickering in information di¤usion processes is studied, exhibited and described in …nancial systems.

In addition to rapid ‡ickering, before a tipping point occurs, the information di¤usion process starts desynchronizing accross nodes. We observe either asynchonicity of signals or arising noises within the system. To handle such pattern, we compute a dummy variable taking a unit value if the node enters total clustering, and 0 otherwise. Then, we divide the pre-crisis period into four equal sub-samples, and compute the Jaccard similarity coe¢ cient over each sub-sample to capture the transition from synchronicity to asynchronicity. The 14 Documents de travail du Centre d'Economie de la Sorbonne -2016.46R (Version révisée) Jaccard similarity coe¢ cient is a pairwise correlation index which checks for the similarity in the date of appearance of clusters. Corresponding results are displayed in Figure [START_REF] Duchesne | Robust tests of independence between two time series[END_REF]. The darker the color, the more synchronous the nodes become. Synchronization is strong over the two …rst sub-periods (except for Portugal), and then vanishes. Indeed, over the third sub-sample, the network starts desynchronizing. Over the fourth sub-period, there is a disconnection in the information transmission patterns, shown by a decrease of most pairwise correlations. However, the network still exhibits a weak synchronous core, which is composed of Germany, Italy, France and UK. Such feature suggests that, just before the Global Financial Crisis, we have a core network that remains weakly synchronized, and a periphery network, which is fully desynchronized.

Please insert Figure (8) about here

As a conclusion, shocks are continually di¤used and absorbed within the network a long time before the crisis occurs. All the system's components (i.e. stock exchanges) interact in a synchronous way. Di¤erently, before the crisis, shocks are di¤used and absorbed in a discontinuous and asynchronous manner by network's components. Information di¤usion patterns become intermittent (i.e. ‡ickering phenomenon), which announces a forthcoming phase transition (i.e. a crisis). The ‡ickering phenomenon appears approximately one year before the crisis. Therefore our results suggest that ‡ickering acts as an early warning signal, and the degree of desynchonization reveals the vicinity of the tipping point.

Please insert Figures [START_REF] Dakos | Flickering as an early warning signal[END_REF] [START_REF] Duchesne | Robust tests of independence between two time series[END_REF] [START_REF] Hong | Testing for independence between two covariance stationary time series[END_REF], and about here

Conclusion and discussion

In this paper, we have analyzed the dynamic relationships among ten European stock exchanges. We have focused on networks where two nodes are connected by functional or causal connectivity. Instantaneous correlations are also considered. Our major …ndings are manyfold. Using a period-based analysis, we have found that the network of Euro zone stock exchanges was unstable over time, 15 Documents de travail du Centre d'Economie de la Sorbonne -2016.46R (Version révisée) so that the number of connections and their related strength were highly timevarying. Strikingly, there remain very few causal relationships at the end of our data sample (i.e. post-sovereign debt crisis period), indicating that contagion over these recent years seems to be low. Such information is of huge signi…cance to the regulatory authority (e.g. monitoring and marking-to-market processes, assessment of risk exposures, gauging contagion risk). Expanding on the unstability of the topology, we have focused on motifs of information di¤usion processes (i.e. triangular clusters) in order to capture early warnings of phase transition. We have shown that the whole system exhibited ‡ickering information clusters with a high degree of desynchronization before a phase transition occurs. As a consequence, ‡ickering in information transmission can act as an early warning signal, and the degree of desynchonization reveals the vicinity of a tipping point. Our analysis, also allows to date crisis periods. To our knowledge, this is the …rst time that ‡ickering in clusters is identi…ed in complex …nancial systems. The ability to extract early warnings about forthcoming crises is useful to regulators in order to take preventive measures and mitigate contagion risk. Such tool could e¢ ciently help regulators undertake their monitoring and supervisory activities.

There is an avenue for future research within this area. One would consist in enlarging our dataset to include credit defaults swaps as well as bonds. Another direction could be to study cascading errors, and then relating our network to the riskiness of nodes.

d in i d out i d $ i C Cyc i = (W ) 3 ii d in i d out i d $ i Middleman C M id i = (AA 0 A)ii d in i d out i d $ i C M id i = (W W 0 W )ii d in i d out i d $ i In C In i = (A 0 A 2 )ii
d in i (d in i 1)
C In i = (W 0 W 2 )ii

d in i (d in i 1)
Out

C Out i = (A 2 A 0 )ii

2

  Documents de travail du Centre d'Economie de la Sorbonne -2016.46R (Version révisée) Furthermore, Hackett et al. (2011) and Payne et al. (2009) emphasize the importance of networks'topology while studying clustered and degree-correlated networks respectively.

(

  2012). Nevertheless, we use a di¤erent class of Granger non-causality tests, within the framework of independence tests for time series 1 . Such tests are performed on normalized innovations of Generalized Auto-Regressive Conditional Heteroskedastic (GARCH) models in which we allow the variance processes to have recurrent (Markov-Switching GARCH) or non-recurrent states or regimes (Changing-Point GARCH). To model series, we adopt the Bayesian Bauwens et al. (2014) methodology. Independence tests for time series are very versatile and provide a very rich information concerning instantaneous correlations,

1

  See Hong (1996),Duchesne and Roy (2001),[START_REF] Koch | A method for testing the independence between two time series that accounts for a potential pattern in the crosscorrelation function[END_REF], El Himdi and Roy (1997), Pham et al. (2001), Hallin and Saidi (2001) among others. 3 Documents de travail du Centre d'Economie de la Sorbonne -2016.46R (Version révisée)

4

  applies the Bauwens et al. (2014) methodology. Section 4 implements period-speci…c independence and non-causality tests on …ltered and orthogonalized data. Section 5 focuses on early warning indicators of crisis. Finally, Section 6 Documents de travail du Centre d'Economie de la Sorbonne -2016.46R (Version révisée)

6

  Documents de travail du Centre d'Economie de la Sorbonne -2016.46R (Version révisée) Then, replacing in (9) to (11) A by W one can focus on the strength of a node, and the strength of the net. To build BUN, WUN, BDN and WDN, i.e. to recover the topology of the network, we use non-correlation, or independence tests for time series. These tests are very versatile and are based on normalized residuals cross-correlations of models (1) or (5). They encompass several tests: i) Non-signi…cance of a crosscorrelation at a lag k = 0 or k 2 f1; M g, ii) Portmanteau test to check for overall independence, i.e. non-signi…cance of all leads and lags, iii) Portmanteau tests to check for non-causality in the Granger sense. Independence tests for time series have been introduced by Haugh (1976). They have been extended by Hong (1996), Duchesne and Roy (2003) or Koch and Yang (1986), this latter also taking into account patterns in cross-correlations. El Himdi and Roy (1997), Pham et al. (2001) or Hallin and Saidi (2001) among other present multivariate extensions. Also, El Himdi et al. (2003) propose a nonparametric test. In this paper we have used the El Himdi and Roy (1997), Hallin and Saidi (2001) and El Himdi et al. (2003) approaches, as well as several re…nements 2 . Having obtained very similar results, in the sequel, only the ones based on the El Himdi and Roy (1997) methodology are presented. Generally, let b (1) = fb

t ; t 2

 2 Zg and b(2) = fb

t ; t 2

 2 Zg be two sets of …ltered series using univariate or multivariate models, i.e. (normalized) residuals of models estimated independently with values in R d1 and R d2 . De…ne the covariances and cross-covariances C (hh) b (0) and C (12) b (k) as:

Figure ( 2 )

 2 Figure (2) displays the heatmaps resulting from independence tests for K = 7. Focusing on degrees (upper panel), all stock exchanges are highly intercon-

Figures ( 3 )

 3 Figures[START_REF] Bak | Self-organized criticality: An explanation of the 1/f noise[END_REF] and (4) provide a deeper analysis of the Euro zone network of stock exchanges while focusing solely on either non-correlation or non-causality tests. Focusing on non-correlation tests, Figure(3) provides a similar information as previous heatmaps because Euro zone stock exchanges are highly correlated. Speci…cally, all stock exchanges are strongly interrelated, and strength begins to increase before the Global Financial Crisis, being maximal during and just after the Global Financial Crisis. Such clustering phenomenon emphasizes the strong simultaneous and joint reaction of stock exchanges. However, there is an abrupt downturn in the network's strength after the post-crisis period so that some stock exchanges start disconnecting.As regards non-causality tests (K = 7), Figure[START_REF] Battiston | Default Cascades in Complex Networks: Topology and Systemic Risk[END_REF] provides key informations about both the reception (i.e. incoming information) and transmission (i.e. outgoing information) of …nancial shocks across stock market places. Before the Global Financial Crisis, the degrees of the network are quite high up to the crisis period, and then vanish. A similar result appears when one focuses on the strength of the network. Strikingly at the end of sample (over period

  ), ii) Determine early warning indicators, preceding tipping points or phase transitions. Please insert Table (4) about here 12 Documents de travail du Centre d'Economie de la Sorbonne -2016.46R (Version révisée)

  D i is the total number of triangular patterns that node i can form.

Figure 1 :

 1 Figure 1: SP500 square returns, and unconditional variance for a two-regime MS-GARCH process.

Figure 2 :

 2 Figure 2: Independence tests. Total degrees and total strength of the network.

Figure 3 :

 3 Figure 3: Instantaneous correlations. Total degrees and total strength of the network.

Figure 4 : 1 Period 2 Figure 5 :

 4125 Figure 4: Causality. Total degrees and total strength of the network.

Figure 6 :

 6 Figure 6: Network representation for periods 3 & 4.

Figure 7 :

 7 Figure 7: Network representations for periods 5 & 6.

Figure 8 :

 8 Figure 8: Total clustering. Six-month rolling window.

Figure 9 :

 9 Figure 9: Density of the network. Six-month rolling windows.

Figure 10 :

 10 Figure 10: Four di¤erent kinds of clustering.

Figure 11 :

 11 Figure 11: Average clustering coe¢ cient for WDNs and ‡ickering periods.

Figure 12 :

 12 Figure 12: Jaccard similarity coe¢ cients for four di¤erent (pre-crisis) subperiods.

Table (

 ( Zg corresponding to European stock exchanges, and b Bench = fb might be biased due to the omitted variable problem (i.e. spurious relationships, see e.g.[START_REF] Triacca | Non-causality: The role of the omitted variables[END_REF]. To tackle this issue, we consider the SP500 index as a central variable which in ‡uences all European exchanges. We then adopt the Duchesne and Nkwimi (2013) methodology to orthogonalize series with respect to the causal structure of another series. The orthogonalization method is a two-step procedure. First, we compute the cross-correlations between each component of b and b Bench . For each k 2 f0; :::; M g, we compute the test statistics[START_REF] Koch | A method for testing the independence between two time series that accounts for a potential pattern in the crosscorrelation function[END_REF] and keep the signi…cant lags. Then, we regress fb

	as U.S.A. (SP500 index return). The analysis is based on daily data spanning
	January 1998 to May 2014. Except for one return series, all series exhibit non-
	null skewness and excess kurtosis. Moreover, as expected, all series exhibit
	second-order dependence.
	Please insert Table (1) about here
	To test for breaks in volatility processes, and discriminate between recurrent (MS-GARCH) and non-recurrent (CP-GARCH) regimes, we follow Bauwens et (i) t=1 on the t g T signi…cant lags of fb (bench) t g T t=1 ,and keep the corresponding residuals fb "
	Please insert Figure (1) about here
	Using the above procedure, we build two sets of normalized residuals b =
	fb (1)0 t ; b (2)0 t ; :::; b (10)0 t Zg =f(( b h (11) t ) 1=2 b (11) ; t 2 Zg =f(( b h (1) t ) 1=2 b (1) t ) 0 ; (( b h (2) t ) 1=2 b (2) t ) 0 ; t 2 Zg corresponding to the SP500. Once data are (10) t ) 1=2 b (10) t (11)0 t ; t 2	) 0 ; t 2
	…ltered by the proper Data Generating Process, we further need to adress a
	key issue. To build networks, we use non-correlation and non-causality tests
	between each pair of nodes, i.e. between each pairs of b . Nevertheless, it is

1) displays benchmark stock market indices as well as related ARCH-LM test statistics for the ten European countries under consideration as well 8 Documents de travail du Centre d'Economie de la Sorbonne -2016.46R (Version révisée) al. (2014). The methodology on a Bayesian approach which combines sequential Monte Carlo (SMC) and Markov Chain Monte Carlo (MCMC) methods. For each model, we perform 10,000 particle Gibbs iterations. After convergence in the Geweke sense (Geweke, 1992), we then compute the marginal likelihood by bridge sampling (1,000 iterations). The number of particles is set to 150 for changing point models, and 250 for Markov Switching models. Finally, we select the model for which the marginal likelihood is maximal. Please, insert Table (2) about here Table (2) displays the results of the Bauwens et al. (2014) Bayesian procedure. Results support a no-break model for AEX and a two-break model (i.e. three non-recurrent states) for ASE. All other series exhibit a recurrent two-state Markov-Switching process (i.e. high and low volatility regimes). In the sequel, normalized residuals will be based on these models. With regard to SP500, our results are similar to Bauwens et al. (2014), as shown by Figure (1). t ) 0 ; :::; (( b h well known that in bivariate systems, non-causality and non-correlation tests 9 Documents de travail du Centre d'Economie de la Sorbonne -2016.46R (Version révisée)

Table 1 :

 1 Description and statistical properties of index returns

	Country	Index	Mean	Variance Skew. Kurt. ARCH(4)
	France	CAC40	0.0002	0.0002	0.05	4.29	469.06 (0)
	Netherland	AEX	0.0001	0.0002	-0.10	5.50	634.78 (0)
	Greece	ASE	0.00003	0.0003	-0.02	3.11	337.43 (0)
	Belgium	BEL20	0.0001	0.0001	0.05	5.63	555.97 (0)
	Germany	DAX	0.0002	0.0002	-0.05	3.83	524.29 (0)
	Italy	FTSEMIB 0.00005	0.0002	-0.12	3.88	512.71 (0)
	Spain	IBEX	0.0002	0.0002	0.00	4.19	482.80 (0)
	Ireland	ISEQ	0.0001	0.0002	-0.61	7.19	526.78 (0)
	Portugal	PSI	0.00005	0.0001	-0.27	7.02	301.96 (0)
	U.K.	UKX	0.0002	0.0001	-0.10	5.81	634.65 (0)
	USA	SP500	0.0002	0.0001	-0.20	6.58	745.58 (0)

Note: P-values are given between parentheses. ARCH-LM test is performed at lag 4. 20 Documents de travail du Centre d'Economie de la Sorbonne -2016.46R (Version révisée)

Table 2 :

 2 Marginal likelihoods

				Regimes
			1	2	3	4	5
	AEX	MS-GARCH	-6293.57 -6294.14	-6296.68
	AEX	CP-GARCH	-6293.57	-6298.78	-6297.46 -6302.92 -6307.9
	ASE	MS-GARCH	-7484.95	-7440.39	-7462.49
	ASE	CP-GARCH	-7484.96	-7464.58 -7437.97 -7437.66
	BEL20	MS-GARCH	-5855.88 -5845.54 -5859.66
	BEL20	CP-GARCH	-5855.88	-5856.19	-5855.08 -5854.99 -5857.82
	CAC40	MS-GARCH	-6575.57 -6570.94 -6576.87
	CAC40	CP-GARCH	-6575.58	-6579.27	-6579.17 -6576.07 -6582.44
	DAX	MS-GARCH	-6672.93 -6671.32 -6680.63
	DAX	CP-GARCH	-6672.93	-6677.58	-6681.49 -6684.95 -6688.8
	FTSEMIB MS-GARCH	-6587.34 -6579.35 -6587.89
	FTSEMIB CP-GARCH	-6587.34	-6586.1	-6579.63 -6579.42 -6589.55
	IBEX	MS-GARCH	-6678.06 -6669.91 -6675.54
	IBEX	CP-GARCH	-6678.15	-6679.26	-6673.07 -6675.38 -6681.4
	ISEQ	MS-GARCH	-6155.85 -6141.69 -6157.37
	ISEQ	CP-GARCH	-6155.83	-6155.25	-6155.85 -6145.67 -6156.4
	PSI	MS-GARCH	-5749.94 -5728.98 -5750.49
	PSI	CP-GARCH	-5749.93	-5747.45	-5732.02 -5736.89 -5731.67
	UKX	MS-GARCH	-5692.76 -5691.33 -5698.55
	UKX	CP-GARCH	-5692.75	-5691.44	-5694.12 -5697.48 -5698.27
	SP500	MS-GARCH	-5775.66 -5765.51 -5776.65
	SP500	CP-GARCH	-5775.66	-5777.91	-5771.92 -5767.62 -5768.15

Table 3 :

 3 Periods of the analysis Documents de travail du Centre d'Economie de la Sorbonne -2016.46R (Version révisée)

		Name	Dates
	1	Dot.com bubble	07JAN98-09OCT02
	2	Pre-crisis	10OCT02-02JUL07
	3	Crisis	03JUL07-01MAY09
	4	Post-crisis	02MAY09-30APR10
	5	Sovereign debt crisis	01MAY10-31MAR13
	6 Post-sovereign debt crisis 01APR13-20MAY14
		21

Table 4 :

 4 Patterns of triangles and clustering coe¢ cients (CC)

	Patterns	CCs for BDNs	CCs for WDNs
	Cycle	C Cyc i	=	(A) 3 ii

In particular, instead of cross correlations, we have also used partial cross-correlations and then used a LR test. All codes available at peretti@univ-paris1.fr

Documents de travail du Centre d'Economie de la Sorbonne -2016.46R (Version révisée)

Acknowledgement 1 The research leading to these results has received funding from the European Union Seventh Framework Programme (FP7-SSH/2007-2013) under grant agreement n 320270 SYRTO. This documents re ‡ects only the author's view. The European Union is not liable for any use that may be made of the information contained therein. This work was achieved through the Laboratory of Excellence on Financial Regulation (Labex ReFi) supported by PRES heSam under the reference ANR10LABX0095. It bene…ted from a French government support managed by the National Research Agency (ANR) within the project Investissements d'Avenir Paris Nouveaux Mondes (investments for the future Paris New Worlds) under the reference ANR11IDEX000602.