Bouchaib Azamir
email: abouchaibazamir@um5.ac.ma

Driss Bennis
email: bdriss.bennis@um5.ac.ma

Bertrand Michel
email: cbertrand.michel@ec-nantes.fr

A Simplified Algorithm for Identifying Abnormal Changes in Dynamic Networks

Keywords: 2010 Mathematics Subject Classification: 55N35, 55U99, 91B84 Key Words. Persistent homology, closeness centrality in a network, central subnetwork, time series

Topological data analysis has recently been applied to the study of dynamic networks. In this context, an algorithm was introduced and helps, among other things, to detect early warning signals of abnormal changes in the dynamic network under study. However, the complexity of this algorithm increases significantly once the database studied grows. In this paper, we propose a simplification of the algorithm without affecting its performance. We give various applications and simulations of the new algorithm on some weighted networks. The obtained results show clearly the efficiency of the introduced approach. Moreover, in some cases, the proposed algorithm makes it possible to highlight local information and sometimes early warning signals of local abnormal changes.

Introduction

A network is an efficient representation of a given set of entities and the existing relationships between them. Actually a network is a graph which entities are the vertices and the relations between them are presented as edges (see for instance [START_REF] Hewapathirana | Change detection in dynamic attributed networks[END_REF] and [START_REF] Jeanneau | Failure Detectors in Dynamic Distributed Systems[END_REF]). Usually, these relations are quantified by (mostly positive) real numbers and in this case we say that the graph (the network) is weighted. In most real-life situations, (weighted) networks evolve over time resulting in a family of (weighted) networks; we then speak of dynamic (weighted) networks (see the beginning of Section 3). In general, there are two kinds of dynamic networks :

• There are dynamic networks such that both the set of vertices and the set of edges are changing over time. For instance, chat groups in social networks where the members of these groups are undergoing changes from moment to moment.

• In some situations, the set of vertices remains unchanged over time as in the case of financial networks such as the weighted networks representing stock market transactions. So, the only changes occur at the level of the edges and at the level of the weights.

Dynamic networks have been subject of several studies. See for instance the papers and the references within [START_REF] Li | Optimal estimation of low-rank factors via feature level data fusion of multiplex signal systems[END_REF][START_REF] Li | Optimization of identifiability for efficient community detection[END_REF][START_REF] Li | Measuring the Network Vulnerability Based on Markov Criticality[END_REF][START_REF] Li | Fast markov clustering algorithm based on belief dynamics[END_REF][START_REF] Li | The dynamics of epidemic spreading on signed networks[END_REF] where dynamic networks have been studied following different approaches. In this paper, we are interested in studying the behaviour of dynamic weighted networks using topological data analysis (TDA). In [START_REF] Gidea | Topological Data Analysis of Critical Transitions in Financial Networks[END_REF], Gidea used TDA to detect the early signs of a financial market crisis. His method is based mainly on the fact that we can associate with any financial network of stocks a metric space whose distance is defined by the correlation coefficients of stock market returns. This allows to compute the so-called persistent homology of this metric space (see the preliminaries in Section 2) and, thanks to the concept of time series, the first signs of a critical transition in the financial network are detected. It is clear that Gidea's method can be applied on any other dynamic network. However, for large networks, the execution time of the algorithms used in Gidea's method will be very high. Thus, one can ask whether the fact of working on particular subgraphs rather than the whole network permits to achieve good results in a reasonable amount of time. Indeed, the abundance of real-world data and its velocity usually call for data summarization. Namely, graph summarization is a useful tool to help identify the structure and meaning of data. It has various advantages including reducing data volume and storage, speeding up algorithms and graph queries, eliminating noise, among others. There are different types of graph summaries depending on whether the data is homogeneous or heterogeneous and also whether the network is static or dynamic. In the literature, graph summarization methods use a set of basic techniques, here we are interested in those that are based on simplification or parsimony: these methods rationalize an input graph by removing nodes or edges less "important", resulting in a sparse graph see [START_REF] Liu | Graph summarization methods and applications: A survey[END_REF]. Here, the summary graph consists of a subset of the original nodes and/or edges. A representative work on node simplification-based summarization techniques is OntoVis [START_REF] Shen | Visual analysis of large heterogeneous social networks by semantic and structural abstraction[END_REF], a visual analysis tool for exploring and understanding large heterogeneous social networks. In [START_REF] Cheng-Te | Egocentric information abstraction for heterogeneous social networks[END_REF], the authors propose a four-step unsupervised algorithm for egocentric information abstraction of heterogeneous social networks using edge, instead of node, filtering. In [START_REF] Zhou | Network Simplification with Minimal Loss of Connectivity[END_REF], a new problem, to simplify weighted graphs by removing less important edges, has been proposed. Simplified graphs can be used to improve the visualization of a network, to extract its main structure, or as a preprocessing step for other data mining algorithms. Our approach is part of the simplification of graphs and aims to identify a subnetwork that contains a large part of the information embodied by the original network.

Our aim in this paper is to show that there are some subnetworks that can be good candidates for this study. Those subnetworks are extracted from the whole graph by eliminating some edges at certain threshold which is determined by the use of the closeness centrality concept (see Section 4 for the definition of closeness centrality). The idea is based on the fact that a node having the highest closeness centrality is able to spread information efficiently through the whole graph (see [START_REF] Opsahl | Node centrality in weighted networks, Generalizing degree and shortest paths[END_REF] for more details). Then, based on this fact, we propose that the desired subnetwork would be the one which contains this node called henceforth central node. After that, we need to set the threshold where edges with higher weights will be eliminated. Also, following the closeness centrality notion, the threshold will be chosen from the list of weights of the incident edges to the central node. However, it is not clear how to determine the optimal threshold. This is why we propose to focus our study on the three quartiles, the minimum and the maximum of the above proposed list of weights. The associated subnetworks will be called central subnetworks (see Section 4 for more details about centrality). Our aim is to determine what threshold levels provides good results. We will see throught several examples that when the threshold is greater than the third quartiles, the adopted approach reduces considerably the execution time of Gidea's method (to almost half in some cases) without compromising quality and results. Moreover, in some cases we get good results even with thresholds greater than the median. This paper is organized as follows:

