Wissem Inoubli

Sabeur Aridhi

Haithem Mezni

Mondher Maddouri

Engelbert Mephu Nguifo

A Distributed and Incremental Algorithm for Large-Scale Graph Clustering

Keywords: Graph processing, Structural graph clustering, Big Graph Analysis, Community detection, Outliers detection, hubs detection 40 Parallelizing SCAN pSCAN [9] Yes No Parallel

Graph clustering is one of the key techniques to understand structures that are presented in networks. In addition to clusters, bridges and outliers detection is also a critical task as it plays an important role in the analysis of networks. Recently, several graph clustering methods are developed and used in multiple application domains such as biological network analysis, recommendation systems and community detection. Most of these algorithms are based on the structural clustering algorithm. Yet, this kind of algorithm is based on the structural similarity. This latter requires to parse all graph ' edges in order to compute the structural similarity. However, the height needs of similarity computing make this algorithm more adequate for small graphs, without significant support to deal with large-scale networks. In this paper, we propose a novel distributed graph clustering algorithm based on structural graph clustering. The experimental results show the efficiency in terms of running time of the proposed algorithm in large networks compared to existing structural graph clustering methods.

Introduction

Recently, the graph model has risen as one of the most used data models in several applications such as, social networks [START_REF] Said | Cc-ga: A clustering coefficient based genetic algorithm for detecting communities in social networks[END_REF], road maps [START_REF] Cao | From gps traces to a routable road map[END_REF], pattern mining [START_REF] Fournier-Viger | A survey of pattern mining in dynamic graphs[END_REF] and bioinformatics [START_REF] Xu | Clustering gene expression data using a graph-theoretic approach: an application of minimum spanning trees[END_REF]. For instance, a recent ranking shows that the popularity of graph databases model increased up to around 500% in the last years [START_REF] Iyer | Bridging the gap: towards approximate graph analytics[END_REF]. It has been shown that the graph model is an optimum data model that allows to represent easily many relationships and facilitates the exploration of data. Taking social networks as an example, the graph model organizes data elements into a set of vertices representing the members, and a list of edges to materialize the relationships between vertices. In addition, the last years featured a big data explosion especially in graph-based social networks. As an example, Facebook in 2013 had over 874 million monthly users [START_REF] Baborska-Narozny | Exploring the 935 relationship between a'facebook group'and face-to-face interactions in'weak-tie'residential communities[END_REF]. This proliferation of a huge amount of data and the massiveness of graphs introduce additional factors to the renewed popularity of graph analytics [START_REF] Iyer | Bridging the gap: towards approximate graph analytics[END_REF]. Consequently, new applications and use cases have been mentioned in the literature. One important task in graph mining is graph clustering. Graph clustering helps identifying tightly connected regions within a graph [START_REF] Žalik | Memetic algorithm using node entropy and partition entropy for community detection in networks[END_REF][START_REF] Günnemann | Finding density-based subspace clusters in graphs with feature vectors[END_REF]. It has been used to solve various problems such as discovering communities in social networks and detecting protein complexes in Protein-Protein Interaction (PPI) networks [START_REF] Xu | Clustering gene expression data using a graph-theoretic approach: an application of minimum spanning trees[END_REF]. It is important to mention that in some applications, the used graph could be large and dynamic, which are two challenging features. The first one is about the graph size that makes its processing beyond the capacity of a single machine. For example, Friendster which is one of the used datasets in social networks, groups more than 65 millions vertices and around 2 billions edges. Ac-30 cording to an experimental study [START_REF] Weng | Efficient distributed approaches to core maintenance on large dynamic graphs[END_REF], the needed main memory after loading this dataset is about 264 GB while the memory of a single high-performance computer is generally much less than 256 GB [START_REF] Weng | Efficient distributed approaches to core maintenance on large dynamic graphs[END_REF]. The second feature i.e., dynamicity, is about the fact that the structure of graphs change over time in terms of 35 vertices and edges [START_REF] Sun | Continuous monitoring of maximum clique over dynamic graphs[END_REF]. In this context and according to Facebook, 400 new users sign up for the website every 60 seconds and 20 million friend requests are sent every 20 minutes in 2020 [START_REF] Weng | Efficient distributed approaches to core maintenance on large dynamic graphs[END_REF] In such situation, the considered graph could be partitioned into several sub-graphs and the computation is performed in a graphs, to evaluate the scalability of DISCAN. We compare DISCAN with four existing structural graph clustering algorithms.

The rest of the paper is organized as follows. After introducing graph clustering in Section 1, we present a brief overview of related works in Section 2. In Section 3, we present the basic concepts related to structural graph clustering. In Section 4, we present our proposed algorithms for large and dynamic graph clustering. In Section 5, we provide the experimental results. The last section is devoted to the conclusions and the future 65 directions.

Related work

Several graph clustering algorithms have been proposed in the literature. Taking as examples, modularity-based approaches [START_REF] Lasalle | Multi-threaded modularity based graph clustering using the multilevel paradigm[END_REF] that represent an optimization solution of the modularity measure for each partitioning schema (generated randomly or according to a heuristic function) [START_REF] Lasalle | Multi-threaded modularity based graph clustering using the multilevel paradigm[END_REF]. The Louvain method [START_REF] Aynaud | Static community detection algorithms for evolving networks[END_REF] represents one of the clustering algorithms based on modularity, that initially generates a random clustering. After that, it starts to change every time a vertex from a cluster to another until getting a maximum modularity. Despite the fact that it gives very connected clusters in the larger graphs, the modularity measure cannot capture the small clusters [27]. Graph partitioning [START_REF] Brandes | Experiments on graph clustering algorithms[END_REF] and min-cut [START_REF] Ding | A min-max cut algorithm for graph partitioning and data clustering[END_REF] are other methods used for the graph clustering which consist of splitting a graph into sub-graphs while 80 optimizing the cut edge during the partitioning. The spectral clustering [START_REF] White | A spectral clustering approach to finding commu-nities in graphs[END_REF] is based on the graph density. It represents an input graph with a matrix and transforms this matrix so that to apply the basic clustering algorithm, like k-means [START_REF] Hartigan | Algorithm as 136: A k-means clustering algorithm[END_REF]. A sampling-based distributed graph clustering method has been 85 proposed in [START_REF] Sun | Distributed graph clustering and sparsification[END_REF]. The proposed algorithm is based on the density of the graph to produce a set of sparse sub-graphs. Graph embedding has also been used in the graph clustering. In [START_REF] Goyal | Graph embedding techniques, applications, and performance: A survey[END_REF], the authors discussed the use of the graph embedding technique to combine the structural and attributed similarity over 90 the graph clustering. The above methods provide, as output, a list of clusters which are not really sufficient to understand the graph behavior. To address this issue, the Structural Clustering Algorithm for Networks (SCAN) was proposed in [START_REF] Xu | Scan: a structural clustering algorithm for networks[END_REF] aiming, not only to identify the clusters in a graph, but also to provide additional information like hubs (vertices between one or more clusters) and outliers (vertices that do not belong to any cluster). These additional pieces of information can be used to detect vertices that can be considered as noise and also vertices that can be considered as bridges between clusters. The functional principle of SCAN is based on graph topology. It consists of grouping vertices that share the maximum number of neighbors. Moreover, it computes the similarity between all the edges of the graph in order to perform the clustering. The similarity computation step in SCAN is linear according to the number of edges, which degrades SCAN performance especially in case of large graphs. Structural graph clustering is one of the most effective clustering methods for differentiating the various types of vertices in a graph. In the literature, several works have been proposed for the structural graph clus-110 tering to overcome the drawback of SCAN. In [START_REF] Shiokawa | Scan++: efficient algorithm for finding clusters, hubs and outliers on large-scale graphs[END_REF], Shiokawa et al. proposed an extension of the basic SCAN algorithm, namely SCAN++. The proposed algorithm aims to introduce a new data structure of directly two-hop-away reachable node set (DTAR). This new data structure is the set of two-hop-away 115 nodes from a given node that are likely to be in the same cluster as the given node. SCAN++ could save many structural similarity operations, since it avoids several computations of structural similarity by vertices that are shared between the neighbors of a vertex and its two-hop-away vertices.

120

In the same way, the authors in [START_REF] Chang | pscan: Fast and exact structural graph clustering[END_REF] suppose that the identification of core vertices represents an essential and expensive task in SCAN. Based on this assumption, they proposed a pruning method for identifying the core vertices after a pruning step, which aims to avoid a high number of structural similarity com-125 putations. To improve the performance and robustness of the basic SCAN, an algorithm named LinkSCAN* has been proposed in [START_REF] Lim | Linkscan*: Overlapping community detection using the link-space transformation[END_REF]. LinkSCAN* is based on a sampling method, which is applied on the edges of a given graph. This sampling aims to reduce the number of structural similarity operations 130 that should be executed. However, LinkSCAN* provides approximate results.

Other works have proposed parallel and distributed implementations of SCAN algorithm [START_REF] Takahashi | Scan-xp: Parallel structural graph clustering algorithm on intel xeon phi coprocessors[END_REF][START_REF] Mai | Scalable and interactive graph clustering algorithm on multicore cpus[END_REF][START_REF] Chang | pscan: Fast and exact structural graph clustering[END_REF][START_REF] Stovall | Gpuscan: Gpu-based parallel structural clustering algorithm for networks[END_REF][START_REF] Wen | Efficient structural graph clustering: an index-based approach[END_REF][START_REF] Shiokawa | Dscan: Distributed structural graph clustering for billion-edge graphs[END_REF][START_REF] Kim | Cass: A distributed network clustering algorithm based on[END_REF][START_REF] Zhao | Pscan: a parallel structural clustering 1080 algorithm for big networks in mapreduce[END_REF]. In [START_REF] Takahashi | Scan-xp: Parallel structural graph clustering algorithm on intel xeon phi coprocessors[END_REF], the authors proposed an approach based on openMP 135 library [START_REF] Bull | Measuring synchronisation and scheduling overheads in openmp[END_REF]. The author's aims were to ensure a parallel computation of the structural similarity and to show the impact of parallelism on the response time. Their method was proven to be faster than the basic SCAN algorithm. Other works have focused on the problem of dynamic graph clustering. In [START_REF] Mai | Scalable and interactive graph clustering algorithm on multicore cpus[END_REF] 140 and [START_REF] Chang | pscan: Fast and exact structural graph clustering[END_REF][START_REF] Chen | Incremental structural clustering for dynamic networks[END_REF], the authors have extended SCAN algorithm to deal with the addition or removal of nodes and edges. Authors in [START_REF] Stovall | Gpuscan: Gpu-based parallel structural clustering algorithm for networks[END_REF], used the graphical processing unit (GPU) whose purpose is to parallelize the processing and to benefit from the high number of processing slots in the GPU which increase the de-145 gree of parallelism. Moreover, distributed approaches are proposed in order to overcome the scalability of structural similarity computing, these algorithms [START_REF] Zhao | Pscan: a parallel structural clustering 1080 algorithm for big networks in mapreduce[END_REF][START_REF] Kim | Cass: A distributed network clustering algorithm based on[END_REF][START_REF] Shiokawa | Dscan: Distributed structural graph clustering for billion-edge graphs[END_REF] are based on big data framework, but they do not support the already partitioned graphs.

150

On the other hand, an index approach is proposed in [START_REF] Wen | Efficient structural graph clustering: an index-based approach[END_REF] where the authors have emphasized the impact of the two parameters µ and on the running time of the structural graph clustering. Using the index approach a significant improvement has been shown in terms of clustering running time. Again, the two sen-155 sitive parameters µ and have been taken into consideration by the authors in [START_REF] Wu | Dpscan: Structural graph clustering based on density peaks[END_REF]. The main goal of the latter consists of estimate the best µ and values in order to enhance the accuracy and efficiency of the clustering results. Most of the above presented works suffer from three major 160 problems: (1) they do not deal with big graphs, (2) they do not consider already distributed/partitioned graphs and (3) they do not consider dynamic graphs.

Through Table 2, we have summarized the discussed approaches according to some features.

165

As shown in Table . 2, most proposed algorithms allow parallel 3. Background

Structural graph clustering: Basic concepts

Graph clustering consists in dividing a graph into several partitions or sub-graphs. As with other clustering techniques, we must use one or more metrics to measure the similarity between two vertices or partitions in the graph. In the structural clustering technique, the graph structure or topology is splitted into a set of sub-graphs that are relatively distant and a set of vertices that are strongly connected. As a well-known algorithm for structural graph clustering, SCAN algorithm uses the structural similarity between vertices to perform the clustering.

In addition, it provides other pieces of information like outliers and bridges. In what follows, we first present an overview of graphs and graph clustering with the SCAN algorithm. Consider a graph G = {V, E}, where V is a set of vertices, and E is a set of edges between vertices. Each of those elements can represent a real property in real-word applications. Let u and v be two vertices in V. We denote by (u,v) an edge between u and v; u (resp. v) is said to be a neighbor of v (resp. u).

In the following, we extend some basic definitions of structural graph clustering, which will be used in our proposed algorithm. Definition 3.1. (Structural neighborhood) The structural neighborhood of a vertex v,is denoted by N(v), and represents all the neighbors of a given vertex v ∈ V, including the vertex v:

N(v) = {u ∈ V|(v, u) ∈ E} ∪ {v} (1)

Symbol Description

N(v)

The neighbors of vertex v N (v)

The strong neighbors of v V c

The core vertices

N (V c )
The

(u, v). σ(u, v) = |N(u) ∩ N(v)| √ |N(u)| . |N(v)| (2)
After calculating the structural similarity with Eq. (2), SCAN uses two parameters to detect the core vertices in a given graph G.

Definition 3.3. ( -neighborhood) Each vertex has a set of structural neighbors, like it is mentioned in Definition 3.1. To group one vertex and its neighbors in the same cluster, they must have a strong connection (denoted by -neighborhood) between them.

SCAN uses a threshold and Eq. (3) to filter, for each vertex, its strongest connections. The -neighborhood is defined as follows.

N (u) = {N(u)|σ(u, v) ≥ } (3)
The threshold (0 < 1) shows to what extent two vertices u and v are connected based on the shared structural neighbors. In addition, it represents a metric with which the most important vertices, also called core vertices, are detected. Definition 3.4. (Core) Core vertices detection is a fundamental step in SCAN algorithm. It consists of finding the dominant vertices in a given graph G. This step allows to build the set of clusters or a clustering mapping. A core vertex v is a vertex which has a sufficient number of neighbors strongly connected with it N (v). We use µ as a minimum number of strong connected neighbors (see Definition 3.3). A core vertex is modeled as follows: Once the nodes and their borders are determined, it is straightforward to start a clustering step. To do so, we use the following definition:

V c = {v | |N (v)| ≥ µ} (4
Definition 3.6. (Cluster) A cluster C (|C| ≥ 1) is a nonempty subset of vertices, where its construction is based on the set of core vertices and their border vertices.

The clusters' building algorithm consists of the following main steps: first, it randomly chooses a core from the cores' list and creates a cluster C. Then, it pushes the core and its borders into the same cluster. At the same time, the algorithm checks if the list of borders has a core vertex. Then, it inserts borders into the same cluster and it applies this step recursively until adding all the borders of the connected cores. Finally, the algorithm chooses other core vertices and executes the previous steps until checking all core vertices. Among the fundamental information returned by SCAN, compared to other graph clustering algorithms, we mention bridge and outlier information, defined as below: Definition 3.7. (Bridge) A bridge b is a vertex v ∈ V that does not belong to any cluster after performing the clustering step, and it has at least two links (edges) with two different clusters. Definition 3.8. (Outlier) An outlier o is a vertex v ∈ V that does not belong to any cluster after the clustering step, and it is not a bridge.

The clustering step aggregates the core vertices and their borders into a set of clusters. However, some vertices do not have strong connections with a core vertex, which does not give the possibility to join any cluster. In this context, SCAN algorithm classifies those vertices into two families: bridges and outliers. A vertex v, that is not part of any cluster and has at least two neighbors in different clusters, is called bridge. Otherwise it is considered as an outlier.

Running example

In this section, we explain through a running example, how SCAN algorithm works. Consider a graph G presented in Fig. 1 and the parameters = 0.7 and µ = 3. In the first step, Algorithm 18 (lines 1-3) use Eq. (2) to compute the structural 245 similarity for each edge e ∈ E. Then, Eq. (3) (lines 5-8) is used to define the core vertices (see gray vertices in Fig. 1). After that, we proceed to the clustering step, then we apply Definition 3.6 (lines 11-16) to build the clustering schema. In the example we have four core vertices: 0, 2, 9 and 10. Each core has a list 250 of border vertices (the neighbors that have strong connections with a core). In the example, the vertex number 2 is a core. This latter has the vertices 1, 4, 5, 3 and 0 as the list of borders, since they have strong connections with the core. The core and its borders build a cluster, and if a border is a core we join all 255 its borders into the cluster. Like in our example, the vertex 2 is a core. Hence, we join all its borders 1, 3, 5, 4, including 0 as being a core vertex. In this case, if the vertex 3 is not a border of vertex 2 and it is a border of vertex 0, then vertex 3 should belong to the same cluster of vertex 2 (which is a core vertex), since it is a reachable border of vertex 2. The last step of SCAN algorithm consists in defining the bridges and the outliers. As shown in Fig. 1, we have two clusters. The first one is composed of vertices 0, 1, 2, 3, 4, and 5, whereas the second cluster is composed of nodes 8, 9, 10, and 11. The remaining vertices (6 and 7) must be categorized as outliers and bridges according to the Definition 3.7. In our example, vertex 7 has two connections with two different clusters, and vertex 6 has only one connection with one cluster, which makes vertex 7 a bridge and vertex 6 an outlier.

DISCAN: A Distributed and Incremental Algorithm for Large-Scale Graph Clustering

In this section, we introduce DISCAN: a new distributed and incremental algorithm for structural graph clustering. Our proposed approach is based on a master/slave architecture and is implemented on top of BLADYG framework [START_REF] Aridhi | Bladyg: A graph processing framework for large dynamic graphs[END_REF]. This latter is a distributed block-centring graph processing framework in which the slaves are responsible for the execution of a specific computation and the master machine coordinates between all the slaves. The input data must be divided into sets of chunks (sub-graphs in our case). Each chunck/partition is assigned to a worker, which performs a specific computation. The master machine orchestrates the workers' execution. In the following, we present the main three steps of DISCAN: (1) graph partitioning, (2) distributed graph clustering named DSCAN [START_REF] Inoubli | Un algorithme distribué pour le clustering de grands graphes[END_REF] and (3) incremental graph clustering.

Distributed graph partitioning

The used distributed graph processing framework uses by default a random graph partitioning and provides the possibility to implement a personalized graph partitioning method. Motivated by the fact that the random graph partitioning method can affect the performance of the proposed algorithm and the graph partitioning problem is an NP-hard problems [START_REF] Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF], we adapted an existing edge partitioning method [START_REF] Ji | Local graph edge partitioning with a twostage heuristic method[END_REF] in a distributed manner as a preliminary step for our distributed clustering algorithm.