Section 2 presents some preliminaries on persistent homology. We start this section with a part (Subsection 2.1) in which we present a short mathematical background that we need to understand the persistent homology associated to weighted graphs (given in Subsection 2.2), and we present also how to implement data to get persistence diagrams associated to weighted graphs (see Subsection 2.3).

In Section 3, we present how to associate persistent homology to dynamic networks (see Subsection 3.1) and show how it was used by Gidea to detect abnormal changes in financial networks (see Subsection 3.2).

Section 4 represents our approach to reduce the computation cost of Gidea's method (see Figure 5 for the flowchart of the proposed method). It is mainly based on a simplification of the whole studied network by considering what we called central subnetworks determined using the notion of closeness centrality (see Algorithm 1). We also describe how to get the persistence diagrams associated to these central subnetworks (see Algorithm 2).

Section 5 concerns the application phase. Namely, we present some numerical experiments in which we compare our method with existing ones. In each of the first three subsections, we simulate a dynamic network. Each subsection deals with a kind of a weighted network whose vertex point cloud is simulated with a given probability distribution. Then the corresponding central subnetworks are derived. A visual comparison between the time series associated to both the whole network and the central subnetwork shows that are very similar (see Figures in this section). This observation is also confirmed by the calculated R-squared coefficients (see Tables in this section). In parallel, we show that using our method the execution time is reduced considerably (see Tables in this section). We end Section 5 by a comparison a performance comparison between our approach and the edge collapse method (Subsection 5.4). It is known that the edge collapse method provides theoretical guarantees and allows to obtain, in output, the same starting persistence diagram (see for instance [START_REF] Jean-Daniel | Edge Collapse and Persistence of Flag Complexes[END_REF]). From Table 4, we deduce that our method is more practical for large and dense networks.

We end this article with Section 6 which includes an application of the method on real weighted networks. In Subsection 6.1, we apply on the financial network used by Gidea [START_REF] Gidea | Topological Data Analysis of Critical Transitions in Financial Networks[END_REF], and in Subsection 7 we consider a cryptocurrency network. As in Section 5, we deduce an improvement of the execution time using the new method.

Persistent homology computed on graphs

Persistent homology is an emergent method for detecting geometrical and topological properties of a space endowed with a topological structure. The concept of persistence was first introduced by Edelsbrunner, Letscher and Zomorodian in [START_REF] Edelsbrunner | Topological persistence and simplification[END_REF] and then refined by Carlsson and Zomorodian in [START_REF] Carlsson | Computing Persistent Homology[END_REF]. Since then, persistent homology has become an essential tool in topological Data Analysis (TDA) and has been applied in various scientific fields such as biology, image processing, sensor networks etc. Nowadays, there are many references (surveys, books and notes) on TDA; for a recent one we refer to [START_REF] Chazal | Fundamental and practical aspects for data scientists[END_REF].

In this section, we give a short presentation on some basic notions concerning particular simplicial complexes as well as its corresponding persistent homology. We will focus, following our context, on simplicial complexes associated to graphs investigated in [START_REF] Bergomi | Topological graph persistence[END_REF]. For a general background on persistent homology one can see [START_REF] Carlsson | Computing Persistent Homology[END_REF][START_REF] Chazal | Fundamental and practical aspects for data scientists[END_REF][START_REF] Edelsbrunner | Computational Topology -An introduction[END_REF][START_REF] Ghrist | Barcodes: the persistent topology of data[END_REF]].

Simplicial complex and simplicial homology groups

We start this subsection with a recall of a simplicial complex and then we give the examples of interest.

Given a finite set V , a simplicial complex with the vertex set V is a set K of finite subsets of V such that the elements of V belong to K and for any σ ∈ K, any subset of σ belongs to K. The elements of K are called the faces or the simplices of K. The dimension of a simplex of K is just its cardinality minus 1 and the dimension of the simplicial complex K is the largest dimension of its simplices [START_REF] Chazal | Fundamental and practical aspects for data scientists[END_REF].

There are a lot of examples of simplicial complexes arising from various contexts. Here, we use the following ones:

Example 2.1 (Simplicial clique complex, [START_REF] Bergomi | Topological graph persistence[END_REF]) Let G = (V, E) be a graph, where V is the set of vertices and E the set of edges. For a positive integer k, a k-clique of G is a set of k vertices whose the induced subgraph is complete. Denote by Cl(G) the set of all the cliques of G. Notice that the set Cl(G) satisfies the two conditions :

• Cl(G) contains all singletons {v} with v ∈ V . • Cl(G) is closed under subsets: if τ ⊆ σ and σ ∈ Cl(G), then τ ∈ Cl(G).
Then, Cl(G) is a simplicial complex which is called a simplicial clique complex of G.

The following (geometric) classical example of simplicial complexes can be found in any introductory books on TDA.

Example 2.2 (Vietoris-Rips complex) Given a finite set of points X in a metric space (M, d) and a real number α ≥ 0. The Vietoris-Rips complex Rips α (X) is a simplicial complex whose simplices are sets {x0, . . . , x k } such that d(xi, xj) ≤ α for all 0 ≤ i, j ≤ k. Now we are ready to recall what are simplicial homology groups of a simplicial complex. To this end, we define some vector spaces and linear maps. Here, we only deal with vector spaces on the field F2 := Z/2Z. Given a simplicial complex K, the vector space generated by the p-simplices of K is denoted by Cp(K). It consists of all finite formal sums of p-simplices called p-chains; i.e., an element c belongs to Cp(K) if it can be written as follows: c = j γjσj for some scalers γj ∈ F2 and a family (σj)j of p-simplices.