In this step, we split the input graph G into several small partitions P 1 , P 2 , ..P n and affect the partitions to the worker machines. To ensure the consistency property while dividing the input graph, we must identify a list of cuts edges in order to have a global view of G. As depicted in Algorithm 2, the master machine first divides equitably an input graph file into subfiles according to the number of edges and the number of partitions, and sends the sub-files to all the workers lines [START_REF] Aridhi | Density-based data partitioning strategy to approximate large-scale subgraph mining[END_REF][START_REF] Aridhi | Bladyg: A graph processing framework for large dynamic graphs[END_REF][START_REF] Aynaud | Static community detection algorithms for evolving networks[END_REF][START_REF] Baborska-Narozny | Exploring the 935 relationship between a'facebook group'and face-to-face interactions in'weak-tie'residential communities[END_REF]. Each worker gets a list of edges and vertices from its sub-file. There-305 after, it sends the list of vertices to all workers, in order to determine the frontier vertices so that to get the cuts edges. When each worker receives a list of vertices from its neighbor workers, it determines the vertices that belong to the current worker (partition). Consequently, these vertices are considered as fron-310 tier vertices in their partitions lines [START_REF] Brandes | Experiments on graph clustering algorithms[END_REF][START_REF] Bull | Measuring synchronisation and scheduling overheads in openmp[END_REF][START_REF] Cao | From gps traces to a routable road map[END_REF][START_REF] Chang | pscan: Fast and exact structural graph clustering[END_REF]. For example, consider the partitions P 1 and P 2 , which are assigned to two workers. Each partition has its set of edges: [START_REF] Abbas | Streaming graph partitioning: an experimental study[END_REF][START_REF] Aridhi | Bladyg: A graph processing framework for large dynamic graphs[END_REF], (1, 4)} and P 2 = {(1, 5), [START_REF] Abbas | Streaming graph partitioning: an experimental study[END_REF][START_REF] Brandes | Experiments on graph clustering algorithms[END_REF], (5, 7)}. When the workers receive the sets of vertices from other workers, they check the intersection 315 between their vertices and the received ones. The obtained list of vertices is considered as a set of frontier vertices. According to our example, vertex 1 is considered as a frontier vertex in P 1 , and vertices 5 and 6 are considered as frontier vertices in P 2 . In the last step, once each worker has determined the frontier 320 vertices, it fixes the cuts edges, i.e. edges that have a frontier vertex (lines 10-18). Step 1: Local clustering. As presented in Algorithm 3, the input graph G is splitted into multiple sub-graphs/partitions (P), each one is assigned to a worker machine. The partitioning step, as mentioned in Section 4.1, is performed according to the α parameter, which refers to the number of worker machines 330 (line 1). To overcome the loss of information during the partitioning step (edges connecting nodes in different partitions), Assume that a graph G is partitioned into two partitions P 1 (vertices in blue) and P 2 (vertices in red), like it is depicted in 340 Fig. 2, and each partition has a set of vertices connected with other partitions. We call them frontier vertices of a given partition P i , and they are denoted by V f P i . For example, V f P 1 ={1, 2, 5} and V f P 2 ={4, 7}. Each v ∈ V f P has a set of internal and external neighbors. For example, vertex 4 is a vertex of the partition P 2 .

P 1 = {(1, 2),

345

It has the vertex 6 as internal and the vertices 1, 2 and 5 as external neighbors. Computing the structural similarity of a frontier vertex u considers that all the neighbors of u belong to the same partition. Thereby, we duplicate all frontier vertices in partition P to all neighbor partitions and we call them external vertices.

350

For example in our running example, P 1 has frontier vertices V f P1 ={1,2 , 5} and P2 is the neighboring partition. Thus, we must duplicate V f P 1 into P 2 to ensure the accuracy of structural similarity of V f P 2 (see Fig. 3). After that, when we apply a local clustering on P 1 and P 2 , 355 we will find several conflicts such as the vertex v ∈ V f P1 is a core vertex in P 1 , and an outlier in P 2 . These conflicts should be avoided in the merging step.

Step 2: Merging. The distribution of similarity computation and the local clustering step can improve the response 360 time of DISCAN, compared to the basic sequential algorithm. However, we should take into consideration the exactness of the returned results, compared to those of the basic SCAN. To ensure the same results as in the basic SCAN, we defined a set of scenarios regarding the merging step. These scenarios 365 will repetitively be applied to every two partitions of G, until combining all the partitions (see Algorithm 3, lines . For each pair of partitions P i and P j , a merging function is executed to combine the local results from P i and P j and store them in global variables like clusters, borders, bridges and outliers. Al- Let c i be a cluster that groups a set of border and core vertices. If c i shares at least one core vertex c with another cluster c j , then c has a set of borders in c i and c j , and all the vertices in c i and c j are reachable from c. Hence, c i and c j should be merged into the same cluster. Let c i and c j two clusters that have a set of vertices (borders or cores), and a set of bridges with other local clusters, and ∃ b a bridge vertex according to the two clusters c i and c j only, where i j. In the merging step and according to Lemma 4.1, if one or several clusters share at least a core vertex, then they will be merged into a single cluster. In this case, (c i ,c j ) ⇒ C which makes b be weakly connected with only one cluster C, then according to Definition 3.7, b should change its status from bridge to outlier.

For instance looking at lines 16 to 22, we have focused on the shared cores between two clusters and the case when they share at least one core. According to Lemma 4.1, we should merge them into one single cluster. Subsequently, in lines 23-25, we verify for each outlier if it does not belong to some sets of cores, borders or bridges. In this case, we must remove it from the list of outliers. Otherwise, a vertex v should be 410 changed as a bridge if it is classified as an outlier in the two clusters c i and c j that are not in the same partition, and if it has two connections with different clusters in the merging step.

Illustrative example

Fig. 3 shows a demonstrative example of a graph clustering 415 using DISCAN. In this example, we use the same parameters ( and µ ) of the running example in Section 3, and two partitions (P1 and P2). In the first step of DISCAN, the input graph G is divided into two partitions P 1 and P 2 as it presented in Fig. 3, where the blue vertices represent the first partition and the red vertices represent the second partition. In the second step, DISCAN duplicates the frontier vertices in each pair of adjacent partitions. For example, the blue vertices 1, 2 and 5 are duplicated in partition P 2 since they represent frontier vertices in their partition. In the same way, the vertices 4 and 7 are du-425 plicated in the partition P 2 . In the third step, all the workers perform the similarity computation, check the status for each vertex and build the local clusters, as it is shown in Fig 3 . The last step of DISCAN consists of combining all local results returned by each worker. As shown in Fig. 3, there are some 430 conflicts in terms of node status. For example, vertex 2 is a core vertex in P 1 whereas it is a noise (outlier) vertex in P 2 .

In the same way, vertex 4 is a border in P 1 and a noise in P 2 .

Then, after building the local clusters, P 1 has one cluster (1, 2, 3, 4, and 5) in which vertex 7 is a noise vertex in P 2 . As

435

for P 2 , it groups the vertices 8, 9, 10, and 11 as a cluster and the remaining vertices (4, 5, 1, 2, 7, and 6) are considered as noise vertices including vertex 7. This latter is a bridge according to basic SCAN (see running example in Section 3)). In the merging step, DISCAN considers that the vertex 7 has two 440 weak connections with two different clusters. Thus, vertex 7 is marked as a bridge.

Distributed graph maintenance

Consider a large and dynamic graph G, which will undergo several changes over time such as adding or deleting edges 445 or/and vertices. When a clustering will be performed, the classic approaches re-run the clustering from scratch, which is obviously very expensive especially in large graphs. In this work, we propose an incremental and distributed algorithm for large and dynamic graph clustering. The main idea of our approach 450 is to determine in each update the vertices and the edges concerned by this update, and according to that, we apply the new updates on the old clustering results. Assume that G = (V, E ) is going to undergo several updates U over time. U can be adding/deleting vertices or edges from/to 455 G. These changes can affect the similarity values and some vertex status (border, core, etc.). Consequently, the clustering schema may be affected in several situations. Definition 4.1. Each vertex u i ∈ U generates modifications of several structural similarities, which is defined as the affected 460 edges E A .These vertices also change the status of several vertices and are noted as affected vertices V A . Definition 4.2. (Affected edges) When adding a vertex v new associated with an existing vertex v old , new edge (v new , V old ) will be created and a set of edges denoted E A will be marked as 465 affected edges and should be updated.

Note that e = (u,v) ∈ E A , where u ∈ V old and v ∈ N(V old ).

In the case of removing a vertex V T BD , a set of edges noted as E T BD should be deleted from G. Therefore, a V c of vertices is concerned by this update. Here V c = (u, v) ∈ E T BD \ V T BD 470 and, according to V c , the affected edges are E A = E i ⊂ G and

E i = (u, v) / {u,v} ∈ V c .
Also when adding or deleting an edge (v i , v j ), the list of neighbors of both vertices v i and v j will be changed which can produce several other edges. The affected edges update their 475 structural similarities. E A is a set of edges (u, v) ∈ E and v i = u or v j = v (Affected Vertices) For each update on G, some structural similarities can be changed. Thus, some vertices change their status (border, core vertices). These vertices are defined as affected vertices V A . V A can be divided into two subsets: (i) directly affected V AD , which update their status depending directly on E A , (ii) indirectly affected V ID which depend on the status of V AD . For example, when a core vertex changes his status to outlier or border, then all these border vertices will become affected indirectly according to this update. Let E A =(v 1 , v 2 ) be following an update V AD =V AD ∪ v 1 ∪ v 2 , while V AI are all neighbors of V AD . Other vertices can be affected indirectly with several updates, and are dependent on the changed clusters. These vertices are defined the affected bridges and 490 noted as V AB . V AB is the list of outliers or bridges which are connected with affected clusters described in the Definition 4.4. 3, for some updates in the structural similarity, when the similarity value exceeds or decreases the threshold the status of this edge maybe changed to strong or weakly connection. Thereby, this change can affect the status of each vertex v ∈ V AD . Consequently, according to 3.5 the V DA can change other vertices status indirectly which are defined as indirectly affected vertices V IA . Rationally, those changes can affect the mapping of the clusters, and several clusters may be changed. Thereby, according to Definition 3.7, ∃ a vertex v ∈ B where v is only depends on two clusters c 1 and c 2 . When c 1 and c 2 will be merged into one cluster c new , v will be weakly connected with only c new . In this case and according to Definition 3.7 v will be an outlier vertex. In the same way, when we have a cluster c and v is an outlier to c with two weak connections related to v 1 and v 2 , after some updates c becomes 520 splited into two clusters c 1 and c 2 when v 1 and v 2 are respectively in c 1 and c 2 . In this case, v becomes a bridge between the new clusters c 1 and c 2 according to the connection of v with v 1 and v 2 .

Fig. 4 shows an example of a graph G with 3 partitions for 525 which we deleted vertex 3 (yellow vertex). Then, all affected edges E A (red edges) change their structural similarities since vertices 0, 2 and 5 (old neighbors of the deleted vertex 3) lost the vertex 3 as a neighbor, and all the edges associated with vertex 3 are removed from G. This new update affects only 530 a sub-set of vertices in G. The example shows that vertex 2 (v 2 ∈ V A ) lost its core status, whereas vertex 9 keeps its core status (v 9 V A ). Thus, E A can change several vertices' status directly (V AD ) or indirectly (V AI ). Like it is shown in our example, vertex 2 ∈ V AD has lost a strong connection with the 535 removed vertex which changed to an outlier in this case. In the same way, V AD can change the status of V AI . Vertices 0, 1, 4 and 5 were considered as border vertices according to vertex 2 (in the initial graph), and in our case, when the vertex 2 lost the core status, as a result V AI are changed to outliers. According Step 1: Graph maintenance. In this step, DISCAN runs the graph maintenance in real time. In each update u ∈ U, it (i) updates the graph G structure, (ii) checks the affected edges E A , and (iii) recomputes the similarities of E A (lines 4-12 of the algorithm 4). Then, it gets V A according to E A in order to memorize them in a global variable. Like discussed in Definition 4.4, V A can affect several clusters in the current partition or in other partitions. Thereby, each worker shares its V A with all workers so that each one determines the affected clusters and saves them. Once the affected clusters are fixed, they affect some bridges or outliers vertices. So the affected bridges should be added to the list of affected vertices to be checked in the next step.

Step 2: Incremental local clustering. This step is performed in micro-batch processing mode, after a number of updates or using a window time. In both methods, DISCAN runs the same scenarios. These latter consist of two choices for a user who selects one of them according to the number of changes per seconds or according to other needs such as the graph size or graph evolution. Therefore, in each batch, DISCAN first checks the core vertices. The checking is performed only on the affected vertices V A , where in general the |V A | |V|. Secondly, DISCAN checks the border vertices like in the first clustering but using only E A , since the border vertices are dependent on the strong connections with core vertices. For this reason, DISCAN checks the core vertices according to E A only. After that, the updated cores and borders vertices will change the clustering schema depending of the affected vertices (cores, borders) like it is described in Definition 4.4. The affected clusters feat are five possible cases owing to each update of a graph:

(1) split one cluster to small clusters, (2) remove an existing cluster, (3) build new clusters, (4) update the existing clusters and (5) merge two or more clusters. Consider set of cores and theirs borders, and the core vertices have strong connections between them. After the removal of a strong connection between two cores c 1 and c 2 , then the clusters should be splited into subclusters depending on c 1 and c 2 . For the case (2), each cluster is built on a list of cores and their borders. The master machine gets all the affected vertices from all workers in order to facilitate the combination of the new changes. Here, some clusters should be verified. In each batch, the master keeps only the past unchanged clusters and requests all work-615 ers to get the changed clusters. Thereby, all workers combine the updated clusters eventually including new clusters. In the merging step, DISCAN uses the same scenarios as in the first clustering (see Lemma 4.1). If at most one cluster shares at least one core vertex, they can be merged into one cluster. In 620 the next step, after getting the new clusters, the master machine requests all workers to get their borders vertices. Then, each worker filters only the affected vertices which will belong to its local bridges, and sends them to the master. The rest of affected vertices will be added to the global list of outliers. Finally, 625 DISCAN initializes the global affected vertices and clusters to empty lists which will to be used in the next batch.

Time complexity analysis of DISCAN

The time complexity of DISCAN mainly depends on the affected edges and vertices in each new update. This complexity

(|V c ∈ V A | -|(v i , v j )| |V A | i, j=1 ), with v i , v j ∈ V c and σ(v i , v j ) ≥ .

Experiments

In this section, we evaluate the effectiveness and efficiency of our proposed algorithm for the structural clustering of large and dynamic distributed graphs.

Experimental protocol 645

We compared DISCAN with four existing structural graph clustering algorithms in the case of static graphs. Then, in a second set of experiments, we evaluated DISCAN performance on dynamic graphs. We also conducted experiments in order to study the impact of DISCAN features on the execution time 650 such as the number of updates.

• Basic SCAN,

• pSCAN: a pruning SCAN algorithm,

• AnySCAN: a parallel implementation of basic SCAN using OpenMP library,

655

• ppSCAN: a pruning and parallel SCAN implementation.

The above mentioned algorithms are implemented with C language. Thus, we used the GCC/GNU compiler to build their binary versions. The compared algorithms could be divided into two categories: (i) centralized algorithms such as SCAN and 660 pSCAN, and (ii) parallel algorithms such as AnySCAN and pp-SCAN. To run both centralized and parallel algorithms, we used a T3.2xlarge virtual machine on Amazon EC2. This machine is equipped with an 8 vCPU Intel Skylake CPUs at 2.5 GHz and 32 GB of main memory on a Ubuntu 16.04 server distribution.

665

In order to evaluate DISCAN, we used a cluster of 10 machines, each of them is equipped with a 4Ghz CPU, 32 GB of main memory, and operating with Linux Ubuntu 16.04. Details on the configuration and the deployment of DISCAN are available following this link: https://github.com/inoubliwissem/ 670 remote-master.

Experimental data

For all test cases with static graphs, we used real-world graphs (see Table 3) obtained from the Stanford Network Analysis Project (SNAP) 1 . Then, to simulate dynamic changes in 675 the graphs, we generated a set of new edges for each static graph (G2, G3, G4 and G5). The new updates are grouped as a set of batches. In each one, we generated five batches with different sizes that vary from 2000 to 10000 new edges.

BLADYG framework

BLADYG is a distributed and parallel graph processing framework that runs on a commodity hardware. The architecture of BLADYG is based on a master/slave architecture. BLADYG starts by reading the input graph from many different sources, which can be local or distributed files, such as Hadoop Distributed File System (HDFS) and Amazon Simple Storage Service (Amazon S3). The communication model used by BLA-DYG is the message passing technique, which consists in sending messages explicitly from one component to another, in order to get or send useful data during the graph processing. In the same way, BLADYG defines two types of messages: (i) worker-to-worker messages, and (ii) master-to-worker messages. BLADYG allows its users to implement their own partitioning techniques.

Experimental results

Speedup of initial distributed graph clustering. DISCAN is designed to deal with dynamic graphs. However, it starts by doing an initial clustering of the input graph. Then, it deals with incremental changes in the graph. We evaluated the speedup of the first step of DISCAN and we compared it with the basic SCAN and its variants presented in Section 5.1. The compared algorithms use different graph representations. In fact, AnySCAN and SCAN implementations use the adjacency list representation [START_REF] Doerr | Adjacency list matchings: an ideal genotype for cycle covers[END_REF], whereas both pSCAN and ppSCAN use the Compressed Sparse Row (CSR) format [START_REF] D'azevedo | Vectorized sparse matrix 975 multiply for compressed row storage format[END_REF]. In our proposed algorithm, we used an edge list format, in which each line represents one edge of the graph. The incompatibility of graph representations poses an additional transformation cost while evaluating the studied methods. For example, the transformation of the live journal dataset from edge list to adjacency list takes around 100 seconds using one machine equipped with an 8 vCPU and 32 GB of main memory.

As shown in Fig. 5, our approach is slower than the other algorithms, in the case of small graphs (G1, G2, and G3). Also, there was a very large gap between DISCAN and the other algorithms, especially with pSCAN and ppSCAN. This gap is reduced when the graph size increases (case of G4 dataset). The plots bars, in Fig. 5, show a gap of 12x between DIS-CAN and basic SCAN with the G1 dataset and 2x only with the G4 dataset. We notice that the gap between DISCAN and ppSCAN depends mainly on the size of the used dataset. For example, with the G1 dataset, the gap between DISCAN and ppSCAN reached 20x, while it is reduced to 11x with the G4 dataset. That can be explained by the pruning step of pSCAN, Imapct of the graph partitioning on DISCAN. In our vision, the partitioning step has a direct impact on the response time of DISCAN. For this reason, we randomly generated four par-735 titioning schemas, and for each one, we got the number of cutedges as follows: 17.6M, 19.2M, 22.3M and 24.6M for the partitions P1, P2, P3 and P4, respectively. Then, we run DISCAN on all the partitions with the same configuration (10 machines, =0.5 and µ=3). As shown in Fig. 6, there is a very clear impact

740

of the graph partitioning on the response time of DISCAN, as this latter rises from nearly 800s to 1000s with P1 and P2. Furthermore, the elapsed time of each DISCAN step varies from one partitioning to another. This disparity is noticed mostly during the merging step and slightly in the clustering step. This is probably explained by the number of vertices, which are duplicated due to the number of cuts-edges produced by the graph partitioning. This number would affect the amount of similarity computation operations during the clustering step, and it increases the communication cost during the merging step.

SpeedUp of incremental clustering. The main goal of this test series is to compare DISCAN with other algorithms. Since there is no incremental algorithm for the structural graph clustering, we compared the speedup of DISCAN with the results produced with pSCAN and ppSCAN, the fastest existing algorithm (see Section 5.1). Initially, we started by running all the algorithms on the used graphs. Then, we periodically added new batch of updates of different sizes. Fig. 7 shows the running time of the tested algorithms with different graphs. In all the used graphs, DISCAN is outperformed by the other algorithms, except for pSCAN which does not support the G5 graph. Despite that pSCAN and ppSCAN re-execute the clustering from scratch, they are faster than DISCAN in the case of G2, and have a close time in the case of G3. In the case of G4, DISCAN initially features a better behavior than pSCAN and ppSCAN. In fact, ppSCAN and pSCAN are faster than DIS-CAN, but the gap in running time begins to narrow between G2 and G4. However, when we add a new batch to the initial graphs, DISCAN becomes faster than pSCAN and ppSCAN. In the case of G3, Fig. 7 shows a gap of 2x between DISCAN and pSCAN and almost close running time to DISCAN and pp-SCAN. Furthermore, the gap between DISCAN and pSCAN starts to increase, to finally reach 3x, and 10% between DIS-CAN and ppSCAN. DISCAN scalability. Fig. 8 shows the scalability of DIS-775 CAN w.r.t. the number of workers, with G2 and G3 datasets, and for different update batches using default parameters ( =0.5 and µ=3).

Overall, the number of workers affects the running time de- pending on the size of the used dataset and the number of up-780 dates. In Fig. 8 with G2 dataset, all curves have almost the same shape. The response time is low with 2 to 4 workers, but this is not always valid, because this improvement depends on the number of updates. The improvements are between 10% and 50%, respectively, for 2000 and 10000 updates. Afterwards, 785 the curves grow until 8 workers, then comes down. In the case of G3 dataset, the scalability becomes very high. The response time decreases depending on the number of workers. This improvement is about 30% and 40% depending on the number of updates. This behavior can be explained by the number of af-790 fected vertices and clusters. When this number is small, the needed resources (e.g., workers) are small. Nevertheless, with many workers, the processing time of DISCAN becomes high due to the communication cost.

Exactness of DISCAN In this test series, we prove the exact-795 ness of DISCAN, by comparing its obtained results to those produced by ppSCAN. For this purpose, we used the informationtheoretic metric and Normalized Mutual Information (NMI) [START_REF] Schütze | Introduction to information retrieval[END_REF].

The NMI is a normalization of the Mutual Information that shows how two clustering results are equals. The NMI value 800 ranges from 0 (no mutual information) to 1 (perfect correlation). Table 4 shows the NMI score between DISCAN and Impact of the batch size. The main goal of this experiment is to evaluate the impact of the batch size on the response time. Initially, we run DISCAN with different datasets (G2, G3, 810 G4 and G5) and different batch sizes (between 1000 and 2000) on a cluster of 10 machines, and using the default parameters ( =0.5, µ=3). Fig. 9 shows that the running time increases for all curves. This is explained by the initial graph size, as we highlighted in Fig. 7, but also in function of the batch size. We 815 can also notice that the increase depends on the size of the initial graph and the batch size. The increase rate is about 5%, 50% and 150%, respectively for G2, G4 and G5. That can mainly be explained by the graph size, since for each update DISCAN checks (in the graph maintenance step) all the affected vertices and edges, in order to update the affected similarities. Such checking depends on the graph size. On the other hand, in the reclustering step, DISCAN first performs the clustering on the affected vertices. Then, it merges all the affected clusters on the master machine. Thus, the running time spent on the merging step depends on the number of affected edges, because it must check all the affected clusters. The affected clusters' checking requires the communication between the master and other workers. In this way, when the batch is small, i.e. few affected vertices, the communication cost becomes acceptable. Impact of the vertex type (internal vs external). Each update on an existing graph may be performed on internal or frontier (external) vertices. In this experiment, we show the difference between the updates in internal and external vertices, in terms of running time. For G2, G3, G4 and G5, we generated several internal and external batches of adding new edges. After that, we ran DISCAN using those batches, in order to compare their computation times. As depicted in Fig. 10, the updates on the frontier vertices are very expensive with regard to the running time. This latter's gap trends to around 50% between 840 internal and external vertices updates. That could be attributed to the graphs' maintenance step, which is performed by DIS-CAN. This latter is time-consuming in the case of external vertices, compared to internal vertices. In fact, for internal vertices, all maintenance operations are performed locally (on the same 845 partition), whereas for external vertices, the graph maintenance is carried out on several partitions, which generates additional costs. These latter are mainly caused by the duplication of the frontier partitions and obviously the communication between all the concerned workers.

850

DISCAN steps. We noticed, from the previous experiment, that the response time depends on the type of vertices (internal or external). For external vertices, the algorithm's performance is slow, unlike the case of internal vertices. tween the machines in the cluster. It is obvious that a massive usage of the communication is recorded during two periods, and a very small communication usage was noticed during the remaining periods. This can be explained by DISCAN behavior, where the graph maintenance and combining steps of DIS-CAN require a lot of communication, which decreases the performance of DISCAN. This also could be attributed to the use of communications between workers (Peer-To-Peer communication) in BLADYG framework, which is expensive compared to the master-slaves communication.

Conclusion

In this paper, we proposed DISCAN, a distributed algorithm for big graph clustering based on the structural similarity. DIS-CAN is build on top of a distributed and master/slaves architecture which makes it scalable and works on the community of 895 modest machines. The proposed algorithm is able to deal with any graph size and is scalable with a large number of machines, in a parallel way. We have presented the main functions of DIS-CAN, starting from the partitioning to the combining of intermediate results, for each worker. Also, we have performed an extensive experimental study to validate and compare our proposed algorithm with other ones. The experiments have shown that DISCAN featured an horizontal scalability that is not guaranteed with other algorithms.

In the future, we will improve DISCAN's graph partitioning 905 step. We plan to exploit the density feature during the graph partitioning, whereas for the dynamic graph clustering, we plan to make DISCAN support large and evolving graphs, in order to check all the snapshots of a graph. Having this in hand, we can assess and follow the evolution of each cluster, as well as 910 other vertex types (border, outlier, and bridge).

gistical and material support that helped us to the development and achievement of this project. They mainly allowed us to perform the experimental study of this work in a data center called GALACTICA (https://galactica.isima.fr). This work was partially supported by the CNRS-INRIA/FAPs project "Tem-920 poGraphs" (PRC2243).

)

  Definition 3.5. (Border) Let v c be a core vertex. v c has two lists of structural neighbors: (1) weak connected neighbors to v c , also called noise vertices (N(V c ) \ N (V c )), and (2) strong connected neighbors called reachable structured neighbors. In our work, reachable structured neighbors are called border vertices. N (V c ) represents the border vertices of a core vertex V c .

Figure 1 :

 1 Figure 1: Running example of SCAN ( = 0.7 and µ = 3).

Algorithm 2 : 8 Find 2 .

 282 Distributed graph partitioning Input : Graph file GF as a text file, parameter (NP number of partitions) Output: P set of partitions 1 BLADYG initialization according to the NP parameter 2 Master machine: split GF into a set of sub-files GF 3 foreach GF i ∈ GF do 4 Assign GF i to worker W i 5 end /* In parallel */ 6 foreach Worker W i ∈ W do 7 Get list of vertices and edges from GF i the list of frontier vertices from the neighbor workers 9 end /* In parallel */ 10 foreach Worker W i ∈ W do 11 foreach Edge ∈ E do 12 (a,b)=Edge ; 13 Let P f i the frontier vertices 14 if (a ∈ P f i ∪ b ∈ P f i ) Initial distributed graph clustering Initial graph clustering (DSCAN) has two main steps: (1) local clustering step and (2) merging step.

  325

Algorithm 3 :

 3 DSCAN Input : Graph G , parameters (µ, , α) Output: Clusters, Bridges, Outliers /* Divide G into subgraphs G = {G 1 G 2 ..G α } according to parameter α */ P ←-Partition (G,α) /* In parallel */ foreach P i ∈ P do Assign P i to W i end /* In parallel */ /* Step 1: Local clustering */ foreach Worker W i ∈ W do Let P i the current partition Find the frontier vertices in P i and duplicate them into neighbor partitions end /* In parallel */ foreach Worker ∈ W do Compute the structural similarity of a partition P i using V f list Retrive local Cores and Borders in P i Build local clusters in P i Find local Bridges and Outliers in P i end /* Step 2: Merging */ All workers exchange theirs local clusters between them; using Worker2Worker message foreach Worker W i ∈ W do if (C 1 ∩ C 2 ∩ .. ∩ C α = V; and ∃V i ∈ Core then C ← Merge(C 1 , C 2 ,..C α ) Send C to the master end else Send local clusters to master end for V i IN Outliers do if (V i ∈ Core ∪ Border ∪ Bridges ) then 26 Remove V i from the list of Outliers end end for V i IN Outliers do Nb Connections ← 0 for C i IN Clusters do 32 if (N(V i ) ∩ C i ∅) then 33 Nb Connections + + 34 end end if ( Nb Connections ≥ 2 ) then 37 Add V i to Bridges 38 Remove V i from Outliers end end end Send Clusers,Bridges,Outliers to the master using Worker2Master message frontier vertices are duplicated into neighboring partitions (line 5-8). Subsequently, for each partition P i , a local clustering is performed on each worker machine (lines 9-14). Fig. 2 shows 335 a demonstrative example of the duplication step. The demonstrative example describes how the graph consistency will be ensured during the partitioning step.

Figure 2 :

 2 Figure 2: Illustrative example of partitioning step

370 gorithm 3

 3 also achieves several scenarios (Lemmas 4.1, 4.2 and 4.3) to solve the encountered conflicts, mentioned below: Lemma 4.1. (Merging local clusters) Let C 1 and C 2 two sets of local clusters in different partitions P 1 and P 2 , respectively. ∃c 1 ∈ C 1 and ∃c 2 ∈ C 2 , Core(c 1 ) ∩ Core(c 2 ) ∅.

Lemma 4 . 2 .

 42 (Outlier to Bridge) Let C 1 and C 2 be two sets of local clusters in partitions P 1 and P 2 , respectively. ∃ two clusters c 1 and c 2 that belong to the sets of clusters C 1 and C 2 . In addition, ∃ o an outlier in both partitions P 1 and P 2 , with N(o) ∩ c 1 ∅ and N(o) ∩ c 2 ∅. If c i and c j (i j) share an outlier o, this means that o is weakly connected with the two clusters c i and c j . Hence, according to the Definition 3.7, o should be changed to a bridge vertex. Lemma 4.3. (Bridge to Outlier) Let c 1 and c 2 two local clus-390 ters in the partitions P 1 and P 2 , respectively. ∃ a bridge b according to only two clusters c 1 and c 2 , when c 1 and c 2 two clusters that will be merged into one cluster, b should be changed into an outlier.

Figure 3 :

 3 Figure 3: The partitioned graph G used in the running example in Section 3

Definition 4 . 4 .Lemma 4 . 5 .

 4445 (Affected clusters) The affected vertices in several situations can affect the clustering schema. The Affected (concerned) clusters represent the 495 sub-set of clusters which contain one or more affected vertices, denoted by C a f f ected . C a f f ected =c ∈ C such that ∃v ∈ (v AD ∪ v ID ) and v ∈ c. Lemma 4.4. Change of structural similarity of affected edges E A are mainly depend on the Definition 3.1. The similarity 500 value is based on the neighbors of both vertices of an edge. Therefore, each update (adding/deleting an edge/vertex) can change the list of neighbors of some vertices. As a result, some edges must change their structural similarity. Change in the status of affected vertex According to the Definition 3.4 and the Definition 3.

540 to Definition 4 . 4 ,

 44 V AD and V AI can change the old clustering schema and our example confirm that. Partition 1 of G groups two clusters. The first one is c 1 = { 12, 13, 14} and the second one is c 2 ={0, 1, 2, 3, 4, 5} (4 and 5 are external vertices). Thus, c 1 and c 2 are affected because c 1 contains the vertex 12 as an af-545 fected vertex, and in the c 2 , all its vertices are affected because of the removed vertex. These clusters can affect in the last step other vertices (bridge or outlier vertices). Like it is depicted in Fig.4 c2 should be removed since it does not have any core vertex, and the vertices 6 and 7 were considered as bridges with c 2 .550Thereby, these bridges are susceptible to change their status.Algorithm 4 describes the main steps of the proposed DIS-CAN. DISCAN provides real-time graph maintenance and a micro-batch clustering. Moreover, it performs the new clustering after several changes, in order to optimize the incremental 555 clustering. We present below the main steps of DISCAN:

Figure 4 :

 4 Figure 4: A partitioned graph G (P1, P2, P3), affected vertices, edges when deleting vertex 3

  If one cluster does have any core vertex it should be removed. Sometimes, a new 595 update makes an outlier vertex to a core vertex c new . If this vertex has a strong connection with any other old core c, it joins the cluster of c, like in the case (4). If c new does have any strong connections with any other core it builds a new cluster, like the case (3). In the last case (5), if there exists a new strong connec-600 tion between two cores in two different clusters, then we merge these latter. In order to deal with all these cases, we remove all the affected clusters and re-build a new clustering in a same way of the first clustering presented in Definition 3.6 and using only the affected vertices (cores and borders vertices). The new 605 clustering is performed only on the changed vertices which will be very faster compared to the first clustering. Finally, DISCAN uses the new clusters and the remaining affected vertices to check if they represent new border vertices. Step 3: Merge the new updates. After each batch, each worker 610 starts to merge the new updates (see Algorithm 4 lines 19-23).

  630 is very reduced compared to the initial complexity of DSCAN, Algorithm 4: DISCAN Input : Initial graph G as a text file, parameter (NP number of partitions), a new update U Output: C, B, O /* Global affected vertices and clusters in each worker */ GlobalA f f ectedVertices=∅; GlobalA f f ectedClusters=∅; /* Step 1: Graph maintenance */ /* Update the inital graph in each new update and get the affected vertices and the affected clusters */ Master machine: send a new update u to all workers ; /* In parallel */ foreach Worker i w i ∈ W do Update the current partition according to U ; Get E A ; Recompute the similarities of E A ; Get the immediately affected vertices V I ; Share the immediately affected vertices V I with all workers; Get the indirectly affected vertices V Ind , and the affected clusters C A ; end /* Step 2: Local clustering schema maintenance */ /* Update the old local clustering schema according to the global affected vertices */ foreach Worker i w i ∈ W do Check Core vertices from GlobalAffectedVertices; Check Border vertices from GlobalAffectedVertices; Check affected clusters; Check affected bridges; end /* Step 3: Merge the new updates */ foreach Worker i w i ∈ W do Merge all affected clusters from all workers; Check new Bridge vertices according to the new clusters; Check the remaining outlier vertices; end /* Reset the global affected vertices and clusters in each worker */ GlobalA f f ectedVertices=∅; GlobalA f f ectedClusters=∅; Send C,B,O to master using Worker2Master message; since the number of affected edges |E A | |E| and the number of affected vertices |V A | |V|. In DISCAN, the time complexity is based on three steps: (1) the graph maintenance, which takes O(|E|/n) in the worst case and O = 1 in the best case, 635 where n is the number of partitions; (2) the similarity computation, which takes O(min(|N(u)|, |N(v)|).|E A |); and (3) the clustering step, which mainly depends on V A . Thereby, the incremental clustering complexity is O

  640

Figure 5 :

 5 Figure 5: Impact of the graph size on the processing time of SCAN variants and DISCAN

Figure 6 :

 6 Figure 6: Impact of the partitioning step on DISCAN computation time ( =0.5, µ=3).

Figure 7 :

 7 Figure 7: Impact of the number of updates on the processing time of the pSCAN, ppSCAN and DISCAN ( =0.5, µ=3).

Figure 8 :

 8 Figure 8: Impact of the workers' number on DISCAN processing time ( =0.5, µ=3).

Figure 9 :

 9 Figure 9: Impact of the batch size on the running time of DISCAN ( =0.5, µ=3)

Figure 10 :

 10 Figure 10: Impact of the vertices type (internal or external) on the processing time ( =0.5, µ=3)

Figure 11 :

 11 Figure 11: Performance of DISCAN's graph maintenance and graph reclustering steps ( =0.5, µ=3).

Fig. 11 clearly

 11 Fig. 11 clearly shows a span of the difference between

Figure 12 :

 12 Figure 12: Resources consumption by DISCAN.

Table 2 :

 2 Summary of symbols.

Table 3 :

 3 Graph datasets

	Graph	|V|	|E|	|E|/|V|
	G1: California road network	1 965 206	2 766 607	1.4
	G2: Youtube	1 134 890	2 987 624	2.63
	G3: Orkut	3 072 441	117 185 083	38.14
	G4: LiveJournal	3 997 962	34 681 189	8.67
	G5: Friendster	65 608 366	1 806 067 135	27.52
	G6: web-ClueWeb09-50m 2	428 136 613	446 534 058	1.04

Table 4 :

 4 Exactness evaluation

	Datasets	Youtube	LiveJournal	Orkut	Friendster
	NMI Value	1.0	1.0	1.0	-
	ppSCAN results on all the experimented datasets, expect for
	the Friendster dataset, as this latter was not tested by ppSCAN.
	Like depicted in Table 4, DISCAN ensures the exactness fea-

805

ture.

https://snap.stanford.edu/data/

Acknowledgment

We would like to express our sincere gratitude to the University of Clermont Auvergne and the LIMOS laboratory especially William Guyot, for providing human conditions, lo-


Khaled Hajar
email: khaled.hajar@grenoble-inp.fr

Majid Mehrasa
email: majid.mehrasa@g2elab.grenoble-inp.fr

Antoine Labonne
email: antoine.labonne@g2elab.grenoble-inp.fr

Ahmad Hably
email: ahmad.hably@grenoble-inp.fr

Seddik Bacha
email: seddik.bacha@g2elab.grenoble-inp.fr.

Reza Razi
email: reza.razi@grenoble-inp.fr

Photovoltaics at the electric mobility's service: French case study

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The European Commission has defined a policy framework for 2030 which implies a 40% reduction of CO2 emissions compared to 1990 [START_REF]A policy framework for climate and energy in the period from 2020 to 2030[END_REF]. This entails reducing energy consumption, improving energy efficiency, and increasing the proportion of energy demand met by renewable sources.

PV and EVs are promising technologies for enhancing energy efficiency and using of renewable energy sources in power and transportation networks. Spatial-temporal modeling of PV power generation and EV charging is important for numerous objectives, including urban planning, power grid design and management, when it comes to the deployment, usage, and system integration of these technologies.

However, some challenges remain in the way of EV battery charging, including charging time, charging station (CS) infrastructure, and the impact of these stations on the current electrical power grid. Using rapid charging techniques, the charge period may be decreased to minutes [START_REF] Domínguez-Navarro | Design of an electric vehicle fast-charging station with integration of renewable energy and storage systems[END_REF]. Large electricity demands are imposed on the utility system by these procedures, which have negative impacts in different way. For example, many issues arise when a large number of CSs are linked to the utility grid at the same time, such as overload, voltage instability, and voltage volatility [START_REF] Shareef | A review of the stage-of-the-art charging technologies, placement methodologies, and impacts of electric vehicles[END_REF]. The upgrading of electrical system is one answer to these problems, but it needs a significant expense. A PV system that may operate as a buffer between the EV charging station (EVCS) and the grid is another preferable approach [START_REF] Preetham | Photovoltaic charging station for Plug-In Hybrid Electric Vehicles in a smart grid environment[END_REF].

Fortunately, France has appropriate level of sunshine duration. Most areas have an average sunshine of more than 2000 hour per year and have an average solar-irradiation levels between 2 and 6 kWh/m2 per day [START_REF] Kalyanpur | Gisement solaire en France : caractérisation de la ressource énergétique, profil de répartition et volatilité[END_REF]. However, EVs are usually charged at home at night. A better way to use of solar energy; without the need for expensive battery storage, is to charge vehicles during the day; using a PV arrays at the workplace.

In France, even with the progress of public transportation, approximately 70% of the employees use their own car to go to the workplace each day [6]. In this regard these vehicles are parked the most of the time during working hours. Besides, the number of EVs is increasing massively in France, such that more than 7 hundred thousand EVs are used until those days, and with more than 35% of vehicle market in 2020, while the objective is to reach one million EV at the end of 2022.

On the other hand, in the first quarter of 2021, the manager of 95% of the public electricity distribution network in France, i.e. ENEDIS had more than 100,000 customers connected for individual self-consumption. In fact, private or professional customers, which are equipped with PV panels, have the capability to produce their own electricity demand and consume it for all or part of their uses. For customers living in individual accommodation, the self-consumption share is around 20% [28]. Thus, the customer can benefit in part from the energy produced with its own PV panels and resell the surplus to the network managed by ENEDIS.

Several previous studies have investigated the architecture of an EVCS based on PV [START_REF] Hajar | Smart charging impact on electric vehicles in presence of photovoltaics[END_REF][START_REF] Di Noia | Real Time Scheduling of a Microgrid Equipped with Ultra-Fast Charging Stations[END_REF][START_REF] Ovalle | Escort evolutionary game dynamics application on a distribution system with PV, BSS and EVs[END_REF][START_REF] Fachrizal | Smart charging of electric vehicles considering photovoltaic power production and electricity consumption: A review[END_REF][START_REF] Yousefi | Predictive Home Energy Management System With Photovoltaic Array, Heat Pump, and Plug-In Electric Vehicle[END_REF][START_REF] Ovalle | Grid Optimal Integration of Electric Vehicles: Examples with Matlab Implementation[END_REF][13][START_REF] Turker | Smart Charging of Plug-In Hybrid Electric Vehicles (PHEVs) on the Residential Electric Grid Regarding the Voltage Plan[END_REF]. The advantage of charging EVs with solar energy has been noted in [START_REF] Razi | A User-Friendly Smart Charging Algorithm Based on Energy-Awareness for Different PEV Parking Scenarios[END_REF][START_REF] Barone | Building to vehicle to building concept toward a novel zero energy paradigm: Modelling and case studies[END_REF][START_REF] Turker | Optimal Minimization of Plug-In Electric Vehicle Charging Cost With Vehicle-to-Home and Vehicle-to-Grid Concepts[END_REF], where this structure enables the growth of both technologies. According to [START_REF] Liu | Optimal Scheduling of Electric Vehicle Charging with Energy Storage Facility in Smart Grid[END_REF], the negative consequences of surplus solar energy can be addressed by using it to charge EVs.

Given the highlighted issues, this paper intends to develop a simple and smart technique for EV smart charging in the presence of PV power production. In this context, a conventional method for smart charging of EVs [START_REF] Mehrasa | Power Management of a Smart Vehicle-to-Grid (V2G) System Using Fuzzy Logic Approach[END_REF][START_REF] Razi | Limiting discharge cycles numbers for plug-in electric vehicles in bidirectional smart charging algorithm[END_REF] is the state flow approach based on PV power forecasting with the aim to:

-Reduce peak load on the main grid

- Reduce charging costs - Increase PV self-consumption
The rest of the paper is organized as follows: Section II describes a typical configuration of EV charging station briefly. Section III introduces the proposed smart charging algorithm. Section IV and V present the simulation results and conclusion of this paper.

Charging station model

First and foremost, the standard layout of a EVCS and the roles of various components in it must be introduced. The desired structure is depicted in Fig. 1, which includes the Distribution Operator System (DSO), home or workplace loads, solar arrays, and EVs. The production of solar energy per time slot 𝐸 𝑝 (𝑡) is estimated using HelioClim irradiation database [START_REF]Solar Energy services for professionals[END_REF]. It is assumed that there is a setup with N solar panels. For this purpose, it is obvious that the output power of PV 𝑃 𝑝 (𝑡) is the total power PPV generated by each single PV module [START_REF] Zhou | Current status of researchon optimum sizing of stand-alone hybrid solar-wind power generationsystems[END_REF]. Second, based on the PV panel's efficiency ℰ , the power of a single panel is linked to the sun irradiance according to the following equation:

𝑃 𝑃𝑉 = ℰ × 𝐼𝑟 × 𝐴 (1)
Where 𝐴 is solar panel's area. As a result, if the sun intensity by square meter be 𝐼 𝑟 (𝑡) at time slot 𝑡, the solar power generation can be assumed to be:

𝑃 𝑝 (𝑡) = 𝑁 × 𝑃 𝑃𝑉 (2)
At moment t, we assume that the CS utilizes the produced energy 𝑃 𝑝 (𝑡) to charge EVs. However, if such trading is possible, the CS can also purchase 𝑃 𝑝.𝑜𝑢𝑡 (𝑡) from the grid or sell 𝑃 𝑝.𝑖𝑛 (𝑡) to the grid.

On other side under consideration, there are different time-varying loads with varying and time-varying power needs, depending on the location of CS in residential buildings, workplace, private or public parking lots [START_REF] Razi | A User-Friendly Smart Charging Algorithm Based on Energy-Awareness for Different PEV Parking Scenarios[END_REF]. When the CS is located in a residential situation, as it was illustrated in Fig. 1, the load demand is near zero during the day and reaches its peak during the night. It should be highlighted that, like power generation in solar arrays, load demand contains uncertainties. The load demand is usually predicted using proper algorithm and must be fully met by the other components in the standard structure.

EV plays a significant role in smart charging algorithms due to its nature [START_REF] Ovalle | Grid Optimal Integration of Electric Vehicles: Examples with Matlab Implementation[END_REF][13]. It is evident that the EV's constraints like output power 𝑃 𝐸𝑉 constraint, EV energy 𝐸 𝐸𝑉 constraint and its SOC must be considered as Equations ( 3)- [START_REF] Kalyanpur | Gisement solaire en France : caractérisation de la ressource énergétique, profil de répartition et volatilité[END_REF]. Flexible managing of EV's charge/discharge due to the parking time equal to approximately 90% of their life time, can provide some economical and technical benefits [START_REF] Razi | A User-Friendly Smart Charging Algorithm Based on Energy-Awareness for Different PEV Parking Scenarios[END_REF].

                (5)
The EV's user, the CS's owner, and the grid operator are all actors. In this regard, the driver must give some information regarding the parking time, battery specification, initial and desired state of charge (SOC).

At the end, the grid, as the dominating player, is directly responsible for power balancing among different components in this system. In fact, the grid power 𝑃 𝐺 has to compensate for the shortage or exceed generated power, while satisfying the load demand 𝑃 𝐿 as shown in the following equation:

𝑃 𝐺 (𝑡) + 𝑃 𝑃 (𝑡) = 𝑃 𝐿 (𝑡) -𝑃 𝐸𝑉 (𝑡) (6)
This equation is known as the power balancing equation. In other words, if total power generation is less than total power consumption, the grid injects the difference into the system. In general, the main goal should be reducing the cost of energy exchanged with the grid. In reality, in France the energy price for residential users typically has two different levels. For example, the electricity price for most of applications is 13.46 and 17.99 cents per kilowatt-hour, during normal and peak hours respectively. The feed-in tariff for PV power generation is reassessed every quarter; Table 1 sums it all up according to the last evaluation at the end of 2021.

Proposed rule-based smart charging

It is a fact that proper planning of electrical energy is vital due to the energy crisis and high energy costs [START_REF] Liaqat | Management and Conservation of Electrical Energy in Industrial Units[END_REF]. It improves the system efficiency, resulting in considerable energy savings and cost reductions [START_REF] Bhatti | Energy crisis in Pakistan, adaptation and mitigation[END_REF].

In general, there are two types of smart charging algorithms for EVs: optimization methods [START_REF] Hajar | Smart charging impact on electric vehicles in presence of photovoltaics[END_REF] - [START_REF] Van Der Meer | Energy Management System with PV Power Forecast to Optimally Charge EVs at the Workplace[END_REF] and rule-based techniques [START_REF] Turker | Smart Charging of Plug-In Hybrid Electric Vehicles (PHEVs) on the Residential Electric Grid Regarding the Voltage Plan[END_REF] - [START_REF] Barone | Building to vehicle to building concept toward a novel zero energy paradigm: Modelling and case studies[END_REF]. Optimization algorithms look for available optimum solutions while taking into account objective functions and system limitations.

On the other hand, the rule-based algorithm follows various rules but may not always result in the best answer. This methodology is typically used as a supplementary approach and real-time solution to correct immediate faults because of its minimal computational volume and relatively high response. The suggested energy management strategy is made up of some various rules, mostly in the form of 'ifthen' statements. The 'if' statements are associated with various circumstances, and the 'then' expressions execute the operating modes [START_REF] Huang | A self-learning scheme for residential energy system control and management[END_REF]. These modes carry out the energy transfer among components of the system [START_REF] Liu | A heuristic operation strategy for commercial building microgrids containing EVs and PV system[END_REF].

Mode 1: Grid to load

In this well-known mode, the energy is purchased from the grid when the provided energy from PV is null or not enough to cover the load's demand.

Mode 2: PV to EV

The energy is transferred from PV to EV in this mode. PV power usage is the first priority to reduce the energy received by the grid [START_REF] Goli | PV powered smart charging station for PHEVs[END_REF]. The energy is sent in a power scale higher than 𝑃 𝐸𝑉 𝑚𝑖𝑛 to respect the safety and the health of battery. The quantity of energy transferred from PV to EV fluctuates depending on the scenario. If the PV output power is adequate to meet the EV demand, the EV is charged autonomously and the system is electrically isolated from the grid. As a result, the produced energy by the PV equals the entire energy consumed by the EV.

Mode 3: PV to load

The PV power feed the load local directly to cover its part or full demand. This mode is activated for different cases as follows:

-The EV's demand is null and the load demand can be covered by PV power.

-The EV's demand can be covered by the PV power and it still have an excess of energy to cover a part or full load's demand.

Mode 4: PV to grid

PV to grid energy flow occurs only if PV output power is greater than the total demand of EV's and load. As a result, the quantity of energy transferred is determined by the EV's SOC.

As mentioned, PV output power is purchased by the main grid as shown in Tab. 1. However, it is sold to the grid at 0.043 cents euro lower less than the current grid power price during peak (Fig. 2). This mode is operated in two steps: the DC-DC converter and the bi-directional inverter [START_REF] Van Der Meer | Energy Management System with PV Power Forecast to Optimally Charge EVs at the Workplace[END_REF]. This function is critical in compensating for the economic losses caused by continuous daylight charging at a fixed price.

Mode 5: Grid to EV

In this mode, energy is obtained from the grid to charge the EV at grid price. In this situation, when the PV is unable to meet the EV's demand under the grid overload situation, the grid meets deficit. The quantity of grid energy used to charge an electric vehicle equals the difference between EV demand and PV energy.

Mode 6: Grid at energy user subscription This mode will be activated when the PV couldn't meet the EV demand at first and the load demand at second. At this time the maximum power subscription of the user will be used as the following equation:

𝑃 𝐺 = 𝑃 𝑚𝑎𝑥 -𝑃 𝑃𝑉 + 𝑃 𝐿 (7)

PV power capacity

Price/kWh for the total sale Price/kWh for the sale of surplus energy Less than 3 kWp 0,1756 € 0,10 € Less than 9 kWp 0,1493 € Less than 36 kWp 0,1064 € 0,06 € Less than 100 kWp 0,0925 € Fig. 2 PV and DSO kWh prices

The suggested algorithm (Fig. 3) divides the functioning of a PV-EV-grid system into four major cases. They are classified based on the EV demand and PV power:  Overload: PV power is lower than the EV demand.  Underload: EV demand is available but equal or less than PV power.  Load: EV demand is 0 and PV power is available.  Inert: PV power and EV demand are 0. The overload and underload actions are intended to provide continuous charging at a fixed price. However, in order to compensate for system economic losses, the operation under no load and stagnant is started when specific predefined circumstances are satisfied.

To reach the SOC at departure time as user demand, a reversible calculation technique is elaborated. This technique consists, before executing the algorithm, to draw a line of EV's SOC while full power charging, going backward from departure time until reaching its 0 value. While executing the algorithm if the SOC(t) reaches this line the full power charging is applied to respect the user demand. Fig. 4 shows an example of the Renault ZOE R110 where the driver wants to leave at 5 p.m. with full charge which takes almost 3 hours The next section will discuss different scenarios' results of EV charging during different weather conditions.

Simulation results

In this work, the Renault Zoe R110 is used in our simulation with the specifications shown in Table 2, as the most popular EV in France. As for PV in France, three installation possibilities exist:

 Partial self-consumption with resale of surplus;  Total sale of electricity to an energy supplier;  Total self-consumption.

Today, installing self-consumption solar panels with surplus resale is the most interesting for a main residence. This makes it possible to consume one's own production throughout the life of the solar panels and to inject and resell the surplus kWh produced on the network for a fixed tariff over 20 years. Indeed, in a situation where a house of approximately 100m 2 , if the used energy is entirely electric and if it uses standard electrical equipment (washing machine, dishwasher, dryer, oven, television…) it will need to install 3 kWp of solar panels. This amount of power represents approximately 20 m 2 of roofing and 10 solar panels in all (the number of modules depends however on the nominal power of the chosen photovoltaic panel). In addition, to charge Renault ZOE R110, it needs to use 9 solar panels on average, which represents a power of approximately 3 kWp. During a day of full sunshine, such an installation produces on average the equivalent of 155 km. According to the information above an installation of 6 kWp will be taken in account for simulation. The irradiation data used in simulations to calculate the PV systems performance are getting from HelioClim forecast archives for Lyon city.

Furthermore, the data concerning the residential load are collected from ENEDIS open data center (Fig. 5) while the user power subscription is 9 kVA. Three main simulations, using MATLAB, will be presented for different date. The chosen dates are selected according the PV production intermittence, according to longest and shortest day of the year as for 21 st June and 21 st December respectively. The third simulation deals with uncertainties of the PV power production during cloudy day on the 6 th of April.

In simulations the user plans his departure at 5p.m. as he arrived at 8a.m. to recharge his EV from its initial SOC of 20% to 90%. Charging the concerned EV with 70% of its capacity means that its range increase about 350km. The average distance made by a car in France is about 31km daily. That means that the scenario taking into account can at least let the user drive his EV about 10 days, since this scenario will not be repeated daily.

In the first simulation, dated on 21 st of December, the maximum PV power production reaches 3kW since the sun irradiation is low at this date (fig. 6).

Fig. 6 Simulation results for 21st of December

The simulation shows that, PV power is not enough to charge the EV, then different modes are applied to satisfy the user demand. Mode 1 and Mode 5 are applied from 8am to 9:30am to feed the load and charge the EV, the same application between 3:30pm and 4:30pm. When the PPV rises and still lower than 𝑃 𝐸𝑉 𝑚𝑖𝑛 , the PV feed the load and the grid feed the load with the deficit power in addition of the power to charge the EV using Mode 6 between 9:30am and 11am. As the PPV > 𝑃 𝐸𝑉 𝑚𝑖𝑛 between 11am and 3:30pm, all the PPV is used for charging the EV (Mode 2), and the load purchased the power from the grid at this time (Mode 1). At 4:30, the SOC reaches the SOC tracker line, which in this situation the full power EV charging is applied, purchased from grid to arrive to the desired SOC at departure time (Mode 5). According to cumulus cost calculation the user will be charged about 13€, when there is no excess power to sell it to the grid. On 21 st of July, the PV power reaches its maximum as sun path is clear (fig. 7). It shows clearly that after the full charge of the EV before departure time by PPV using Mode 2, precisely at 2:15, the PV power is used to feed the load (Mode 3). At the same time, the excess of energy is sold to the grid at the specific price (Mode 4). Hence, the bill shows an interesting profit as the cumulative cost for such scenario is about 0,7€. 8 where the intermittence of irradiation has an effect on the PV power. The Load during this day is fed from the grid (Mode 1) after EV's departure time and its arrival time where the system applies Mode 3 to cover the load demand by PV power. Mode 2 gives the opportunity to charge the car from PV power during parking time, unless when the SOCEV reaches the SOC tracker line where the full charge is applied to satisfy the SOC user demand on departure time.

As it was illustrated in the simulation, the proposed algorithm shows how the maximizing PV power use help to reach the final desired SOC at departure time specified by the user.

Conclusion

In this paper, a flow chart technique was developed, using rule-based to control EV charging in residential case in a way of synchronizing the PV power use with. For this importance, the user contributes to the EV charging by pointing out the arrival and departure time and the corresponding SOC.

The charging algorithm combined with the suggested approach selects the most appropriate charging duration, power amount, and power flow direction in this regard. It should be noted that it was possible to simulate another scenario, but taking into account the irradiance intermittence, the shortest and longest days give a global idea of the algorithm technique that can be implemented in real time without any cost calculation. In other words, the constraints used in this case study show the importance of PV's integration to be used in a synchronous way with EV charging. Then, the effectiveness of the proposed technique was proved by bill calculation and the profit that the user can benefit.

Fig. 1

 1 Fig. 1 Desired configuration of charging station

Fig. 3

 3 Fig. 3 Proposed algorithm chart

Fig. 4

 4 Fig. 4 SOC tracker

Fig. 5

 5 Fig. 5 Residential electricity profile coefficient: (Red: static, Blue: dynamic) (Resource: ENEDIS)

Fig. 7 Fig. 8

 78 Fig. 7 Simulation results for 21st of July

Table 1

 1 Feed in tariff for PV in France at the end of 2021

Table 2

 2 Renault ZOE R110 specifications

	Symbol	Description	Value
	𝑚𝑖𝑛/𝑚𝑎𝑥 𝑃 𝐸𝑉 𝐸 𝐸𝑉 𝑛𝑜𝑚	Minimum/Maximum EV power Nominal capacity of EV battery	-22/22 kW 41 kWh
	𝑆𝑂𝐶 𝐸𝑉 𝑚𝑖𝑛/𝑚𝑎𝑥	Minimum/Maximum EV State of charge (SOC)	20%/90%
	𝑃 𝑐ℎ 𝑚𝑖𝑛/𝑚𝑎𝑥	Minimum/Maximum charger power	1,6/15 kW

Acknowledgements This work has been supported by the aVEnir project of the PIA operated by ADEME.