For a positive integer p, consider the linear map ∂p : Cp(K) → Cp-1(K), called boundary map, defined on p-simplices as follows: For every p-simplex σ, ∂(σ) is the formal sum of the (p -1)dimensional faces (i.e., subsets of σ of cardinal p). An element of the image of ∂p is called a boundary. Thus, the boundary ∂p(c) of a chain c = j γjσj is obtained by extending ∂p linearly; i.e., ∂p(c) = j γj∂p(σj). The p-chains that have boundary 0 are called p-cycles. They form a subspace Zp of Cp. The p-chains which are the boundary of (p + 1)-chains are called p-boundaries and form a subspace Bp of Cp. It is important but not difficult to show that ∂p • ∂p+1 = 0 which is equivalent to Bp ⊆ Zp. Then, if we consider the quotient vector space Zp/Bp, that means we have annihilated the p-boundaries which are not p-cycles. For instance, if we take K to be Cl(G), the simplicial clique complex of a graph G, the dimension of the vector space B1/Z1 will be exactly the number of "holes" in G and the dimension of the vector space B0/Z0 is the number of the connected components of Cl(G) (i.e., the connected components of the graph (network) G). For this reason and of course other important ones, the vector space Bp/Zp is considered as one of the principal notions in algebraic topology that helps in describing topological features. It is denoted by Hp(K) and usually called the p th simplicial homology group of K. Its elements are called homology classes.

Persistence diagrams

When a simplicial complex K has a history in the sense that it is an union of a chain of simplicial complexes, we can capture more information on K; especially, the behaviour of homology groups of these complexes can be used as a signature of the complex K that can be used to distinguish it from other complexes. This is one of many important things that persistent homology is performing.

Consider the following chain of simplicial subcomplexes of a complex K, called a filtration of K:

∅ ⊆ K0 ⊆ K1 ⊆ • • • ⊆ Kp = K
This filtration provides more information on K in the following sense: for every couple i, j such that 0 ≤ i ≤ j ≤ p, the injection Ki → Kj induces a homomorphism on the n th simplicial homology groups for each dimension:

f i,j n : Hn(Ki) → Hn(Kj). The n th persistent Betti number β i,j n is the rank of the vector space Im(f i,j n ); that is, β i,j n = dim(Im(f i,j n ))
. Persistent Betti numbers count how many homology classes of dimension n that survive during the passage from Ki to Kj. We say that a homology class α ∈ Hn(Ki) is born entering in Ki, if α does not come from a previous subcomplex; that is, α /

∈ Im(f i-1,i n ).
Similarly, if α is born in Ki, it dies entering Kj if the image of the map induced by Ki-1 ⊆ Kj-1 does not contain the image of α but the image of the map induced by Ki-1 ⊆ Kj does. In this case the persistence of α is j -i. Finally, all the collected data of births and deaths are presented in a diagram which is the multi-set of points with coordinates correspond respectively to the birth time and the death time of homology classes. This diagram is called an n-dimensional persistence diagram, or simply a persistence diagram, of K. As a simple example, the filtration represented in Figure 2 Certainly, the persistence diagram of K reveals more information on it than those extracted from the (static) complex K. Moreover, persistence diagrams can be used to compute the degree of similarity between complexes. To this end, some metric distances are introduced on the space of persistence diagrams. In this paper, we use the so called p-Wasserstein distance (for a positive integer p). It is defined by the formula:

Wp(∆1, ∆2) = inf φ [ q∈∆ 1 q -φ(q) ] 1/p
where ∆1 and ∆2 are two diagrams and φ varies across all one-to-one and onto functions from ∆1 to ∆2. In this paper we use just the 2-Wasserstein distance. Now, to apply the concept above on graph, the notion of weight functions is used as follows: Let G = (V, E, ω) be a weighted graphs, where V is the set of vertices and E the set of edges, such that the weight function ω : E → R + is assumed to be upper bounded by a positive real number m. Let K = Cl(G) be the clique complex of G. We would like to construct a filtration of K (i.e., a chain of complexes that covers K). To do so, let us consider, for every a ∈ R + , the sublevel set E(a) = ω -1 ((-∞, a]) and the associated subgraph G(a) of G which will be called the subgraph of G at the threshold a. Then, we consider the associated clique complex K(a) at the a th level. In particular, K(m) = K. Now, for a sequence a0 < a1 < • • • < ap = m of real numbers, we get a filtration of K (called Rips filtration):

∅ ⊆ K0 ⊆ K1 ⊆ • • • ⊆ Kp = K
where Ki = K(ai). Therefore, the persistent homology, described above, applied on this filtration provides more information on the graph G as we will deduce throughout this paper.

Implementation

Nowadays, there are various softwares for computations of persistent homology and corresponding information. In this article, we often use the R package TDA (for a short tutorial and introduction on the use of the R package TDA, see [START_REF] Fasy | Introduction to the R package TDA[END_REF]), except in Subsection 5.4 where we use also the Gudhi library 1 . We will also use the R software for computations corresponding the time series (see for instance [START_REF] Chatfield | The Analysis of Time Series[END_REF]).

In this subsection, we present how to implement the method described in Subsection 2.2 in order to get the persistence diagram of a weighted graph. It should be noted that the existing software implements data from a metric space. Thus, in order to implement the method described in Subsection 2.2, we need a distance between nodes. The weight function can be used to this end (see Subsection 3.2). So here we assume that the weight function defines a distance between nodes. In other words, the graph with the weight function is a metric space. In this case, the associated clique complexes are nothing but the Vietoris-Rips complexes. Now, the implementation which provides persistence diagrams of a weighted graph, as it is conceived, deals with matrices of distances associated to a metric space. These matrices are, in our context, matrices of weighted complete graphs. Then, given a weighted complete graph G, one can determine its persistence diagram by using the Rips filtration method such that the max-scale of the filtration is the maximum of the weights.

It is also possible to compute the persistence diagram of a not necessary complete graph. Let G = (V, E, ω) be a weighted graph, where V and E are the sets of vertices and edges, respectively, and ω : E → R + is a weight function assumed to be upper bounded by a positive real number m. The data of this graph can be represented in a square matrix W = (Wi,j) such that Wi,j = ω(i, j) if (i, j) ∈ E and Wi,j = m + 1 otherwise. This approach is adopted to not take in consideration the non connected vertices in the filtration process since the corresponding sequence of real numbers, as explained in Subsection 2.2, ends at m. Notice that if one would like to determine the persistence diagram of G(s), the subgraph of G at a threshold s strictly less than m, we consider the matrix W = ( Wi,j) such that Wi,j = Wi,j if Wi,j ≤ s and Wi,j = m + 1 otherwise.

Persistent homology of dynamic networks

In this section, we present how to associate persistent homology to dynamic networks and show how it was used by Gidea to detect abnormal changes in financial networks.

Description of the method

First, we recall what is a dynamic network. As concluded in [17, Section 2.4], there is no consensual formal definition of a dynamic network. Some papers define a dynamic system as a distributed system in which the communication graph evolves over time, while others define it as a model where processes can join and leave the system during a run. Some articles mix both of those proposals in the same model ( [START_REF] Jeanneau | Failure Detectors in Dynamic Distributed Systems[END_REF]). As presented in [START_REF] Hewapathirana | Change detection in dynamic attributed networks[END_REF]: a (discrete) dynamic weighted network can be mathematically represented as a time sequence of weighted graphs, (Gt = (Vt, Et, ωt)) t∈N , where Vt and Et are the set of vertices and the set of edges, respectively, and ωt : Et → R + is a weight function at time t. If the set of vertices remains unchanged over time; that is, Vt = V for all t, then the weighted graph at any time t will be simply Gt = (V, Et, ωt). In this case, a dynamic weighted network can be encoded as a weighted matrix, W (t) = (Wi,j(t)), where Wi,j(t) is the weight of the edge between vertices i and j at time t. Now, by applying the method described in Subsection 2.2 on each weighted graph Gt, we end up with a times series of persistence diagrams (∆t)t. To induce a scalar time series from (∆t)t, we consider a fixed persistence diagram ∆, then the 2-Wasserstein distances, W2(∆, ∆t), between the persistence diagrams ∆t and ∆, give rise to a (scalar) time series. This time series makes it possible to detect abnormal changes within the dynamic network. This idea was used by Gidea in [START_REF] Gidea | Topological Data Analysis of Critical Transitions in Financial Networks[END_REF] to detect abnormal changes in a financial network. The following subsection presents briefly Gidea's work.

Gidea's application

The dynamic weighted network studied by Gidea in [START_REF] Gidea | Topological Data Analysis of Critical Transitions in Financial Networks[END_REF] was a financial network with a weight function defined via correlations between nodes (stocks) as follows: For each stock i and a day t, xi(t) is the daily returns based on the adjusted closing prices Si(t); i.e., xi(t) = S i (t+1)-S i (t)

S i (t)
. Let xi(t) be the arithmetic return of a stock i at time t. The correlation coefficient between nodes i and j over a time interval of the form [t -T, T ], where T > 0, is defined by:

Ci,j(t) := T τ =t-T (xi(τ ) -xi)(xj(τ ) -xj) T τ =t-T (xi(τ ) -xi) 2 T τ =t-T (xj(τ ) -xj) 2
where xi and xj denote the averages of xj and xj, respectively, over the time interval [t -T, T ]. Then, following [27, Section 13.1], d(i, j)(t) = 2(1 -Ci,j(t)) is a distance function between nodes i and j. Notice that the values taken by the distance d vary between 0 and 2; especially, if two nodes i and j are perfectly correlated we have d(i, j)(t) = 0, while d(i, j)(t) = 2 when they are perfectly anti-correlated. With d, this network is a metric space and so it can be seen as a time evolving weighted network; i.e., as a graph G(V, E) with the set V of nodes representing the collection of stocks and the weight function ωt (at a time t) from the set of edges E into [0, ∞) defined by ωt(e) = d(i, j)(t) for every edge e. Thus, we can generate the associated persistence diagram ∆t (at a time t) as described in Section 2. We know that the set of these persistence diagrams is endowed with the 2-Wasserstein distance. We fix a persistence diagram ∆t 0 at an initial time t0, then the behaviour of the time series (Xt)t := (W2(∆t, ∆t 0 ))t will translate the (topological) changes in the studied financial network. In particular, it could help in detecting a change prior to the critical transition (i.e., the peak of the crisis), meaning that the stock correlation network undergoes significant changes in its topological structure.

In [START_REF] Gidea | Topological Data Analysis of Critical Transitions in Financial Networks[END_REF], Gidea applied his method on the network derived from the DJIA stocks listed as of February 19, 2008, and the data considered corresponds to the period between January 2004 and September 2008. The corresponding graphical representation of the time series (Xt)t is presented in Figure 4. One can notice from Figure 4, as Gidea concluded in [START_REF] Gidea | Topological Data Analysis of Critical Transitions in Financial Networks[END_REF], that the obtained time series shows significant changes in the topology of the correlation network in the period prior to the onset of the 2007-2008 financial crisis (see [START_REF] Gidea | Topological Data Analysis of Critical Transitions in Financial Networks[END_REF]).

When the network is large, as for instance with social networks, dealing with the entire network lead to a very high computational burden. It is therefore important to find a way to significantly reduce the execution time of the above method without deteriorating its performance. To this end, we propose a simplified method based on the closeness centrality notion.

Persistent homology of dynamic central subnetworks

In order to reduce the computation cost of Gidea's method, one could think of considering a particular subnetwork rather than the whole network. But, to keep similar performance as with the initial method, the chosen subnetwork has to "summarize" as well as possible the global network. Our aim is to show that the notion of closeness centrality can help in determining suitable subnetworks which we call central subnetworks.

In this section, we start by explaining how the closeness centrality can be used to determine the desired central subnetwork. We will give an algorithm which details the different steps of extracting the central subnetwork from the whole network. Then, we show how to get persistence diagrams of dynamic central subnetworks.

Recall that the closeness centrality of a node i in a weighted network G(V, E, ω), with the weighted matrix W = (ω(i, j)), is the following quantity:

C ω c (i) = 1 j δ(i, j)
where δ(i, j) = min( 1 ω(i, h)

+ • • • + 1 ω(h, j)
)

such that h are intermediary nodes on paths between i and j (see [START_REF] Opsahl | Node centrality in weighted networks, Generalizing degree and shortest paths[END_REF] for more details). The closeness centrality of a graph helps in detecting nodes that are able to spread information efficiently through the whole graph. Then, based on this fact, we propose that the central subnetwork would be the one which contains a node having the highest closeness centrality. This node will be called central.

For practical implementation, we propose to chose the desired central subgraph from the subgraphs G(s) defined in Subsection 2.2. Recall that G(s) is the subgraph resulting from the sublevel set ω -1 ((-∞, s]) of the weight function ω at a threshold s. Therefore, in order to ensure that the central node is present in the central subgraph, the thresholds s will be chosen among the weights of the edges incident to the chosen central node. Thus, once a threshold s is adopted, one can implement the above method, using the matrices W = (Wi,j) and W = ( Wi,j), as explained at the end of Subsection 2.3. Notice that the list of weights of the edges incident to the chosen central node form exactly the line of the weighted matrix W corresponding to the central node. This row, seen as a statistical series, will be sorted in ascending order. Clearly, its smallest element is always zero, so it will be not considered and the resulting ordered statistical series will be denoted by Uc. Then, the choice of the threshold is determined by the choice of its rank in Uc which will be called the threshold rank. Therefore, the algorithm representing the steps of constructing the weighted matrix W of the central subnetwork from the matrix W of the whole network is given in Algorithm 1.

Algorithm 1 Construct the matrix W Require: Weighted matrix W = (W i,j ), threshold rank r and the maximum value of weights m. Ensure: W = ( W i,j ) The weighted matrix of the central subnetwork 1. Compute the closeness centrality of all nodes.

2. Determine a central node c of the graph G.

3. Extract the row u c = (W c,j ) j . 4. Induce the vector U c = (W c,j ) j =c . 5. Compute the threshold s of rank r in the vector U c . 6.

W ← W for 0 ≤ i, j ≤ n -1 do if W i,j ≥ s then W i,j ← m + 1 else W i,j ← W i,

Algorithm 2 The time series of 2-Wasserstein distances

Require: The matrix W t obtained using Algorithm 1 for each time t, set a reference time t 0 . Ensure: The time series ( X t ) t := (W 2 ( ∆ t , ∆ t0 )) t between each persistence diagram ∆ t and the persistence diagram ∆ t0 at the time t 0 1. Using Rips filtration, create the persistence diagram ∆ t of each time t associated to the matrix W t . 2. Compute the 2-Wasserstein distances ( X t ) t .

The flowchart of the proposed method is given in Figure 5.

It is clear that our method is mainly based on the choice of the adequate threshold. To get clear idea about the effectiveness of the choice of threshold that provides good results, we will implement the method for various threshold values. We will focus on five threshold values corresponding to remarkable ranks. Explicitly, we exploit the following cases:

• Min threshold: The first threshold, s0, will be the minimum value of the statistical series Uc.

• Q1 threshold: s1 will be the first quartile of Uc.

• Q2 threshold: s2 will be the second quartile (median) of Uc.

• Q3 threshold: s3 will be the third quartile of the statistical series Uc.

• Max threshold: s4 will be de the maximum value of the statistical series Uc.

Numerical experiments

In this section, we apply our method described in Section 4 to various simulated dynamic networks. We study in each example from which threshold we obtain a good simplification of the whole graphs while maintaining the global observations that we can obtain from the associated time series. For the latter, in addition to a visual comparison between the studied time series charts of (Xt)t and ( Xt)t, we use the adjusted R-squared. In fact, the reason behind using the adjusted R-squared is based on several observations which indicate that there is some linearity between the studied time series. This hypothesis is confirmed through various examples.

First experiment: dynamic network with a fixed central node

For this first experiment, we propose to study a dynamic network with 100 networks of 51 nodes and having the same central node.

Description: As we know, a weighted network is represented by weighted matrix. Then, to simulate a dynamic network with 100 networks, we simulate 100 square weighted matrices of order 51. In this experiment we propose to fix the central node in all networks of the studied dynamic network. To do so, each matrix (representing a weighted network) will be obtained as follows:

• First, we simulate 50 vectors of length 10 as realizations of a reduced centred normal distribution.

• To isolate the fixed central node during all 100 networks, we take the 51 st vector as sum of the other 50 vectors.

• We then compute the correlation matrix (ci,j) between these vectors.

• Finally, the desired weighted matrix is the distance matrix (di,j), where di,j = 2(1 -ci,j).

Over the 100 networks, the 51 st node is always the central node, it is thus considered to compute the thresholds s0 to s4 as explained at the end of Section 4.

Next, from each square weighted matrix, we derive its persistence diagram of 0-dimensional features. At the end, we compute the times series (Xt)t of the 2-Wasserstein distances between all the obtained 0-dimensional persistence diagrams and a fixed 0-dimensional persistence diagram.

The graphical representation of this time series is displayed in Figure 6. Now, to see the efficiency of our approach described in Section 4, we compute, at each of the five thresholds proposed at the end of Section 4, the time series ( Xt)t associated to the central subnetworks (see Figures 6 to 11). via the adjusted R-squared values in the third column 3 of Table 1. But, this is not the case at the threshold s0 (see Figure 11). Namely, the adjusted R-square coefficient at this threshold is 0.002. Now, to compare the execution time of each method, we compute the time ratio between them; i.e., the execution time of our algorithm over the execution time of Gidea's one (see the second column in Table 1). We can deduce that the execution time is considerably reduced using our algorithm, namely for the thresholds s1, s2 and s3. Notice that the average percentage of pruned edges, at each threshold, is presented in the fourth column of Table 1. Naturally, this average percentage increases when the threshold decreases.

Second experiment: dynamic network constructed from random covariance matrices

In this subsection, we will simulate a dynamic network of 150 networks, where each network has 60 nodes, by the use of generated covariance matrices.

Description: We generate 60 vectors of length 10, each one is simulated from a multivariate normal distribution with zero mean and a covariance matrix generated, as in [START_REF] Joe | Generating Random Correlation Matrices Based on Partial Correlations[END_REF], by the use of linearly transformed Beta(α, α) distribution on the interval (-1, 1)2 . Next, we compute the weighted matrix (di,j) as in Subsection 5.1. This way we end up with a network of 60 nodes. By repeating this operation 150 times, each time with a different generated covariance matrix, we built a dynamic network. This is still a naive dynamic network because the graphs are simulated independently for this experiment.

The time series chart is displayed in Figure 12. Now, we compute, at each of the five thresholds proposed in Section 4, the time series ( Xt)t associated to the central subnetworks (see Figures 13 to 17). As in Subsection 5.1, we calculate time ratios, adjusted R-squared values and the average percentages of pruned edges (see Table 2). Comment: Although there is no strong central node in the simulated networks for this experiment, we still observe a good fitting of ( Xt)t on (Xt)t, as well a significant improvement in terms of execution time, in particular with the small thresholds s1 and s2.

Third experiment: a simulated dynamic network using the central normal law and an AR(1) process

In order to test the performance of the method on different sizes of dynamic networks, in this third experiment, we will consider 200 nodes per network. Also, to diversify the simulation methods, we follow a new way to construct the studied dynamic network.

Description: This experiment consists of 200 weighted matrices, each one of dimension 200 × 200, derived from the simulation of 200 vectors of length 20. The ten first components of each vector are realizations of the reduced centred normal distribution law. The last ten components of each vector come from the AR(1) stationary autoregressive model yt = 0.7 × yt-1 + t, where t is a white noise (see [START_REF] Chatfield | The Analysis of Time Series[END_REF]). Now, after calculating weighted matrices, as in the description of Experiment 1, we end up with a dynamic network.

The graphical representation of the time series (Xt)t, and the one of the central subnetworks ( Xt)t, at the studied thresholds, are shown in Figures 18 to 23.

Also, we calculate time ratios, adjusted R-squared values and the average percentages of pruned edges (see Table 3).

Threshold Time ratio Adjusted R-squared s 4 0.95 0.9967 s 3 0.3 0.9998 s 2 0.17 0.9997 s 1 0.12 0.9997 Table 3: Execution time ratios, adjusted R-squared and average percentages of pruned edges for the third experiment.

Comparison with edge collapse method

Recall that the edge collapse algorithm reduces a flag complex to a simpler one with the same persistent homology (see for instance [START_REF] Jean-Daniel | Edge Collapse and Persistence of Flag Complexes[END_REF]). This method must be applied on the 1-skeleton (graph) of a flag or a clique complex (the same used in our context). So, naturally one could ask for a comparison between this method and ours. This subsection is devoted to the performance comparison between our approach and the edge collapse method, in terms of cost in execution time 3 . For this, we apply the edge collapse method as well as our algorithm on different examples of networks used in this paper. Namely, we use examples of weighted networks issued, respectively, from the dynamic networks of Experiments 1, 2 and 3. We use also a weighted network issued from the dynamic network in Gidea's application (see Subsection 3.2) and a new network with 250 nodes simulated in the same way as the networks in the second experiment.

The results are displayed in Table 4.

Comment: From Table 4, we see that, for Experience 1 (51 nodes) and Experience 2 (60 nodes), the edge collapse method is faster than ours at the thresholds s4 and s3 while it is not the case at the thresholds s2 and s1. Moreover, our method shows a better execution time for the 200 node graph.

Following these observations, it appears that the edge collapse method is more efficient as soon as the number of nodes is small. This is confirmed by the data in the first row of from the networks used in Subsection 3.2.

However, as soon as the number of edges is larger it appears that our method is faster. To confirm this observation, we simulate a network with 250 nodes as in the second experiment (see Subsection 5.2). Therefore, the results of the application presented in the last row of Table 4 confirm the assumption.

Finally, besides comparing the two methods in terms of execution time, it should be noted that the edge collapse method provides theoretical guarantees and allows to obtain, in output, the same starting persistence diagram.

Application on dynamic real data networks

In this section, we evaluate our method on two real data networks.

Dynamic network derived from the DJIA stocks

In Subsection 3.2, we recalled how Gidea used topological data analysis to study a financial network. Here, we show how our method performs faster than Gidea's one without compromising quality and results.

Thus, we apply our method, at the proposed thresholds, on the network derived from the DJIA stocks described in Subsection 3.2. The charts of these time series are given in Figures 25 to 29. The chart of the time series (Xt)t for the DJIA stocks data given in Figure 4 is put next to the new ones (in Figure 24) for easy visual comparison.

We can see that the early signs of a financial market crisis in the time series (Xt)t corresponding to the whole network is retained at the same period in the new time series ( Xt)t at the thresholds s1, s2, s3 and s4. In fact, at these thresholds, one can observe that the time series ( Xt)t and (Xt)t behave similarly, as confirmed by the adjusted R-squared value (see Table 5), although we have pruned a significant number of edges from the whole network (see the third column of Table 5). Table 6 gives the time ratio corresponding to the proportion of the execution time of our approach over the execution time of Gidea's one. Our approach reduced the execution time by 21%, 61%, 72% and 74% at thresholds s4, s3, s2 and s1 respectively. However, when we consider the threshold s0 (see the graph in Figure 29), one can notice that the time series ( Xt)t and (Xt)t are clearly different, as confirmed by the value of the adjusted R-squared in the linear regression of the times series ( Xt)t on (Xt)t which is 0.45. Nevertheless, the slight deviation in the behaviour of the time series on the s0 scale could reveal topological properties of the network at the local level which are not detected by the global network.

In conclusion, based in the above observations, the optimal threshold of our method lies between the first and the third quadrant of the statistical series of weights of the edges incident to the central node.

Cryptocurrency dynamic network

Cryptocurrency dynamic networks have been a subject of studies of several works (see for instance [START_REF] Gidea | Topological recognition of critical transitions in time series of cryptocurrencies[END_REF][START_REF] Ismail | Detecting Early Warning Signals of Major Financial Crashes in Bitcoin Using Persistent Homology[END_REF][START_REF] Saengduean | Topological Data Analysis for Identifying Critical Transitions in Cryptocurrency Time Seriesy[END_REF]). Here, we are interested in a dynamic network constructed from the multivariate time series of the closing prices of the four cryptocurrencies Bitcoin, Ethereum, Litecoin and Ripple, from August 24, 2016 to February 19, 2020 4 . The dynamic network is constructed, following [START_REF] Ismail | Detecting Early Warning Signals of Major Financial Crashes in Bitcoin Using Persistent Homology[END_REF], as follows: Let ci(t) be the closing price of the i-th cryptocurrency at the trading day t. The Logreturn ri,t at the trading day t is defined as ln( c i (t) c i (t-1) ) for i = 1, 2, 3, 4 and t = 1, ..., 1274. Each trading day t is mapped to the point xt = (r1,t, r2,t, r3,t, r4,t) ∈ R 4 . We end up with the point cloud X = {xt} t=1274 t=1 embedded in R 4 . Now, applying a sliding window of size w = 50 to the point cloud X, we obtain 1225 time varying point clouds X(t) = {xt-49, ..., xt} t=1274 t=50 . Therefore, the desired weighted dynamic network is (X(t))t endowed with the weight function defined in Subsection 3.2. Now for each point cloud X(t), we compute the persistent homology of its Rips filtration and derive the corresponding persistence diagram. Subsequently, the time series of the 2-Wasserstein distances between all the persistence diagrams and a fixed one are calculated. The time series chart is given in Figure 30. This time series shows two periods of behavioural change. The first period was marked by a first peak recorded on September 14, 2018, followed by a near-recession before declining again on November 1, 2018. The second period is where the time series is increased between May 27, 2019 and July 13, 2019. Notice that there are two major incidents in the cryptocurrency financial market. The first one happened on November 07, 2018 and the second one on June 26, 2019 (see [START_REF] Ismail | Detecting Early Warning Signals of Major Financial Crashes in Bitcoin Using Persistent Homology[END_REF]). The first peak of each period can be considered as an early sign of a crisis [START_REF] Gidea | Topological Data Analysis of Critical Transitions in Financial Networks[END_REF]. Now, we apply our algorithm on this dynamic network. The time series charts are given in Figure 31. As in the previous examples, there is a strong linear relationship between the time series (Xt)t and ( Xt)t, especially at thresholds s4 and s3. This is confirmed by the adjusted R-squared values (see the first column of Table 7). Moreover, one can observe that there is a positive correlation between the two time series. To confirm this observation, we use Kendall's tau. Indeed, Kendall's tau makes it possible to measure the strength and direction of association that exists between two variables (see [START_REF] Li | Robust rank correlation based screening[END_REF]). The values of Kendall's tau, listed in the third column of Table 7, allow us to confirm the existence of a strong positive correlation between the two series (Xt)t and ( Xt)t, especially at thresholds s4 and s3. Now, to see the efficiency of our algorithm, we compare the execution times via the execution time ratio as in the previous examples (see the second column of Table 7). The reduction in execution time was 2%, 61%, 77% and 83% at thresholds s4, s3, s2 and s1 respectively.

In conclusion, based in the above observations, the optimal threshold of our method lies between the second and the third quadrant of the statistical series of weights of the edges incident to the central node.

Conclusion

In many context, weighted networks are very large and their study requires special treatment. The proposed method is centred on the simplification of the graphs by using a particular thresholding which is based on the notion of centrality of a graph. According to the established various simulations as well as applications on real data, it can be seen that the proposed method has proved its effectiveness for the threshold s3, and some times even for the thresholds s1 and s2. Thus, these thresholds make it possible to simplify a graph into a central subnetwork which represents it and retains its characteristics. Moreover, several given adjusted R-squared values assure that there is a linear relationship between the times series (Xt)t and ( Xt)t. However, it would be very important to investigate this conclusion from theoretical point of view. Also, the proposed method is based on determining the "good" threshold which provides considerable simplification. In our study, we discussed "good" thresholds related to each example, but determining theoretically the optimal threshold of a given network is an open question. In addition to the open questions above, we present some future research directions suggested by anonymous reviewers. First, our approach is probably related to persistent local homology [START_REF] Fasy | Exploring persistent local homology in topological data analysis[END_REF]. Indeed, by eliminating some edges and extracting subnetworks from the whole graph in this way, and then computing persistent homology for these simplified graphs; in a sense we are computing "localized" topological features. Moreover, persistent homology is known to be challenging to compute [START_REF] Fasy | Exploring persistent local homology in topological data analysis[END_REF]. We plan to investigate the interest of our method for computing more efficiently local topological features.

Finally, distributed persistent homology computation would help also in our purpose. Indeed, several distributed approaches have been proposed to compute persistent homology (see for instance [START_REF] Bauer | Distributed computation of persistent homology[END_REF] and [START_REF] Malott | Distributed Computation of Persistent Homology from Partitioned Big Data[END_REF]). We consider that our approach by simplifying a filtration is different from those approaches which organize computation over several clusters. However, these two family of approaches are complementary: after simplifying a filtration, it is also possible to take advantage of distributed algorithms. This also will be considered in our future research works.

Example 2 . 3

 23 The simplicial clique complex Cl(G) associated to the graph G in Figure1has three connected components, and so the dimension of H0(Cl(G)) is three. But it has only one hole because A9A10+ A10A11+ A11A12 +A12A9 is a cycle but not a boundary. Notice that A5A6 +A6A7 +A7A8 + A8A5 is a boundary of the 3-chain A5A6A8 + A6A7A8.

Figure 1 :

 1 Figure 1: A graph G with three connected components.

  is a filtration of the simplicial clique complex Cl(G) given in Example 2.3.

Figure 2 :

 2 Figure 2: Filtration of the simplicial clique complex given in Example 2.3.

Figure 3 :

 3 Figure 3: The (0-dimensional) persistence diagram associated to the filtration of Figure 2.

Figure 4 :

 4 Figure 4: Wasserstein distances between persistence diagrams of the whole networks derived from the DJIA stocks.

Figure 5 :

 5 Figure 5: Flowchart of the proposed method.

Figure 6 :

 6 Figure 6: The time series (X t ) t for the first simulation.

Figure 7 :

 7 Figure 7: The time series ( X t ) t at the threshold s 4 for the first simulation.

Figure 8 :

 8 Figure 8: The time series ( X t ) t at the threshold s 3 for the first simulation.

Figure 9 :

 9 Figure 9: The time series ( X t ) t at the threshold s 2 for the first simulation

Figure 10 :

 10 Figure 10: The time series ( X t ) t at the threshold s 1 for the first simulation.

Figure 11 :

 11 Figure 11: The time series ( X t ) t at the threshold s 0 for the first simulation.

Figure 12 :

 12 Figure 12: The time series (X t ) t for the second simulation.

Figure 13 :

 13 Figure 13: The time series ( X t ) t at the threshold s 4 for the second simulation.

Figure 14 :

 14 Figure 14: The time series ( X t ) t at the threshold s 3 for the second simulation.

Figure 15 :

 15 Figure 15: The time series ( X t ) t at the threshold s 2 for the second simulation.

Figure 16 :

 16 Figure 16: The time series ( X t ) t at the threshold s 1 for the second simulation.

Figure 17 :

 17 Figure 17: The time series ( X t ) t at the threshold s 0 for the second simulation.

Figure 18 :

 18 Figure 18: The time series (X t ) t for the third simulation.

Figure 19 :

 19 Figure 19: The time series ( X t ) t at threshold s 4 for the third simulation.

Figure 20 :

 20 Figure 20: The time series ( X t ) t at threshold s 3 for the third simulation.

Figure 21 :

 21 Figure 21: The time series ( X t ) t at threshold s 2 for the third simulation.

Figure 22 :

 22 Figure 22: The time series ( X t ) t at threshold s 1 for the third simulation.

Figure 23 :

 23 Figure 23: The time series ( X t ) t at threshold s 0 for the third simulation.

Figure 24 :

 24 Figure 24: The time series (X t ) t for the DJIA stocks data.

Figure 25 :

 25 Figure 25: The time series ( X t ) t at threshold s 4 for the DJIA stocks data.

Figure 26 :

 26 Figure 26: The time series ( X t ) t at threshold s 3 for the DJIA stocks data.

Figure 27 :

 27 Figure 27: The time series ( X t ) t at threshold s 2 for the DJIA stocks data.

Figure 28 :

 28 Figure 28: The time series ( X t ) t at threshold s 1 for the DJIA stocks data.

Figure 29 :

 29 Figure 29: The time series ( X t ) t at threshold s 0 for the DJIA stocks data.

Figure 30 :

 30 Figure 30: Time series (X t ) t of the four cryptocurrencies stocks data.

Figure 31 :

 31 Figure 31: Time series ( X t ) t concerning the four cryptocurrency stocks data, of central subnetworks at, respectively, the thresholds s 4 , s 3 , s 2 and s 1 .

Table 1 :

 1 Execution time ratios, adjusted R-squared and average percentages of pruned edges for the first experiment.

	Threshold Time ratio Adjusted R-squared Average percentage of pruned edges
	s 4	0.95	0.9389	4.17
	s 3	0.31	0.9962	39.83
	s 2	0.2	0.9977	64.42
	s 1	0.16	0.991	85.32

Table 2 :

 2 Execution time ratios, adjusted R-squared and average percentages of pruned edges for the second experiment.

	Threshold Time ratio Adjusted R-squared Average percentage of pruned edges
	s 4	0.86	0.9998	1.61
	s 3	0.43	0.9987	27.83
	s 2	0.22	0.997	58.85
	s 1	0.16	0.9812	84.01

Table 4

 4 which represents the results of the applications of the two methods on a graph with 28 nodes resulting

	Execution time in seconds

Table 4 :

 4 Execution times of our method and of the edge collapse method.

Table 5 :

 5 Adjusted R-squared in the linear regression of the times series (X

t ) t on ( X t ) t for the DJIA stocks data.

Table 6 :

 6 Execution time ratios for the application on DJIA stocks data.

	Threshold Time ratio
	s 4	0.79
	s 3	0.39
	s 2	0.28
	s 1	0.26

Table 7 :

 7 Execution time ratios, adjusted R-squared and Kendall's tau values with the studied thresholds for the cryptocurrencies stock data.

	Threshold Time ratio Adjusted R-squared Kendall's tau
	s 4	0.98	0.98	0.80
	s 3	0.39	0.76	0.64
	s 2	0.23	0.55	0.54
	s 1	0.17	0.35	0.49

https://gudhi.inria.fr

For this, we use the function genPositiveDefMat of the package clusterGeneration of the R software.

Comment: As for Experiment 2, there is no strong central node in the simulated networks. We still observe a good fitting of ( Xt)t on (Xt)t (see Table3), as well a significant improvement in terms of execution time, in particular with small thresholds. Once again, the information contained in the time series (Xt)t is not sufficient when considering the threshold s0 (see Figure23).

This comparison was suggested by an anonymous referee. We thank her/him for raising this interesting point.

The data was downloaded from the webpage www.investing.com

Acknowledgements

We thank the anonymous reviewers for their careful reading and many insightful comments and suggestions that have helped us to significantly improve the quality of our article.