Keywords:

vi

A french version of the abstract is available in the appendix B.

In recent years, it appears that autonomous operation of electrical systems is required. As technologies have evolved significantly since the deployment of electrical networks, their operation and methods have not evolved commensurately. Progress on communication networks and data management could open the doors to a new generation of power systems. The flexibility that can be enabled with these new technologies could radically change the current operation of power grids. Renewable energies, often considered unreliable, also bring their share of complications. Indeed, how to ensure system stability if production and consumption are stochastic? Within unidirectional and rigid systems, this sounds complicated. By considering the end user no longer as a fixed load, but rather as an involved actor, it creates the possibility that new solutions could emerge.

This thesis is devoted to the study of agents called prosumers because they can, via generators based on renewable energy, both produce and consume electricity. It is conceivable that, if their productions are above their own needs, prosumers will seek to sell their surplus. Of course, these surpluses are extremely volatile because they depend on many factors such as the weather at a given time, but also on the consumption of these agents. Since it does not exist, for the moment, accurate real data on the dynamics of these surpluses, the beginning of the thesis was devoted to the modeling and simulation of these prosumers. For this purpose, we used real weather data as inputs. These simulations enabled us to obtain time series describing how the excess productions (positive or negative) evolve for different agents.

The study of these series highlighted nontrivial spatiotemporal correlations which are of great importance for aggregators. As their name suggests, these agents form portfolios of generators, loads, and storage means, in order to sell services to the network operator. These services are intended to maintain the stability of the system, either by frequency regulation or by balancing production and consumption. By aggregating various prosumers, an aggregator may seek to stabilize its capacity. This is important because an aggregator, bound by a contract with the operator, may be subject to penalties if it is unable to fulfill its role. We show in this thesis that the correlation structure between the prosumers has a direct and decisive impact on the stability of aggregations, and therefore the risk assumed by aggregators. Thus, we propose an algorithm to minimize the risk of a set of aggregations, while maximizing their expected gain. The greedy method is based on graph theory and allows significant gains compared to a more random approach.

If the energy market and the interconnections between countries are supposed to help stabilize the system, it is still highly likely that a large increase in storage devices will be required. The placement of these devices in a network where generators and loads are dynamic and stochastic appears as a challenge. Indeed, the nonlinear dynamics of the electricity grid and the multitude of possible disturbances make the existence of a globally dominant placement rather unlikely. It seems more appropriate to seek a strategy with a good performance on average of possible situations. Given the size of the state space, a non-exhaustive method with warranty vii appears to be necessary. We propose to answer this question with an approach based on control theory in networks. We model the electrical system by a network of coupled oscillators, which phase angles dynamic is an approximation of the actual dynamic of the system. The goal is to find the subset of the graph nodes that, during a disturbance of the system, would control it back to the equilibrium if the right signals are injected. We show that these signals can be interpreted as the power to which the storage devices inject or absorb. We then seek the placement that allows minimizing the average control energy. We thus propose a scalable algorithm, based on sub-modular functions, for finding a placement close to the optimum. We also show that there is a limit that forces the worst possible case returned by the algorithm. depending on reliability parameter φ for Gaussian distributions (see equation 4.14). Blue curve with triangles stands for a coalition S with an expected production of 5 units and a standard deviation of 0.5. Under a grid policy of φ = 0.1, it is able to announce a contract value of P CRCT S = 4.36. The same coalition in term of expected production (µ = 5), but with a higher variance (σ = 1.5, cyan curve with circles) can only afford a smaller contract value of P CRCT S = 3.07. The red curve with diamonds stands for a coalition with a higher expected production (µ = 7), but with a very high unpredictability (σ = 5). For low values of φ, this coalition is thus heavily penalized and can only afford a contract of 0.59 units. Under grid policy (φ = 0.1, P M IN = 2), this last coalition is thus not allowed to enter the market (red dot below the horizontal dashed line). . . . . . . . . . 4.11 Gaussian mean approximation (N = 100, φ = 0.1, μ = 5, σ = .5, ρ = 0.2). Subplot a shows how the parameter α of the utility function should be chosen in function of the mean size of the coalitions (see equation 4.20).

Subplot b displays the corresponding utility functions for different values of α. Blue curve with diamonds favors small coalitions of 2 agents while the green one with triangles favors 5 agents coalitions. Finally, the red curve with squares has an optimal size of 15 agents. . . . . . . . . . . 4.12 Histograms of utility values for coalitions of size 3 ( N = 3) in a N = 200 prosumers example (φ = 0.1, α = 0.08, μ = 3.9 M W , σ = 1.9M W , ρ = 0.69). Red bars stand for cliques in the decorrelation graph, and blue bars for all the other possible triples. Cliques tend to exhibit higher utilities than random coalitions. . . . . . . . . . . . . . . . . . . . . 4.13 Utility of random coalitions depending on their size in a N = 200 prosumers example (φ = .1, μ = 3.9 M W , σ = 1.9M W , ρ = 0.69). Blue dots show real mean utility values and the thick red curve its smoothed version by applying a Savitzky-Golay filter. On this plot, α = 0.006, and was selected according to eq. 4.20 in order to favor N = 40 agents coalitions. 4.14 Coalitions formed in the (contract value, volatility) space. The color map indicates the underlying quality. The closer to red the better (high contract values with small volatility). On the opposite, blue areas show poor quality (small contract values with high volatility). Blue dots stand for the decorrelated coalitions that we formed while green squares show correlated coalitions. The smaller yellow markers stand for the gravity centers of the coalition structures. The black dotted line shows how contract values and volatility evolve when the size of the coalitions increases (a subset of the points are labeled by the size of the coalition they represent). Each point is the average over 10 5 unconstrained draws of a random coalition.

We also show the distribution of the gravity centers of random coalition structures with red ellipses (center is the mean, and each ellipse corresponds to one standard deviation). . . . . . . . . . . . . . . . . . . . 4 At t = 800, P 5 goes from -1 to -2 (power inbalance). Consequently, the frequencies θi deviate from the synchronized state. At t = 1000, optimal control inputs (see equation 6.32) are injected at nodes 0, 2, and 4 (nodes with ellipses) such that the system is brought to the synchronized state at time t = 1500 (control time T = 500). . . . . . . . . . . . . . . . . . 8 n D vs the relative standard deviation of the capacity distribution of the batteries σ λ µ λ . The dots are averages over 100 measurements and the curves are obtained using a Savitzky-Golay filter, each color shows the results for a given metric. The graphs are erdos-renyi with N = 100 and p = 0.3, and µ λ = 100 units. . . . . . . . . . . . . . . . . . . . . . . . . . . 7.9 European transmission power grid [START_REF] Tue | The RE-Europe data set[END_REF]. Nodes

Introduction 1.1 Energetic transition

Since the industrial revolution the amount of energy consumed increased continuously, as shown in figure 1.1. Since the world population has also grown in the mean time, figure 1. [START_REF] Ajmone-Marsan | The emerging energy web[END_REF] shows what is happening at the level of the individual (data of figure 1.1 are divided by world population estimates). With the advance of technology, more and more energy is required to secure our living standards, and it seems quite unlikely that this curve will plateau all of a sudden. During the 20th century, countries built impressive systems for delivering power, gaz, and water to the populations. Production techniques evolved such that different sources can be combined. Nowadays, a large portion of the energy that we consume comes from nuclear plants, especially in France. But a non negligible share is still provided by coal or oil based plants (see chapter 2 for more details).

Although these systems work with decent reliability, the necessity for improvements is becoming more and more obvious. There are several well known reasons for this, ecological concerns, progresses in renewables and storage efficiencies, the necessity to renovate old installations, or security to name a few [START_REF] Ajmone-Marsan | The emerging energy web[END_REF] [START_REF] Sarvapali | Putting the 'Smarts' into the Smart Grid: A Grand Challenge for Artificial Intelligence[END_REF]. Indeed, most power systems were built before the information revolution that occurred at the end of the 20th century. The whole architecture was thus not initially thought of as to incorporate information, at least not in the way we use it nowadays.

Power systems are not the same as they were at their early stage though. They indeed evolved with the technology advances so that the real benefits of re-thinking the whole architecture versus the cost of such a huge operation is dividing the community. In a period of budget cuts, should we invest in the renovation of old fossil plants or in the development of renewables and new techniques ?

One of the most known problems of the smart grid vision is perhaps the will of a large penetration of renewables [START_REF] Yan | A Survey on Smart Grid Communication Infrastructures: Motivations, Requirements and Challenges[END_REF] [START_REF] Sarvapali | Putting the 'Smarts' into the Smart Grid: A Grand Challenge for Artificial Intelligence[END_REF]. These generators use natural and free resources such as wind, tides, or solar power instead of fossil ones. Most of these resources are known to be hardly predictable and not necessarily correlated with the consumption curves [START_REF] Van Hulle | Integrating Wind, European project report[END_REF]. In a world where the service rate should be as close as 100% as possible, a system relying only on such stochastic generators seems quite unrealistic.

A reliable power system functioning with distributed renewable energy sources might indeed be hard to imagine when we start thinking about it in more depth. But we might also feel this way because we are so used to the current system that conceiving something completely different is beyond our reach. Not taking the availability of power for granted and organize the consumption in function of the production can be hard to accept when our whole lives where spent the other way around. Is the transition to smart grids a simple upgrade in the technologies, or is it rather a deeper mutation down to the way users perceive the energy ? This thesis focuses on the end users of a smart grid system. We assume that they are equipped with smart meters, storage equipments, and that they own small renewable generators that supply energy to their home appliances. These agents will be called prosumers because they have both the ability to consume and produce power.

Structure of the thesis

This thesis is structured in two main parts that both deal with prosumers, but with a different perspective. Both parts are organized with the same logic. The first chapters for each part (chapter 3 for Part 1 and chapter 6 for Part 2) present the notions and formalism required for the understanding of the rest of the work. Their role is also to locate our contributions in the related literature.

The core chapters for each part (chapter 4 for Part 1 and chapter 7 for Part 2) explain our contributions to the smart grid literature. Hence, the works presented in these chapters are the fruits of our labor unless it is clearly stated otherwise. Although we tried to split clearly our contributions from the state of the art in different chapters, it was sometimes more logical and practical to explain some concepts directly within the contribution chapters. In this situation the references are clearly stated such that no confusion should be possible.

The last chapter of Part 1 (chapter 5) presents currently ongoing work that we chose to include here because it constitutes a natural extension to the contributions made in chapter 4. It relies on concepts introduced in chapter 3 and 4 but requires more tools which are reviewed within chapter 5 itself. Again, the distinctions between the existing literature and our contributions are clearly stated. 1 by population estimates (from [START_REF]Our Finite World[END_REF]).

The two parts of the thesis both require more basic knowledge about power grids, graph theory, complex systems, and smart grids. These are introduced in chapter 2 that follows this introduction. Obviously, no personal contribution is made here, and this chapter should be read as a refresher on these topics. The reader comfortable with these concepts can skip chapter 2 and go directly to Part 1.

Discussed subjects

Understanding smart grid systems requires the study of traditional power grids. Chapter 2 will thus explain the basic architecture of power systems from generation to end-users. However, we will rapidly turn to a complex system framework for their description. Some basic notions of graph theory and complex systems will be presented and later used to better understand the topology of power grids. The last part of chapter 2 introduces smart grid key challenges and its global architecture.

Part 1

As explained briefly in this introduction, the focus of this thesis is on a special kind of end-users called prosumers. Part 1 is devoted to the study of prosumers as they try to sell their production on electricity markets. Chapter 3 define more precisely these prosumers, their importance in the smart grid ecosystem, and the challenges they pose. One of these challenges consists in enabling prosumers to sell their surplus of production. In this thesis, we chose to study such possibility through a market environment, where energy is traded between market participants with the idea of maximizing the benefits while keeping a stable system. Energy markets are already parts of power systems but they are expected to become more significant in the future. They are introduced in the second section of chapter 3.

We will see that, although simple prosumers cannot reasonably enter these markets, aggregations controlled by a central entity could very well be considered as participants. Forming these aggregations with the aim of joining the market and make profits is the task of aggregators (see chapter 3). These aggregators sells a service such as a production capacity for a given period and are remunerated according to the quality and reliability of this service. Eventually, if an aggregator fails to provide the service, some penalties could be applied. Maximizing the benefits necessitates thus to pay attention to the compositions of the aggregations.

Chapter 4 starts by explaining how we simulated prosumer productions and consumptions based on real weather data. The chapter then presents the algorithm that we developed as to form stable aggregations of prosumers for electricity markets. The idea behind this work is to optimize the expected production to risk ratios for the aggregators. This algorithm relies on a special kind of graphs, called correlation graphs, that describe the correlation relationships between a set of variables. The work presented in chapter 4 was done on static correlation graphs although correlation can be seen as a time dependent measure. In chapter 5, we take this into account and study correlation graphs as temporal graphs whose topologies evolve along time. Relying on recent results based on tensor factorization, we study time dependent clusters of correlated variables with some real examples related to energy consumption in power grids.

Part 2

In all chapters of Part 1, the network topologies and power dynamics were abstracted so that we could only focus on the clustering of the prosumers without the constraints of the network connecting them together. The goal of Part 2 is to include these constraints by explicitly considering the grid topology and the power dynamics (in a simplified version). More specifically, we assume in Part 2 a pool of prosumers interconnected by electrical lines. As will become clear later on, this kind of network is quite unstable because of the stochasticity of the prosumers productions and consumptions. The central question of Part 2 is to decide where to place storage elements in the network such that we have the ability to control the system at low energetic costs.

Chapter 6 presents the tools used in chapter 7. It is divided in two main sections about dynamics on networks and control of networks. More precisely, chapter 6 starts by explaining dynamics on networks at large before turning to the power grids. It turns out that the complex and non linear power grid dynamics can be represented, under a few assumptions, by a synchronization model. Chapter 6 explains how this abstraction can be done, and presents a few examples for simple networks. The emergence of synchronization in complex systems has been studied lately and fascinating results have been obtained and will be of great help in chapter 7.

Synchronization of the electrical machines to a common frequency in the power grid is a necessary condition for stability (see chapter 2). If the frequency deviates from the reference value, it can potentially damage elements in the system. The synchronization model described in the first section of chapter 6 can be used to show that such problems can happen when there is an imbalance between production and consumption. Intuitively, a smart grid system with stochastic production and consumption seems quite likely to experience thess kinds of situations, such that some sort of control should be implemented. These control actions, called frequency regulation, are already implemented in current power systems. Nevertheless, a large penetration of renewables calls for new optimized methods.

In Part 2, we study the frequency regulation problem in the case where users are prosumers and the control actions are taken at storage elements distributed in the network. That is, we consider a network of renewable generators and loads whose outputs might change over time. It can very well be the case that generators at t-1 become loads at t and vice versa. The generators and loads of such networks are thus susceptible to change. The problem we address is to find beforehand the best placement for storage elements in this situation. The second section of Chapter 6 provides tools related to control and optimal control theory. Since this is a vast subject, we particularly focus on recent advances on control in networks.

In chapter 7, we use the results of chapter 6 to tackle the storage placement problem. For a power system abstracted in an oscillator network, we develop an algorithm relying on optimal control theory and the optimization of submodular set functions. We show that this algorithm enables us to find placements that require less energy for frequency regulation, even in this stochastic context.

Finally, the last chapter concludes the present thesis by a summary of the contributions as well as an extension to ongoing and future work.

Chapter 2

Smart grids as complex systems

A smart grid can be thought of as an electrical grid coupled with an information system [START_REF] Wang | A survey on the communication architectures in smart grid[END_REF]. Such information system is utilized to organize and insure the proper functioning of the global system. It thus takes information from measurement units (such as smart meters), sends signals to smart appliances, and composes with uncertain renewable energy resources. Obviously, all these operations should be made within stable regions of the power grid state space. Actually, understanding the smart grid challenges necessitates the good comprehension of what power grids are, what they look like, and how they behave. This chapter first presents power grids in a very general manner and introduces concepts of graph theory that will help us understand what they are. Finally, we will introduce in more depth smart grids and related challenges.

Power grids

A power grid is an interconnected network for delivering electricity from suppliers to consumers. Power is produced at generating stations that may be located near a fuel source, at a dam site, or somewhere to take advantage of renewable energy sources. Generating stations are usually located away from heavily populated areas and are usually quite large to take advantage of the economies of scale. This means that the generated power needs to be transported from these generation sites to the wholesale customer, which is usually the company that owns the local electric power distribution network. To decrease the losses in the transmission network, the bulk power is stepped up to high voltage through transformers. At a substation, the power is stepped down from a transmission level voltage to a distribution level voltage. And finally, upon arrival at the service location, the power is stepped down again from the distribution voltage to the required service voltage (see figure 2.1).

Power grids are networks that do not seem random at first glance [START_REF] Giuliano | Towards Decentralized Trading : A Topological Investigation of the Dutch Medium and Low Voltage Grids[END_REF]. Indeed, strong geographical and budget constraints are weighting on the construction of power grids. Generation sites as well as cities, where most of the end users live, are not positioned randomly over a given territory and impact the topology of the grid. Since deploying a substation, a transformer, or an electrical line is expensive, we expect the grid to be the result of some kind of optimization process, even unconscious. For example, it is well known that tree structures are the cheapest topologies still providing connectivity. But at the same time, since redundancy is absent from such structures, they are extremely fragile against failures. Such redundancy over cost tradeoffs are actually typical of engineered systems. Another particularity that might be visible by the eye is that each country is responsible for developing its own network, meaning that there might be large variability across countries, and under-developed interconnections between them.

We clearly need a more rigorous framework to study the topology of power grids. In the next section, we introduce notions of graph theory and complex system theory that will be used throughout this thesis.

Graphs and complexity

Graphs and their representations

A graph G can be defined as a tuple (V, E), where V is the vertex set and E is the edge set. It is also very common to refer to vertices as nodes and to edges as links. In this thesis we use these words alternately without any distinction. In this section, we denote by n = |V | the number of nodes in the graph, and by m = |E| the number of edges. These edges can be directed or undirected depending on the kind of relationships we are trying to model. Directed edges can represent people following each other on Twitter for instance while undirected edges can be used for facebook friendships. Indeed, Facebook requires that both parties agree on being friends while one can follow anybody on Twitter without any approval. Along this thesis, we will restrict ourselves to simple graphs, that is, graphs that do not exhibit multiple edges or self-loops. Unless stated otherwise, a graph will always mean a simple undirected graph.

If a graph has no edges, i.e m = 0, it is called an empty graph. On the contrary, a graph where all possible edges are present, i.e m = n(n-1) 2 for undirected and m = n(n-1) for directed graphs, is called a complete graph. In between these two extremes, a graph is said to be connected if any node can be reached by any other node. In other words, a graph is connected if there exists a path between any pair of nodes. A path is a special kind a walk (sequence of vertices and edges, with both endpoints of an edge appearing adjacent to it in the sequence) where there is no repetition of vertices and edges. A graph that is not connected can be split in a set of connected components, the smallest possible connected component being a single node.

The most basic way of representing a graph is to store the list of nodes and the list of edges. Because most of real world networks are sparse, this method has the advantage of requiring small amount of memory to store a graph. However, a matrix representation, the so-called adjacency matrix, is often used because several graph properties can be deduced from it. Let A be the n × n adjacency matrix of G such that a ij = 1 if node i is connected to node j and a ij = 0 otherwise. Obviously, adjacency matrices of undirected graphs are symmetric and therefore have real eigenvalues and an orthogonal eigenvector basis. This set of eigenvalues is often called the spectrum of the graph and is known to display several interesting properties. Besides, the element (i, j) of A k gives the number of (directed or undirected) walks of length k from vertex i to vertex j. A direct and pretty useful consequence is that the number of triangles N ∆ of an undirected graph G can be calculated by: Chapter 2. Smart grids as complex systems

N ∆ = T r[A 3 ] 6 (2.1)
,where T r[•] is the trace operator (see [START_REF] Schank | Finding, Counting and Listing all Triangles in Large Graphs, An Experimental Study[END_REF] for more information).

For an undirected simple graph, a node i can be connected to k i ∈ [0, n-1] other nodes, where k i is called the degree of node i. For directed graphs, each node i has an in-degree k in i of links pointing to it, and an out-degree k out i of edges departing from it. That being said, another important matrix representation of a graph is the Laplacian matrix L = D-A, where D is the n×n degree matrix (d ij = k i if i = j, and d ij = 0 otherwise). The Laplacian matrix, is symmetric and positive-semidefinite such that it has a positive real spectrum. The smallest eigenvalue of the Laplacian will always be zero, and the number of times zero appears as an eigenvalue is the number of connected components in the graph. This matrix has a long list of fascinating properties [START_REF] Merris | Laplacian matrices of graphs: a survey[END_REF] and is often used for studying complex phenomena in networks [START_REF] Chung | Spectral Graph Theory[END_REF] [START_REF] Newman | Networks: An Introduction[END_REF]. It will be pretty useful later on in this thesis when the subject of synchronization in networks will be tackled.

Characterizing graphs

Although they might seem pretty abstract to some readers, graphs can be used to represent an outstanding number of systems or phenomena. From airports interconnections [START_REF] Hossain | Australian Airport Network Robustness Analysis : A Complex Network Approach[END_REF] to social networks [START_REF] Ahn | Analysis of Topological Characteristics of Huge Online Social Networking Services[END_REF], world wide web topology [START_REF] Dorogovtsev | Evolution of Networks: From Biological Nets to the Internet and WWW[END_REF], or power grids [START_REF] Pahwa | Topological Analysis and Mitigation Strategies for Cascading Failures in Power Grid Networks[END_REF] [79], the network-oriented approach is becoming more and more popular. But once the system has been abstracted into a nice and beautiful graph, what kind of information have we obtained ? For very small graphs, a simple plot might give some interesting information, but when the number of nodes increases above, say, a hundred, one usually obtain a hairy and messy ball that does not really teach us anything. In this context, how can we say that two graphs are similar to each other?

For such systems, a possible solution is to build metrics that captures some property of the network. Then, by comparing these metrics across networks, one is theoretically able to assess whether two networks can be considered as close or not and on which criterion. By just looking at the number of nodes and edges, one can come up with the density measure that captures the fraction of possible edges that are indeed present in the graph:

density(G) = 2m n(n -1) (2.2)
If we consider connected graphs, we know that we can reach any node j from any other node i. Most likely, there will exists multiple walks from i to j, but among them, the one that requires the minimum number of edges is called the geodesic distance between i and j (d ij ). This enables to look at two other natural measures : ,where e(i) is the eccentricity of node i, that is, the greatest geodesic distance between node i and any other node. Basically, these measures capture how spread out the graph is. These three measures give a rough idea of the graph structure, but in most cases this is not sufficiently accurate and more precise quantities need to be computed.

diameter(G) = max i∈V e(i) (2.3) radius(G) = min i∈V e(i) (2.4)
P E R U Z Z I S T R O Z Z I T O R N A B U O N M E D IC I P A Z Z I A C C IA IU O L A L B IZ Z I B A R B A D O R I B IS C H E R I C A S T E L L A N G IN O R I G U A D A G N I L A M B E R T E

Centrality measures

Instead of considering the whole graph, let focus on its parts, i.e its nodes and links. Are every node and every edge equally "important" within a graph ? And what do we mean by "important" ? A centrality measure attributes a real value to each node and/or edges depending on some property that we wish to capture. The most basic node centrality measure, the degree, has already been introduced in the previous sections. The measure enables to rank nodes according to their number of connections. Although simple, this number is in many networks an indicator of nodes' importance.

Figure 2.2 shows the network of social relations among Renaissance Florentine families. Nodes represent families and a link is present between two families if they have business relationships (note that another network with marriage relationships also exists). Among these families, the Medicis were known to be extremely powerful at the time. Some studies used network representations to understand why the medicis where so strong [START_REF] John | 7. Robust Action and the Rise of the Medici, 1400-1434[END_REF]. Here, we are not particularly interested by understanding the shape of the network, but rather the relative importance of its nodes. The right panels of figure 2.2 display different centrality measures as to compare the families. Here, the degree captures the number of business relations that a given family has created. We can see that the Medicis have the greatest degree, but also that the difference with the others is not that large, meaning that there are perhaps other explanations for the Medicis domination. The closeness centrality is defined as :

C G (i) = 1 j∈V d ij (2.5)
, where d ij is the distance between nodes i and j. This metric quantifies how close to all the other nodes a given node is. We can see on figure 2.2 that this metric does not seem to separate clearly the Medicis from the other families.

The betweeness centrality is defined as :

B G (i) = 2 (n -1)(n -2) s =v =t σ st (v) σ st (2.6)
, where σ st is total number of shortest paths from node s to node t, and σ st (v) is the number of those paths that pass through v. Betweenness centrality quantifies the number of times a node acts as a bridge along the shortest path between two other nodes. By looking at figure 2.2, we can see that the betweenness centrality of the Medicis is much larger than for the other families. This means that, in order to communicate efficiently, the families had to pass through the Medicis more frequently than any other family. It has been suggested that this could be an explanation for the Medicis' domination [START_REF] John | 7. Robust Action and the Rise of the Medici, 1400-1434[END_REF].

There exists many more centrality measures for nodes or edges that aim at capturing a specific effect [START_REF] Fontoura | Characterization of complex networks: A survey of measurements[END_REF] [START_REF] Dorogovtsev | Evolution of Networks: From Biological Nets to the Internet and WWW[END_REF]. We only present here another measure which might feel less obvious to the reader. The eigenvector centrality is a measure of the influence of a node in a network. The key idea is that, for a given node i, a connection to another node j with a high centrality should contribute more to the centrality of i than other links to low centrality nodes. It is possible to think of it as a popularity measure, that is, my popularity should depend on the popularity of the nodes I am connected to. Indeed, the famous Google's PageRank is a variant of the eigenvector centrality measure. The Eigenvector centrality of node i can be obtained by looking at the i th component of the eigenvector corresponding to the largest eigenvalue of the adjacency matrix.

Random models

As for now, we looked at graphs in a static way, meaning that we consider relations within a population at a given time and we abstract these into a graph. Nevertheless, we might be interested in understanding how such topologies arised. Indeed, most networks do not appear suddenly with all their properties, they are usually the result of a long process of additions and removals (nodes and/or links). Take a social network for instance. At the beginning, only very few people are present, the so-called early adopters, but as time goes on, more and more people subscribe and begin to form ties with already present persons.

A key point in graph theory was the discovery of random graph models by the physicists Paul Erdös and Alfréd Rényi in 1959 [START_REF] Erdds | On random graphs I[END_REF]. Their model builds a network from a set of nodes by assuming that all nodes are equally likely to link together. More precisely, one considers all possible pairs of nodes and link them with a given probability p. Obviously, if p tends to zero the graph tends to an empty graph, and if p tends to one, the graph tends to a complete graph. In between, Erdös and Rényi discovered the different values at which different phenomena occur. shown that if p > 1/n then the graph will contain almost surely a giant component. For smaller values of p, the network will only contains isolated nodes and small components as visible on the two left most subplots of figure 2.3. Moreover, if p > ln(n) n , then the graph will almost surely be connected (see subplots 3 and 4 of figure 2.

3).

This model is extremely important in complex systems theory since it gives a null hypothesis. That is, if a graph is shown to be close to an erdosrenyi graph, one can presume that the underlying process that gives rise to this graph is mostly due to randomness. A natural question that we can ask now is: are real networks random ? Very interestingly, the answer tends to be almost always negative [START_REF] Mark | Random graphs as models of networks[END_REF], meaning that real world networks are not the results of pure noise, but rather the outcomes of underlying hidden processes.

An erdos-renyi random graph has on average p n 2 edges and the distribution of the degree of any vertex is binomial :

P [k i = k] = n -1 k p k (1 -p) n-1-k (2.7)
which tends to a Poisson distribution when n → ∞ and np = Cste. This means that nodes degrees are quite homogeneous and that large deviations from the mean degree are extremely unlikely. This is a first point which can let us think that most real networks are not random [START_REF] Mark | Random graphs as models of networks[END_REF], because they tend to have very heterogeneous degrees [START_REF] Barabási | Emergence of Scaling in Random Networks[END_REF]. A very few nodes have often very large degrees while the rest has relatively small numbers of connections.

The most famous networks exhibiting this kind of property are the internet, the world-wide-web, or the airport network. More precisely, it is known that their degree distributions can be put as a power-laws [START_REF] Barabási | Emergence of Scaling in Random Networks[END_REF] :

P [k i = k] ∼ k -γ (2.8)
where γ is a parameter whose value typically ranges between 2 and 3, and are usually called scale-free networks. Power-law distributions are not specific to networks and can be found in many diverse domains. For instance, it has been shown that the wealth of populations tends to follow powerlaws. There exist very nice models that explain and reproduce the scalefree effect. They usually rely on the "rich get richer" principle as to mimic the large inequalities that come from power-laws. For graph theory, the Chapter 2. Smart grids as complex systems Barabasi-Albert preferential attachment model. Nodes sizes are proportional to their degrees. Barabási-Albert model is one of several proposed models that generates scale-free networks [START_REF] Barabási | Emergence of Scaling in Random Networks[END_REF]. It incorporates two important general concepts: growth and preferential attachment. Basically, nodes are added one by one and the probability that a new node j connects to an older node i is proportional to the degree of that node p i = k i v kv (the sum goes over all existing nodes). Because of preferential attachment, older nodes tend to accumulate more connections than younger ones, forming hubs. Figure 2.4 shows a small example of a growing network with preferential attachment. Every time a node is added, it connects to δ old nodes (δ = 2 in figure 2.4) with a biased probability toward high degree nodes. It is clearly visible that old nodes, e.g nodes with small labels, tend to have more connections that new nodes.

By looking at social networks, it seems clear that neither ER or BA models are able to capture their true underlying structures. The BA model captures well the degree distribution, but misses more complex structural properties. Indeed, nodes of real networks do not necessarily connect only based on degree. For instance people do not necessarily become friends with the most popular person in the network if they do not know each other. They rather tend to connect to people they know. And since it is likely that two of my friends have met and are friends themselves, local triadic structures are extremely common in real networks, especially social networks. The clustering coefficient is a way of measuring the importance of triangles within a graph and can be computed either globally or locally :

C GLOB = 3 × N ∆ N V (2.9)
where N ∆ is the number of triangles in the graph, and N V is the number of connected triplets. C GLOB basically computes the portion of closed triplets over the total number of triplets. The local clustering coefficient of a vertex i in a graph G(V, E) quantifies how close its neighbors are to being a clique :

C i = |{e jk : v j , v k ∈ N i , e jk ∈ E}| k i (k i -1) (2.10)
where e jk is the edge from node j to node k, and k i is the degree of node i. This measure was introduced in 1998 by Duncan Watts and Steven Strogatz who observed that some real networks (especially social networks) exhibit both a small average shortest path length and a high clustering coefficient [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF]. This observation is at odds with ER networks that do not have such clustering. Watts and Strogatz then proposed a novel graph model, often called the small-world model, that reproduces these characteristics [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF].

The idea of the model is to start from a large world such as a lattice of locally well connected nodes. This starting point has a high clustering coefficient but a large average shortest path (see figure 2.5). The model then re-wires a fraction p of the links to some randomly chosen nodes. Clearly, if p = 0 we still have the lattice, and if p -→ 1 we tend to obtain a random ER network (see figure 2.5). Nevertheless, in between these two extremes, we see on figure 2.5 that the average shortest path length decreases much more rapidly when p increases above zero than the clustering coefficient. This means that for a region of relatively small p values, we obtain a graph which has both a low average shortest path length as well as a high clustering coefficient.

Community structures

The small-world model captures the small distance, yet, highly clustered topologies of some real networks such as social networks. However, when comparing, even by eye inspection, small-world networks to real social networks, it seems that something is missing. Indeed, social networks seem to have much more complicated underlying structures with regions of high density of links and regions with very few links. These clusters of well connected nodes are often called communities in complex system theory, and a whole branch is devoted to uncover them in large graphs. The first idea that might come into mind for detecting communities is to minimize a graph cut function that basically indicates how many edges lie in between groups. However, methods relying on cut functions were shown not to perform well. Indeed, the basic cut placing all nodes in one group and none in the other always minimizes the cut function but is of little use. There has been multiple suggestions in order to penalize this result and force the algorithm to perform non trivial cuts. But, most of these methods require special knowledge about the partitioning such as the sizes Chapter 2. Smart grids as complex systems of the communities. It turns out that cut functions might be not the most suited functions for community detection :

The fundamental problem with all of these methods is that cut sizes are simply not the right thing to optimize because they don't accurately reflect our intuitive concept of network communities. A good division of a network into communities is not merely one in which the number of edges running between groups is small. Rather, it is one in which the number of edges between groups is smaller than expected.

Mark Newman in [59] (2006)

This is a significantly different approach to community detection that led Newman to propose another objective function called the modularity [START_REF] Newman | Finding community structure in networks using the eigenvectors of matrices[END_REF], which is widely used nowadays. Modularity is the fraction of the edges that fall within the assumed communities minus the expected such fraction if the edges were distributed at random :

Q = 1 (2m) vw A vw - k v k w (2m) δ(c v , c w ) (2.11)
where δ(c v , c w ) = 1 if node v and w belong to the same community and δ(c v , c w ) = 0 otherwise. Finding both the number of communities and partition of the nodes requires an algorithm for optimizing Q. One of the mostly used methods is the Louvain algorithm, but several other methods have been developed (Label propagation [START_REF] Nandini Raghavan | Near linear time algorithm to detect community structures in large-scale networks[END_REF], clique percolation [START_REF] Palla | Uncovering the overlapping community structure of complex networks in nature and society -Supplementary[END_REF], Walktrap [START_REF] Pons | Computing communities in large networks using random walks (long version)[END_REF], spectral methods [START_REF] Newman | Spectral methods for community detection and graph partitioning[END_REF], maximum likelihood estimation [START_REF] Yang | Overlapping Communities Explain Core Periphery Organization of Networks[END_REF]...).

In order to evaluate the performance of community detection algorithms, one need to compare the results with the true structure. In most networks, this ground truth might not be accessible such that models were developed as to reproduce these graphs from a known community structure. A widely used model for this purpose is the planted partition model, where nodes are assigned to communities and links are added afterwards. In this model, there are two different probabilities :

• p in : probability of having a link between two nodes within the same community

• p out : probability of having a link between two nodes in different communities.

Figure 2.6 shows the resulting graphs for a small example with 4 communities of 20 nodes each. When p in is similar to p out , the resulting graph is mostly random with no real community structure. When p in is larger than p out , communities start to appear and become more and more separated as p in increases. The case where p out > p in basically means that nodes within the same community are less likely to connect that nodes in different communities. However this might not make much sense at first glance, anti-communities have received more attention lately [START_REF] Yu | A New Method for Detecting Anti-community Structures in Complex Networks[END_REF] [START_REF] Newman | Finding community structure in networks using the eigenvectors of matrices[END_REF].

These definitions and models still have some limitations. For example, we made the implicit assumption that a node could only belong to a single community although this might not be true in the reality. Actually, in social networks people most often belong to multiple communities (family, friends, work colleagues, associations, and so on...) [START_REF] Yang | Overlapping Communities Explain Core Periphery Organization of Networks[END_REF]. Obviously, if two nodes share multiple communities they become much more likely to be connected. Figure 2.7 shows an example of such overlapping community structure. The network of figure 2.7 was constructed with 3 different communities of different sizes (blue, red, and green), but nodes can belong to more than one group such that we observe smaller but more densely connected clusters at the intersections of the communities (nodes in white are involved in all communities). Detecting overlapping community structures has attracted much attention lately, and multiple solutions have been proposed [73] [93].

This section was devoted to give to the non specialist reader the necessary information to read the rest of the manuscript and is not intended to be a complete state of the art of the complex system theory, a task that is way out of the scope of this thesis. The interested reader could refer to very complete and well-written survey on the subject [START_REF] Newman | Networks: An Introduction[END_REF] [START_REF] Fontoura | Characterization of complex networks: A survey of measurements[END_REF]. The next section will use some of these complex system concepts to study power grid topologies.

Power grids as complex networks 2.3.1 Abstracting the topology

As explained in the introduction part of this chapter, power grids are usually divided in 4 different parts (see figure 2.8) :

• Generation : Installations where power is generated. In order to be sent over long distances, power is elevated to high voltages through transformers and injected in the transmission network.

• Transmission : Most transmission lines are high-voltage three-phase alternating current (AC). High-voltage direct-current (HVDC) technology is used for greater efficiency over very long distances, for submarine power cables, or for interchange of power between grids that are not mutually synchronized. Electricity is transmitted at high voltages (115 kV or above) to reduce the energy loss which occurs in longdistance transmission.

• Distribution : Carries electricity from the transmission system to individual consumers. Distribution substations connect to the transmission system and lower the transmission voltage to medium voltage ranging between 2 kV and 35 kV with the use of transformers. Primary distribution lines carry this medium voltage power to distribution transformers located near the customer's premises. Distribution transformers again lower the voltage to the utilization voltage of household appliances and typically feed several customers through secondary distribution lines at this voltage.

• Customer : The end-user of the electricity. Residential and most commercial customers have classic needs and are connected to the secondary distribution lines. However, some professional customers whose business requires larger amount of power may be connected directly to the primary distribution level or the transmission level. Although power grids include heterogeneous structures, it seems appealing to represent them as abstract graphs where edges represent electrical lines and nodes any kind of elements that may be at the end of a line (generators, transformers, substation, loads...). With this approach, it was shown that transmission networks exhibit very different topologies from distribution ones [START_REF] Hines | Do topological models provide good information about electricity infrastructure vulnerability?[END_REF] [71] [START_REF] Hines | The topological and electrical structure of power grids[END_REF]. While the later tend to be tree-like (or locally tree-like) with only few redundant links, the former exhibit a mesh structure. Intuitively, because power grids are hierarchical structures, we expect that a failure in the transmission grid would result in far worse damages than a failure in one of distribution systems. Operators have therefore invested more money in increasing the redundancy within transmission than distribution systems.

Such an important difference between transmission and distribution led the scientists to study them apart. Although more and more data are getting public these days, it should be noted that for a very long time very few reliable data sources were available concerning power grids. A consequence is that most topological studies focus on the transmission network which is often easier to obtain than distribution local networks.

Are power grids similar to other networks ?

A first question that one usually tries to answer when studying a graph is to understand whether it is the result of some underlying process or the pure product of randomness. In the case where the network is not random, finding other well-studied networks that exhibit similarities could potentially lead to a better understanding. The following results may not be true for every possible sample of power grids since there exists a large amount of them and some may have specific characteristics. We review here the tendency that emerges when compiling the literature on the subject.

Several measures indicate that power grids (at any voltage level) have little in common with Erdös-Rényi random graphs. This point is quite clear and universal across the literature [START_REF] Giuliano | The Power Grid as a complex network: A survey[END_REF]. For example, the diameters of power grids tend to be much larger than for ER networks. It was also shown that the degree distributions of power grids tend to be exponential. That is, the node degrees within power grids tend to be quite homogeneous. This particularity is in strong opposition with scale-free networks such as the internet or the WWW, where some nodes have very large degrees.

If power grids are neither random nor scale-free, researchers then tried to check whether they were small-world. In general, the various studies tend not to have a common answer for this question [START_REF] Giuliano | The Power Grid as a complex network: A survey[END_REF]. It is indeed very specific to the samples analyzed and no general conclusion can be drawn. This is especially true for the High Voltage grids, while the Medium and Low Voltage networks seem far from being small-world networks.

Are power grids robust ?

Robustness is the ability of a system to tolerate failures or attacks. Failures are usually supposed more or less random while attacks are the results of a strategy aiming at maximum damages. These two concepts are very different and some networks, such as scale-free networks, tolerate random failures very well while they are extremely vulnerable against hub-oriented attacks. For power grids, the same behavior has been observed, they tend to bear random failures while being vulnerable to high degree or high betweeness oriented attacks.

That being said, there are multiple ways to account for robustness. Static approaches remove a certain fraction of the nodes or edges and look at the size of the giant connected component [START_REF] Osman Ya Gan | Robustness of power systems under a democraticfiber-bundle-like model[END_REF] [START_REF] Zhang | Optimizing the robustness of electrical power systems against cascading failures[END_REF]. As nodes are removed, the size of the giant component goes to zero at some point. The nature of this transition is of particular interest since it has been shown that, depending on the topology and the attack, a discontinuous (first order) or a continuous (second order) transition can occur.

Percolation in complex networks [START_REF] Cohen | Complex Networks[END_REF] appears as a convenient framework for studying cascades. Although several works have considered such approaches for power grid robustness, it has been suggested that they were not capturing the reality really well [START_REF] Hines | Do topological models provide good information about electricity infrastructure vulnerability?[END_REF]. Indeed, power grids have static topologies but dynamic behaviors occur within this topology since electricity is flowing along the edges (see chapter 6 for dynamics on networks). Not taking this into account may lead to inaccurate conclusions.

Although most power systems are built to sustain the loss of any single component (the so-called "N-1" rule), large blackouts are well-known phenomenon that occur once in a while. Usually, blackouts do not happen due to the loss of some fraction of edges or nodes. They rather are the result of a cascading process when the failure of one component leads to the failure of one or more other components and so on. When a line fails (because of a tree fall, heat, or overcapacity for instance), the power that was flowing along this line is redistributed on adjacent lines according to Kirchoff's law. These lines could in turn become overloaded and fail and so on. Depending on the initial failure, the topology, and the utilization of the lines, a cascade could die out quickly or spread to a non negligible portion of the network. Eventually, the cascade brings the whole network down. Multiple studies have investigated the robustness of power grid with this approach by using betweeness centrality or more electricity-specific measures [START_REF] Rosas-Casals | Topological Vulnerability of the European Power Grid Under Errors and Attacks[END_REF] [72] [START_REF] Simpson-Porco | Voltage collapse in complex power grids[END_REF].

Smart grids

Toward a renewable production

One of the most important goals of the 21st century consists in changing radically the way our society produces energy. The traditional way based on fossil energy is becoming tenuous as fossil deposits are becoming scarcer and scarcer while the demand keeps increasing over the years. Increasing the penetration of renewables into the production portfolio has clearly been displayed as a crucial objective by politicians and scientists. Nevertheless, recent facts from Germany have shown that using more renewables could increase the amount of CO2 released in the atmosphere. As contradictory as it may seem, fast ramping coal plants had to be used in order to compensate for wind power fluctuations.

Renewable energies such as wind or sun power, despite of being "free and clean", pose indeed numerous challenges [START_REF] Sarvapali | Putting the 'Smarts' into the Smart Grid: A Grand Challenge for Artificial Intelligence[END_REF]. First of all, generators based on these energies cannot be scheduled like traditional power plants. They produce when the resource is active, which might not coincide with the moment when consumers desire to use energy (see chapter 3). Furthermore, fluctuations are stochastic and hardly predictable such that a strong increase in flexibility for future power systems is required [START_REF] Huber | Integration of wind and solar power in Europe : Assessment of fl exibility requirements[END_REF].

The first idea that might come to mind is to store the electricity when it is abundant for discharging it later when it becomes scarce. Although a useful idea, it has been argued that this approach as a large scale solution would not be viable. Electricity is indeed a quantity that does not store really well, Chapter 2. Smart grids as complex systems and most storage devices are far from perfect and have a finite number of life cycle. In addition to the huge losses, the costs (installation and maintenance) for such a large scale storage system would be prohibitive.

Demand-Side Management and Dynamic pricing

It appears that changing the way we produce requires that we change both the way we handle electricity and the way we consume it. These parts can no longer be (almost) independent of each other, but rather linked through information. Using sensors deployed across the system for monitoring its state is nothing new, but the information flows from the base to the top while electricity moves in the opposite direction. Imagine that both could flow in both directions : operators could send real time information to enduser and see their reactions, while bi-directional power-flows could open the doors to local generation-consumption cycles with less losses.

The feasibility of such bi-directional systems is still under investigation, especially for large scale systems. Nevertheless, smart meters, which provide the interface between the end-user and the system, are deployed at an accelerating rate. In addition to the fine grain records of the consumptions, these units will be connected to the smart appliances of the house and be able to control them to some extent. The idea is to incorporate the end-user in the system by no longer considering it as a dead load, but rather as some signal-responding entity. End users have usually different kinds of loads. Some appliances, such as TV, lights, or oven for instance should clearly be available on demand. One can indeed hardly imagine the TV going off in the middle of a film because of the grid operation conditions... However, other kind of appliances like washing machines, air conditioners, or heaters for example are delayable to some extent. That is, users might not care at the exact time the machine is started as long as it finishes at a given time. For air conditioners, users are usually only concerned with the temperature of their home when they are present.

It has been suggested that having a dynamic price (DP) for electricity could help reverberate the production conditions on the end users [START_REF] Shengrong Bu | Dynamic pricing for demand-side management in the smart grid[END_REF] [START_REF] Logenthiran | Demand side management in smart grid using heuristic optimization[END_REF] [81] [START_REF] Gabriel Gast | Impact of Demand-Response on the Efficiency and Prices in Real-Time Electricity Markets[END_REF]. That is, periods when the expected production is supposed to be larger than the consumption, users could face a small price and conversely for peak consumption periods. Smart meters receive these upcoming variable rates and schedule delayable loads as to take advantage of them. Demand-Side Management (DSM) is currently an active research area where multiple data analysis and machine learning methods are implemented as to make the meters more efficient and autonomous [START_REF] Panagiotis | Big Data Analytics for Dynamic Energy Management in Smart Grids[END_REF] [START_REF] Young | Leveraging Big Data to Develop Next Generation Demand Side Management Programs and Energy Regulations Recent Research Methods Focusing on Dynamic Market Analysis[END_REF].

Electric vehicles

An important challenge comes from the fact that the portion of Electric Vehicles (EV) is supposed to grow in the upcoming years [START_REF] Sarvapali | Putting the 'Smarts' into the Smart Grid: A Grand Challenge for Artificial Intelligence[END_REF]. If, in the future, the whole population is equipped with EV, the induced load on the system will be huge and poses great challenges. For example, it is known that most people commute in a correlated fashion. They go to work in the morning and come home in the evening. It means that, if nothing is done, the amplitude of the already expensive and problematic morning and evening peaks will increase even more. Furthermore, it has been pointed out that unexpected correlated behaviors (football match, clearance sales...) could create bottlenecks in the grid. That is, some unexpected crowd drives to some specific location and put their vehicles in charge, thus creating a load that the system might not be able to handle.

If EVs seem to create problems, they could also provide solutions. Because an EV is basically a moving battery, it could be used as an emergency reserve. This can be the case for the owner of the EV that faces an outage and still want to consume meanwhile. But this could also be used for grid stability through the Vehicle to Grid (V2G) technology. V2G consists in allowing EV, against remuneration to the owners, to discharge into the grid when there is an emergency [START_REF] Jansen | Architecture and Communication of an Electric Vehicle Virtual Power Plant[END_REF]. Although a beautiful idea, it has been argued that rebalancing production and consumption with V2G was not realistic. However, V2G could very well provide a mean for frequency regulation.

Toward a more distributed system

Actual bulk power generation sites are located far away from consumption areas yielding important losses during the transport. They are also large and not many such that they constitute strategic points whose failure would be catastrophic. By exploiting renewable energy sources closer to the consumption, losses could be reduced. These Distributed Energy Resources (DER) could also provide more flexibility and resilience to the system because the loss of a single DER would have much less impact than the loss of a plant.

Microgrids are small subsystems composed of DER, loads, and storage units that are connected to the main grid through the point of common coupling (PCC) [START_REF] Zhang | Robust energy management for microgrids with high-penetration renewables[END_REF] [START_REF] Erol-Kantarci | Reliable overlay topology design for the smart microgrid network[END_REF]. The idea behind microgrids is that they could disconnect from the main grid and operate in islanding mode [START_REF] F D Kanellos | Micro-Grid Simulation during Grid-Connected and Islanded Modes of Operation[END_REF]. Such islands could then continue to operate on their own without pumping power from the endangered grid. These islandings could decrease the load on the main grid meanwhile the operator restores a stable state. There has been a lot of studies on the possibilities that come with microgrids. Superislanding methods, for example, assume that microgrids are able to disconnect in groups and share energy together [START_REF] Pahwa | Topological Analysis and Mitigation Strategies for Cascading Failures in Power Grid Networks[END_REF] [START_REF] Erol-Kantarci | Reliable overlay topology design for the smart microgrid network[END_REF]. In this manner, microgrids which have an excess of production could feed other microgrids where there is a production deficit.

Electric vehicles, microgrids, or prosumers are representative concepts of the emergence of a new decentralized system. Studying these systems where divergent interests come into play has been tackled with success by using game theory [START_REF] Saad | Game Theoretic Methods for the Smart Grid[END_REF] [START_REF] Nguyen | A game theory strategy to integrate distributed agent-based functions in smart grids[END_REF]. Coalitional game theory for example can be used to study whether multiple microgrids would have a common interest in forming a super-island. The core idea is that, by forming coalitions, agents achieve better payoffs than when playing alone. However, the mechanism by which a coalition re-distributes the profits to the agents is paramount for its stability. Indeed, if agents realize that another organization would increase their gains, they will probably leave the current coalition. Finding the stable coalition structure that maximizes the social welfare is often the objective although it is known to be a hard problem [START_REF] Aziz | Complexity of Coalition Structure Generation[END_REF]. Assessing the stability of a given game is one of the main strengths of this framework, and may be one of the reasons for its popularity in the smart grid literature.

Smart grid architecture

Although smart grids are still new systems under active development, a general layered architecture seems to be accepted by the community (see figure 2.10). The bottom layer contains all physical components that generate, exchange, and consume power. On top of this, a control layer uses the information acquired by sensors such as Phasor Measurement Units (PMU) to maintain a stable system. The top layer implements the services such as energy markets. This schema is of course very general and each layer can be sub-divided in multiple sublayers with different time scales. This very general architecture gives a rough idea about how the different components are organized. However, it does not tell us how the different subsystems should be built. Although the power grids will surely need to adapt to this new system, the communication network has received a lot of attention lately [START_REF] Wang | A survey on the communication architectures in smart grid[END_REF]. Its architecture [START_REF] Negeri | Architecting the Smart Grid As a Holarchy[END_REF], supported technologies [START_REF] Yan | A Survey on Smart Grid Communication Infrastructures: Motivations, Requirements and Challenges[END_REF], and even specific protocols [START_REF] Lloret | A Group-Based Protocol for Improving Energy Distribution in Smart Grids[END_REF] are currently developed and improved.

Smart grids appear as complicated systems that have multiple dependencies. Understanding whether such systems are possible, viable, or robust is one of the main questions in the field and will probably require extensive use of models and experimentation to find answers. Because human beings are part of this system, complex multi-disciplinary models mixing power engineering, complex system theory, economics, game theory, sociology, psychology, and so on, need to be developed. The most basic inputs might indeed not have the expected large scale effect. If attention is not paid to understanding the system in depth, unexpected and devastating effects may occur. Dynamic pricing for example provides some sort of control on the consumption, but the mechanism by which individuals respond to such prices is way more complex than for typical dynamic systems. Wanting to delete an evening peak by increasing the prices and scheduling lower rates later in the night, can very well result in delayed consumption peaks in the middle of the night when the production is at its lowest.

Discussion

We can see that the smart grid, in order to be a viable solution, would require several important changes to the actual power grids. As explained in the introduction, we focus in this thesis on the end-user who is expected to change radically. The user of the future will posses small DER units, storage equipments (EV, batteries...), as well as smart appliances optimizing their consumption according to variable rates sent by the operator. Obviously, these agents will behave in specific and still unknown ways.

This chapter presented important notions for understanding the rest of the thesis. Due to space constraints, we had to make a drastic selection on what to include in this opening chapter, such that it only gives a high-level overview of the fields. The interested reader is refered to the references to get a more precise idea about these topics.

We now turn to the first part of this thesis related to prosumers and electricity markets. In chapter 3 of Part 1 we discuss more extensively the concept of prosumers and provide the formalisms and methods to support such environments.

Part I

Formation of Stable Coalitions for Electricity Markets

Structure of Part 1

The first part of this thesis is devoted to study the formation of coalitions of prosumers in the smart grid. The objective is to enable prosumers to sell their extra-production on electricity markets. We propose in this part an aggregation method based on the correlation between the prosumers. The main idea consists in grouping uncorrelated agents together in such a way that the obtained coalitions have a high productivity with a relatively low risk. This part is organized in three chapters. Chapter 3 presents the concepts of prosumers, energy markets, aggregators, and correlation graphs that we will use extensively later on. Chapter 4 constitutes the core of this part and presents our work on the simulation of prosumers and the formation of coalitions. This chapter is basically a summary of two publications that we made in 2015 [START_REF] Gensollen | Coalition formation algorithm of prosumers in a smart grid environment[END_REF] and 2016 [START_REF] Gensollen | Stability and Performance of Coalitions of Prosumers Through Diversification in the Smart Grid[END_REF]. Finally, chapter 5 presents ongoing work on dynamic correlation graphs. Although it is not published yet, we chose to include this more recent work in this part because it is a natural extension of the work done in chapter 4 on static correlation graphs.

Chapter 3

Prosumers and Market Aggregators

In this chapter, we introduce the required concepts that we will use in chapter 4. We explain in section 3.1 what prosumers are and their role in the smart grid environment [START_REF] Grijalva | Prosumer-based smart grid architecture enables a flat, sustainable electricity industry[END_REF]. We will show that prosumers might be able to sell their own production, when available, on electricity markets [START_REF] Parag | Electricity market design for the prosumer era[END_REF]. Section 3.2 explains how these specific environments work. A point that we argue in this thesis is that, because of their size and stochasticity, prosumers alone might not be allowed to enter these markets. We wish to show in this first part of the thesis that proper aggregations of prosumers [START_REF] Negeri | Architecting the Smart Grid As a Holarchy[END_REF] are preferable both in terms of production and reliability. Therefore, we give in section 3.3 some notions about market aggregators and portfolios. We specifically review in details the Markowitz's portfolio theory that exhibits similarities with our approach. We also point out limitations of the portfolio theory that motivated us to find alternative approaches. In section 3.4 we introduce correlation graphs as a way to represent the correlation structure of a pool of variables by using graph theory related tools. These types of graphs will be used in our work presented in chapter 4.

The Prosumers

Nowadays, power grids are essentially top-down hierarchical architectures with few centralized power plants. This is especially true in France where a large majority of the production comes from nuclear power plants (see figure 3.1). In such a system, the consumption for the next days is predicted and production is scheduled accordingly with safety margins. The end user is then completely passive and consumes when he needs to. Because people tend to consume more when they are at home, this leads to well-known consumption peaks occurring in the evening and, to a lesser extent, in the morning. This has numerous consequences among which the fact that the plants and the networks are dimensioned according to these peaks, which is expensive.

One of the major goals of the smart grid is to increase significantly the share of renewables in the production portfolio [START_REF] Yan | A Survey on Smart Grid Communication Infrastructures: Motivations, Requirements and Challenges[END_REF]. In addition to their stochastic natures, DER usually cannot be scheduled and only produce when the resource is active, which may not coincide with the consumption peaks. This is striking when thinking about solar power. The production peak (expected around 12 am to 3 pm) lies right in-between the morning and evening consumption peaks [START_REF]Nice Grid[END_REF] (see figure 3.2). At this point, there are two ways of thinking: either acting on the production side by deploying storage or increasing the capacities and the interconnection, or acting on the consumption side. Thanks to the ability of the smart grid to vehicle information, the grid operators have the possibility to transfer the production conditions on the end users. Dynamic pricing and demand-side-management are indeed technologies that could sensitize consumers to the real time state of the system. Elastic loads could hence be delayed to off-peak periods saving money on both sides [START_REF] Shengrong Bu | Dynamic pricing for demand-side management in the smart grid[END_REF] [50] [START_REF] Samadi | Advanced Demand Side Management for the Future Smart Grid Using Mechanism Design[END_REF].

But the idea goes even further. It is indeed likely that, at some point, people will invest in small personal or residential DER. At the time this thesis is written, it is already an ongoing process with solar arrays deployed on roof tops every day. The idea is simply to reduce the electricity bills by taking advantage of the free resources, that is, using one's own production to satisfy their consumption. Here, we will refer to these agents, that both consume and produce, as prosumers [START_REF] Dinusha Rathnayaka | Prosumer Management in Sociotechnical Smart Grid[END_REF]. If a prosumer produces more than he consumes, there are a few possibilities :

• Consuming more by delaying some loads initially scheduled further in time.

• Storing the surplus of production for using it later.

• Selling the surplus.

• Spill the surplus (turning off some DER).

Obviously, the last possibility is the one that a prosumer will use in last resort since it is wasting resources. The first two are totally legitimate solutions although they might not always be possible. A prosumer might 00:00 01-Dec 03:00 06:00 09:00 12:00 15:00 18:00 21:00 0 indeed have no load to delay and a full battery. Additionally, since storages are not perfect, a prosumer might be willing to sell power even if its storage is not full, depending on the current selling price.

There is a clear necessity to design comprehensive information systems such that the prosumer operations are supported, simplified, and automated as much as possible. It is also crucial that such agents do not endanger the system stability by tacking crazy actions or using it unexpectedly. Building models and running simulations could help preventing such problems.

Electricity markets

In this section we study how prosumers could sell their production surplus. In a competitive environment, such operations happen on a market where sellers post their offers and buyers place bids on the offers that they want to purchase [START_REF] Parag | Electricity market design for the prosumer era[END_REF] [START_REF] Linnenberg | A market-based multi-agent-system for decentralized power and grid control[END_REF]. Although markets are common systems of our society, the emergence of energy markets, and more precisely electricity markets, is recent [START_REF] Hvelplund | Renewable energy and the need for local energy markets[END_REF].

A possible reason is that electricity is, by nature, difficult to handle. Indeed, it is difficult to store and route properly. This means that electricity has to be available on demand and that measuring precisely who sells what to who might be difficult. Furthermore, since demand and supply vary continuously, the system operator need to coordinate the dispatch of generating units to meet the expected demand of the system. If there is a mismatch between supply and demand the generators speed up or slow down causing the system frequency to increase or decrease. In most power systems all units should be synchronized to a common frequency (usually 50Hz or 60Hz). If the frequency deviates too much from the reference value, severe damage could occur to the equipment. In such a situation, the system operator will act to add or remove either generation or load as to get back to the Chapter 3. Prosumers and Market Aggregators stable state. The fact that electricity behaves in such complex ways makes electricity markets very specific environments.

A first distinction should be made between retail electricity markets and wholesale markets. A wholesale electricity market exists when competing energy producers offer their electricity output to retailers. The retailers then re-price the electricity and take it to the retail market. The retail electricity market enables end-users to choose their supplier from competing electricity retailers. It is common that end users of the retail markets face fixed prices contrariwise to the wholesale markets. In these cases, customers have no incentive to take into account, through their consumption, the production conditions that impact the wholesale markets. Since we are studying how prosumer could sell power to markets, we consider here wholesale electricity markets.

The price in the day-ahead market is generally determined by matching the offers to the bids as to obtain a classic supply and demand equilibrium price for all hourly intervals. Obviously, such a market relies on predictions and participants are therefore exposed to risk. This risk can be either related to the price volatility, or the volumes exchanged. At times of peak demand or supply shortages, the wholesale electricity prices can have indeed very high volatility. The particular characteristics of this price risk are highly dependent on the physical fundamentals of the market such as the mix of types of generation plant and relationship between demand and weather patterns.

Volume risk is related to the fact that participants have uncertain volumes of production and consumption. This becomes especially true when portfolios contain large shares of renewables. Furthermore, market price risk and volume risk are not independent, and one can usually observe a correlation between extreme prices and volume events. This is easily understandable since outages, which can lead to price spikes, are more likely to happen during peak periods when the network operates in tense conditions.

Because of risk, market participants tend to establish contracts in sophisticated electricity markets. The idea behind contracts is that participants try to share the financial risks in a pre-agreed manner. These contracts can take multiple forms such as simple fixed price forward contracts for physical delivery and contracts for differences where the parties agree a strike price for defined time periods. The contract for differences specifies a strike price, such that, in a given period, the wholesale price index can either be higher, lower, or equal to the strike price. In cases when it is higher, the generator will refund the difference between the strike price and the actual price for that period. Likewise, a retailer will refund the difference to the generator when the actual price is less than the strike price. Many other hedging arrangements, such as swing contracts, Virtual Bidding, Financial Transmission Rights, call options and put options are traded in modern electricity markets.

Aggregators and portfolios

35

Aggregators and portfolios

Aggregators in the wholesale market

The wholesale market could enable prosumers to sell their production surplus to other entities. Nowadays, there exist already numerous participants to such markets. But, in a smart grid system, where a large number of end users seek to sell or buy in random ways, a stable market seems pretty unlikely. Managing the interactions and financial transactions of so many small and unpredictable entities is a challenge.

Aggregators are market participants that are responsible for portfolios of generators, loads, and storages. An aggregator can be viewed, from the market point of view, as a single dispachable generation unit. The profits and losses made by the aggregator are then shared in a pre-agreed manner between the entities within the portfolio. On the one hand, aggregators provide a hierarchical organization of the market participants, and on the other hand, they reduce the market volatility. Indeed, having a large and diverse pool of resources is known to provide stability. Although a key point for wholesale electricity market aggregators, this is not specific to electricity and was studied in other contexts such as finance.

Markowitz portfolio theory

The optimization of expected returns to risk is a traditional goal in finance, and a wide literature exists on this topic. It is well-known for instance, that the more risk one is willing to accept, the higher his potential gains. On the contrary, when investing exclusively on low risk assets, one should expect relatively small gains. This trade-off is formalized in the Markowitz' portfolio theory [START_REF] Harry | Portfolio Selection: Efficient Diversification of Investments[END_REF] in 1952 for which he was later awarded a Nobel price in economics. More precisely, given a set of assets for which we have some historic data of returns, the objective is to find a linear combination of these assets (the so-called portfolio) which maximizes the expected value while minimizing the variance of the portfolio's return [START_REF]Modern Portfolio Theory[END_REF].

Under this model, the return of a portfolio is the weighted combination of the constituent assets' returns, while the portfolio volatility is a function of the correlations between the component assets [START_REF] Zivot | Chapter 1 Portfolio Theory with Matrix Algebra[END_REF]. The fact that risk depends on the correlation between the assets is at the root of the diversification principle. An investor can indeed reduce the risk of a portfolio simply by holding combinations of elements that are not perfectly positively correlated.

A first assumption from Markowitz is that investors are risk averse, meaning that given two portfolios that offer the same expected return, investors will prefer the less risky one. The exact trade-off between expected returns and risk is the same for all investors, but different investors will evaluate the trade-off differently based on individual risk aversion characteristics.

It is possible to have a visual representation by plotting the assets as dots in the risk-expected return space (see figure 3.3). The collection of all such possible portfolios defines a region in this space which left boundary is a hyperbola. In the absence of a risk-free asset, the upper edge of this region is called the efficient frontier (also called "the Markowitz bullet"). Combinations along the efficient frontier represent portfolios for which there is lowest risk for a given level of expected return. This is basically the answer of Markowitz to the problem: if one is able to put a number on his risk acceptance or on the target expected return, the corresponding efficient portfolio is a priori the best option.

Although this model is a cornerstone in finance and risk management, it was criticized for diverse reasons. First, risk is estimated by looking at past market data and quantified by a probability of losses. But the reasons for losses are not explained by the model such that there is no guarantee that the estimated parameters would give good results for predicting the future. This is a major difference compared to many engineering approaches to risk management. Indeed, structural models focus on the relationships between the constituents and Monte-carlo simulations are used to assess the probability of a given outcome. These models can thus be used to compute rare events probabilities, which is only possible with past data if there were several occurrences of these events.

Furthermore, the portfolio theory uses variance to quantify risk, which might be justified under the assumption of elliptically distributed returns. This is the case in the modern portfolio theory where returns are assumed to follow a Gaussian distribution. But this assumption has been criticized by many economists because of its inadequacy with real market returns [START_REF] Chicheportiche | The Joint Distribution of Stock Returns is Not Elliptical[END_REF] :

"Simply, if you remove their Gaussian assumptions and treat prices as scalable, you are left with hot air." Nassim Nicholas Taleb

Correlation graphs

As shown by Markowitz portfolios theory (see section 3.3), the correlation between the assets impacts the variance of the expected returns. The gaussian assumption of portfolio theory enables analytic results in the form of an efficient frontier. However, in the case of the prosumers production surplus this assumption might not hold such that we need to find other ways to study the correlations.

Since the work of [START_REF] Mantegna | Hierarchical structure in financial markets[END_REF], an interesting approach consists in computing a distance metric based on the correlation coefficients in order to organize the series in a correlation graph. Nodes represent the series considered while the edges are weighted by the metric. Because the metric can be computed for all pairs, these graphs are complete and of little use as is. Historically, the approach used by [START_REF] Mantegna | Hierarchical structure in financial markets[END_REF] was to compute a minimum spanning tree as to obtain a hierarchical clustering of the series.

Later on, it was pointed out that, by definition, a spanning tree could not capture the underlying clustering structure hidden in the correlation graph. In this paper, we use another classical filtering technique calledgraph [START_REF] Garas | The structural role of weak and strong links in a financial market network[END_REF]. It consists in selecting a threshold , and filtering out edges with smaller weights. As we will see further in this paper, this approach has the advantage of preserving clusters of correlated series.

Discussion

This chapter introduced the concepts that will be used in chapter 4. We started by defining and explaining why prosumers are so important in the smart grid systems. These agents both consume and produce such that their extra-production might be positive or negative depending on multiple criteria such as weather conditions or consumption habits. Because they use renewables, prosumers tend to have stochastic extra-production that are difficult to predict on the individual scale. A gigantic market allowing these unreliable units to sell and buy on short time-scale seems quite unstable and difficult to manage. This is especially true considering the strong stability constraints that weight on power grids.

We thus believe, and we will show in the next chapter, that forming aggregations controlled by a central entity could be a solution for having clearer and more stable markets. Aggregators select prosumers and form groups that they control. They are responsible for all the market operations and are rewarded with a share of the financial gains of the coalition. This approach is similar to the portfolio theory presented in this chapter where the goal is to find a linear combination of assets that maximizes the expected return for a given risk acceptance. Nevertheless, we will see in the next chapter that production distributions are usually not gaussian, such that we propose another formation algorithm that will use correlation graphs.

Chapter 4

Forming Stable Aggregations of Prosumers for Electricity Markets

This chapter uses the concepts introduced in chapter 3 and explains the formation of stable aggregations of prosumers for electricity markets. Section 4.1 gives the details about how we simulated the production and consumption of these agents. Section 4.2 introduces the market model that we used, and section 4.3 explains the algorithm that we built for forming aggregations. In section 4.4, we give some examples and study the performance of the algorithm. The work presented in this chapter was published in [START_REF] Gensollen | Coalition formation algorithm of prosumers in a smart grid environment[END_REF] and [START_REF] Gensollen | Stability and Performance of Coalitions of Prosumers Through Diversification in the Smart Grid[END_REF].

Simulation of prosumers

In this first section we wish to simulate the production and consumption of the prosumer agents presented in chapter 3. Using pure random distributions is a direct and simple possibility but is probably not very realistic. In order to get a better understanding about prosumers, we should start by collecting and analyzing data on these agents.

Existing production/consumption data sources

An essential component of the smart grid is the smart meter which makes the interface between the end user and the rest of the system. Smart meters coupled with sensors measure quantities of interest (like instantaneous consumption), receive information from the grid (electricity prices for instance), and take actions accordingly (demand side management programs). Smart meters are currently and gradually deployed, and will probably provide interesting datasets to work on. Unfortunately, at the time this thesis was started, production and consumption data for prosumers over a large region were not yet available to our knowledge. Some interesting experiments are nonetheless being conducted and data are progressively made public [38] [8].

Chapter 4. Forming Stable Aggregations of Prosumers for Electricity Markets

Weather data

In this section, we use weather quantities like wind speed or solar radiance as alternative data for generating realistic production and consumption series. Fortunately, these kinds of data are easier to find, and since the development of small personal weather stations, their geographical granularity keeps increasing. Since these quantities depend both on time and location, we discretise time into slots and space into zones in the following (see block 1 of fig. 4.1). A zone is simply a portion of the considered region of study for which we sampled data. Therefore, if prosumers i and j are positioned on the same zone, they are exposed to the same weather (see figure 4.

2).

Adding some intra-zone noise can easily be done though not considered in this paper. We denote by P i (t) the instantaneous available extra-production of agent i at time t :

P i (t) = P P i (t) -P D i (t) (4.1)
Where P P i (t) represents the total production of agent i at time t and P D i (t) its consumption at time t. In other words, P i (t) represents the instantaneous surplus of power that agent i is willing to sell at time t. We simulated these traces by considering separately P P i and P D i . For a prosumer i, it is possible to write both quantities as a sum over the distributed energy resources (DER i ) and loads (load i ) of i :

P P i (t) = k∈DER i P k (t) (4.2)
P D i (t) = k∈load i P k (t) (4.3)
For simplicity, in this paper we only consider wind-turbines (WT) and photovoltaic panels (PV) as possible DERs for the agents (DER i = W T i ∪ P V i ):

P D i (t) = k∈W T i P k (t) + k∈P V i P k (t) (4.4)
We denote by ν i (t) and Ψ i (t) the wind speed (in m.s -1 ) and the solar radiance ( in W.m -2 ) at the location of agent i and at time t, so that :

P P i (t) = k∈W T i F W T (ν i (t)) + k∈P V i F P V (Ψ i (t)) (4.5)
Where F W T (resp. F P V ) is the power curve for the wind-turbines (resp. photovoltaic panels).

DER models

Wind Turbine model

As explained above, wind turbines are incorporated through their power curve F W T that maps an input wind speed to a produced power quantity. We are thus looking, in this section, for such a function. First of all, it is known that, within functioning range, the output power P is a function of the cubed wind speed ν 3 . This means that a small increase of wind speed yields a large increase of output power. However, it is the fact that not all wind turbines are identical and that there exist multiple designs with different characteristics such as the height, the length of the blades and so on. Since wind speed is usually correlated with altitude, higher turbines tend to produce more than smaller ones. In the same manner, the rotor swept area as well as the air density are parameters of interest for designing a precise power curve. Furthermore, the orientation of the turbine according to the orientation of the wind also impacts the production. There are already too many parameters and information to feed in the model. Indeed, since our focus is not on precise DER modeling but more general, we seek more simple and scalable models with few parameters. The turbines were thus modeled by the following parameters (see figure 4.3 for a graphic representation) :

• Cut-in speed : At very low wind speeds, the force exerted by the wind on the blades is not sufficient to make them rotate. But, as the speed increases, they begin to rotate and generate power. The speed at which the turbine first starts to rotate and generate power is called the cut-in speed. This parameter is denoted ν in and typically ranges between 3ms -1 and 4ms -1 .

• Rated output power : Above the cut-in speed, if the wind speed continues to increase, the level of output power rises rapidly. However, there is a point where the output power reaches the limit that the electrical generator is capable of. This limit to the generator output is called the rated output power and denoted by P m .

• Rated output speed : The wind speed at which the rated output power is reached. Above the rated output speed, the design of the turbine is arranged to limit the power to maximum possible level and there is no further rise in the output power. This parameter is denoted by ν out and typically ranges between 12ms -1 and 17ms -1 .

• Cut-out speed : As the speed increases above the rated output speed, the forces on the turbine structure continue to rise and, at some point, there is a risk of damage to the rotor. As a consequence, a braking system is employed to bring the rotor to a standstill. This is called the cut-out speed. This parameter is denoted by ν cut and is typically around 25ms -1 .

In this thesis, we set all speed limits for all turbines to be the same, and only use the rated output power as a parameter representing the turbine maximum production capacity. We now have to decide an equation relating the output power to the wind speed when the latter is in-between the cut-in speed and the rated output speed. We choose the simple form (see figure 4.3) :

F W T (ν) =            0 if ν < ν in Pm ν 3 out -ν 3 in ν 3 - Pmν 3 in ν 3 out -ν 3 in if ν ∈ [ν in , ν out ] P m if ν ∈ [ν out , ν cut [ 0 if ν > ν cut (4.6)

Solar Array power curve

As for wind turbines, we need to define a power curve for solar arrays. Such a function would take as input the solar radiance and output a production power. Obviously, if we succeed in writing the input radiance as a power density (W.m -2 ), then almost all the work would be done. The problem is that weather stations extremely rarely record such a quantity, and for the datasets that we used, the best that we could obtain at the time was time series of cloudiness. Cloudiness is a well-known measures ranging between 0 (no clouds) to 8 (sky completely cloudy).

The approach that we used was to consider the cloudiness traces as degradation factors on some perfect solar radiance profile that we need to generate. Therefore, we want that the perfect profile reproduce sun power basic properties like daily periodicity and seasonality. To do so, we used a model called Helios that can be found in [START_REF] Dans | Rayonnement solaire[END_REF]. The whole model is not reproduced here for space concerns but we explain the main idea. the Helios model takes as input the location on earth defined as the triplet (latitude, longitude, altitude) as well as a timestamp, and computes the fraction of sun power that arrives at this point at that specific time if there are no clouds. We can see on the left panel that seasonality is reproduced, that is, the solar radiance is stronger during the summer than in the winter. Furthermore, we can observe on the two right panels that daily periodicity and logic are respected (no sun at night), and that the period of sunshine is larger in the summer than in the winter.

The cloudiness can be incorporated to the Helios model through the following equation :

Ψ(t) = Ψ (t) 1 - 3 4 η(t) 8
3.4 (4.7)
where Ψ(t) (resp. Ψ (t)) is the real (resp. ideal) radiation at time t, and η(t) is the cloudiness at time t. If we know the location of a prosumer (latitude, longitude, altitude), and if we have the corresponding cloudiness traces, we can compute the density of solar power (in W m -2 ) at this location. As for wind turbines, modeling solar arrays is a domain on its own. There are indeed multiple parameters to take into account like the efficiency, the angle of the array towards the sun light and so on. Here, we use the following simplified power curve :

F P V (Ψ) = ρSΨ (4.8)
where S is the total surface of the arrays, and ρ is the array efficiency (around 20%). Please note that these power curves are very simple models and that more complex and detailed model can be found for example in [START_REF] Lydia | A comprehensive review on wind turbine power curve modeling techniques[END_REF].

Consumption Model

At this point, if we have the right data, we are able to model the production of prosumers using wind turbines, solar arrays, or a combination of both. However, we still have to account for the consumption of these prosumers. Real consumption data can be found in [START_REF]Irish Social Science Data Archive[END_REF] or [] for example. since these data were not available in the beginning of the present thesis, we also design a model to simulate consumption traces. When looking at figure 4.5 it appears that electricity consumption tends to be bursty. There is some base load and large peaks at specific hours. Usually, these peaks are in the morning and evening, but this is not always the case. The amplitudes of the base load and peaks differ from user to user and are related to the habits and installation of each user (the house may be heated with electricity or gaz which changes the consumption significantly).

Modeling electric consumption has already been widely tackled in the literature. Models can be basically divided into two main categories : Topdown and bottom-up approaches. Top-down techniques take aggregated consumption data as inputs and try to estimate individual consumption patterns while bottom-up methods use a fine modeling of users consumptions as to obtain realistic aggregated consumption curves. In this paper, we used a bottom-up model since the end user, or relatively small aggregations of end users, are in our interest. The main objective was to capture both daily patterns and seasonal variations of the consumptions. We assumed an additive model where the consumption of an agent is the sum of a seasonal heating term that depends on the outside temperature and an electronic consumption term that depends on the hour of the day. By denoting τ (t) the outside temperature at timestamp t, we can express the consumption P D i (t) of agent i at time t :

P D i (t) = F heat i (τ (t), t) + F elec i (t) (4.9)
where F heat i (τ (t), t) is the power curve that maps the temperature to a heating consumption, and F elec i (t) computes the consumption of agent i (other than heating) at a given hour of the day. In the simulation, all agents have a desired inside temperature T i , supposed to be a constant for simplification. By using thermodynamic laws F heat i (τ (t), t) can be approximated by : where B i is the surface of thermal exchanges for agent i and R i is their thermal resistance. We denote by Ω i the maximum consumption possible for agent i, which is basically the sum of all its appliances powers. We also denote by ω i (t) = {ω i (t 0 ), ..., ω i (t 24 )} the vector of the average fraction of Ω i used for each hour. We can therefore write :

F heat i (τ (t), t) = B i R i [T i -τ (t)] (4.10)
F elec i (t) = Ω i (ω i (t) + ) (4.11)
where is a noise term. The vector ω i (t) enables us to easily differentiate agent consumption behaviors. Business or residential areas for instance can be easily distinguished with this kind of model.

Results of simulations Data used

We collected two main datasets for modeling the prosumers [37] [57]. For [START_REF]Infoclimat[END_REF], the data start in January 2006 and end in December 2012, with a sampling frequency of three hours. Note that such a low sampling rate is far from perfect since short time event are very unlikely to be reported (see [START_REF] Anvari | Suppressing the non-Gaussian statistics of Renewable Power from Wind and Solar[END_REF] for more information). Furthermore, the data available are average wind speed and temperature, but the cloudiness is not reported. The data are collected are weather stations located in the main french agglomerations, which gives a quite sparse sampling of the french territory.

For [START_REF]National Centers For Environmental Information[END_REF], data were available for the year 2010 and contains, among other things, the hourly average wind speed, temperature, and cloudiness collected at US airports. This gives us between 3 and 10 stations per states.

Configuration of the prosumers

In the model, a prosumer i is instantiated by specifying :

• Z i : The zone on the map where prosumer i lives.

• DER i The DER set of i that comprises :

-W T i : The set of wind turbines owned by i. A wind turbine is configured by fixing its rated output power.

-P V i : The set of solar arrays owned by i. A solar array is configured by fixing its surface (all array have the same efficiency for simplicity).

• Load i : The load set of i that comprises :

-Heating habits computed from the desired temperature T i and the surface B i .

-Other consumptions Therefore, the notion of prosumer is quite loose here, the agents can be configured as to represent anything from a single wind-turbine for instance (DER i = {W T 0 } and load i = ∅) to a pure load (DER i = ∅ and load i = {L 0 }) through more complex combinations. This enables us to control precisely the profile of the agent population that we create. Of course, random configurations of the agents is possible if there is no prior on their profiles. The examples of figure 4.7 show prosumers which almost always produce because they were configured with much more DER than loads. The opposite case, or a more balanced situation where the net production can be either positive or negative are also possible.

Examples

Limitations

In this section we aimed at simulating the production and consumption of prosumers. More precisely, we were interested in being able to generate timeseries of production and consumption given a distribution of prosumers on a territory. We believe that the originality of our approach was to use weather data as inputs of the model rather than standard distributions that would have been less realistic. Depending on weather and time, agents can have positive or negative net productions that we can control with good granularity thanks to this work.

We want to stress out that multiple improvements could easily be done to this model for people having both the time and the will to do so. The number of types of DER could be increased and more realistic power curves could be designed for instance. Besides, we neglected, for simplicity, several factors such as the wind orientation, and the angle of the sun towards the arrays. A higher frequency for the weather data could also lead to interesting work concerning short-time perturbations.

Market model

In the previous section we explained how we could simulate production and consumption for different prosumers by using weather data. The purpose of this section was to obtain timeseries of extra-production for a pool of prosumers. Depending on the DER they own as well as their personal behavior, these series might look very different (see figure 4.7). In this section, we study how prosumers could enter electricity markets and on what criteria.

We consider a set A = {a 1 , a 2 , ..., a N } of N prosumers of the distribution network. Each agent is configured randomly and we simulate its extra-production P i (t), ∀i ∈ A for a given period (see chapter 3). Based on these historical values, our objective is now to form groups of prosumers so that the global power production resulting from the superposition of individual's extra-productions be both sufficiently high and predictable. Let P S (t) = i∈S P i (t) be the available extra-production of coalition S at time t.

Suppose now that coalition S has to suggest a production value P CRCT S to enter the market. This means that, during the time S is on the market, it will have to inject in the grid exactly P CRCT S at any time t and will be rewarded proportionally to this amount, with penalties if it deviates. Obviously, the actual extra-production will not be constant at this value and will oscillate due to intermittences in the production and consumption (see figure 4.8). If S has an available production always greater than P CRCT S , it is losing some gains since it could have announced a higher contract value. If the production oscillates around P CRCT S , by using batteries or demand side management techniques, S could be able to maintain its production to the contract value at any time. Nevertheless, if the oscillations are too important compared to the available storage capacity, S will probably break the contract and pay penalties. We can see that there is a return over risk tradeoff here. Coalitions should thus find the right balance between announcing too low and losing some potential gains, and claiming too high and paying penalties. Let us illustrate the rest of the notations and concepts with a simple example. We consider only two agents i and j such that the distribution of their extra-production can be approximated by normal distributions : P i ∼ N (µ i , σ i ) and P j ∼ N (µ j , σ j ). This is only for explanation purposes as it is of course rather unrealistic in real situations where the distributions are skewed. We can write the distribution of the coalition S = {i, j} as P {i,j} ∼ N (µ ij , σ ij ) (see figure 4.9), where :

µ ij = µ i + µ j σ ij = σ 2 i + σ 2 j + ρ ij σ i σ j (4.12)
, ρ ij being the Pearson's correlation coefficient between P i and P j . If the coalition {i, j} proposes a contract value P CRCT S , all instants when {i, j} will produce less than P CRCT S is critical. Indeed, in this kind of situations, {i, j} will either have to discharge batteries to keep up with its contract, or pay penalties to the grid. The probability that {i, j} is under-producing compared to the contract : P r[P i,j ≤ P CRCT ] is thus an important indicator of the coalition's quality. A well-known result for normal distributions is that the cumulative distribution function can be written as :

P r[P ij ≤ P CRCT S ] = 1 2 1 + erf P CRCT S -µ ij σ ij √ 2 (4.13)
, where erf is the error function :

erf (x) = 2 √ π
x 0 e -t 2 dt. The contract a given coalition is willing to take depends on its capacity to compensate for under-producing (using batteries, backup generators...), and its risk acceptance. Selecting the right contract value appears thus as an interesting problem on its own that we plan to investigate in future works. In order to keep the present paper in a reasonable length, we simplify the contract value selection problem by giving some responsibilities to a third party named the market operator. Their role is to constrain the market entry to coalitions able to propose both sufficiently high and sufficiently credible contract values. More formally, let φ ∈ [0, 1] be the reliability threshold fixed by the market operator as a maximum value for the probability of under-producing. The highest contract value that a coalition can propose is thus P CRCT S such that P r[P ij ≤ P CRCT S ] = φ. In the Gaussian example, it implies that coalition {i, j} is announcing (see figure 4.9) :

P CRCT S = µ ij - √ 2σ ij erf -1 (1 -2φ) (4.14)
This is the best contract value that the coalition S can afford for a given stability policy φ of the market operator. Figure 4.10 shows how P CRCT S evolves according to the reliability parameter φ. For illustration, the range of φ values is shown from 0 to 1, but in practice, only small values of φ really make sense : φ = 1 for instance means that coalitions can announce absolutely anything since the probability of producing less than any contract value is necessarily less than one by trivial definition of a probability. As shown on figure 4.10, coalitions with high expected productions but presenting a high unpredictability are penalized and can only afford small contracts. The market operator also specifies a lower bound P M IN on the contract values as not to overload the market with unrealistic small coalitions. We thus characterized a valid coalition as one satisfying the two conditions :

P r[P ij ≤ P CRCT S ] ≤ φ P CRCT S ≥ P M IN (4.15)
On figure 4.10, P M IN is fixed to 2 units for illustration purpose. For φ = 0.1, only blue triangles and cyan circles coalitions are valid while red diamonds coalition is not. The same coalition in term of expected production (µ = 5), but with a higher variance (σ = 1.5, cyan curve with circles) can only afford a smaller contract value of P CRCT S = 3.07. The red curve with diamonds stands for a coalition with a higher expected production (µ = 7), but with a very high unpredictability (σ = 5). For low values of φ, this coalition is thus heavily penalized and can only afford a contract of 0.59 units. Under grid policy (φ = 0.1, P M IN = 2), this last coalition is thus not allowed to enter the market (red dot below the horizontal dashed line).

The Gaussian assumption of this small example is convenient as it allows us to write P CRCT S analytically. Nevertheless, such an assumption is rather unrealistic in practice. In the following, we keep the same framework but release this Gaussian assumption unless the contrary is specified (see eq. 4.20).

Aggregation method

In this section we study the formation of prosumer aggregations such as to maximize the available production on the market. That is, from the pool of agents and a given number of aggregators that want to participate in the market transactions, we wish to form the corresponding number of coalitions that optimize the expected production to risk ratio. For this purpose, we introduce a utility function based on the contract value explained above.

Utility function

Here, we use the notions of contract values and valid coalitions developed in section 4.2 in order to design a proper utility function. The contract basically indicates the rate at which a coalition has to inject power in the grid. It seems then natural that coalitions are remunerated proportionally to their contract values gain(S) ∝ P CRCT S . More precisely, if λ is the unitary price rate for electricity, a coalition S injecting P CRCT S in the grid during a period [t 0 , t k ] earns :

gain(S) = t k t 0 λP CRCT S dt = P CRCT S t k t 0 λdt (4.16)
since P CRCT S is supposed to be a constant rate over the contracted period). Unfortunately gain(S) is not a concave function of the coalitions' sizes, meaning that coalitions can grow as large as the number of agents allows it, without any counterbalance effects. Such a model, that virtually allows infinitely large coalitions and contract values, is in practice not realistic. There are indeed costs (communication costs for instance) that increase with the coalitions sizes. We take this observation into account by rescaling the utility of a coalition S by its size in term of number of agents (|S|):

U(S) = 1 |S| α P CRCT S P M AX , if S is valid, 0, if S is not valid (4.17)
where parameter α controls to what extent the size of a coalition impacts its utility, and P M AX is a normalizing factor. Based on U, the marginal contribution of an agent i can be expressed as δ S (i) = U(S + {i}) -U(S). A coalition S has thus an interest in adding an additional agent i if :

δ S (i) ≥ 0 ⇔ P CRCT S+{i} ≥ P CRCT S |S| + 1 |S| α (4.18)
If α = 0, agents are added as long as they increase the contract value of the coalition. If α > 0, additional agents have to increase the contract value by some factor.

Chapter 4. Forming Stable Aggregations of Prosumers for Electricity Markets

In real situations, the shape of such utility function might be complex with numerous local maximums. We choose in this paper to favor the exploration of the space around balanced regions, i.e regions where coalitions sizes are relatively balanced. Therefore, we use α as a proxy for having both a concave utility function and preferences in the search space. Given a situation with N prosumers and N COAL desired coalitions, we wish to select α such that the utility function tend to favor coalitions of approximately N = N/N COAL agents.

In the general case where distributions and correlation structures have no special form, finding an analytical expression for α appears complicated. To overcome this problem, we seek an approximation for α in a simplified situation where all power distributions are approximated by normal distributions and all prosumers are considered equivalent to a mean agent : ∀i ∈ A, P i ∼ N (μ, σ), where μ = 1 N i∈A µ i , σ = 1 N i∈A σ i , and ∀i, j, ρ ij = ρ. In this simplified case, we can express the utility as a function of μ, σ, ρ, N , and α (see Appendix). We then select α such that :

   ∂U ∂|S| |S|= N = 0 ∂ 2 U ∂|S| 2 α=α ≤ 0 (4.19)
Which leads to :

α N = 0.7σ(ρ -1)erf -1 (2φ -1) μ N (ρ N -ρ + 1) + 1.4σerf -1 (2φ -1)(ρ N -ρ + 1) (4.20)
Figure 4.11 shows how α and the utility function evolves according to the mean size of the coalitions N . Given a policy (φ, P M IN ) and a pool of N prosumers, we are now able to quantify the quality of any coalition S.

De-correlation graphs

We aim at forming N COAL coalitions {S 1 ; S 2 ; ...; S N COAL } such that the global utility U = N COAL i=1 U(S i ) is maximized. Since achieving such a goal is a well-known hard problem due to the combinatorial explosion in the number of possible aggregations, we propose in this section a greedy heuristic using decorrelation graphs to solve the problem.

Representing the correlation structure

As seen in section 4.2, the variance of the aggregated production impacts directly the contract values, and depends on the covariances between the agents productions. We argue here that, by having some representation of the correlation structure between the agents, the search landscape for high utility coalitions could be reduced, such that good coalitions are more likely to be found quickly. Usually, this correlation structure is formalized with a covariance matrix or a correlation matrix that contains all the correlation coefficients between the agents : M = (ρ ij ) ∀i,j∈A 2 . By using a metric to map this matrix in a weighted adjacency matrix, it is possible to obtain a graph representation of the correlation relationships between the agents. In the following, we use two opposite distance metrics : U α =f( N) Blue curve with diamonds favors small coalitions of 2 agents while the green one with triangles favors 5 agents coalitions. Finally, the red curve with squares has an optimal size of 15 agents.

U α 2 U α 5 U α 15 U α 15
d 1 ij = 1 -ρ 2 ij d 2 ij = ρ 2 ij = 1 -d 1 ij (4.21)
Clearly, d 1 (resp. d 2 ) maps two correlated series as close points (resp. distant) while two uncorrelated series are distant (resp. close). These metrics enable us to compute a correlation graph G 1 = (A, E 1 ) and a "decorrelation" graph G 2 = (A, E 2 ). For any i and j, the weight of the edge

e ij is d 1 ij in G 1 and d 2 ij in G 2 .
In both cases, we want to keep only the edges which weights are located in the lower tail of the distance distributions. In other words, we want to compute the -graphs of G 1 and G 2 such that only meaningful edges remain. Selecting the filter is an important point affecting the landscape search for the coalition formation. Unfortunately, there seems to be no clear consensus in the literature on how to select such a threshold. We will see later in this section that cliques in G 2 are potential seeds for the coalitions. Since we want to generate N COAL coalitions, we need at least N COAL cliques of a given size to start. Besides, since we consider coalitions as disjoint, the starting cliques should be non overlapping. We select our optimal threshold for G 2 as :

= min ∈[0,1] { s.t. |Θ k (G 2 )| ≥ N COAL } (4.22)
where G 2 is the de-correlation graph G 2 filtered by , and Θ k (G) is the set of non overlapping cliques of size k in a given graph G. In other words we select as the smallest threshold possible such that the filtered de-correlation graph contains at least N COAL non overlapping cliques of size k. In practice, since finding cliques requires exponential time, we use triangles [START_REF] Schank | Finding, Counting and Listing all Triangles in Large Graphs, An Experimental Study[END_REF] (k = 3 in eq. 4.22) rather than cliques as soon as the number of nodes is not small. Note also that the existence of as defined in equation 4.22 is not guaranteed.

Cliques

In [START_REF] Garas | The structural role of weak and strong links in a financial market network[END_REF] the structural roles of weak and strong links on financial correlation graphs is investigated. The author shows that strong links, accounting for strong correlation relationships, are responsible for the clustering, while weak links provide the connectivity between clusters. Indeed, if we consider three items, say a, b, and c such that a and b are strongly correlated and b and c are also strongly correlated, then it is likely that a and c are also strongly correlated. It can be easily shown using the cosine addition formula 1 , that if ρ ab > x and ρ bc > x with x > 0, then ρ ac > 2x 2 -1).

Correlation graphs capture this weak transitivity notion through clusters of correlated series. Nevertheless de-correlation seems like a more complex concept than correlation in the sense that there is not even a partial notion of transitivity when it comes to it. Therefore, the clustering coefficients of G 1 is much higher than the one of G 2 . This can be seen as another formulation of [START_REF] Garas | The structural role of weak and strong links in a financial market network[END_REF] on the structural roles of weak and strong links on financial correlation graphs. Strong links, accounting for strong correlation relationships, are responsible for the clustering, while weak links provide the connectivity between clusters. Searching for clusters in G 2 and hoping that this strategy will provide a nice coalition structure of internally uncorrelated coalitions seems thus pointless. Consider now a clique in G 2 , which is a complete subgraph of G 2 . Since there is a link for every pairs of nodes, we know, by construction, that a clique has a mean correlation and a maximum correlation less than .

Figure 4.12 shows the distributions of the utility values for cliques of size 3 (triangles) in G 2 and for all the other possible triplets of agents. It is clearly visible that cliques tend to exhibit higher utilities because of their decorrelation property. Choosing cliques in G 2 as coalitions seems therefore appealing. Nevertheless, the quality of the results seems to decrease as the sizes of the cliques increase. Indeed, the larger the desired cliques, the more dense G 2 becomes (see equation 4.22). There is a point where cliques result more from noisy edges than true de-correlation, which decreases the quality of the results. Directly mapping cliques to coalitions by this decorrelation oriented approach is thus not sufficient. It is indeed possible that adding agents to these cliques has the combined effect of increasing the expected production while decreasing its stability. The question revolves around measuring the benefits of this production surplus compared to the disadvantage of having coalition with high volatility. This can be quantified by the marginal benefit in equation 4.18.

Clique percolation

The algorithm takes inputs from : Cliques tend to exhibit higher utilities than random coalitions.

• The agents : historical series of available productions P i ,

• The market operator : market entrance policy (P M IN , φ),

• The "user" : Number of desired coalitions N COAL and size of starting cliques k.

The first steps consist in computing the de-correlation graph G 2 as well as the optimal threshold . Cliques of size k in G 2 are considered as coalition seeds. The next step is a local greedy improvement over the landscape represented by G 2 . Cliques add alternatively the node i in their neighborhood that yields the best marginal benefit M AX i∈N (clique) δ clique (i) where N (clique) is the neighborhood of a given clique. See algorithms section in the appendix.

Results

The algorithm presented in the previous section is supposed to generate a given number of coalitions that have good utilities. As it comprises mainly of a greedy optimization based on local improvements, there is no guarantee that the algorithm finds the global optimum. Since there is, to our knowledge, no state of the art algorithm that aggregates uncorrelated agents in an optimum way, we compare the results with :

• Random sampling of coalitions : Coalitions are formed randomly without any other constraint than the desired size. This enables us to have an idea about the distributions of utility values for coalitions of a given size. • Random sampling of coalition structures : Coalition structures are sampled randomly by shuffling and random divisions of the agents. This algorithm (see appendices) uses such a sampling and returns the highest utility coalition structure sampled. We refer to this algorithm as "random".

• Correlated : Opposite version of our algorithm. It performs a community detection on the correlation graph G 1 . The resulting coalitions have thus very high internal correlations. We thus expect this algorithm to perform very bad compared to the others. See appendices.

Before running the algorithms, we need to calibrate the utility function by choosing the value of the α parameter. Recall that the purpose of this parameter is to take into account some constraints on the coalition's sizes if needed. In this paper, we do not have any technical constraints on coalition sizes though we designed the utility such that these could be taken into account. We select the desired size as being N/N COAL (where . means floor). Figure 4.13 shows how the mean utility of a coalition evolves with its size when the optimum size is set to 40 agents.

Figure 4.14 shows the coalitions formed with the considered algorithms in the contract value / volatility space. The color map in the background indicates regions where we expect high utilities (red) and the ones where we expect very poor utility values (blue). The bottom right corner, with high contract values and low volatilities, is therefore the region where we wish to form our coalitions. A single coalition is represented by a marker and the color and shape of a marker indicates by which algorithm the coalition has been formed. Besides, the sizes of the coalitions are indicated on 4.4. Results

59

the markers, and the marker size is also proportional to the coalition size. We can see that the utility function results in approximately balanced coalitions. Small yellow markers indicates the gravity centers of their respective coalition structures. The coalitions of correlated agents (green squares) are clearly of poor quality according to our criteria since they can only afford small production contracts, and with a very high volatility. The decorrelated coalitions (blue dots) are closer to the bottom right corner indicating a much better quality in term of productivity over volatility ratio. The black dotted line indicates the mean values for the random coalitions sampling technique. Each small dot stands for the mean position of all sampled coalitions of this given size. Variances are not indicated for readability, but are usually quite large since this sampling only takes the size as a constraint. We can see that as coalitions get larger, they tend to increase on average their contract values, but at the price of a higher volatility. The results of the random coalition structure sampling are shown with the red ellipses that represent the distribution of the gravity centers of the sampled structures. Since the center of the ellipses stands for the mean and each ellipse adds one standard deviation, more than 99% of the sampled gravity centers are within the largest ellipse. The small yellow dot below the ellipses indicates the gravity center of our solution. It is thus visible that our greedy graph based algorithm is able to find a quite good coalition structure in terms of volatility and contract values.

A key point for the coalitions, besides stability and productivity, is their resilience. The resilience of a system refers to its ability to perform its tasks when subject to failures of its components. We consider here the case of random failures of the power electronics of some agents that has the consequence of preventing them from participating in the market. Therefore, the notion of resilience we will use in the following can be seen as the ability of the coalition structures to inject stable power in the grid when some of its internal agents are removed. According to our model, the market operator specified two thresholds (P M IN and φ) such that the power injected by every coalition is constrained :

P CRCT S ∈ [P M IN , P CRCT S ].
As long as a coalition can propose a contract value higher than P M IN , it is valid and allowed to enter the energy market. We define the resilience of a coalition S as the probability that S produces more than the P M IN threshold : R S = P r[P S >= P M IN ] = 1 -P r[P S < P M IN ]. And we extend this measure to the coalition structures :

R CS = S∈CS 1 -P r[P S < P M IN ] (4.23)
We consider that prosumers fail randomly, and we denote by ψ ∈ [0, 1] the fraction of agents that failed. Figure 4.15 exhibits how the resilience of the coalition structures evolves according to ψ (see appendix section Resilience algorithm for more details). On the top subplot, P M IN was voluntarily selected relatively low such that the resiliences of the three structures fit on the same figure. When the P M IN requirement increases, the differences between the algorithms also increase as visible on the bottom subplot of figure 4.15. The decorrelated coalitions achieve a more resilient production on the market in the sense that they sustain a higher fraction of node failures.

Discussion

Chapter 4 presented a method for energy market aggregators. By seeking diversification in the assets they own, we show that the expected productivity to risk ratios of the portfolios are improved. In this framework, this translates to higher contract values for the coalitions, and therefore higher utilities. We particularly studied the case where a given number N COAL of aggregators were trying to build optimized portfolios. We showed that the variance of the production of a coalition was related to the inner-correlations between the prosumers inside the coalition. Since these agents produce and consume in non-trivial ways, these correlations are far from obvious. Furthermore, because of the diversity of the possible distributions (usually not gaussian) for the productions and consumptions of the agents, we could not use a Markowitz framework for our purposes. Instead, we chose a graph based approach where correlation (and decorrelation) graphs were used to find and expand uncorrelated cliques, which is one of the main contribution of this work. We showed that our algorithm was performing better than other aggregation methods.

Although this approach gave interesting results, we believe that correlation graphs could be used in a deeper manner. In this chapter, (de)correlation graphs were static representations of the (de)correlation structures between the agents. Nevertheless, the correlations between the agents are susceptible to change depending on both the time at which they are computed, and the size of the window on which they are computed. Intuitively, we feel that this lack of dynamics may hide some information, and even worse, may lead to false conclusions. We will see in the next chapter, devoted to a dynamic approach of the correlation graphs, why this could be the case and what are the improvements that we can obtain.

Chapter 5

Correlation graphs dynamics

In chapter 4, correlation graphs were introduced and used to form coalitions of prosumers. In this chapter, we aim at studying these graphs in more depth. The work done in chapter 4 was considering static correlation graphs although correlation can be seen as a dynamic measure. We show here that using the dynamics of correlation can be useful for a deeper understanding of the data.

This chapter starts with a small section (section 5.2) on the Pearson correlation coefficient and how we could use this measure to define temporal correlation graphs. Following the approach developed in [START_REF] Gauvin | Detecting the Community Structure and Activity Patterns of Temporal Networks: A Non-Negative Tensor Factorization Approach[END_REF], we use three dimensional tensors to represent these temporal graphs. We thus give some notions about tensors and tensor decompositions in section 5.3. The idea developed in [START_REF] Gauvin | Detecting the Community Structure and Activity Patterns of Temporal Networks: A Non-Negative Tensor Factorization Approach[END_REF] consists in using tensor decomposition in order to find a dynamic clustering of the nodes. We propose in this chapter to use this method for studying dynamic correlation graphs. After explaining the idea in more depth, we show some results on toy models and real data in section 5.4. Nevertheless, at the time this thesis is written, this work is still ongoing and not published yet.

Limitations of static methods

The correlation graph based methods proposed in [START_REF] Mantegna | Hierarchical structure in financial markets[END_REF] or [START_REF] Onnela | Clustering and information in correlation based financial networks[END_REF] were only applied to static graphs. That is, either single snapshots of dynamic graphs, or graphs based on correlation computed over the total samples lengths. Although both methods give interesting results, the former focuses on a single short period while the latter might overlook short time-scale events. For correlation graphs, we could very well imagine two nodes i and j that behave most of the time in a de-correlated fashion, but over a short period, these two nodes could exhibit a strongly correlated behavior. By plotting ρ ij (t) we could easily spot this peak, but when we are dealing with a complex system with a large number of interacting components, things can get more complicated.

In [START_REF] Kullmann | Time-dependent cross-correlations between different stock returns: A directed network of influence[END_REF], the authors study the time dependent cross correlations of stock returns at the NYSES with the idea that the return value of one stock at a given time may influence that of another stock at a different time. This can be done by studying correlation between shifted time series. This approach enables [START_REF] Kullmann | Time-dependent cross-correlations between different stock returns: A directed network of influence[END_REF] to build a directed network of influence where a is connected to b if a "pulls" b. However, [START_REF] Kullmann | Time-dependent cross-correlations between different stock returns: A directed network of influence[END_REF] indicates that this effect cannot be strong and the shift in the correlation coefficients should be small on financial data. Indeed, a strong effect could be used for arbitrage purposes, which is excluded from an efficient market.

[7] considers the case of correlation networks which structures might change at specific time points. Economic recession for financial data for instance might cause such transformation. The idea of [START_REF] Barnett | Change Point Detection in Correlation Networks[END_REF] is to use a dichotomic approach : when a statistically significant change point is found then the correlation graph is split into two distinct graphs, one for each period. The method is then repeated on each graphs until no change point is found.

Here we consider the correlation graphs as dynamic, meaning that the edges present at time t depends on the correlation coefficients computed over a time window [t -∆t, t]. Therefore, the topology evolves according to how the correlation structure changes.

Dynamic correlation graphs

We assume that we have a set X of N measurements over a given period [t 0 , t f ] that we call the samples. We further suppose that the sampling rate is the same for all the samples x i ∈ X , and that all measurements are aligned.

As explained in chapter 4, the Pearson's correlation coefficient between two variables X and Y is the covariance of X and Y (cov(X, Y )) divided by the product of their standard deviations :

ρ XY = cov(X, Y ) σ X σ Y (5.1)
where σ X is the standard deviation of variable X. When working with samples (X = {x t 0 , ..., x t f } and Y = {y t 0 , ..., y t f }), this coefficient can be written in another form that might be more convenient :

ρ XY = t f t=t 0 (x t -x)(y t -ȳ) t f t=t 0 (x t -x) 2 t f t=t 0 (y t -ȳ) 2 (5.2)
This coefficient varies between -1 and 1 and gives an intuition about the linear dependency between the two variables X and Y that produced the samples {x t 0 , ..., x t f } and {y t 0 , ..., y t f } (see 5.1). A value close to 1 or -1 (resp. 0) indicates a strong (resp. weak) linear dependency. Note however, that a null correlation coefficient does not mean independence. Some structure, different than linear dependence, might very well be present (see figure 5.1).

It can be the case that X and Y represent processes with some kind of temporal patterns such that the correlation between X and Y might change. In such a situation, we might be interested in observing the evolution of this correlation. We denote by :

ρ t XY = t t=t-∆t (x t -x)(y t -ȳ) t t=t-∆t (x t -x) 2 t t=t-∆t (y t -ȳ) 2
(5.3) the correlation coefficient between X and Y at time t over the time window ∆ t . That is, we compute the correlation only on the sufficiently recent measurements that we have. For a given resolution ∆t, we can plot ρ t X,Y as a function of time in order to gain insight about the evolution of the dependencies between variables X and Y. By using the same methods as described in chapter 4, we can define G t as the filtered correlation graph at time t. It is then possible to build a sequence of snapshots G t 0 , G t 1 , ..., G T of the temporal graph G .

Tensors

Temporal graphs as three-ways tensors

Temporal graphs are receiving more and more attention by the scientific community lately. Such graphs are indeed an interesting framework to study the evolution of some kind of relationship within a community. As will be explained in chapter 6, the dynamics of graphs describe how the topology evolves with time, while dynamics on graphs focus on describing a given process over a static topology. In other words, dynamics on graphs affect the states of the nodes or edges while dynamics of graphs affect the whole topology.

As explained in chapter 2, one of the most basic way to account for the topology of a graph is the adjacency matrix that indicates the presence of links between any two nodes. We can therefore represent the sequence of snapshots G t 0 , G t 1 , ..., G T by a succession of matrices {A 0 , A 1 , ..., A T -1 }. By stacking these matrices in a third dimension, we obtain a three dimensional array or a three ways tensor T ∈ N ×N ×T (see figure 5.2). In other words, the element t ijk of T indicates whether or not node i and node j are connected at time k.

Although simple, this way of representing the temporal network hardly gives information about the structure of the data. For regular human beings, it is usually difficult to see the structure of the data within a multidimensional object. Dimensionality reduction techniques have been used for decades in data science, among which the famous Principal Component Analysis (PCA). Roughly speaking, PCA projects the data over the directions of the space that yield the maximum variance. Inevitably, this results in throwing away information for gaining clarity.

Tensor decomposition has been used recently in order to study temporal graphs [START_REF] Sapienza | Detecting Anomalies in Time-Varying Networks Using Tensor Decomposition[END_REF] [START_REF] Gauvin | Detecting the Community Structure and Activity Patterns of Temporal Networks: A Non-Negative Tensor Factorization Approach[END_REF]. Tensor decomposition can also be seen as a dimension reduction technique from multi-dimensional arrays to matrices. First recall that the rank of a matrix is the minimum number of column vectors needed to span the range of the matrix. A matrix thus has rank one if it can be written as an outer product of two nonzero vectors:

A = u • v = uv T .
More generally, the rank of a matrix is the smallest number of such outer products that can be summed to produce it:

A = u 1 v T 1 + u 2 v T 2 + ... + u k v T k (5.4)
Similarly, a N-way tensor of rank one is a tensor that can be written as an outer product of N vectors:

T = u 1 • u 2 • ... • u N (5.5)
It has been shown that every tensor could be expressed as a sum of rank 1 tensors [START_REF] Huy Phan | Nonnegative Matrix and Tensor Factorizations[END_REF]. The rank of a tensor T is thus defined as the minimum number of rank 1 tensors with which it is possible to express T as a sum. This means that a three dimensional tensor T of rank R can be decomposed as a sum of R rank 1 tensors:

T = R r=1 a r • b r • c r = {A, B, C} (5.6)
where A = (a 0 , a 1 , ..., a R ), B = (b 0 , b 1 , ..., b R ), and C = (c 0 , c 1 , ..., c R ) are the loading matrices of T .

Tensor factorization

Finding matrices A, B, and C of equation 5.6 given T is not trivial at all and is a problem on its own. The problem can be relaxed in the following way [START_REF] Huy Phan | Nonnegative Matrix and Tensor Factorizations[END_REF] :

T = {A, B, C} + E (5.7)

Tensors

67

where E denotes the residuals. Obviously, we seek the matrices A, B, and C such that we minimize the residuals, or equivalently, the difference between the data T and the model {A, B, C}. The most commonly used model to factorize tensor is the PARAFAC model :

x ijk = R l=1 a il b jl c kl + e ijk (5.8)
The idea behind PARAFAC is to use an alternative least square algorithm (ALS) that computes iteratively the difference between the data and the model, update the model accordingly, and loop until convergence is reached. There are multiple difficulties when fitting a PARAFAC model to data among which the slow convergence or the necessary initialization of the model that can impact the end results as well as the convergence speed. The PARAFAC model tries to find a decomposition that fits the data as well as possible, but the rank of the tensor that we are looking for is unknown. That is, the number of components is unknown and has to be specified by the user.

This again looks similar to PCA where the user has to provide the number of components. However, the components for PCA do not change when the model is fitted with a different number of components. That is, the axes are always the same and ranked in the same order no matter how many are computed. This means that one can simply select the number of components that gives the desired complexity / interpretability ratio, and discard the others. This is not the case for PARAFAC which components completely change when fitting with different numbers of components. The point is that, by selecting too many components, the model will probably overfit the data, and underfit with too few components.

Finding the right value for the number of components is again far from trivial and can be done in different ways. The most common technique is called the core consistency check [START_REF] Bro | A new efficient method for determining the number of components in PARAFAC models[END_REF] [START_REF] Huy Phan | Nonnegative Matrix and Tensor Factorizations[END_REF]. Explaining all the details about core consistency is out of the scope of this paper, however we present here the general idea such that the reader with no tensor decomposition knowledge is not lost. As a matter of fact, PARAFAC can be seen as a restricted version of the more general Tucker3 model [START_REF] Huy Phan | Nonnegative Matrix and Tensor Factorizations[END_REF] (see figure 5.3) :

x ijk = w 1 l=1 w 2 m=1 w 3 n=1 a il b jm c kn g lmn + e ijk
(5.9)

The decomposition provided by the Tucker3 model contains a core 3 dimensional array G = (g ijk ). Basically, the outer product between the ith factor from A, the jth factor from B and the kth factor from C is weighted by the g ijk element of the core G. PARAFAC is a restricted version of Tucker3 in the sense that it can be seen as a Tucker3 with a core containing only zeros except on the diagonal which contains only ones.

Imagine now that we want to fit our data with a three components PARAFAC and Tucker3 model. If a three component PARAFAC model is appropriate, it means that the core of the Tucker3 model will be close to a tensor with 3 ones on the diagonal and 24 zeros elsewhere (denoted by H in the following). We can compute a metric that basically indicates if the core G that we found is close to H. The most commonly used metric is the core consistency : Core Consistency = 100

1 -F i=1 F j=1 F k=1 (g ijk -h ijk ) 2 F i=1 F j=1 F k=1 t 2 ijk (5.10)
A core consistency between 100% and 80% indicates good fit while much lower values or even negative values indicate that the fit is poor. Generally, the core consistency is quite high for small numbers of components, but the variance explained by the model is quite low. When we increase the number of components, the core consistency decreases while the variance explained increases. Hopefully, if PARAFAC is appropriate to model the data, there might be a point where the core consistency drops from an acceptable value to a much smaller value, and might indicate what number of components to use.

The question of how to interpret the decomposition remains [START_REF] Sapienza | Detecting Anomalies in Time-Varying Networks Using Tensor Decomposition[END_REF] [27].

Results

69

Let suppose that we are studying what people write (on Twitter for example). For a set of users, we can collect the tweets that he/she published as well as the time at which they were published. By splitting these tweets into words, we obtain, for each user, a list of terms that were used at different times. If we wish to represent the data as a temporal network, we could use a three way tensor X ∈ N ×M ×T such that x nmt indicates if the term m was used by user n at time t. If we decompose X = {A, B, C} with K components, we have :

• A N ×K is the association of each user n to a factor k

• B M ×K is the association of each term m to a factor k

• C T ×K shows the time activity of each factor

In the case of dynamic correlation graphs, the tensor stacks a sequence of adjacency matrices in a third dimension, such that the frontal slices of the tensor are symmetric. In this particular case, the matrices A and B are equivalent and provides the same information. This means that, for temporal undirected networks, matrices A and B associate each user to the factors, and C provides the time activity of each factor. We show in the next section examples of the PARAFAC decomposition.

Results

An illustrative example

We build here an illustrative example to show how the decomposition of dynamic correlation networks works. We create artificially correlated clusters of timeseries with the following procedure. We draw N clusters random signals (here N clusters = 3) of length L (here L = 500) such that the different signals are uncorrelated. We then generate N samples (here N = 99) of length L by adding noise to the cluster signals. This way, we have a simple structure of 3 clusters of 33 series that are strongly correlated within a cluster, and poorly across clusters.

The correlation matrix computed over the whole length of the sample is visible on figure 5.4 (left panel). As expected, the three clusters structure of the data is clearly visible. This random and stationary example is a case where simple static correlation graphs completely render the correlation structure. But most data are not that simple. Most of the time they are the results of some complex and non stationary processes.

Let us now introduce a perturbation in the data. Lets imagine that the timeseries represent stock values on financial markets for instance (even if this is pretty unrealistic). The clusters could be the economic sectors, since the stocks within a same sector tend to be more correlated than across sectors. During economic crisis, people tend to lose their self control and often act in a very correlated fashion. We introduce a small perturbation in the data supposed to represent a crisis impacting some, but not all, sectors. Besides, only a fraction of nodes within the concerned sectors will be impacted. More precisely, between t = 50 and t = 100, we assume that the nodes {20, 21, 22, ..., 39, 40} correlate quite strongly. That is, a fraction of cluster 1 and a fraction of cluster 2 will be way more correlated than before during this period, but afterwards everything will be back to "normal". By looking at the new correlation matrix on figure 5.4 (right panel), we still see the global structure of three correlated clusters, but we completely miss the perturbation that we introduced. Actually, it is very hard to spot any difference between the before and after perturbation correlation matrices. Even with the nodes ordered properly and with the knowledge of the impacted nodes, we can hardly see a difference between the two correlation matrices. The reason is that these matrices are obtained by computing the correlation over the total length of the samples, averaging out the perturbation introduced above.

Figure 5.5 shows snapshots of the filtered correlation graph, where the nodes are colored and positioned according to their cluster. The first and last snapshots show the topology at times outside the perturbation window, and the three middle snapshots show the topology within the perturbation. For such a simple example, the perturbation is clearly visible since there is a net increase of connectivity between blue and red nodes in the three middle snapshots. Nevertheless, for realistic situations with more nodes and more complex perturbations, recovering the structure by looking at snapshots of the topology might become complicated.

Another simple way for studying this graph would consist of plotting diverse metrics versus time. For example, plotting the number of edges at the different times clearly shows an increase during t ∈ [START_REF] Logenthiran | Demand side management in smart grid using heuristic optimization[END_REF][START_REF] Zivot | Chapter 1 Portfolio Theory with Matrix Algebra[END_REF]. Because the situation here is extremely simple, we would be able to detect the perturbation with such a direct approach. However, in real situations this would probably not be feasible. Actually, it is not hard to build an example where two perturbations occurring at the same time have opposite consequences on a global metric such as the number of edges. In this case, the perturbations would be undetectable by this approach.

Our objective is thus to use tensor decomposition of the temporal graph in order to recover both the clusters and the perturbation. Figure 5.6 shows the results when using PARAFAC tensor decomposition on the present simple illustrative model. Recall that we need to find the number of components of the model that we want to fit. For this purpose, we use the core consistency check introduced in the previous section. The top left subplot of figure 5.6 shows the core consistency of the decomposition. Clearly, there is a sharp drop between 4 and 5 factors. This means that using 5 or more components for the model will probably overfit the data, while using 3 or less components will probably underfit. In other words, this tells us that we should use 4 factors for the decomposition although this can seem surprising since we know that N clusters = 3.

The top right plot of figure 5.6 shows the matrix A of the decomposition (matrix B is not shown because it exhibits the same information since the frontal slices of the tensor are symmetric). We can see first that each cluster is recovered: nodes {0, 1, ..., 32} are mostly represented by factor 2, nodes {33, 34, ..., 65} by factor 1, and nodes {66, 67, ..., 98} by factor 3. Additionally, nodes {20, 21, ..., 40} are also represented by factor 0. The bottom subplot of figure 5.6 shows the temporal activity of the 4 factors. Factors 1, 2, and 3 look pretty close to noise (because they are, due to the model), but factor 0 has a clear peak of activity during the period t ∈ [50; 100]. This means that the nodes {20, 21, ..., 40}, associated with this factor, tend to have way more links during this period than during the rest of the simulation. The PARAFAC model was thus able to capture both the cluster structure and the short time perturbation that we introduced.

Using tensor decomposition on real data

We now investigate how this method works on real data. As a an example, we use individual electricity consumption data that can be obtained from the Irish Social Science Data Archive (ISSDA) [START_REF]Irish Social Science Data Archive[END_REF]. The Commission for Energy Regulation (CER) is the regulator for the electricity and natural gas sectors in Ireland. They initiated a smart metering project in 2007 with the purpose of undertaking trials to assess the performance of smart meters, their impact on consumers' energy consumption and the economic case for a wider national rollout. The project took place during 2009 and 2010 with over 5000 Irish homes and businesses participating. The customers, who participated in the trials had an electricity smart meter installed in their homes/premises and agreed to take part in the research project.

The dataset that we use contains the electricity consumption of these anonymized users. The records start around the 15th July 2009 and end the 31 December 2010 with a sampling frequency of one record every 30 minutes. We select a random sample of a hundred users and only look at the correlation over August 2009 (for example). Because this tensor already contains 100 × 100 × 31 × 24 × 2 = 14, 88.10 6 integers, increasing either the population size or the time window quickly triggers memory issues. There are multiples ways this can be improved. First of all, since the frontal slices are symmetric, we have redundant information that we could get rid of by considering only the upper or lower triangle matrices. Secondly, since we consider adjacency matrices of filtered correlation graphs, we have the possibility to "sparsify" the graphs by tuning the filter threshold. By doing so, we should obtain sparse three dimensional tensors that would theoretically require less memory to be stored. Of course, this is not "free" since at some point, a higher filter threshold would throw away meaningful information. At the time this chapter is written, this is still ongoing work, such that we only present here the result of tensor decomposition on the reduced example (100 users during August 2009).

Figure 5.7 shows the result of tensor decomposition on this reduced example. By using the core consistency check, we found that a 6 component PARAFAC model may be a good choice. The left panel of figure 5.7 shows the matrix A that maps the users to the factors. The right panel shows the activity of each factor during the month of August. By looking at factor 0 (at the bottom) we clearly see some periodic pattern. Indeed, nodes attributed to this component tend to correlate during the week and are uncorrelated on weekends. It means that these nodes tend to consume power in a correlated fashion during the week while this is much less marked in the weekends. The other factors are more noisy but also exhibit some periodic behaviors. For example, factor 1 tends to have a spike of activity every Monday.

Clearly, both node attribution and temporal activity of the factors are much more noisy than the ones obtained in the toy model. Although this had to be expected due to the presence of noise in real data, there may be some improvements that could be done to the method that we wish to look at in a near future. Furthermore the dataset also provides information about the users, such that checking what kind of users are clustered together could give insights about the quality of the results.

Discussion

Chapter 5 presented dynamic correlation graphs studied through a tensor decomposition method. This method uses the PARAFAC model that fits the data tensor with a decomposition that can be represented with three matrices. When fitting the model, one has to provide the number of components. On the contrary to PCA, this number has to be selected carefully such that there is no underfitting or overfitting. A method for estimating this number is the core consistency check that, ideally, exhibit a sudden drop when the number of components is too large. We showed in this chapter that this method could be used with success for studying dynamic correlation graphs. The illustrative model, studied in section 5.4.1, showed that we were able to find both the underlying structure and short time events within the data. We then proposed a real world example in section 5.4.2 where we studied a correlation graph of the electricity consumption of Irish homes and businesses. We showed that periodic pattern of correlation could be extracted and nodes classified according to these patterns.

We want to stress out the fact that the work presented in this chapter is still ongoing and had to be paused due to thesis report obligations. Hopefully, this will be improved and completed in a near future.

The three following chapters also deal with prosumer agents within the smart grid, but a different approach is explored. Until now, the electricity network was not explicitly considered, that is, we did not assume any topology nor physical constraints. In the following chapter, we introduce dynamics on networks and explain how the power grid could be represented in a tractable model.

Part II

Storage Placement in Prosumer Networks

In the first part of this thesis we studied prosumers on a high level, such that network topologies and power dynamics were abstracted. In this second part, the electrical grid and the physical constraints of the system will be considered explicitly. We assume here a network of prosumers interconnected with electrical lines. Some of these agents can be viewed as generators while others can be viewed as pure loads. As we saw in the first part, prosumers extra-productions are likely to change for diverse reasons such that these generators and loads might not be fixed on the contrary to current power grid. We will see that the equilibrium between production and consumption is a necessary condition for stability. But, in this stochastic context, it seems quite unlikely to hold without interventions of the operator.

There exists multiple ways to adjust production and consumption (see chapter 2), but we focus here on storage devices such as batteries. The main question that we answer in this second part is to find the set of locations, within a prosumer network, for installing these storages. Obviously, the more storage we install, the easier the control of the system, the extreme case being one storage device per node. For budget reasons, it seems quite likely that only a fraction of the nodes will be equipped with storage devices, at least at the beginning. As one might expect, we show in this part that all sets are not equally efficient, even when they are of the same size. We propose here to quantify this efficiency notion and to tackle the problem from a controllability perspective. More precisely, we wish to find the subset of nodes in the graph that would require the minimum energy to control the system on average of the possible perturbations, given that generators and loads might change over time.

This second part is organized in two chapters. Chapter 6 gives the required notions on dynamics on networks and control of networks. Chapter 7 explains how we answered the storage location problem. We indeed propose an algorithm, based on submodular set functions, that takes the physical constraints of the system into account and outputs a set of locations that enables the control with low energy. The work presented in chapter 7 was submitted to the SmartGridComm 2016 conference and is currently under review.

Chapter 6

Power Grid Dynamics and Control

This chapter is divided in two main sections. Section 6.1 is related to the dynamics in networks and aims to explain how the non-linear power grid dynamics can be expressed through a concise synchronization model. We start by giving some notions about dynamics on networks and how they can be studied. We focus then on synchronization, and especially on the Kuramoto model that will be used later on to simplify the power grid dynamics. We also provide, at the end of this first section, some examples as to give to the non specialist reader some intuition for the model. Section 6.2 introduces control theory through the special case of networks. More precisely, we consider the case of a dynamic on a given network that we wish to control. We first explain what is control and what are the state-of-the-art tools to discuss the controllability of networks. We then focus on optimal control which aims at finding the right inputs such that a specific cost function is minimized.

Power grid dynamics

Dynamical systems

Dynamical systems theory considers how systems change over time. A dynamical system is a system whose state is uniquely specified by a set of variables and whose behavior is described by predefined rules [START_REF] Sayama | [END_REF]. Dynamical systems are pretty much everywhere and can be very different, the growth of populations, the motions of objects, the swinging pendulum, or even the behavior of "rational" individuals can all be represented as dynamical systems. There are two classic ways for studying their dynamics: the discrete time steps approach or the continuous time approach. Their general mathematical formulations are as follows:

• Discrete time dynamic :

x t = F (x t-1 , t) (6.1)
• Continuous time dynamic :

dx dt = F (x, t) (6.2)
where x t is the state vector of the system at time t. That is, x t contains the state variables of the system at time t. F is the function that encodes Chapter 6. Power Grid Dynamics and Control the dynamics of the system and can take various forms from simple linear functions to much more complicated non-linear ones.

For "simple" systems, although the dynamics might be quite complicated, the number of variables involved is usually relatively small. For these systems it might be possible to observe their behavior with standard methods such as time series, phase space plots, or cobweb plots [START_REF] Sayama | [END_REF]. However, when it comes to complex systems, the number of variables involved in the model jumps from just a few to thousands or tens of thousands. In addition, all dynamical components may interact with each other in nontrivial ways. This is exactly what makes complex systems so difficult to study, but at the same time so fascinating. Key concepts, such as emergence and self-organization, all derive from the fact that such a system is made of a massive amount of interactive components. Studying these properties at various scales and understanding how these properties are linked across scales is the basic approach for studying complex systems.

Networks and dynamics

Although dynamical (complex) systems are a very interesting topic, it is out of the scope of the present thesis. We will focus here on the special case of networks for which we can discern three different kinds of dynamics:

• Dynamics on networks: Usually, models of this category consider how the states of the nodes change over time through the interactions represented by the links between them. A key point is that the topology of the network is fixed over time, only the states of the nodes are evolving.

• Dynamics of networks: These models consider dynamical changes of the network topology over time. The reasons might be to understand the mechanisms that give birth to particular network topologies (preferential attachment for example), to evaluate robustness and vulnerability of networks, or to understand how to improve certain properties of networks.

• Adaptive networks: These models describe the co-evolution of dynamics on and of networks, where node states and network topologies dynamically change adaptively to each other.

The power grid dynamic clearly belongs to the first class, since the desired model should explain how current is exchanged between interconnected fixed units. The topology of the grid might change with the addition of new lines, transformers, generators and so on, but the time-scale at which such modifications occur is much larger than the time-scale of the power dynamic, such that we can consider that the grid topology is fixed over time.

The general idea of dynamics on networks is that each node i is associated to one (or more) variable(s) x i . Each node is connected to other nodes, i.e its neighbors, that impact the value of x i . In turn, i also impacts the values of its neighbors' variables x j , j ∈ N i . The rules that describe how these modifications occur are the essence of the model. For example, epidemic models try to explain the diffusion of diseases or information in a network. Roughly speaking, the variables x i says whether the node is infected or susceptible to become infected, and the links account for the presence of contacts between individuals. The disease then spreads along links from infected individuals to susceptible ones with some probability. Of course, numerous variants have been developed, and these models are used in unexpected domains such as viral marketing for instance.

Other models focus on explaining the emergence of global information when individuals all have different opinions at the beginning. In this case, the variable x i represents the belief of node i and its value is updated by taking into consideration the beliefs of its neighbors. Imagine that we wish to compute the mean belief x AV G = 1 N i x i in such a distributed way :

X(t + 1) = W X(t) (6.3)
where X(t) = {x 0 (t), x 1 (t), ..., x N (t)} is the vector of beliefs at time t, and W is the following matrix :

W ij =      1 max{k i ,k j }+1 if (i, j) ∈ E 1 -l∈N i 1 max{k i ,k l } if i = j 0 otherwise (6.4)
where k i is the degree of node i. Figure 6.1 shows an example with simple network topologies. After convergence of the algorithm, all nodes have the same average value. However, the speed of convergence is clearly impacted by the topology of the network. Such consensus models can be used to recover true information from several noisy measurements of sensors for instance. Because of their distributed nature they also provide an interesting framework for smart grid systems. [START_REF] Zhang | Incremental cost consensus algorithm in a smart grid environment[END_REF] for example uses distributed consensus algorithms in order to re-dispatch production among generators after a power imbalance.

The literature on dynamical models on networks is very rich and is a trendy subject. In the next section, we will focus on synchronization models that share some characteristics with consensus algorithms.

Coupled oscillators

In 1665 Christian Huygens noticed that the two clocks placed on his mantelpiece had acquired an opposing motion. That is, their pendulums were beating in unison but in the opposite direction. Regardless of how the two clocks were started, he found that they would return to this state. This is the first recorded observation of a coupled oscillator system. The reason for such a behavior was that the two pendulums were affecting each other through slight motions of the supporting mantelpiece. He reported the results by letter to the Royal Society and it was referred to as "an odd kind of sympathy" in the Society's minutes. This concept is now known as entrainment.

Since the discovery of Christian Huygens, coupled oscillators have been extensively studied in the physics community. Amusing experiments with metronomes placed on a wooden board, itself placed on wheels are visible on the internet (see for instance Kuramoto model). Yet, synchronization arises in various natural systems where the coupling seems less obvious than the wooden board. For instance, it is known that fireflies clouds achieve synchronization of their flash while no entity gives the global frequency. That is, fireflies do not look at a single bandmaster on which they try to synchronize, they rather have a small local knowledge of the neighboring bugs. How is it possible to explain the emergence of synchronization in such a complex system ?

Simple Kuramoto model

Although coupled oscillators were known for centuries, a complex system approach of coupled oscillators had to wait until 1975, year in which the Kuramoto model was published [START_REF] Kuramoto | Lecture Notes in Physics, International Symposium on Mathematical Problems in Theoretical Physics[END_REF]. This model was first proposed by Yoshiki Kuramoto and is a mathematical model used to describe synchronization. In the most popular version, each of the oscillators is considered to have its own intrinsic natural frequency ω i , and each is coupled equally to all other oscillators. In this situation, the dynamic is often written as :

dθ i dt = ω i + K N N j=1
sin(θ jθ i ), i = 1 . . . N (6.5)

Power grid dynamics

83

This is clearly a nonlinear model but, as N → ∞, this model can be solved exactly [START_REF] Steven | From Kuramoto to Crawford: exploring the onset of synchronization in populations of coupled oscillators[END_REF]. Let us introduce the order parameters r and ψ as :

re iψ = 1 N N j=1
e iθ j (6.6)

In equation 6.6, r represents the phase-coherence of the oscillators, while ψ indicates the average phase. By combining equations 6.5 and 6.6, we can re-write the dynamic as :

dθ i dt = ω i + Kr sin(ψ -θ i ) (6.7)
Which can further be simplified by working on a rotating frame (thus setting ψ = 0) :

dθ i dt = ω i -Kr sin(θ i ) (6.8)
In this situation, by using the order parameter, we are thus able to decouple the equations.

Most of the time however, the coupling is not general and a given oscillator is only coupled to a set of neighbors (the right-hand side sum of equation 6.5 goes only on the neighbors of node i). In this context, a graph representation is often used such that nodes represent oscillators and link weights indicate the strength of the coupling between two nodes. A more general form for the dynamic of the system can be written as :

D i θi = ω i - N j=1 a ij sin (θ i -θ j ) (6.9)
where a ij is the "row i, column j" term of adjacency matrix A, and D i is the damping coefficient of node i.

Synchronization

The purpose of the Kuramoto model is to study and explain how synchronization occurs in a system of interacting units. One of the most fascinating thing about oscillators networks is that, in certain conditions, nodes that have only local knowledge are able to synchronize at the system level to a main frequency. Phrased in this way, synchronization seems close to consensus, and there are indeed strong similarities between the two phenomena. The key question is whether we can predict if a given network will synchronize or not. Intuitively, there are multiple parameters that impact the synchronization of a network. For example, we expect both the distribution of the natural frequencies g(ω) and the topology of the underlying network to have an impact on the synchronization. The most obvious definition of synchronization is that all frequencies are equal to a same value : ω i = ω sync , ∀i. However, another important notion is the phase cohesiveness γ that quantifies the spread of the phase angles. That is, we say that a solution has phase cohesiveness γ if every pair of connected oscillators has phase distance smaller than some angle γ ∈ [0, π/2[ : |θ iθ j | ≤ γ, ∀(i, j) ∈ E. A very interesting work by Florian Dörfler [START_REF] Dörfler | Synchronization in complex oscillator networks and smart grids[END_REF] showed that the synchronization condition could be written in a surprisingly concise way. For a network of coupled oscillators with adjacency matrix A, Laplacian matrix L, and vector of natural frequencies ω, the synchronization condition can be written as :

L † ω ∞,E ≤ sin(γ) (6.10)
where L † is the Moore-Penrose pseudo inverse of L, and

x ∞,E = max {i,j}∈E |x i -x j | (6.11)
is the worst case dissimilarity for a vector x = (x 1 , x 2 , ..., x n ) over the edge set E. This means that, if this condition is respected for a given network, it will synchronize with phase cohesiveness γ to a common frequency :

ω sync = N k=1 ω k N k=1 D k (6.12)
For the classic Kuramoto oscillator model coupled in a complete graph with uniform weights a ij = K/N (see equation 6.5), the synchronization condition 6.10 reduces to the condition K > max i,j∈{1,...,N } |ω iω j |. That is, the coupling strength has to be larger than the maximum natural frequencies dissimilarity in order for the system to synchronize.

From oscillators to the power grid

At first glance the link between oscillators and the power grid might not seem obvious. In this section we explain briefly why a kuramoto-like model is an interesting choice for modeling the power grid dynamic.

The power grid can be roughly seen as generators linked to loads through electrical lines (see figure 6.3). A generator is an electric machine that converts mechanical energy to electrical energy. Other kind of electric machines are motors that convert electrical energy to mechanical energy, and transformers that change the voltage level of an alternating current. Electromagnetic generators can be divided in two broad categories: dynamos and alternators. The formers generate direct current while the latter generate alternating current.

Electric machines are composed of a rotating part called the rotor, and a static part called the stator. The rotor generates a moving magnetic field around the stator, which induces a voltage difference between the windings of the stator. This produces the alternating current (AC) output of the generator. In simple words, the rotating speed of the rotor impacts directly the electric production of the generator, such that it could be possible to model the dynamic of the power grid by considering the phase angles and frequencies of the rotating parts of the elements in the grid.

Modeling the power grid dynamic

In this section, we introduce the coupled oscillators network model used to simplify the power grid dynamic. More details can be found in [START_REF] Filatrella | Analysis of a power grid using a Kuramoto-like model[END_REF].

The objective is to achieve synchronization of the grid at the main frequency Ω = 50Hz. Each oscillator i has a phase angle δ i and a frequency δi . Therefore, we seek an equilibrium of the form :

δi = Ω, ∀i (6.13)
For convenience, we express the dynamic of the oscillators in terms of the deviations from the main frequency : δ i (t) = Ωt+θ i (t). Let ω i = θi , such that δi = Ω + ω i . The equilibrium, in terms of the deviations dynamics, is : ∀i, ω i = 0

The next step consists in translating the dynamics of the generators and machines into equations involving the phase angles θ i and the frequencies ω i . Generators and machines are composed of a turbine that dissipates energy at a rate proportional to the square of the angular velocity :

P diss,i (t) = K Di ( δi (t)) 2 (6.14)
where K Di is the dissipation constant of entity i. Furthermore, it also accumulates kinetic energy at a rate :

P acc,i (t) = 1 2 I i d dt δi (t) 2 (6.15)
where I i is the moment of inertia of entity i. For simplicity, we consider that all entities have the same dissipation constants(K D ) and moment of inertia (I). The condition for the power transmission between i and j is that the two devices do not operate in phase. The phase difference between i and j is :

δ j (t) -δ i (t) = Ωt + θ j (t) -Ωt -θ i (t) = θ j (t) -θ i (t).
The transmitted power along the line can be written as :

P transmitted = -P M AX ij sin(θ j -θ i ) (6.16) with P M AX ij
being the maximum capacity of the line (i, j). Each entity i is then described by a power balance equation of the type (see figure 6.3) : P S,i = P diss,i + P acc,i + P transmitted,i , (6.17)

where P S,i is the power of an ideal source or sink at node i. By substituting equations 6.14, 6.15, and 6.16 into equation 6.17 and re-arranging the terms, we obtain the following non-linear coupled system of equations :

Chapter 6. Power Grid Dynamics and Control

P M A X = 2 P M A X = 2 0 1 2 P0 = 2.0 P1 = -1.0 P2 = -
P S,i = IΩ θi + I θi + 2K D Ω θi + K D Ω 2 +K D θi 2 -j∈N i P M AX ij sin [θ j -θ i ] (6.18)
We now use simplifications based on the fact that we consider small deviations from the main frequency : δi ∼ Ω which means that ω i = θi << Ω, such that the squared term K D θ2 i can be neglected. Moreover, we assume that the rate at which energy is stored in the kinetic term is much less than the rate at which energy is dissipated by friction : θi << 2K D I (see [START_REF] Filatrella | Analysis of a power grid using a Kuramoto-like model[END_REF] for more details). Equation 6.18 becomes :

θi ∼ ψ i -α θi - j =i K ij sin [θ j -θ i ] (6.19) where α = 2K D I is the dissipation term, K ij = P M AX ij IΩ
are the coupling strengths, and

ψ i = P S,i IΩ -K D Ω I
encodes the power distribution of the elements. In order not to overload the equations in the following, we simplify the constant term K D Ω I by working in a rotating frame such that ψ i = P S,i IΩ .

Examples

In this section we show some examples where we use the model 6.19 to simulate the grid dynamic. We first consider a very simple network with a generator feeding two machines (see left panel of figure 6.4). We assume that the generator produces 2 units of power and that machines consume one unit each, such that the production matches the consumption. Moreover, the maximum capacities of the lines are set to 2 units and we take the following values for the parameters : I = 10 -1 , K D = 10 -1 , and Ω = 50Hz. We select the initial state randomly inside some hypersphere centered on the stable state. This will result in a transient phase before synchronization that is visible on the right plots of figure 6.4. We also show the power that flows on each electrical line. As visible, the power oscillates during the Power flow on line (0,2)

P M A X = 2 P M A X = 2 0 1 2 P0 = 2.0 P1 = -1 → P1 = -2 → P1 = -1 P2 = -1.0 FIGURE 6.5:
Simple example of the effect of a power mismatch in the Kuramoto-like model for the power grid dynamic.

transient but stabilizes to one unit on each line. We also see that during, the transient, no line is overloaded (P ij (t) < P M AX ∀t).

It is interesting to observe how the model reacts when there is a mismatch between production and consumption. For this simulation we start in the same conditions as the previous one, but between t = 600 and t = 1000, we introduce a perturbation. During this period, one of the machine will consume 2 units of power instead of one. This results in a power imbalance that steers the frequencies away from the synchronized state as visible on figure 6.5. Indeed, after t = 600, the frequency drops significantly before reaching the synchronized state after t = 1000. Although such a mismatch does not seem to cause much problem in the model, this could result in dramatic damages on real power systems.

Control in networks 6.2.1 What is control ?

In this section, we introduce some key notions related to the controllability of complex networks. Although we are concerned with control in networks here, control theory has a much larger spectrum of applications. Control theory asks how to influence the behavior of a dynamical system with appropriately chosen inputs so that the system's output follows a desired trajectory or ends in some chosen final state. One of the most fundamental notion of control theory is the feedback. Basically, the difference between the actual and the desired final state is applied as a feedback into the system input. By acting so, the system's output converges to the desired value.

Obviously, we need a way of representing the state of the system and the equations that govern its evolution. The concept of state was introduced into control theory by Rudolf Kalman in 1960s, and was inspired by the phase space concept used in physics. Any state of a dynamical system can then be represented as a vector in the state space where the axes correspond Chapter 6. Power Grid Dynamics and Control to the state variables. The equations governing the dynamic are usually written in the form of a set of differential equations :

ẋ(t) = F (t, x(t), u(t); Θ) y(t) = H(t, x(t), u(t); Θ) (6.20)
In equation 6.20, x(t) ∈ N is the state vector of the system at time t, and u(t) ∈ M is the input vector of control signals injected at time t. Θ is the set of system parameters, and y(t) is the observed state of the system. Obviously, the study of system 6.20 highly depends on the functions F and H. There exists two main categories for these functions : linear and nonlinear.

A large part of control theory focuses on the study of linear systems because non-linear systems are known to be much more difficult to study. A classic approach that partially overcomes the difficulties due to nonlinearity is to linearize the systems around their equilibrium points. It is then possible to look at the controllability of the linearized version of the system.

For complex systems, things become quite difficult since they comprise many interacting units on which we often lack full knowledge. It means that we may not know all the details about equations 6.20. Nevertheless, there has been extensive work on understanding control of these systems, such that we are able to discuss the controllability of a system without the precise and complete knowledge of all the parameters.

In the rest of the section, we focus on control in networks. We consider a graph G = (V, E) of N nodes, where V is the vertex set and E is the edge set. The topology of this network can be encoded through the adjacency matrix M, which element m ij ∈ {0, 1} indicates whether i and j are connected. If the edges are weighted we can set m ij = w ij where w ij is the weight of edge(i, j), and zero if there is no edge. Graphs are often used to model complex interactions inside a population. Let us attribute to each node i the variable x i that represents the state of node i. Depending on the model, this state can represent an opinion, a physical quantity, a probability and so on. If there is an edge between i and j, we might expect some interaction that would eventually change the values of x i and x j . Such a dynamic is usually described with a system of differential equations. If we assume a linear first order dynamic, this can be written as Ẋ(t) = AX(t), where X(t) = {x 0 (t), ..., x N -1 (t)} is the vector of node states at time t, and matrix A encodes both the dynamics and the topology of the system (A can be, among other, the weighted adjacency matrix of the underlying graph).

If there is no action from the outside, the system state will evolve according to X(t) = X 0 e At where X 0 is the initial state of the system. Imagine now, that this dynamic could be somehow influenced by injecting some signals. More precisely, let us assume that we can inject these signals in a subset of the nodes, called drivers, such that the dynamics becomes Ẋ(t) = AX(t) + Bu(t), where the matrix B indicates which nodes receive the signals and u(t) is the vector of inputs at time t. Assume that the system is in some initial state X 0 and we aim at bringing it to some final state X T in some amount of time T. Control can be seen as finding the sequence of inputs {u(t 0 ), ...u(t T )} that would do it given the dynamics A. Furthermore, we say that the system is controllable in T steps if it can be steered from FIGURE 6.6: Controllability of networks. Source : [START_REF] Liu | Control Principles of Complex Networks[END_REF] any initial state X 0 to any final state X T through a sequence of control inputs. This means that drivers may or may not enable the full control of the system depending on the dynamic, the topology, and of course the selected drivers.

Figure 6.6 presents a very small example of a three node network. On subplot a of figure 6.6 we apply a single control input on node 1. Although it might seem surprising to some reader, the system is not fully controlled by only one input on node 1 [START_REF] Liu | Control Principles of Complex Networks[END_REF]. Indeed, by changing the input u 1 (t), x 2 (t) and x 3 (t) can only evolve in a correlated fashion. This can be verified by writing the dynamic equations where the result is that the system state is stuck in some hyperplan a 31 x 2 (t) = a 21 x 3 (t) as shown on subplot b. As a matter of fact, it is impossible to fully control this small network with a single input, and one has to add another driver (either node 2 or node 3) as shown on subplot c of figure 6.6.

The example of figure 6.6 was simple enough so that we were able to determine if a given set of drivers controlled the system, and what was the smallest driver set that could control the system. In practice, for larger systems, these two questions are far from trivial and are at the heart of several fascinating works.

Kalman rank criterion

A classical result for quantifying the ability of driver sets to control a system was proposed by Kalman. He showed that a linear system (A, B) is controllable if the controllability matrix

C = [B, AB, A 2 B, ..., A N -1 B] (6.21)
has full rank [START_REF] Ogata | Modern Control Engineering. Instrumentation and controls series[END_REF]. That is :

rank(C) = N (6.22)
For the small example of figure 6.6 (subplot a) we have :

C =    b 1 0 0 0 a 21 b 1 0 0 a 31 b 1 0    (6.23) 90
Chapter 6. Power Grid Dynamics and Control which does not have full rank, hence the system of figure 6.6.a is not controllable. For the subplot c, we have :

C =    b 1 0 0 0 0 0 0 b 2 a 21 b 1 0 0 0 0 0 a 31 b 1 0 0 0    (6.24)
which, in this case, has full rank, meaning the system of figure 6.6.c is controllable.

Kalman's rank criterion appears as a nice and concise condition to test the controllability of a given system. Nevertheless, this approach quickly becomes complicated when studying the controllability of non trivial networks. Indeed, in such cases matrix C becomes huge and requires large amount of memory. In addition, computing the rank of very large matrix can be time consuming, especially if such operation has to be done repetitively. But even more problematic is the numeric precision of the machine on which the matrix is computed. If the system is stable, we have that A k -→ 0 when k -→ ∞. Since the matrix A is taken at large power exponents for these real systems, differentiating zeros from non zeros quickly becomes an issue, and yields inaccurate rank computations [START_REF] Liu | Control Principles of Complex Networks[END_REF]. This means, that other methods have to be employed to determine the controllability of a system.

PHB test

The Popov-Belevitch-Hautus (PBH) controllability test [START_REF] Camlibel | Popov-Belevitch-Hautus type controllability tests for linear complementarity systems[END_REF] states that the system (A, B) is controllable if and only if :

rank [sI -A, B] = N, ∀s ∈ C (6.25)
Since the sI -A block of the matrix [sI -A, B] has full rank whenever s is not an eigenvalue of A, we only need to check each eigenvalue of A for the PBH test. Although the PBH test links controllability to the eigenvalues and eigenvectors of matrix A, it can be shown to be equivalent to the Kalman's rank condition.

The PBH test can also be used to determine the minimum number of drivers required to fully control the system. First recall that for an eigenvalue λ, its algebraic multiplicity is the multiplicity of λ as a root of the characteristic polynomial p(λ) = det(A -λI). The geometric multiplicity of λ is the maximal number of linearly independent eigenvectors corresponding to this eigenvalue. It can be shown that the number of control inputs must be greater than or equal to the largest geometric multiplicity of the eigenvalues of A :

N D = max i {µ(λ i )} (6.26) where µ(λ i ) = dim(V λ i ) = N -rank(λ i IN -A)
is the geometric multiplicity of eigenvalue λ i (which is also the dimension of its eigenspace). Note that for undirected networks the adjacency matrix is symmetric, such that the algebraic multiplicity is equivalent to the geometric multiplicity.

Based on the PBH test and the spectral study of A, [START_REF] Yuan | Exact controllability of complex networks[END_REF] built an algorithm for finding the minimum driver set to control a system. One of the FIGURE 6.7: Structural controllability. Source : [START_REF] Liu | Control Principles of Complex Networks[END_REF] advantage of this method is that it works with directed and undirected networks.

The PBH approach is a pretty useful tool for control in networks and can be applied to much larger networks than the Kalman's rank criterion. The complexity of this approach is roughly equivalent to the diagonalization problem for which efficient algorithms exist. However, diagonalizing matrices is still a time and resource consuming operation. For very large networks, this approach turns into memory and CPU related issues, such that other methods are needed. Furthermore, the approach developed in [START_REF] Yuan | Exact controllability of complex networks[END_REF] supposes that we have the exact anf full knowledge of the system parameters, which might not be always the case.

Lin structural controllability

A different approach to study controllability in complex network was introduced by Lin in 1974 [START_REF] Lin | Structural controllability[END_REF]. This approach is particularly interesting for large systems where the exact values for the parameters are not known. More precisely, we call (A, B) a structured system if the elements in A and B are either fixed zeros or independent free parameters. In this case, matrices A and B are called structured matrices. The system (A, B) is then structurally controllable if the nonzero elements in A and B can be selected such that the resulting system is controllable (rank(C) = N ). Since the nonzero elements of A and B are free, we can build a set of of all possible systems that share the same zero-nonzero connectivity structure as (A, B). It has been shown that almost all systems of this set are controllable except for some specific cases with Lebesgue measure zero. This means that if a system is structurally controllable, then it is controllable for almost all possible parameter realizations. Structural controllability requires thus the knowledge of the links between the elements, but not the exact weights of these links.

This framework enables to study the controllability of a system by looking only at its topology, avoiding matrices operations. It has been shown by Lin that the system (A, B) is not structurally controllable if and only if it has inaccessible nodes or dilations. Inaccessible nodes are simply nodes for which there is no path starting at an input vertex (see subplot a of figure 6.7). Obviously, these nodes cannot be influenced by the actions of the drivers. A dilation occurs when a small subset of nodes tries to control a Chapter 6. Power Grid Dynamics and Control larger subset of nodes. More precisely, we say that a digraph G(A, B) contains a dilation if there exists a subset of nodes such that its neighborhood set has fewer node (see subplot b of figure 6.7). The minimal structure that contains neither inaccessible nodes nor dilation is called a cactus. Cacti contain two kinds of structures : a stem, that is a path originating from an input vertex, and buds that are cycles with an extra-edge ending in one of the vertices of the cycle. An example of a cactus is shown on subplot c of figure 6.7. By definition, if we add a single edge to a cactus then the system is not controllable anymore unless we add one or more control signals. This leads to Lin's structural controllability theorem: Theorem 1. An LTI system (A,B) is structurally controllable if and only if G(A,B) is spanned by cacti.

Although an interesting theorem, this does not tell us how to find the minimum set of drivers that control a given system. Yet, an elegant and purely graph theoretical method has been developed from this theorem. This approach relies on the maximum matching problem, which is a widely studied problem in graph theory. For undirected graphs, a matching is a set of edges without common vertices, while for directed graphs, a matching is a set of directed edges that do not share common start or end vertices. A maximum matching is then a matching of the largest possible size. A matching splits the nodes in two categories : the matched nodes located at the end of a matching edge, and the unmatched nodes. Furthermore, we say that a maximum matching is perfect if all nodes are matched. This leads to the minimum input theorem of Lin : Theorem 2. To fully control a directed network, the minimum number of inputs, or equivalently the minimum number of driver nodes, is

N D = max {N -|M | , 1},
where |M | is the size of the maximum matching.

If we can find a maximum matching for a given graph, then, by applying a control input to every unmatched node we are able to control the system. This means that, in this context, finding the minimum set of driver for a given system is equivalent to finding the maximum matching of the corresponding digraph. The real value of this theorem comes from the fact that the maximum matching problem in a digraph in not NP-hard, but can be solved in polynomial time by using the Hopcroft-Karp algorithm, which runs in O( √ V E) time. Structural control is therefore an extremely powerful method since it allows to discuss (large) network control easily even if the exact weights of the edges are unknown. Note however that the independence of the parameters is a key assumption. If A is the adjacency matrix of an undirected network for instance, the independence of the nonzero parameters is not verified since A is symmetric.

Optimal control

In the previous section we gave some notions about control, and more specifically, control in networks. We reviewed different methods for determining if a given system is controllable or not, and how to select the minimum set of drivers to obtain full control. If we have the control of the system, we are able, by definition, to move it from any initial state x 0 to any final state x T by injecting a sequence of inputs u(t). In this case however, there might be more than one sequence of control inputs u(t) that could drive it from x 0 to x T (see figure 6.8). Although all these sequences have the same result on the state of the system, they may not incur the same cost to the controller or the environment. Depending on our definition of the cost, some sequences of inputs will be less expensive than others. Among all these possibilities, optimal control is devoted to find the sequence that minimizes some cost function J [START_REF] Kirk | Optimal Control Theory: An Introduction[END_REF]. In the general case, the cost can be written as a function of the states of the system x(t), the control inputs u(t), and the final state x T :

J = Φ [x 0 , t 0 , x T , t T ] + t T t 0 L [x(t), u(t), t] dt (6.27)
where Φ is the endpoint cost, and L is the Lagrangian. A special case of the general nonlinear optimal control problem is the linear quadratic (LQ) optimal control problem [START_REF] Kirk | Optimal Control Theory: An Introduction[END_REF]. The LQ problem consists in minimizing the quadratic continuous-time cost function :

J = 1 2 x T (t f )S f x(t f ) + 1 2 t f t 0 [ x T (t)Q(t)x(t) + u T (t)R(t)u(t) ] dt (6.28)
Subject to the linear first-order dynamic constraints :

ẋ(t) = A(t)x(t) + B(t)u(t) (6.29)
and the initial condition :

x(t 0 ) = x 0 (6.30)

Control of LQ systems, and a fortiori control of systems, is out of the scope of this thesis and numerous articles and books are available on the subject [START_REF] Kirk | Optimal Control Theory: An Introduction[END_REF] [START_REF] Fleming | Deterministic and Stochastic Optimal Control[END_REF]. In this thesis, we will focus on a very specific case of cost function. Indeed, we will see in chapter 7 that we will use control theory for modeling the actions of storage devices on the system. For these devices, we are concerned with the amount of energy that they inject or withdraw from the grid. This energy E can be written in terms of the control inputs u(t) during the control phase [START_REF] Tyler | On Submodularity and Controllability in Complex Dynamical Networks[END_REF] :

E = T 0 u(t) 2 dt (6.31)
This control energy can be seen as a specific case of the cost function 6.28 where S f = 0, Q(t) = 0, ∀t, and R(t) = I, ∀t. It can be shown [START_REF] Liu | Control Principles of Complex Networks[END_REF] that the control inputs that minimize E can be written as :

u (t) = B T e A T (T -t) W -1 (T )v f (6.32)
where ν f = X T -X 0 e AT is the difference between the desired final state X T and the final free state X 0 e AT , and

W (t) = t 0 e Aτ BB T e A T τ dτ (6.33)
is called the Gramian matrix of the system [START_REF] Liu | Control Principles of Complex Networks[END_REF]. It can also be shown that the system is controllable if and only if the Gramian is not singular, and that its rank indicates the dimension of the controllable subspace [START_REF] Tyler | On Submodularity and Controllability in Complex Dynamical Networks[END_REF]. Besides, the minimum control energy associated with the inputs u (t) can be written as [START_REF] Tyler | On Submodularity and Controllability in Complex Dynamical Networks[END_REF] :

E min = ν T f W -1 (T )ν f (6.34)
In cases where W is not invertible, the pseudo-inverse W † can be used to obtain similar information in the controllable subspace.

Discussion

In this chapter we first explained how the dynamics on networks could be studied. We reviewed different types of dynamics on networks, and studied in more depth the Kuramoto model for synchronization. This model was indeed shown to provide a good simplification of the power grid dynamics.

Starting from a network of generators and loads inter-connected with electrical lines, we explained how the non linear dynamics of such a system could be simplified to a Kuramoto-like model. The obtained system of equations 6.19 can be used to understand how the parameters and the topology influence the dynamics of the system. We saw that synchronization is indeed not the objective in all networks and that it occurs only if certain conditions are satisfied (see equation 6.10).

In the examples of section 6.1 we looked at the effects that a small power imbalance has on the frequency at which the system synchronizes. Roughly speaking, if the production is lower than the consumption, the frequency tends to decrease and vice versa if the production is higher than the consumption. The inertia of the electrical machines has a direct impact on the repercussion of a power imbalance on the frequency. Unfortunately, DERs are known to have smaller inertia than power plants, meaning that the frequency will be impacted faster in case of perturbations. In addition, we saw that DER cannot be scheduled and tend to be hardly predictable. In a power system with a large share of renewables, maintaining the frequency at a constant value seems thus even more complicated than it is today. Is is likely that different methods should be used in the future for frequency regulation as to cope with these kinds of problems.

In section 6.2 we presented control in networks. We considered some kind of dynamical process occurring on a given topology. This process changes the system state in a deterministic manner such that, if we know the initial state and the dynamic we can compute the successive states the system will be in. In the case where this evolution does not coincide with the desired one, we assumed that we were able to influence the dynamics at some specific nodes, by injecting signals. These nodes, called the drivers, and these signals, called the control inputs, are related in complex ways. That is, for a given topology and dynamic, the control signals depend on the chosen drivers. But this can be understood the other way around : the drivers that we choose might depend on the control signals that they require for controlling the system.

First of all, we saw that the ability to move the system in the state space without restriction was given by some driver sets but not necessarily by all of them, such that the question of finding the smallest one is paramount. Although a lot of contributions focus on this minimum driver set problem, we argued that controlling the dynamics was maybe not all we need. In some cases the signals that are injected do not incur a cost, such that the theoretical ability of control is sufficient. However, as we will see in chapter 7, we are particularly interested in these signals. More precisely, we would like to be able to control the system with a small amount of control energy (see 6.34) possibly at the expense of the addition of a few more drivers. Optimal control theory provides useful tools for this kind of problems. Actually, we consider here a specific case of optimal control sufficiently simple for the existence of an analytical expression for the optimum control inputs (see equation 6.32).

In the next chapter, we use the results developed here to study the storage placement in power systems composed of prosumers using renewables.

Chapter 7

Optimal storage placement for prosumer networks

This chapter tackles the problem of optimum storage placement in a network of prosumers. It uses the concepts introduced in chapter 6 on dynamics and control. We first explain the problem in more depth and explain what we mean by prosumer networks. We will see that control theory can be used in order to model the actions of the storage devices in the modified Kuramoto model developed in chapter 6. In section 7.2 we derive the multiple constraints that weight on the grid and storage devices. Our objective, as we will see, consists in finding the optimum subset of nodes for installing storage.

Due to the size of the systems considered, we argue that clever optimization methods are preferable to complete-enumeration ones. Relying on [START_REF] Tyler | On Submodularity and Controllability in Complex Dynamical Networks[END_REF], we use the submodularity of some control based functions in order to build an optimization algorithm. Submodular set functions are introduced in section 7.3.2 and the algorithm developed is presented in section 7.4. The last section of this chapter provides some results on the performance of the algorithm and how the number of storages evolves with the topology of the network.

Prosumer networks

In this chapter, we explore the use of storage in a network of prosumers. These agents, both producer and consumer of electricity, can behave as generators or loads depending on complex external conditions (see figure 7.1). As we saw in the previous chapters, weather conditions and the time of the day have strong impact on both the consumption and production of the prosumers. A consequence of the extensive use of DER is that perturbations are very likely, and may endanger the system stability.

In chapter 4, we studied a market oriented solution where aggregations of prosumers were forming coalitions tied to produce a pre-defined amount of power with penalties if they deviate. Nevertheless, since penalties will not prevent coalitions to fail if they must fail, it seems important for the grid operator to anticipate this kind of situations. Mismatches between production and consumption may indeed cause desynchronization of the system, which in turn, may damage the equipment and lead to blackouts.

There are multiple solutions for providing this kind of safety. Usually, frequency regulation is provided by some tier with a specific contract. The goal is to inject or withdraw large amount of power on a relatively short time in order to maintain the frequency of the system within acceptable bounds. During this period, actions should be undertaken by the operator so that the required backup generation is brought online. In addition to this kind of schema, storage devices scattered across the network are a possible safety reinforcement.

If rebalancing the production and the consumption is necessary, we should make sure that it is done without violation of the system's physical constraints. Electrical lines have indeed maximum capacities, and storage is also limited with bounded rates of charge/discharge. In other words, we must have the capability of controlling the grid's dynamic within a physically possible portion of the state space.

Storage placement has often been studied in the smart grid literature with an optimization framework. Authors consider a set of possible locations as well as a budget and they maximize some utility function. For example [START_REF] Gkatzikis | Collaborative placement and sharing of storage resources in the Smart Grid[END_REF] studies the placement of storage devices within microgrids in a collaborative scheme. The authors solve an interesting optimization problem mixing placement-dimensioning of storage with utilization. Moreover, [START_REF] Gkatzikis | Collaborative placement and sharing of storage resources in the Smart Grid[END_REF] uses a Nash bargaining framework to determine how prosumers should share the costs and benefits of the storages. However, [START_REF] Gkatzikis | Collaborative placement and sharing of storage resources in the Smart Grid[END_REF] does not take into account the grid dynamic as well as its controllability.

Control of smart grid systems has been recently studied in [START_REF] Farraj | On Using Distributed Energy Resources to Reshape the Dynamics of Power Systems During Transients[END_REF], where the authors use linear-quadratic optimal control theory in order to compute DER outputs. Control inputs rely on information collected by sensors and phasor measurement units and a communication network is used for sharing the information. The performance is then studied under practical limitations such as latency, sampling rate, or signal-to-noise ratio. The objective of [START_REF] Farraj | On Using Distributed Energy Resources to Reshape the Dynamics of Power Systems During Transients[END_REF] is the control of the system when perturbations occur. The control signals are used for adjusting the productions of the DER to some extent, but storage is not considered within this work. The present work differs from [START_REF] Gkatzikis | Collaborative placement and sharing of storage resources in the Smart Grid[END_REF] and [START_REF] Farraj | On Using Distributed Energy Resources to Reshape the Dynamics of Power Systems During Transients[END_REF] in that we study the placement of the storages from a controllability perspective in a stochastic context due to DER. Moreover, we aim at models and methods that could be scalable to some extent.

We assume that we are given a prosumer network and we have to find both the number and the locations of the storage devices that should be deployed. Once this choice is made, we have to stick with it whatever perturbations may occur. In addition, we suppose that the storage devices are controlled in a centralized way. Since installing these devices is expensive, we would like to minimize their number. In parallel, the amount of energy that flows out or from the devices is also a quantity of interest. If this energy is large, it means that we are charging and discharging a lot, which may result in reduced life time for example. The objective is then to find the smallest set of storages, as well as their locations, that will require small control energy (see chapter 7).

We saw in chapter 7 that the control energy depends on the initial and final states of the system. Since we do not have any prior on the future perturbations that may occur, we chose to minimize the average control energy required to move the system around the state space.

Dynamic and constraints

Recall from chapter 6 that an approximation of the grid's dynamic can be written in the following way :

θi ∼ ψ i -α θi - j =i K ij sin [θ j -θ i ] , (7.1)
where

α = 2K D I is the dissipation term, K ij = P M AX ij IΩ
are the coupling strengths, and

ψ i = P S,i IΩ -K D Ω I
encodes the power distribution of the prosumers. In order not to overload the equations, we simplify the constant term K D Ω I by working in a rotating frame such that ψ i = P S,i IΩ . The dynamic is still non linear because of the sine coupling. Therefore, we also assume that the phase angle differences are small such that sin [θ jθ i ] ∼ θ jθ i . By using vector notations, the dynamic can be written in the following form :

θ = Ψ -α θ -(K • L)θ (7.2)
Where A • B represents the Hadamard product between matrices A and B, and L is the Laplacian matrix of the underlying topology (L ij = k i if i = j and L ij = -m ij otherwise, see chapter 2). Equation 7.2 is a continuous time second order linear system of N equations.

By introducing

X =    θ θ 1   ,
we transform this into a first order linear system of 2N + 1 equations, which is discretized with time step ∆t, leading to :

Chapter 7. Optimal storage placement for prosumer networks

X(t + ∆t) = AX(t) (7.3)
With transition matrix A :

A =    I I∆t 0 -(K • L)∆t (1 -α∆t)I Ψ∆t 0 0 1    (7.4)
Note that the transition matrix A encodes all the system parameters, topology, and power distribution. So far we have expressed the grid dynamic as a coupled oscillators network, but we did not incorporate the different physical constraints on the network.

Flow Constraints

Recall from chapter 6 that a condition for synchronization in a coupled oscillators network is L † ω ∞,E ≤ sin(γ) [START_REF] Dörfler | Synchronization in complex oscillator networks and smart grids[END_REF], where L † is the Moore-Penrose pseudo inverse of the Laplacian matrix of the network, ω is the vector of the natural frequencies of the oscillators, and x ∞,E = max (i,j)∈E |x ix j |. If this condition is satisfied, the oscillators synchronize at the common frequency ω SY N C with the phase lock

|θ i -θ j | ≤ γ ∈ [0, π 2
], ∀(i, j) ∈ E. On the other hand, the power that flows on line (i, j) ∈ E can be written as

P i-→j = -P M AX ij sin (θ j (t) -θ i (t)). If θ j (t) -θ i (t)
is small, the flow constraints at time t are straightforward :

∀(i, j) ∈ E, | θ j (t) -θ i (t) | ≤ 1 (7.5)
If these constraints are verified for all instants t during the control phase then no line gets overloaded by the action of the control inputs. Writing the synchronization condition in our settings thus gives :

(L • K) † Ψ ∞ ≤ sin(1) (7.6)
If constraint 7.6 is satisfied, the oscillators synchronize to a common

frequency ω SY N C = N k=1 Ψ k N k=1 α k = N k=1 P S,k
IΩN α . Since the dynamics is expressed in term of deviations from Ω, synchronization at Ω is achieved if ω SY N C = 0. Which gives the production consumption balance constraint :

N k=1 P S,k = 0 (7.7)
Constraints 7.5 7.6 and 7.7 ensure that the system is able to synchronize at Ω without overloading lines.

Battery Constraints

A storage i has a maximum charge/discharge rate r i , some amount of energy stored Λ i (t) at time t, and a maximum capacity Λ i,M AX (see figure 7.2). We assume that all maximum rates (r) and all maximum capacities Λ M ax are the same across the storage equipments. We also denote by Λ(t) the vector of energy level at time t. Since u (t) specifies the control inputs, the energy level dynamic of the batteries is Λ(t + ∆t) = Λ(t)u (t)IΩ. Which can also be written as :

Λ(t) = Λ(0) -IΩ t k=0 u (k) (7.8)
where Λ(0) is the vector of initial levels in the batteries. Obviously, Λ(t) has to stay within possible bounds : ∀t, 0 ≤ Λ(t) ≤ Λ M AX . Which can be written in terms of the control inputs :

∀t, - Λ(0) IΩ ≤ - t k=0 u (k) ≤ Λ M AX -Λ(0) IΩ (7.9)
During each time slot, the battery cannot charge or discharge at a rate higher than r (see figure 7.2) :

∀t, | u (t)IΩ | ≤ r (7.10)
Given the dynamic of equation 7.3 and the constraints of equations 7.5, 7.6, 7.7, 7.9, and 7.10, how can we select the driver nodes such that we use low control energy on average ?

Submodular set functions

In this section, we explain the method that we used in order to find the driver nodes for the grid's dynamics (eq. 7.3).

Gramian based optimization

Recall that E min (see eq. 6.34) depends on the initial and final states as well as on the inverse of the gramian matrix W, which only depends on A and B. W can thus be used to obtain information about the average control energy required to move the system in the state space. In the prosumer network that we consider, generators and loads (Ψ) are susceptible to change, meaning that initial (X 0 ) and final (X f ) states might also vary. In such a scenario, we prefer to aim at good performance on average, rather than very good performance in few specific cases and bad performance in all other situations.

Since the control energy is related to W -1 , systems with "large" W will tend to be controlled with low energy. Still, this notion of "large" W is not very accurate and we need to quantify it by defining some metric based on W. We already mentioned the rank of W as being the dimension of the controllable subspace, but it is also known that the trace of W and W -1 give information about average controllability and average control energy [START_REF] Tyler | On Submodularity and Controllability in Complex Dynamical Networks[END_REF]. In such a situation, we can build a set function that, given a set of driver nodes S, returns the value of one of these metrics. Indeed, given A and S, we can obtain the system dynamics (A, B S ) and compute the gramian W S . In other word, such a function would quantify the ability of a given set of nodes to control the system on average. The objective would then be to find the set S k of size k that maximizes this function.

A key point, demonstrated in [START_REF] Tyler | On Submodularity and Controllability in Complex Dynamical Networks[END_REF], is that the set function

F : S -→ T r[W S ] (7.11)
is modular and the two functions

F : S -→ T r[W -1 S ] F : S -→ rank[W S ] (7.12)
are submodular. As we will see in the next section, this nice result enables us to look for the driver node set that optimizes the average control energy with a simple greedy heuristic that also provides a worst case guarantee.

Submodularity

We introduce here submodular set functions and explain how their maximization can be achieved in reasonable time. More information about submodularity can be found in [START_REF] Krause | Submodular function maximization[END_REF].

A set function F : 2 V -→ defined over a finite set V is said to be submodular if for all sets X, Y ∈ V , such that X ⊆ Y and for all element x ∈ V \ Y , we have :

F (X ∪ {x}) -F (X) ≥ F (Y ∪ {x}) -F (Y ) (7.13)
A very intuitive example is the optimum placement of sensors in an area (see figure 7.3). Sensors can be placed on a grid of locations and function F computes the surface of the space that is being sensed. Note first that adding a new sensor i to the current set S cannot decrease the value of F : F (S + {i}) >= F (S). Furthermore, if we add sensor i to a small set S 1 we tend to get larger improvements than if we add i to a larger set S 2 ⊃ S 1 .

This basically means that submodular functions exhibit a diminishing return property which makes them particularly interesting for optimization. Generally speaking, finding the set S k of size k that maximizes a set function F is a difficult problem because the number of sets grows exponentially with the number of nodes. Therefore complete enumeration and evaluation is only feasible on very small examples. Nevertheless, if the set function is submodular, a simple greedy heuristic returns a solution is the optimum set of size k) [START_REF] Krause | Submodular function maximization[END_REF]. This heuristic starts with a set S (possibly empty) and iteratively adds the element i that exhibits the highest marginal gain :

F (S ∪ {i}) ≥ F (S ∪ {j}) ∀j.
For a ground set of N elements, this heuristic computes F k(2N -k+1) 2 times. Since the evaluation of F can be costly, a well-known lazy-greedy variation has been proposed by [START_REF] Minoux | Accelerated greedy algorithms for maximizing submodular set functions[END_REF]. This smart implementation uses the submodular structure of the marginal gains in order to reduce the number of calls to F. This requires to maintain a sorted table of marginal gains for all elements. When looking for new element i to add to set S, the top one is selected and the new marginal gain F (S ∪ {i}) -F (S) is computed. If this gain is larger than the gain of the second element in the table, then i is added to S. Otherwise i is inserted back in the table with its updated gain and the same treatment is applied to the element that is now on the top of the table. Because of the submodularity of F, this method performs as well as the original one, but can result in speedups of several orders of magnitude.

Theoretically, we are now able, for a given prosumer network, to compute A, B, and W. For some trajectory in the state space, we can use equation 6.32 to find the optimum control inputs. However, these inputs do not take into account the physical constraints on the possible trajectories due to lines and batteries finite capacities.

Finding the optimal storage placement in prosumer networks

Performance evaluation

Finding the driver set S k of size k using the gramian W S k of the system (A, B S k ) does not require initial and final states. Besides, W S k does not depend on the modified power distribution Ψ of the nodes. We are indeed looking for k controllers that perform well on average over all possible situations. On the contrary, the constraints derived above (eq. 7.5, 7.6, 7.9 and 7.10) are bounded to a particular trajectory in the state space. We indeed check whether the power grid can sustain the controlled dynamics when transitioning from a given initial state to a target final state. As we do not know what these states could be, we could use multiple scenarios and test whether S k can control the system without violation of constraints. In this paper, we use a slightly different approach. We consider that the system is initially at equilibrium (all elements are synchronized at Ω) and that control will be necessary if a perturbation (power imbalance) occurs and takes the system out of equilibrium (see figure 7.4). Depending on how much time we need to start the control phase, the state of the system (the initial state for control) might be "somewhere around" the synchronized state. In order to test whether a set S k can control the system without violation of constraints, we sample initial states within some hypersphere centered on the synchronized state and check all the constraints. If for all trajectories, the constraints are respected, then we consider that S k enables the control of the system. Frequencies FIGURE 7.4: At t = 800, P 5 goes from -1 to -2 (power inbalance). Consequently, the frequencies θi deviate from the synchronized state. At t = 1000, optimal control inputs (see equation 6.32) are injected at nodes 0, 2, and 4 (nodes with ellipses) such that the system is brought to the synchronized state at time t = 1500 (control time T = 500).

Increasing k means that we deploy more storage which increases the costs but tends to lower the energy required as we will see in the next section. Using the submodularity of the set functions introduced above, we can build a sequence of growing sets S 1 ⊂ S 2 ⊂ ... ⊂ S k and stop as soon as S k enables the control of the system for some k.

Algorithm 1 Optimization with grid constraints

k = 0 S k = ∅ while Not Constrained control do k ← k + 1 S k = S k-1 ∪ argmax i∈N \S k-1 F (S k-1 ∪ {i}) end while
The purpose of selecting the drivers according to a Gramian related metric is to minimize, on average, the amount of control energy needed. Conversely, if we select the drivers randomly, we expect to need, on average, more energy to control the system. In figure 7.5, we compare the average control energy E in function of the proportion of drivers among the total number of nodes n D = N D /N nodes , for a set of drivers selected thanks to our algorithm with randomly selected drivers (in both cases overloading and battery limits constraints are satisfied). We draw 10 4 scale-free topologies with 50 nodes, and random power distributions and line capacities.

For each system we select a random number of drivers N D ∼ U(1, N nodes ) and we find two driver sets of size N D . One is chosen randomly and the other is found with algorithm 1. For both sets, if the control is possible, we draw a random initial state Y i and a random final state Y f , and we compute the control energy required for driving the system from Y i to Y f . Since the algorithm is based on T r[W -1 ], we could plot T r[W -1 ] in function of n D but we prefer to validate our method by computing the actual average energy. As expected, both curves decrease as the number of drivers increases, meaning that, as the number of drivers grows, the average control energy tends to decrease, but we tend to use less energy when the drivers are selected with our algorithm. Note that this difference tends to zero when n D tends to one, because almost all nodes are then selected, yielding little flexibility for optimization.

Topological effect on n D

We investigate next how the topology of the grid and the physical constraints affect the minimum size of the driver set. n D is no longer selected randomly, but minimized. We consider the simple case of an Erdös-Rényi topology with probability of connection p. We show on Figure 7.6 how the minimum size of the driver set evolves with p for different Gramian based metrics and for two levels of constraints :

• Level 1 : full control and grid constraints. The system is controllable (i.e it can be moved from any point to any other point) and under the constraints (i.e it can be moved without overloading any line or breaking any battery limits).

• Level 2 : full control only : the system can be moved from any point to any other point of the state space, without considering any overloading or battery limit constraints.

When p ∼ 0, nodes tend to be very poorly connected such that we need to control almost all nodes in the grid. As p increases, the connectivity of the graph rises and the number of drivers decreases. At some point, the connectivity of the graph starts to harm its controllability, and more drivers are needed (this effect is in accordance with the literature). As expected, the driver sets for the level 1 of constraints are larger than for level 2 (for all metrics) because we impose far more constraints on the control inputs. Erdos-Renyi or scale-free networks are known to provide poor approximations for real world power grids, which tend to have homogeneous degrees as well as spatial properties (see chapter 2). Indeed, power grids aim at routing power from generation sites to the consumers, which are both far from uniformly distributed over the different countries. In addition, power grids were built by governments or companies within each country without a global cross border thinking, which often results in well connected subgraphs within countries, and few connections across borders. These constraints lead to topologies exhibiting community structures. Therefore, we study the control of the prosumers in graphs with communities. More precisely, we use a block model (N, N clusters , p in , p out ) to generate random topologies where N is the number of nodes, N clusters is the number of clusters (or communities), p in is the probability that two nodes within the same cluster are linked, and p out is the probability that two nodes in two distinct clusters are connected (see top panel of figure 7.7).

The bottom left panel of figure 7.7 displays how the number of drivers evolves with the number of clusters for different values of p in when p out is fixed (p out = 0.1). For small values of p in ∼ p out clusters are poorly marked, and the connectivity is low. The number of drivers in these conditions is large and increases slowly when the number of clusters augments. As p in increases, the clusters becomes more densely connected such that within a cluster less drivers are required in order to control it. As the number of clusters grows, more drivers are required. For large values of p in , the behaviour is more complex. We see indeed that for p in = 0.9 and N clusters = 2, almost The curves are averaged over 100 realizations.

94% of the nodes are needed for control, but this quantity first decreases with the addition of a few more clusters (71% for N clusters = 5), before increasing. This behavior can be explained by the fact that controlling a very dense network requires, in our settings, a very large portion of nodes to be drivers. Controlling one cluster alone thus requires to control almost all nodes within this cluster. Nevertheless, when a relatively small (compared to the number of nodes in the graph) number of clusters are interconnected with a few links, nodes in one cluster are able to control nodes in other clusters to which they are connected. As the number of clusters grows, the global connectivity increases rapidly, such that the number of drivers also rises. We show this behavior in more details on the bottom right panel of figure 7

Effect of storage capacities

Until now, we have considered all batteries to be equal, i.e they have the same capacities and charge/discharge rates. Although simple, this assumption might not be true in practice where different types of batteries exist.

Optimizing both the locations and cost over reliability tradeoff of different types of storage is out of the scope of this work. Nevertheless, we studied how the number of drivers behaves when the batteries have different capacities. More precisely, we draw the capacities of the batteries from a normal distribution N (µ λ , σ λ ) and keep a simple erdos-renyi topology for the power grid. Note that each node is assigned a capacity regardless of its characteristics (degree, betweeness, and so on...). In figure 7.8, we plot n D as a function of the relative standard deviation of the battery capacity distribution σ λ /µ λ . We see that n D increases with the variance of the capacity distribution for all three gramian based metrics considered. Moreover, this rise is abrupt since n D goes from 60% for σ λ µ λ ∼ 0.15 to 100% for σ λ µ λ ∼ 0.27.

Real topologies

Since real power grids topologies are known to be far from random, we consider here, as a real case, the European transmission power grid which topology was obtained from [START_REF] Tue | The RE-Europe data set[END_REF]. The network contains 1494 nodes and 2156 edges and spans 25 European countries. A representation of this graph can be found in figure 7.9 where the nodes are colored according to their country. We select the power distribution and the line capacities randomly, and use the method described above. We use the trace of the Gramian matrix for the optimization. The top panel of figure 7.10 shows that the rank of the Gramian increases with the size of the controllers until reaching full rank (rank[W S ] = 2N nodes ) for N D = 1244. Above this point, we compute the average control energy needed to drive the system from an initial random state to a random final state. The curves on the bottom panel of figure 7.10 show the results for the optimized driver sets and for random driver sets. As can be seen on figure 7.10, as the size of the driver set increases, the control energy tend to decrease. But, we need less energy with the optimized driver set than with randomly sampled sets. with optimization random random FIGURE 7.10: Gramian rank and control energy evolution for European transmission power grid (see figure 7.9).

Discussion

In this chapter, we considered networks of prosumers which can behave as generators or loads depending on weather conditions. In this stochastic context, we proposed an optimization method of the storage placement for frequency regulation through optimal control theory (see chapter 7). The modeling approach developed in chapter 6 enabled us to simplify the grid's dynamic such that the framework of optimal control could be used. Besides, the physical constraints on the network and storages were taken into account in the process. Because we do not consider any prior on the perturbations that may occur, we choose an approach that aims at minimizing the control energy in any direction of the state space. The optimization method relies on submodular set functions (see section 7.3) and the gramian matrix (see chapter 7). We show in this chapter that, by using our algorithm, we are able to find a storage placement that, on average, minimizes the energy that should be injected or absorbed by the storage devices while complying with the physical constraints of the grid and storages.

We believe that interesting work could be done by combining this model with real production and consumption data. There are indeed complex spatial and temporal correlations that impact these distributions [START_REF] Gensollen | Coalition formation algorithm of prosumers in a smart grid environment[END_REF]. In contrast, we considered that the control has to be in any direction of the state space but confronting this assumption with real traces could lead to interesting further research.

Chapter 8 Conclusion

This thesis was devoted to study smart grids with a complex system approach. Power grid systems already have a significant array of control tools to operate in a stable and reliable way. In the current unidirectional and static systems, these tools are able to maintain stability. But in more complex, interconnected, and distributed environments, there is need for smart and automated actions. Real time data could be obtained by sensors scattered across the network. Distributed system architectures for storing and processing these large amount of data could be combined with machine learning algorithms that would predict events and reinforce the control of the system.

In such multi-scale and interdependent environments it might be difficult to understand how the whole system behaves. Complex system theory addresses these kinds of problems, where some collective phenomena appear from individual behaviors. While a large amount of work focuses on very specific components of the smart grids that could be tested in isolation, this work used relatively simple models and assumptions for the individuals and studied their repercussions at a larger scale.

This thesis was divided in two main sections. The first one focuses on modeling energy markets with aggregation of prosumers as participants, while the second part addresses the optimization of storage placement in order to achieve frequency regulation in a network of prosumers.

The main contributions for the first part were the development of a prosumer model based on real weather data that enabled us to capture the spatio-temporal correlations between these agents. A model for the energy market was also proposed and used for studying how market aggregators could group prosumers in such a way that they maximize their expected gains at low risk. We argued that diversification was a key concept in this process, such that we studied a de-correlation based clustering. We proposed a greedy optimization that starts with uncorrelated cliques of agents, and increases their sizes as long as their utilities are improved. We then compared the results against other methods and showed that the proposed algorithm was performing better than the others. We believe that methods based on this work could be used by aggregators on energy markets as to maximize their expected gains for a given risk acceptance. Using real prosumers data when they will become available could help improve the proposed method. Furthermore, we suggest in chapter 5 a possible direction to gain insight on the market and improve the method. We indeed proposed to use tensor decomposition to study dynamic correlation graphs as opposed to static versions of these graphs. Being able to understand the patterns in the dynamics of such graphs would surely provide precious information to the market aggregators.

Concerning the second part, we believe that the novel contribution was first to combine the power grid dynamic with optimal control as to answer the question of storage placement in a stochastic context. In addition, we incorporate the physical constraints of the power grid and energy storage devices in the process. We also explored an optimization method based on submodular set functions that is easy to implement and has a worst case guarantee. The proposed algorithm is thus able to produce an efficient placement strategy given a topology for the power grid. It seems unavoidable that large amounts of storage devices would have to be installed in future smart grid systems. Optimizing their locations beforehand could therefore lead to important savings. This question has been tackled in the literature before, but never, to the best of our knowledge, by this optimal control and submodularity approach. We believe that this work brings a different perspective on this question, and we hope that more work would be undertaken in this direction.

In terms of publications, the research performed for the first part resulted in a conference paper published at the IEEE ICC 2015 as well as a journal paper published in IEEE Transactions on Smart Grid 2016, both as first author (see appendix A for a complete list of publications). For the second part, a conference paper has been published at IEEE SmartGridComm 2016. The work presented in chapter 6 on dynamic correlation graphs is still incomplete because it was undertaken short before the redaction of the present thesis. This work is currently being completed and will hopefully be submitted around September 2016.

My current work also includes the mentoring of M. Lester Padilla, a master level intern, who works on extracting power grid topologies from OpenStreetMap (OSM) data. This internship was created after an exciting seminar organized in our offices in March 2016 and ended in September 2016. The idea is based on the SciGRID project developed at NEXT EN-ERGY, EWE-Forschungszentrum für Energietechnologie in Germany. The internship aims at extracting, from the OSM data, a power grid topology with generators and loads. With additional information like the type of the generators, their capacities, the capacities of the electrical lines, and so on, we believe that this work will help researchers to obtain realistic data to test their research on.

On a more distant perspective, because of my ongoing work on temporal graphs, I developed interest for studying the detectability of evolving communities in temporal graphs. This interest is still at a very early stage and I hope to have time in a near future to focus on it. Another future work might also be related to the Grid4Earth project on microgrids.

Besides the work done as part of my thesis, I also gave courses (monitorat) at the Pierre et Marie Curie University (UPMC) during these three years. In the beginning, this was the opportunity for me to experience teaching because I was not sure, right from the start, that it would suit me. In the end, it confirmed to me that this is something that I particularly enjoy. Looking back on these last years, I feel very fortunate to have had the opportunity to learn and experience a lot of fascinating things. It is also frustrating to have so many things on the "to-do" or "to-look-at" lists and so little time to explore them in depth. Although it was in the back of my head since the beginning of my PhD, now, I know for sure that I wish to work in academia as a professor in the future. Appendix C. Modéliser et optimiser un réseau électrique distribué, une approche systèmes complexes des prosumers dans le smart grid fossiles ne sont pas inépuisables et qu'elles ont été fortement surexploitées ces dernières décennies. Par ailleurs, il a été démontré que leur exploitation engendrait un certain nombre de problèmes environnementaux. Nous sommes donc arrivés à un moment clé de l'histoire des systèmes énergétiques puisqu'il apparait essentiel d'investir pour leur modernisation. Le point crucial étant de savoir si ce budget doit supporter la réinstallation de dispositifs dont les sources s'amenuisent et tendent à aggraver la situation climatique, ou s'il doit soutenir des projets alternatifs innovants. La question est donc de déterminer s'il existe des alternatives crédibles à nos systèmes actuels. On souhaiterait idéalement pouvoir jouir des mêmes services sans en avoir les conséquences problématiques. Comme la source du problème semble provenir de la génération, on pourrait imaginer le résoudre en remplaçant les sources d'énergies utilisées. Il est en effet connu depuis longtemps que certaines énergies peuvent être considérées, à notre échelle temporelle, comme inépuisable. L'énergie solaire, le vent, le courant des fleuves, les vagues et marrées, ou la géothermie ne sont que les exemples les plus évidents. Ces énergies, dites renouvelables, ont l'avantage d'être non polluantes, gratuites, et inépuisables de telle sorte qu'on pourrait même s'étonner de ne pas avoir construit dès le début nos systèmes énergétiques autour de celles-ci.

En réalité, bâtir un système énergétique de grande taille en utilisant uniquement des sources renouvelables est un problème qui attend encore, au jour d'aujourd'hui, une solution. En effet, un important défaut de ces énergies renouvelables est qu'elles sont généralement intermittentes et stochastiques. Contrairement aux générateurs fossiles que l'on peut programmer à l'avance, les générateurs renouvelables ne produisent que lorsqu'ils sont soumis à la ressource en question. Hors il est bien connu que l'intensité de la plupart de ces ressources est tout sauf constantes. Le rayonnement du soleil par exemple est nul durant la nuit, et fortement variable durant la journée car il dépend à la fois de l'heure, de l'orientation, de la nébulosité, etc. Il en va de même avec le vent qui apparait comme une ressource extrêmement volatile.

Les consommateurs, qui sont la raison d'être des systèmes énergétiques, n'ont généralement que peu conscience de ces problématiques. Dès lors que ceux-ci payent leur abonnement, ils considèrent la disponibilité de l'énergie comme acquise, et ce quelle que soit l'heure, le jour, ou la saison. Il semble donc extrêmement compliqué de fournir ces utilisateurs avec des moyens de production aussi peu fiables étant donné l'architecture de nos systèmes actuels. C'est l'une des problématiques clé de la transition énergétique, et c'est précisément là que les technologies de l'information ont beaucoup à apporter pour provoquer une mutation en profondeur des réseaux énergétiques.

C.1.2 L'utilité de l'information dans le smart grid

L'architecture des réseaux électriques actuels est hiérarchisée et relativement rigide. Les générateurs ont été construits à proximité des ressources qu'ils exploitent, c'est-à-dire souvent loin des utilisateurs finaux, si bien qu'il est nécessaire d'acheminer l'électricité depuis ces sites distants jusqu'aux clients. Afin de transporter l'électricité sur de longues distances, il est judicieux d'élever sa tension par l'intermédiaire de transformateurs, car cela Pourtant, au niveau des utilisateurs, la consommation n'est pas constante et dépend de nombreux paramètres comme le jour, la saison, la température, les habitudes des clients, etc... Il existe néanmoins des tendances générales bien connues. Les pics de consommation du matin et du soir sont notamment des phénomènes émanant de la corrélation des comportements. Si ces pics sont prévisibles, ils n'en restent pas moins problématiques puisqu'ils obligent les opérateurs à dimensionner le réseau pour y répondre alors même que leurs durées sont assez brèves. Lisser ces pics est un objectif déjà ancien au sein du monde de l'électricité, mais cela apparait encore plus important pour un système basé sur des sources renouvelables. L'exemple de la production photovoltaïque est extrêmement parlant puisque le pic de production, situé entre midi et deux heures de l'après-midi, est justement placé au milieu des deux pics de consommation. Autrement dit, si rien n'est fait, le système est constamment en déficit ou en excédent de production, ce qui ne peut être acceptable pour des raisons évidentes de stabilité.

Contrairement aux générateurs fossiles, il n'est généralement pas possible d'agir directement sur la production renouvelable pour la décaler dans le temps, si bien que d'autres solutions moins directes doivent être envisagées. L'une des plus évidentes consisterait à constamment stocker et déstocker les surplus de production pour s'ajuster à la demande. Même si le stockage de l'électricité est un des axes clé des réseaux électriques futurs, il est probablement inconcevable de se baser uniquement sur cela. En effet, l'électricité est une grandeur qui se stocke mal et dont les équipements ont généralement des durées de vie assez faibles (batteries). Le coût d'investissement et d'entretien d'un tel parc de dispositifs de stockage apparait donc comme prohibitif. Néanmoins, il est assez clair désormais que le stockage de l'électricité, dans des proportions beaucoup plus importantes qu'aujourd'hui, sera nécessaire dans le futur.

Une des idées fondamentale du smart grid est donc d'associer l'utilisateur final à l'équilibre du réseau, en ne le considérant, non plus comme une « charge morte », mais comme un acteur à part entière. Cela suppose un échange constant d'information entre les divers acteurs du système que seul un réseau de communication peut fournir (certaines études proposent aussi d'utiliser le réseau électrique grâce au CPL). L'idée repose sur le déploiement massif de compteurs intelligents qui font l'interface entre le réseau et l'utilisateur. Ces dispositifs ont pour rôle, entre autres, de mesurer régulièrement la consommation et de la transmettre en amont sur le réseau. Cela permet à l'opérateur, par agrégation, de connaitre en quasi temps réel la distribution de la consommation dans le système. Appendix C. Modéliser et optimiser un réseau électrique distribué, une approche systèmes complexes des prosumers dans le smart grid Par ailleurs, l'opérateur peut également envoyer des informations aux compteurs afin de les avertir des conditions sur le réseau. L'un des proxys envisagés pour répercuter ces conditions sur l'utilisateur est un prix de l'électricité dynamique. En fonction de l'état du système et de ses prévisions à court termes, l'opérateur fixe les prix pour les périodes futures et les diffuse sur le réseau. Grâce à ces informations, les compteurs intelligents sont en mesure de planifier les divers appareils afin d'optimiser une fonction d'utilité propre à chaque utilisateur. En effet, il apparait que certains appareils électroménagers comme les machines à laver, lave-vaisselles, ou climatisations peuvent être reporté dans une certaine mesure. A contrario, d'autres appareils comme la télévision, ou l'éclairage doivent être opérationnels à la demande pour des raisons évidentes de confort. Il est ainsi envisageable de déclencher certaines consommations uniquement lors de périodes où les prix sont faibles si le gain monétaire réalisé dépasse la perte utilitaire engendrée. C'est globalement l'idée du « Demand Side Management (DSM) », implémenté sur le compteur, qui tire profit de la dynamicité des prix de l'électricité.

Demand Side Management, prix dynamiques, et stockage distribué de l'électricité sont des concepts de bases des réseaux électriques du futur. Cependant, une grande partie de la littérature consacrée au smart grid va encore plus loin dans le rapprochement entre la production et la consommation.

C.1.3 Une production décentralisée et un réseau plus résilient

Comme évoqué plus haut, la production et la consommation sont aujourd'hui clairement séparées, tant au niveau géographique que topologique. Par ailleurs, cette production est assez centralisée, notamment en France où la majeure partie provient des centrales nucléaires. Sous ses apparences de stabilité, cette organisation est en réalité extrêmement fragile et vulnérable puisque le fonctionnement du système entier repose sur quelques points et liens très haute tension.

L'étude de la topologie des réseaux électriques a connu un regain d'intérêt ces dernières années grâce au développement des systèmes complexes. Le réseau électrique peut en effet être facilement abstrait en un graphe où les arêtes représentent les lignes électriques, et les noeuds les divers équipements (générateurs, sous-stations, transformateurs. . . ). Analyser ensuite les propriétés structurelles de ces graphes permet de mieux comprendre comment ceux-ci tendent à se comporter. Prenons le « World Wide Web » comme exemple, où les pages internet représentent les noeuds, et les liens hypertexte forment les arrêtes. Intuitivement, on imagine qu'il doit exister une sorte de diversité du nombre de liens par pages. Sous la forme de graphe, cela revient à étudier la distribution des degrés des noeuds du graphe. Un résultat connu est que le Web possède une distribution des degrés en loi de puissance, ce qui signifie qu'une grande majorité des noeuds ont des degrés assez petits mais qu'il existe des noeuds, appelés « hubs », avec des degrés beaucoup plus grands. Pour des graphes purement aléatoires (Erdös-Rényi) la probabilité de trouver ce genre de noeuds est quasiment nulle, de telle sorte que la présence des ces hubs n'est en aucun cas le fruit du hasard, mais le résultat d'un processus sous-jacent. Une des conséquences de cette distribution en loi de puissance est que le Web est très résistant aux pannes aléatoires, mais extrêmement vulnérable aux attaques ciblées sur ces fameux hubs. Pour s'en convaincre peut-être faut-il s'imaginer surfer sur une toile dépourvue de Google, Yahoo, ou Facebook. . . L'architecture un peu particulière des réseaux électriques rend leur classification moins évidente que pour d'autres réseaux réels. Par ailleurs, cette approche purement topologique ne prend pas en compte la dynamique de l'électricité sur le réseau, si bien que d'autres approches ont du être mises au point spécialement pour étudier la résilience des réseaux électriques. Ces travaux se focalisent généralement sur les phénomènes de cascades qui représentent les répercutions d'une perturbation initiale. Il a ainsi été montré que la chute de seulement quelques lignes pouvait totalement fragmenter le réseau jusqu'à le rendre non fonctionnel. Ces « black-out », aux conséquences parfois catastrophiques, ne nous sont pas étrangers et se produisent de temps à autre. La tendance étant par ailleurs à l'aggravation avec la complexification et le vieillissement des systèmes électriques. Une question cruciale est ainsi d'estimer la résilience d'un réseau électrique intelligent dont la production est en grande majorité renouvelable. Toutefois, afin de pouvoir parler de sa résilience encore faut-il avoir une idée de sa topologie, des emplacements de ses générateurs, etc. . . Si de larges centrales renouvelables raccordées au réseau très haute tension seront surement construites (c'est d'ailleurs déjà le cas actuellement) afin de tirer profit des économies d'échelles ou de ressources éloignées (éolien offshore par exemple), de nombreux articles prônent le développement parallèle d'une production locale. En incluant des moyens de production au plus proche des consommateurs on diminue fortement le besoin de transport, et donc les pertes que celui-ci engendre. Par ailleurs, un réseau dont la production est décentralisée apparait comme beaucoup plus résilient car, même fragmenté, il peut éventuellement continuer à fonctionner. Bien entendu ce genre de réseaux est encore au stade de la recherche, mais des applications moins ambitieuses, comme les micro-grilles, sont d'ores et déjà en train de voir le jour. Ces micro réseaux électriques sont composés de générateurs, charges électriques, et moyens de stockage, et sont reliés au réseau principal par un point unique (« Point of Common Coupling », PCC). Ils ont ainsi la possibilité de se déconnecter du réseau pour opérer en autosuffisance pendant une période donnée. L'intérêt pour ce genre d'opérations peut être, par exemple, de soulager le réseau principal lorsqu'il opère proche de sa limite, permettant ainsi de se prémunir contre d'éventuels black-out.

C.1.4 Les prosumers

En poussant ce concept de production locale encore plus loin, on pourrait imaginer que l'utilisateur lui-même produise une partie de son électricité. C'est d'ailleurs déjà le cas actuellement avec l'augmentation des installations photovoltaïques sur les toits des lotissements. Ces utilisateurs, souvent appelés « prosumers », ont donc la possibilité de consommer « gratuitement » ce qu'ils produisent. Comme expliqué plus haut, il est néanmoins fort probable que leurs activités ne coïncident pas vraiment avec leur production, si bien qu'à moins de posséder également une batterie, cette production est perdue. Bien entendu, il existe un certain nombre de parades Appendix C. Modéliser et optimiser un réseau électrique distribué, une approche systèmes complexes des prosumers dans le smart grid comme retarder certains appareils (DSM), ou utiliser l'énergie pour chauffer l'eau par exemple. Toutefois, il est envisagé que ces prosumers puissent revendre leur production lorsque celle-ci est en excédent. Cela est loin d'être évident à mettre en place et doit faire l'objet d'importantes études tant sur le plan électrique que sur le plan économique. Contrairement aux flux électriques « top-down » décrits plus haut, on envisage ici des flux bidirectionnels lourds de conséquences sur l'architecture et la stabilité du système.

Cette thèse est centrée sur ces utilisateurs et leur intégration au sein du système électrique intelligent. Nous abordons ces prosumers suivant deux angles d'attaques qui donnent naissance aux deux parties principales de cette thèse. Nous commençons par étudier comment ces-derniers peuvent parvenir à revendre leurs surplus de production sur des marchés de l'électricité. Dans un second temps, nous nous focaliserons sur la stabilité du réseau électrique en présence de ces prosumers. Nous chercherons alors à installer des dispositifs de stockage à des points stratégiques du réseau afin de maintenir l'équilibre du système lors de fluctuations liées à la stochasticité des énergies renouvelables utilisées. Tout au long de la thèse des concepts liés à la théorie des graphes et des systèmes complexes seront utilisés. Ces concepts sont expliqués dans le chapitre 2 de la thèse, et de nombreuses références bibliographiques y sont fournies.

C.2 Formation de coalitions stables pour les marchés de l'électricité C.2.1 Modélisation des prosumers

Comme expliqué précédemment, un prosumer possède un ou plusieurs petits générateurs renouvelables, des appareils consommant de l'électricité, et éventuellement un moyen de stockage (qui est considéré dans certaines études comme la batterie d'un véhicule électrique). Intuitivement, on comprend qu'un certain nombre de paramètres, comme la météo, la saison, le jour de la semaine, l'heure de la journée, ou le comportement du prosumer influent sur le surplus de production de ce dernier. Comprendre comment ce surplus évolue dans le temps pour divers prosumers est au centre de notre problématique de revente sur les marchés. Toutefois, étant donné que les prosumers sont encore des projections théoriques de ce que pourrait être les futurs consommateurs, il n'existe que très peu de données les concernant. Même si cela tend à s'améliorer au fil des années, nous n'avions pas, au début de cette thèse, de données sur lesquelles nous baser. Une partie non négligeable de cette thèse fut ainsi consacrée à modéliser et simuler ces agents par l'intermédiaire d'un autre type de données plus facilement accessibles : les données météorologiques. Outre l'accessibilité de celles-ci, nous avons fait ce choix car la vitesse du vent et l'ensoleillement apparaissent comme des proxys raisonnables pour modéliser des productions éoliennes et photovoltaïques. Par ailleurs, les stations météorologiques forment généralement un maillage assez bon des territoires que nous avons considéré, ce qui nous permet d'avoir une discrétisation de l'espace acceptable. On effectue ainsi un découpage de Voronoï du territoire considéré autour des stations météorologiques pour lesquelles nous avons récolté C.2. Formation de coalitions stables pour les marchés de l'électricité 127 des données. On dispose ensuite de manière aléatoire un ensemble de N prosumers et on associe chaque agent au profil météorologique de la cellule sur laquelle il se trouve. Pour n'importe quel instant t de la simulation on peut donc avoir accès, pour un agent i, à la vitesse du vent (ν i (t)), l'ensoleillement (Ψ i (t)), ou la température (τ i (t)) auxquels il est soumis.

En notant P i (t) = P P i (t) -P D i (t) le surplus de production d'un agent i (sa production moins sa consommation à l'instant t), l'idée de base de notre approche est de décomposer P P i (t) et P D i (t) en fonction des équipements et préférences de i. Plus précisément, dans un cas où seuls des éoliennes et panneaux photovoltaïques sont disponibles, cela revient à écrire :

P P i (t) = k∈W T i F W T (ν i (t)) + k∈P V i F P V (Ψ i (t)) (C.1)
Où W T i (resp. P V i ) représente les éoliennes (resp. panneaux photovoltaïques) de i. De plus, il nous faut un moyen de convertir nos entrées (vitesse du vent, ensoleillement) en production pour les DER considérés. Cela est réalisé grâce aux deux fonctions F W T et F P V qui sont des modèles simplifiés de ces générateurs.

En ce qui concerne la consommation, notre objectif était de parvenir à reproduire les effets saisonniers comme quotidiens grâce à un modèle « bottom-up ». Nous avons ainsi divisé la consommation en deux contributions : l'une (F i heat) s'interprétant comme un terme de chauffage, et l'autre (F i elec) comme une consommation d'équipements :

P D i (t) = F i heat(τ (t), t) + F i elec(t) (C.2)
Nous ne rentrerons pas plus en détails ici sur les fonctions F i qui sont détaillées dans le chapitre 3 de la thèse. Les jeux de données principaux ont été obtenus à partir de [START_REF]Infoclimat[END_REF] et [START_REF]National Centers For Environmental Information[END_REF]

C.2.2 Les agrégateurs

Grâce à cette modélisation, nous sommes en mesure de paramétrer avec précision un large panel de prosumers, et de simuler l'évolution de leurs surplus de production. En étudiant ces quantités, nous avons remarqué une certaine diversité des motifs due à la multiplicité des profils sous-jacents. La question qui nous intéresse est donc de savoir si cette diversité peut servir à l'intégration des prosumers sur les marchés de l'électricité. En effet, de par leur faible production et l'instabilité de celle-ci, il semble assez improbable que des prosumers seuls puissent proposer des contrats sur les marchés. Il a ainsi été proposé qu'un autre type d'agent, appelé agrégateur, fasse l'intermédiaire entre les marchés et les prosumers. Un aggrégateur représente un ensemble de prosumers (appelé agrégation ou coalition dans cette thèse) et s'occupe de prendre les décisions stratégiques et économiques pour ces derniers. En d'autres termes, il forme un portfolio de générateurs, charges, et moyens de stockage qu'il est à même de contrôler et s'occupe de passer des contrats avec d'autres entités. Contrairement à un prosumer seul, un agrégateur possède une capacité beaucoup plus importante qu'il peut en plus moduler avec une granularité beaucoup plus fine.

Toutefois, le point que nous soulevons dans cette thèse est que l'étape d'agrégation est primordiale pour la pérennité de la coalition. En effet, lorsqu'un contrat est passé entre deux entités, l'une des deux s'engage à injecter sur le réseau une certaine puissance durant une certaine période contre une rémunération proportionnelle à cette quantité et cette durée. Toutefois, si pour une raison quelconque, l'agrégateur ne parvenait pas à honorer son contrat, il subirait des pénalités financières proportionnelles à l'écart de production et à la durée de ces écarts. Tout le problème est que la production qu'offre un agrégateur est en réalité une somme de surplus de production de prosumers, réalisés grâce à des générateurs renouvelables.

L'agrégateur est donc face à un certain nombre de problèmes. Tout d'abord, il ne peut pas programmer sa production mais il doit l'estimer afin de proposer un contrat qu'il pense réalisable. Par ailleurs, s'il possède un certain contrôle sur les prosumers, il ne peut raisonnablement pas les forcer à suivre toutes ses directives. Un prosumer est en effet libre de consommer ce qu'il souhaite lorsqu'il le souhaite. En d'autres termes, un agrégateur se base sur des prévisions pour proposer un contrat, mais sa décision dépend aussi de son rapport au risque. En effet, plus le contrat est élevé, plus les gains peuvent être importants. Mais la probabilité de ne pas produire suffisamment, i.e le risque, augmente aussi. Cette probabilité est donc une quantité cruciale dans les décisions stratégiques et économiques d'un agrégateur, si bien que former sa coalition en fonction de celle-ci peut être une stratégie payante.

C.2.3 Agrégation et risque

C'est ce point ci que nous adressons dans le chapitre 4 de cette thèse. Etant donné un ensemble de N prosumers pour lesquels on possède un historique de leurs surplus de production, on cherche à former M coalitions optimisant le rapport entre l'espérance de leur production et le risque de sous produire par rapport aux contrats annoncés. Plus formellement, soit P S (t) la production d'une coalition S à un instant t. Par définition, on peut écrire P S (t) = i∈S P i (t) comme la somme des surplus de productions (P i (t)) réalisés par les prosumers appartenant à la coalition S. ]. ρ + (t) et ρ -(t) sont des paramètres fixés par l'opérateur de marché sur lesquels l'agrégateur n'a aucun contrôle. Ainsi, le but de ce dernier est de proposer une valeur de contrat qui maximise E[Gains S ]. Bien qu'étant un problème intéressant en soit, le travail réalisé ici se place en amont de ce choix. En effet, l'agrégateur possède un autre degré de liberté, il peut choisir la composition de sa coalition parmi un ensemble de prosumers afin d'agir directement sur le terme P S (t) de l'équation précédente. La difficulté de cette opération est que l'agrégateur ne possède que des informations sur le passé des prosumers alors qu'il souhaite calculer ses gains futurs. On comprend toutefois qu'un agrégateur cherche à maximiser l'espérance de sa production future E[P S (t)] tout en minimisant sa variance V ar[P S (t)].

Cela n'est pas sans rappeler certaines problématiques clé des marchés financiers. Plus précisément, la théorie des portfolios de Markowitz adresse presque exactement ce problème. Un trader cherche une combinaison linéaire des actions disponibles telles que le portfolio soit optimum. Markowitz montre qu'il existe un ensemble de portfolios, plus ou moins risqués, ayant cette propriété. Bien entendu, plus un portfolio optimum est risqué, plus les gains attendus sont importants. Cette théorie souffre néanmoins d'un défaut de taille. En effet, son fonctionnement repose sur l'hypothèse que les retours des actions suivent des lois normales (en réalité, on peut étendre les résultats de Markowitz à un ensemble un peu plus grand mais toujours très limité). Il a depuis été montré que les marchés financiers réels ne satisfaisaient généralement pas cette hypothèse.

Les agrégateurs ont également ce problème car les distributions des productions des prosumers ne sont généralement pas normales. On peut tout de même écrire :

E[P S (t)] = i∈S E[P i (t)] σ(P S (t)) = i∈S σ 2 i + i j ρ ij σ i σ j (C.4) Où σ i = V ar[P i (t)] et ρ ij ∈ [-1, 1]
est le coefficient de corrélation de Pearson entre P i et P j . Les termes croisés faisant intervenir les corrélations entre prosumers ont donc une grande importance dans la variance de la production de la coalition. Autrement dit, la structure de corrélation entre les prosumers d'une même coalition impacte directement la stabilité de sa production.

C.2.4 Former les coalitions maximisant les gains attendus

Etant donné que les agrégateurs ont accès aux historiques des P i (t), ils peuvent estimer les espérances, variances, et corrélations qui en découlent. Ils peuvent ainsi estimer, pour une coalition donnée, leur espérance de gains. Revenons toutefois à notre problème où M agrégateurs cherchent à former M coalitions à partir de N prosumers. Dans ces travaux, nous n'avons pas considéré de compétition entre les agrégateurs même si cela doit surement mener à des études très intéressantes. Notre approche fut de réaliser cette tâche tel que les gains soient maximisés globalement. Plus précisément, on cherche une répartition des prosumers en M groupes tels que la somme des gains soit maximum. Appendix C. Modéliser et optimiser un réseau électrique distribué, une approche systèmes complexes des prosumers dans le smart grid Bien que l'on soit en mesure d'estimer les gains pour n'importe quelle coalition, une recherche exhaustive est impensable dès lors que N dépasse quelques dizaines d'agents. Nous proposons donc une approche alternative se basant sur la théorie des graphes. Nous représentons la structure de corrélation entre les prosumers comme un graphe où les noeuds représentent ces derniers tandis que les arêtes ont un poids dépendant de la corrélation entre les deux extrémités. Cette approche fut proposée à la base par Mantegna en 1999 [START_REF] Mantegna | Hierarchical structure in financial markets[END_REF] pour étudier la structure des marchés financiers, et fut depuis améliorée par différents travaux de Onella [START_REF] Onnela | Dynamics of market correlations: Taxonomy and portfolio analysis[END_REF] [START_REF] Garas | The structural role of weak and strong links in a financial market network[END_REF]. La principale contribution de ces travaux fut de montrer qu'un filtrage sur les arêtes du graphe permettait de mettre en évidence des clusters fortement corrélés. En d'autres termes, si on est en mesure de construire ce graphe et de le filtrer correctement, on peut retrouver la structure de corrélation par l'intermédiaire d'un algorithme de détection de communautés. Appliquer cette méthode stricto sensu à notre problème génère des coalitions fortement corrélées. En d'autres termes, on regroupe ainsi des agents produisant de façon similaire, ce qui, nous le verrons plus en avant, résulte en des coalitions extrêmement instables.

Nous proposons ainsi de former un graphe tel que l'absence de corrélation soit un facteur rapprochant les noeuds. Ainsi, plus deux prosumers tendent à produire de façon décorrélée, plus le poids du lien les connectant sera important. Si bien que le filtrage du graphe est censé mettre en évidence les regroupements que nous considérons comme stables. Bien qu'un bon plan de prime abord, la réalité est plus compliquée car le graphe obtenu ne possède pas de structure bien définie comme son dual. Nous montrons toutefois que les cliques de ce type de graphe ont une corrélation interne assez faible de telle sorte qu'elles apparaissent comme des structures stables selon nos critères. Nous proposons donc d'utiliser ces cliques comme des points de départ pour les coalitions. Nous utilisons ensuite un algorithme inspiré de la détection de communautés par expansion de clique afin d'augmenter la taille de ces dernières. Cette opération gloutonne est contrôlée par l'intermédiaire d'une fonction d'utilité que nous cherchons à maximiser. Des prosumers sont ainsi ajoutés et retirés des cliques si ces opérations augmentent l'utilité des cliques, et ce jusqu'à ce qu'un maximum soit atteint. Bien entendu, rien dans cet algorithme glouton ne garantie l'optimalité globale de ce maximum. Nous ajoutons ainsi une part d'aléatoire dans cet algorithme qui peut être vue comme une sorte de recuit simulé. Avec une certaine probabilité diminuant dans le temps, un prosumer n'augmentant pas l'utilité d'une coalition peut être tout de même ajouté. En effectuant un certain nombre de passes de cet algorithme, nous montrons que l'on est en mesure d'obtenir des résultats proches de l'optimum (lorsque celui-ci peut être trouvé).

La contribution principale de nos travaux [START_REF] Gensollen | Coalition formation algorithm of prosumers in a smart grid environment[END_REF] et [START_REF] Gensollen | Stability and Performance of Coalitions of Prosumers Through Diversification in the Smart Grid[END_REF] fut de montrer qu'en formant les coalitions de prosumers en fonction de la dé-corrélation, les agrégateurs étaient en mesure de mieux prédire la production de leur coalition, et ainsi de générer des profits plus importants que s'ils avaient formé leurs coalitions au hasard. Nous montrons également que former ses coalitions au hasard est loin d'être la pire des stratégies possibles. En effet, la diversité des profils que permet d'obtenir un choix aléatoire est assez bonne et permet à cette stratégie de générer des gains honorables. Former des coalitions de prosumers fortement corrélés conduit par contre à des C.2. Formation de coalitions stables pour les marchés de l'électricité 131 productions fortement instables et difficilement prédictibles. Nous montrons ainsi que les agrégateurs ayant opté pour cette stratégie se retrouvent criblés de dettes dues aux pénalités.

Ces travaux se focalisent sur les surplus de production des prosumers et leur revente sur les marchés. Nous avons ainsi été amenés à faire un certain nombre d'hypothèses et de simplifications. La plus visible peut-être est l'absence de topologie et de dynamique pour le système électrique. On ne prend en effet jamais en compte dans ces travaux les contraintes que cela induit sur les coalitions. Par exemple, lors de l'étape d'agrégation, il se peut que certaines coalitions ne puissent être formées à cause de la topologie du réseau, ou que certaines coalitions aient des contraintes plus complexes sur leur production dues aux capacités finies des lignes électriques. Une autre simplification concerne les graphes de corrélation que nous avons utilisés pour former les coalitions. Ces graphes sont des versions statiques d'une structure dynamique plus complexe. En effet, la corrélation entre deux séries temporelles peut être vue comme une mesure dynamique de la dépendance linéaire entre ces séries. Plus précisément, il est possible de calculer la corrélation sur une fenêtre temporelle glissante dont la taille est un paramètre. En fonction de la taille de cette fenêtre il est possible de mettre en évidence des événements à l'échelle de temps plus ou moins grande, tandis que la dynamicité de la mesure permet de capter d'éventuels motifs saisonniers.

L'étude des graphes dynamiques est plus complexe que celle des graphes statiques, si bien que pendant longtemps la parade consistait à agréger les relations pour les ramener à une version statique. De récents progrès ont permis toutefois à l'étude de ces graphes de prendre un nouvel essor. Dans le chapitre 4 de cette thèse nous présentons des travaux encore en cours dont l'objectif est l'étude des graphes de corrélation dynamiques. Pour ce faire, nous nous basons sur une approche développée par [START_REF] Gauvin | Detecting the Community Structure and Activity Patterns of Temporal Networks: A Non-Negative Tensor Factorization Approach[END_REF] et qui utilise la factorisation de tenseurs pour mettre en évidence la structure spatio-temporelle de ces graphes. Un graphe dynamique peut être vu comme une suite temporelle de matrices d'adjacence qui encodent les snapshots successifs. En organisant ces matrices selon un troisième axe, on obtient un tenseur en trois dimensions contenant toute l'information du graphe dynamique. Toutefois, il est compliqué pour un esprit humain normalement constitué d'extraire des informations structurelles condensées à partir de cette représentation tridimensionnelle. La factorisation non négative de tenseurs est alors une des techniques permettant de condenser l'information. Nous montrons qu'en appliquant cette méthode aux graphes de corrélation, on est en mesure d'observer des motifs récurrents ainsi que des pics de corrélation courts et intenses qui sont généralement la traduction d'événements particuliers (crises financières par exemple). Nous proposons ensuite une application directe de cette méthode pour étudier la consommation électrique de foyers irlandais (données obtenues par l'intermédiaire de [START_REF]Irish Social Science Data Archive[END_REF]). Ces travaux sont encore en cours et seront probablement publiés après la soutenance de thèse, si bien que nous ne nous attarderons pas plus sur ce sujet.

C.3 Placement de stockages dans un réseau de prosumers C.3.1 Problématique générale

La seconde partie de cette thèse est toujours consacrée aux prosumers, mais propose une approche légèrement différente. Nous proposons ainsi de prendre en compte explicitement la topologie et la dynamique du réseau électrique. Notre objectif n'est alors plus la revente de surplus de production, mais l'installation de dispositifs de stockage permettant de maintenir la stabilité du système. Plus précisément, nous considérons un réseau de prosumers interconnectés par des lignes électriques. Certains de ces prosumers se comportent comme des générateurs car ils sont en excédant de production, tandis que d'autres peuvent être vus comme des charges car ils consomment plus qu'ils ne produisent. Comme nous l'avons vu dans la partie I, cet état n'est pas gravé dans la pierre, il dépend principalement des conditions météorologiques et des comportements des prosumers à un instant donné. Si bien que cette organisation entre générateurs et charges est fortement susceptible d'évoluer dans le temps. Nous sommes donc face à un réseau où générateurs et charges ne sont pas fixes, et dont les contributions sont stochastiques. Il est assez connu que le réseau électrique doit être synchronisé sur une fréquence commune Ω pour fonctionner (en Europe Ω = 50Hz). Plus précisément, la fréquence à laquelle le réseau est synchronisé doit être située dans un intervalle de valeurs acceptables [Ω-, Ω+ ]. Une condition nécessaire pour que cette synchronisation puisse avoir lieu est que la production et la consommation soient équilibrées. Si l'une est plus importante que l'autre, la fréquence du système dévie de Ω. Si rien n'est fait pour rééquilibrer la production et la consommation, la fréquence peut éventuellement sortir de l'intervalle de stabilité et provoquer des dommages aux divers équipements.

De ce point de vue, la stabilité d'un réseau de prosumers semble difficile à garantir puisque générateurs et charges changent constamment d'emplacements et de puissances. Nous proposons de maintenir la stabilité du système grâce à des dispositifs de stockage disséminés dans le réseau. L'idée, assez simple, consiste à stocker l'électricité lorsque la production excède la consommation, et à décharger celle-ci lors du cas inverse. Comme nous l'avons expliqué précédemment, cette méthode seule ne pourra probablement pas permettre de piloter le système, tout du moins avec les connaissances sur le stockage que nous avons actuellement. Néanmoins, activer des batteries est beaucoup plus rapide que d'allumer ou éteindre des générateurs de secours. En d'autres termes, le stockage peut être vu comme un moyen d'action rapide préalable à une réorganisation plus profonde du portfolio de production. Ce genre d'action est communément appelée régulation de fréquence.

La question que nous adressons ici est de déterminer à la fois le nombre et l'emplacement de ces dispositifs tels que le système puisse être contrôlé. Comme ces dispositifs sont couteux, nous cherchons à minimiser leur nombre (on fait l'hypothèse que les coûts d'installation sont les mêmes sur tout les noeuds du graphe). Nous montrerons dans ce qui suit que ces ensembles d'emplacements sont loin d'être tous équivalents. Nous développons un critère énergétique afin de comparer les performances de plusieurs ensembles, et nous montrons comment trouver celui qui fournit les meilleures performances en moyenne.

C.3.2 Modéliser la dynamique du réseau électrique

Pour cette étude nous avons besoin de mettre la dynamique du réseau électrique en équations. Toutefois, comme nous le verrons dans les parties suivantes, ce modèle doit être suffisamment simple pour pouvoir l'étudier par l'intermédiaire de la théorie du contrôle. Nous avons ainsi opté pour l'approche utilisée par [START_REF] Filatrella | Analysis of a power grid using a Kuramoto-like model[END_REF] qui modélise cette dynamique par un réseau d'oscillateurs couplés. Ces entités possèdent tous une fréquence propre à laquelle ils oscillent s'ils sont isolés. Par l'intermédiaire du réseau, un oscillateur est couplé à un ensemble d'autres oscillateurs voisins. Ainsi, la fréquence d'un oscillateur est impactée par celles de ses voisins et vice versa. On peut montrer que sous certaines conditions sur la topologie et la distribution des fréquences propres, le réseau se synchronise à une fréquence commune.

Le lien entre le réseau électrique et les oscillateurs couplés n'est pas forcément évident de prime abord. Ce processus ainsi que les hypothèses simplificatrices nécessaires sont détaillés dans [START_REF] Filatrella | Analysis of a power grid using a Kuramoto-like model[END_REF] et dans le chapitre 6 de la thèse. L'idée principale est que la dynamique des angles de phase de ces oscillateurs est une approximation de la dynamique réelle du système. Même dans cette forme simplifiée, cette dynamique n'est toujours pas linéaire car les équations sont couplées au travers d'un terme sinusoïdal. Nous faisons alors une hypothèse classique consistant à linéariser ces termes au premier ordre. On obtient alors une dynamique pouvant s'écrire sous la forme Ẋ = AX, où X est l'état du système à un instant donné, et A est la matrice gouvernant la dynamique du système. Cette dernière encode les paramètres du système comme la topologie du réseau, les coefficients de d'amortissement ou d'inertie des éléments par exemple.

C.3.3 Contrôle et réseaux

Sans aucune intervention extérieure, une dynamique du type Ẋ = AX a pour résultat une trajectoire dans l'espace d'état donnée par X(t) = e At . Cette trajectoire peut être ce que l'on désire, mais on peut également avoir le besoin d'influencer la dynamique de manière à suivre une trajectoire différente. Dans notre cas d'étude, supposons qu'un prosumer se mette soudainement à consommer plus qu'avant. Si tous les autres conservent la même attitude, le système est perturbé car la production n'est plus à la hauteur de la consommation. Ceci modifie l'état du système et place ce dernier sur une trajectoire qui peut potentiellement l'amener dans une région instable. Notre objectif est donc de ramener le système sur une trajectoire correcte en injectant au niveau de certains noeuds des signaux judicieusement choisis. Plus formellement, on peut réécrire la dynamique du système comme étant Ẋ = AX + Bu, où la matrice B encode les noeuds au niveau desquels sont injectés les signaux u(t). Toute la question est alors de déterminer B et u(t) en fonction de A, X 0 , et X T , où X 0 est l'état initial et X T l'état final désiré.

C.3.4 Contrôle optimal

Pour certaines applications, les signaux u(t) n'ont pas de signification physique réelle si bien que de grandes variations d'amplitude n'ont pas vraiment d'importance. Pour d'autres applications toutefois, ces signaux représentent une action qui peut être couteuse. Dans notre cas de système électrique, on peut interpréter ces signaux comme des taux de charge et de décharge des équipements de stockage. Bien entendu, charger et décharger des batteries possède un coût même dans le cas où l'énergie provient de générateurs renouvelables, si bien que l'on souhaiterait contrôler le système en effectuant un minimum de ces opérations. Cela est d'autant plus important qu'il peut exister plusieurs séquences de contrôle permettant d'amener un système donné d'un même état initial à un même état final. Trouver la « meilleure » séquence est au coeur de la théorie du contrôle optimal. Plus précisément, pour un système (A, B), un état initial X 0 , et un état final X T , le but est de trouver une séquence u (t) qui minimise une certaine fonction de coût J(u, X). Cette fonction de coût peut dépendre des signaux u(t) mais aussi des états dans lesquels le système va se trouver durant la phase de contrôle.

Pour le cas qui nous intéresse, nous choisissons une forme particulière de fonction de coût : J(u) = t f t 0 u(t) 2 dt = E appelée énergie de contrôle. Celle-ci quantifie indirectement la quantité d'énergie physique nécessaire pour le contrôle, et pénalise les fortes charges et décharges successives des batteries. Pour ce cas particulier de fonction de coût, il est possible de déterminer u (t) :

u (t) = B T eA T (T -t)W -1 (T )ν f (C.5)
Où ν f = X T ˘X0 e AT est la différence entre l'état final désiré et celui atteint sans contrôle, et W (t) = t 0 e Aτ BB T e A T τ dτ est la matrice gramienne du système. L'énergie de contrôle pour amener le système (A, B) de X 0 à X T en un temps T grâce aux signaux u (t) est alors minimum et s'écrit :

E min = ν T f W -1 (T )ν f (C.6)
Assez logiquement, l'énergie de contrôle minimum dépend des matrices A et B, du temps T, ainsi que des états initial et final. Cela signifie que pour un même triplet (A, B, T ), mais pour des couples (X 0 , X T ) différents, l'énergie de contrôle peut varier fortement. Etant donné que les prosumers qui composent le réseau sont difficilement prévisibles, la nature des perturbations peut être très diverse. Autrement dit, l'état initial X 0 dans lequel se trouve le système peut varier fortement en fonction du type de perturbation à laquelle nous devons répondre. Nous avons ainsi besoin de trouver une matrice B de noeuds contrôlés telle que l'énergie de contrôle soit minimum en moyenne. Pour ce faire, remarquons que la matrice W intervient dans l'expression de l'énergie de contrôle, mais ne s'exprime qu'en fonction des matrices A et B. En d'autres termes, W ne dépend pas des états initial et final, mais joue tout de même un rôle dans le calcul de l'énergie de contrôle. Ainsi, W peut être utilisé pour obtenir des informations sur l'énergie moyenne de contrôle.

C.3.5 Minimiser l'énergie moyenne de contrôle

Comme E min ∼ W -1 (T ), nous cherchons à sélectionner un ensemble de contrôleurs tel que W soit « grand ». Afin de formaliser cette notion, nous utilisons la trace de l'inverse de W (T r[W -1 ]) comme proxy. En effet, il a été montré que cette quantité était directement liée à l'énergie moyenne de contrôle, si bien que nous souhaitons minimiser cette quantité en sélectionnant l'ensemble optimum S de contrôleurs. En notant B S la matrice B obtenue en sélectionnant le sous-ensemble S de contrôleurs, W S la matrice gramienne du système (A, B S ), et F : S -→ -T r[W -1 S ], le problème devient :

M AX S∈N F (S) (C.7)
Pour une fonction F quelconque ce problème d'optimisation est difficile à résoudre, et il est souvent nécessaire d'utiliser des méthodes heuristiques sans garantie de performances. Cependant, des travaux récents sur le contrôle optimal ont montré que certaines métriques liées à la matrice gramienne possèdent une structure spéciale. Il a ainsi été démontré que la fonction F évoquée précédemment possède une structure sous modulaire, ce qui signifie que : F (X ∪ {x})˘F (X) ≥ F (Y ∪ {x})˘F (Y ), ∀X, Y, tq X ⊂ Y et ∀x ∈ N \ Y (C.8) Ce résultat nous permet d'utiliser un algorithme glouton relativement simple qui ajoute des éléments un à un en fonction des gains marginaux engendrés. Pour une fonction quelconque il n'y a aucune garantie qu'un algorithme aussi simple donne de bons résultats. Si la fonction d'ensemble est sous-modulaire, il a été montré que le résultat obtenu était égal, dans le pire des cas, à 63% de l'optimum. En pratique, cet algorithme fonctionne très bien et retourne des résultats souvent beaucoup plus proches de l'optimum que de la borne inférieure.

C.3.6 Intégrer les contraintes physiques du système

Notre méthode commence ainsi à émerger. A partir de la dynamique simplifiée (matrice A), nous pouvons utiliser l'algorithme glouton évoqué cidessus pour trouver le plus petit ensemble de noeuds du graphe tels que nous ayons le contrôle du système et que notre énergie de contrôle moyenne soit minimum. Cette approche, bien que valide en théorie, ne prend pas Appendix C. Modéliser et optimiser un réseau électrique distribué, une approche systèmes complexes des prosumers dans le smart grid en compte les diverses contraintes physiques qui pèsent sur le réseau électrique et sur les dispositifs de stockage. En effet, les lignes électriques possèdent des capacités maximum, tout comme les batteries dont les capacités de charge et décharge sont limitées. L'état du système et la trajectoire de celui-ci lors de la phase de contrôle sont donc contraints. Il est ainsi nécessaire de vérifier que ces contraintes ne seront pas violées lors de la sélection des contrôleurs. Une des difficultés est que ces contraintes ne peuvent être vérifiées que pour une trajectoire donnée, alors même que nous cherchons un placement efficace en moyenne. L'état initial de la phase de contrôle, et donc l'énergie de contrôle, dépend de la perturbation à laquelle le système a été soumis. Afin de déterminer si un placement S respecte les contraintes physiques du système, nous tirons aléatoirement des états initiaux dans une hyper-sphère centrée sur l'état d'équilibre, et nous vérifions les contraintes pour chacune des trajectoires qui en découlent. Si toutes ces trajectoires respectent les contraintes, alors nous considérons que le placement S permet le contrôle du système à la fois du point de vue théorique et physique.

C.3.7 Résultats

Afin de valider notre algorithme, nous comparons ses performances par rapport à une approche plus aléatoire. Pour un grand nombre de topologies aléatoires, nous tirons des ensembles de contrôleurs aléatoirement et nous comparons l'énergie moyenne de contrôle résultante avec celle obtenue via notre méthode. Cela nous permet de montrer que notre algorithme performe, en moyenne, toujours mieux que l'approche aléatoire, mais que la différence de performance est variable en fonction de la taille de l'ensemble des contrôleurs. Plus précisément, si les contrôleurs sont très peu nombreux par rapport au nombre de noeuds dans le graphe, alors les deux méthodes donnent des énergies de contrôle extrêmement élevées avec une différence assez faible entre les deux. A l'opposé, si le nombre de contrôleurs est quasiment égal au nombre de noeuds dans le graphe, alors tout est contrôlé et notre optimisation n'a pas de réelle utilité. Les deux énergies moyennes sont donc similaires. Pour des cas médians, nous montrons que notre méthode performe beaucoup mieux que l'approche aléatoire.

C.4 Conclusion

Cette thèse a été consacrée à l'étude des réseaux électriques intelligents avec une approche basée sur les systèmes complexes. Bien que les réseaux électriques actuels possèdent déjà un important panel d'outils de contrôle qui permet un fonctionnement fiable et stable, l'émergence de systèmes plus complexes, interconnectés, et distribués, nécessite des actions intelligentes et automatisées. Des données mesurées en temps réel par des capteurs disséminés sur les réseaux pourraient être combinées avec des algorithmes d'apprentissage automatique qui permettraient de prédire les événements et renforcer le contrôle du système.

Dans ce genre d'environnements interdépendants et multi-échelle, il pourrait être difficile de comprendre comment l'ensemble du système se C.4. Conclusion 137 comporte. La théorie des systèmes complexes aborde ce genre de problématiques où certains phénomènes collectifs émergent à partir de comportements individuels. Alors qu'une grande partie des travaux liés au smart grid se concentrent sur des composants très spécifiques des réseaux intelligents qui peuvent être testés en isolement, ce travail utilise des hypothèses et des modèles relativement simples pour les individus et étudie leurs répercussions à plus grande échelle.

Cette thèse est divisée en deux sections principales. La première se concentre sur la modélisation de marchés de l'énergie avec des agrégations de prosumers peu fiables en tant que participants, tandis que la seconde partie aborde l'optimisation du placement de batteries afin d'assurer une régulation de fréquence dans un réseau de prosumers.

La principale contribution pour la première partie est le développement d'un modèle de prosumer basé sur des données météorologiques réelles qui nous a permis de capturer les corrélations spatio-temporelles entre ces agents. Un modèle pour le marché de l'énergie a également été proposé et utilisé pour étudier comment les agrégateurs de marché pouvaient former des coalitions de prosumers de telle sorte qu'ils maximisent leurs gains avec de faibles risques. Nous avons montré que la diversification était un concept clé dans ce processus, de telle sorte que nous avons étudié une stratégie de regroupement sur la base de la corrélation. Nous avons proposé une optimisation gourmande qui commence par des cliques d'agents peu corrélés, et augmente leur taille aussi longtemps que leurs utilités sont améliorées. Nous avons ensuite comparé les résultats par rapport à d'autres méthodes et montré que l'algorithme proposé était plus performant que les autres. Nous pensons que les méthodes basées sur ce travail pourraient être utilisés par les agrégateurs sur les marchés de l'énergie afin de maximiser leurs gains attendus pour un risque donné. La méthode proposée pourrait probablement être améliorée en utilisant des données réelles de prosumers lorsque celles-ci seront disponibles. En outre, nous proposons dans le chapitre 4 une direction possible pour mieux comprendre la structure de corrélation entre les prosumers et possiblement améliorer la méthode. Nous avons en effet proposé d'utiliser une décomposition de tenseurs pour étudier les graphes de corrélation dynamiques au lieu de se contenter de leurs versions statiques. Être capable de comprendre la dynamique de ces graphes pourrait certainement fournir des informations précieuses aux agrégateurs de marché.

Nous pensons qu'une des contributions principales de la seconde partie fut de combiner la dynamique du réseau électrique avec la théorie du contrôle optimal afin d'étudier le positionnement de batteries dans un contexte stochastique. Par ailleurs, nous avons intégré les contraintes physiques du réseau électrique et des batteries dans ce processus. Nous avons également utilisé une méthode d'optimisation basée sur les fonctions sous-modulaires qui est facile à mettre en oeuvre et qui possède une garantie de performance. L'algorithme proposé est donc en mesure de produire une stratégie de placement efficace pour une topologie de réseau électrique donnée. Il semble inévitable que de grandes quantités de batteries devront être installées dans les futurs systèmes électriques. Optimiser leur emplacement à l'avance pourrait donc conduire à des économies importantes. Cette question a été abordée dans la littérature, mais jamais, à notre connaissance, par la théorie du contrôle optimal et la sous-modularité. Nous pensons que 138

Appendix C. Modéliser et optimiser un réseau électrique distribué, une approche systèmes complexes des prosumers dans le smart grid ce travail apporte une perspective différente sur cette question, et nous espérons que d'autres travaux seront entrepris dans cette direction. En termes de publications, le travail réalisé pour la première partie a donné naissance à un article présenté lors de la conférence IEEE ICC 2015, ainsi qu'à un article de journal publié dans IEEE Transactions on Smart Grid 2016, tous deux en tant que premier auteur (voir annexe ref AnnexeA pour obtenir une liste complète des publications). Pour la deuxième partie, un article sera présenté à la conférence IEEE SmartGridComm 2016 en novembre prochain. Un papier journal est également en cours de rédaction et sera probablement soumis au cours de l'été 2016. Les travaux présentés dans le chapitre 5 sur les graphes de corrélation dynamiques sont encore incomplets, car ils ont été entrepris peu avant la rédaction de la présente thèse. Ce travail est en cours d'achèvement et nous espérons qu'il sera soumis lors de l'automne 2016.

Mon travail actuel comprend également le mentorat de M. Lester Padilla, stagiaire de Master, qui travaille sur l'extraction de topologies de réseaux électriques à partir d'OpenStreetMap (OSM). Ce stage fut décidé après un séminaire passionnant organisé dans nos bureaux en Mars 2016 et devrait se terminer en Septembre 2016. L'idée est basée sur le projet SciGRID développé à NEXT ENERGY, EWE-Forschungszentrum für Energietechnologie en Allemagne. Le stage vise à extraire, à partir des données OSM, une topologie de réseau électrique contenant les générateurs et les charges. Avec des informations supplémentaires comme le type des générateurs, leurs capacités, les capacités des lignes électriques, et ainsi de suite, nous pensons que ce travail aidera les chercheurs à obtenir des données réalistes pour tester leurs recherches.

Dans une perspective plus lointaine, à cause de mon travail actuel sur les graphes temporels, j'ai développé une attirance pour l'étude de la détectabilité et l'évolution des communautés dans les graphes temporels. Cet intérêt est encore à un stade très précoce et j'espère avoir du temps à y consacrer dans un avenir proche. Un autre travail futur pourrait également être lié au projet Grid4Earth sur les microgrids.

Outre le travail effectué dans le cadre de ma thèse, j'ai également donné des cours (monitorat) à l'université Pierre et Marie Curie (UPMC) au cours de ces trois années. Au début, ce fut l'occasion pour moi de faire l'expérience de l'enseignement, car je ne savais pas, dès le départ, que cela me conviendrait. En fin de compte, le monitorat m'a confirmé que l'enseignement est quelque chose que j'apprécie particulièrement. Rétrospectivement, je me sens très chanceux d'avoir eu l'occasion d'apprendre et de découvrir beaucoup de choses fascinantes. Il est également frustrant d'avoir tant de choses à faire ou étudier et si peu de temps pour les explorer en profondeur. Bien que c'était dans un coin de ma tête depuis le début de ma thèse, je sais maintenant que je souhaite travailler dans le milieu universitaire en tant que professeur à l'avenir.

3. 1 4 . 8

 148 Screenshot from RTE website. Repartition of the production for a random day. . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Solar production (yellow) and consumption of user (red). Peaks of production do not coincide with consumption peaks. . . . 3.3 Efficient frontier given by the Markowitz theory of portfolios. (source: Wikipedia) . . . . . . . . . . . . . . . . . . . . . 4.1 Simulation process scheme. . . . . . . . . . . . . . . . . . . . 4.2 Schema of the space discretization. Agents A and B for example are both located in zone 0, and thus exposed to the same weather. . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Wind power curve model. . . . . . . . . . . . . . . . . . . . . 4.4 Solar irradiance at Paris during 2015 obtained with the Helios model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Two examples of electicity consumption at the user level (smart meter records from the ISSDA dataset). . . . . . . . . . . . . 4.6 The proposed model can also be used to model electricity production and consumption for microgrids. Depending on the configuration, an agent can be used to represent DER(s), load(s), prosumer(s), or a microgrid. . . . . . . . . . . . . . . 4.7 Normalized net production for 3 different prosumers over 2007 and 2008 (daily average values). . . . . . . . . . . . . . . xvi Available production (straight lines) and contract values (dashed lines) for two coalitions S 1 and S 2 . The areas filled with stars represent periods where storage should be charged, while areas filled with circles represent periods where storage should be discharged. . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.9 Probability distribution for the production of a simple gaussian example. . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.10 P CRCT S

xvii 4 .

 4 15 Resilience of the coalition structures when nodes fail randomly (see equation 4.23) for P M IN = 10M W (top subplot) and P M IN = 80M W (bottom subplot) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Sets of point and their Pearson's correlation coefficient. Source : Wikipedia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 From temporal networks to three dimensional tensors. Source : Andre Panisson at PyData, 2016 . . . . . . . . . . . . . . . . 5.3 PARAFAC and Tucker3 models. . . . . . . . . . . . . . . . . . 5.4 Correlation matrix based on total sample length before and after perturbation. . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Snapshots of the dynamic correlation graph. . . . . . . . . . 5.6 Tensor decomposition. . . . . . . . . . . . . . . . . . . . . . . 5.7 Tensor decomposition for smart meters records. . . . . . . . 6.1 Average consensus in networks. Topologies have a direct impact on the convergence of the algorithm. . . . . . . . . . . . 6.2 Schema of coupled oscillators. . . . . . . . . . . . . . . . . . . 6.3 Electrical line representation. (source: [23]) . . . . . . . . . . 6.4 Simple example of Kuramoto-like model for the power grid dynamic. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.5 Simple example of the effect of a power mismatch in the Kuramoto-like model for the power grid dynamic. . . . . . . 6.6 Controllability of networks. Source : [48] . . . . . . . . . . . 6.7 Structural controllability. Source : [48] . . . . . . . . . . . . . 6.8 Different control input sequences can drive the system from initial to final state. . . . . . . . . . . . . . . . . . . . . . . . . 7.1 Storage placement in prosumer networks. . . . . . . . . . . . 7.2 Simple storage model. . . . . . . . . . . . . . . . . . . . . . . 7.3 Submodularity example with sensor placements. . . . . . . . 7.

7 . 5

 75 log(E) against n D for random and optimized driver sets (N nodes = 50). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.6 n D against link probability p for erdos-renyi topologies (N = 100). Curves are averaged over 100 measurements. The top three curves show the results for the three metrics taken into consideration when all constraints are considered (see Level 1 in the main text). The bottom three curves exhibit the results for the same metrics when only the full controllability constraint is considered (see Level 2). . . . . . . . . . . . . . . 7.7 left panel : n D vs N clusters for different values of p in and p out = 0.1. N = 200 and curves are averaged over 100 realizations. right panel : n D against p in for systems of N = 200, p out = 0.1, and for different values of N clusters . The curves are averaged over 100 realizations. . . . . . . . . . . . . . . . xviii 7.

FIGURE 1 . 1 :

 11 FIGURE 1.1: World Energy Consumption by Source (from [68]).

FIGURE 1 . 2 :

 12 FIGURE 1.2: Per capita world energy consumption, calculated by dividing world energy consumption shown in Figure 1.1 by population estimates (from [68]).

  L F I S A L V IA T I

Figure 2 . 7 FIGURE 2 . 3 :

 2723 FIGURE 2.3: Erdös-Rényi networks of n = 50 nodes for different values of p.

  FIGURE 2.4:Barabasi-Albert preferential attachment model. Nodes sizes are proportional to their degrees.

FIGURE 2 . 7 :

 27 FIGURE 2.7: Overlaping community structure.

FIGURE 2 . 8 :

 28 FIGURE 2.8: Structure of the power grid.Source : Wikipedia

FIGURE 2 . 9 :

 29 FIGURE 2.9: European high voltage power grid extracted with Gridkit (13871 nodes and 17277 edges).

FIGURE 2 . 10 :

 210 FIGURE 2.10: Smart grid multilayer achitecture. Source:Wikipedia.

FIGURE 3 . 1 :

 31 FIGURE 3.1: Screenshot from RTE website. Repartition of the production for a random day.

FIGURE 3 . 2 :

 32 FIGURE 3.2: Solar production (yellow) and consumption of user (red). Peaks of production do not coincide with consumption peaks.

FIGURE 3 . 3 :

 33 FIGURE 3.3: Efficient frontier given by the Markowitz theory of portfolios. (source: Wikipedia)

3 FIGURE 4 . 1 :

 341 FIGURE 4.1: Simulation process scheme.

FIGURE 4 . 2 :FIGURE 4 . 3 :

 4243 FIGURE 4.2: Schema of the space discretization. Agents A and B for example are both located in zone 0, and thus exposed to the same weather.

FIGURE 4 . 4 :

 44 FIGURE 4.4: Solar irradiance at Paris during 2015 obtained with the Helios model.

  Figure 4.4 shows an example for the city of Paris during 2015.

FIGURE 4 . 5 :

 45 FIGURE 4.5: Two examples of electicity consumption at the user level (smart meter records from the ISSDA dataset).

FIGURE 4 . 6 :

 46 FIGURE 4.6: The proposed model can also be used to model electricity production and consumption for microgrids. Depending on the configuration, an agent can be used to represent DER(s), load(s), prosumer(s), or a microgrid.

Figure 4 .

 4 Figure 4.7 shows the normalized net productions of 3 different prosumers obtained from the model developed above. The curves span years 2007 and 2008 and are daily averaged for clarity. As visible, the combination of the location, DER, and consumption yields very different net production patterns. Some prosumers with low consumption and solar production exhibit very bursty production without visible seasonality (see top subplot of figure 4.7). While others have a clear seasonal pattern with a net production much higher in the summer than in the winter (see bottom subplot of figure 4.7). These prosumers might have a majority of solar arrays as DER and/or a strong heating consumption.The examples of figure 4.7 show prosumers which almost always produce because they were configured with much more DER than loads. The opposite case, or a more balanced situation where the net production can be either positive or negative are also possible.

Chapter

FIGURE 4 . 9 :

 49 FIGURE 4.9: Probability distribution for the production of a simple gaussian example.

Chapter 4 .

 4 FIGURE 4.10: P CRCT S depending on reliability parameter φ for Gaussian distributions (see equation 4.14). Blue curve with triangles stands for a coalition S with an expected production of 5 units and a standard deviation of 0.5. Under a grid policy of φ = 0.1, it is able to announce a contract value of P CRCT S = 4.36.The same coalition in term of expected production (µ = 5), but with a higher variance (σ = 1.5, cyan curve with circles) can only afford a smaller contract value of P CRCT

FIGURE 4 . 11 :

 411 FIGURE 4.11: Gaussian mean approximation (N = 100, φ = 0.1, μ = 5, σ = .5, ρ = 0.2). Subplot a shows how the parameter α of the utility function should be chosen in function of the mean size of the coalitions (see equation 4.20). Subplot b displays the corresponding utility functions for different values of α. Blue curve with diamonds favors small coalitions of 2 agents while the green one with triangles favors 5 agents coalitions. Finally, the red curve with squares has an optimal size of 15 agents.

1

  cos(a + b) = cos(a)cos(b) -sin(a)sin(b)

FIGURE 4 . 12 :

 412 FIGURE 4.12: Histograms of utility values for coalitions of size 3 ( N = 3) in a N = 200 prosumers example (φ = 0.1, α = 0.08, μ = 3.9 M W , σ = 1.9M W , ρ = 0.69). Red bars stand for cliques in the decorrelation graph, and blue bars for all the other possible triples.Cliques tend to exhibit higher utilities than random coalitions.

Chapter 4 .

 4 Forming Stable Aggregations of Prosumers for Electricity Markets

FIGURE 4 . 13 :

 413 FIGURE 4.13: Utility of random coalitions depending on their size in a N = 200 prosumers example (φ = .1, μ = 3.9 M W , σ = 1.9M W , ρ = 0.69). Blue dots show real mean utility values and the thick red curve its smoothed version by applying a Savitzky-Golay filter. On this plot, α = 0.006, and was selected according to eq. 4.20 in order to favor N = 40 agents coalitions.

Chapter 4 .FIGURE 4 . 14 :FIGURE 4 . 15 :

 4414415 FIGURE 4.14: Coalitions formed in the (contract value, volatility)space. The color map indicates the underlying quality. The closer to red the better (high contract values with small volatility). On the opposite, blue areas show poor quality (small contract values with high volatility). Blue dots stand for the decorrelated coalitions that we formed while green squares show correlated coalitions. The smaller yellow markers stand for the gravity centers of the coalition structures. The black dotted line shows how contract values and volatility evolve when the size of the coalitions increases (a subset of the points are labeled by the size of the coalition they represent). Each point is the average over 10 5 unconstrained draws of a random coalition. We also show the distribution of the gravity centers of random coalition structures with red ellipses (center is the mean, and each ellipse corresponds to one standard deviation).

FIGURE 5 . 1 :

 51 FIGURE 5.1: Sets of point and their Pearson's correlation coefficient. Source : Wikipedia.

FIGURE 5 . 2 :

 52 FIGURE 5.2: From temporal networks to three dimensional tensors. Source : Andre Panisson at PyData, 2016

FIGURE 5 . 3 :

 53 FIGURE 5.3: PARAFAC and Tucker3 models.

FIGURE 5 . 4 :

 54 FIGURE 5.4: Correlation matrix based on total sample length before and after perturbation.

70 Chapter 5 90 FIGURE 5 . 5 :

 7059055 FIGURE 5.5: Snapshots of the dynamic correlation graph.

3 FIGURE 5 . 6 :

 356 FIGURE 5.6: Tensor decomposition.

1 F a c. 2 F a c. 3 F a c. 4 F

 1234 a c.

FIGURE 6 . 1 :

 61 FIGURE 6.1: Average consensus in networks. Topologies have a direct impact on the convergence of the algorithm.

FIGURE 6 . 2 :

 62 FIGURE 6.2: Schema of coupled oscillators.

FIGURE 6 . 3 :

 63 FIGURE 6.3: Electrical line representation. (source: [23])

FIGURE 6 . 4 :

 64 FIGURE 6.4: Simple example of Kuramoto-like model for the power grid dynamic.

FIGURE 6 . 8 :

 68 FIGURE 6.8: Different control input sequences can drive the system from initial to final state.

FIGURE 7 . 1 :

 71 FIGURE 7.1: Storage placement in prosumer networks.

FIGURE 7 . 2 :

 72 FIGURE 7.2: Simple storage model.

FIGURE 7 . 3 : 104 Chapter 7 .

 731047 FIGURE 7.3: Submodularity example with sensor placements.

7. 4 .

 4 Finding the optimal storage placement in prosumer networks

FIGURE 7 . 5 :

 75 FIGURE 7.5: log(E) against n D for random and optimized driver sets (N nodes = 50).

FIGURE 7 . 6 :

 76 FIGURE 7.6: n D against link probability p for erdos-renyi topologies (N = 100). Curves are averaged over 100 measurements. The top three curves show the results for the three metrics taken into consideration when all constraints are considered (see Level 1 in the main text). The bottom three curves exhibit the results for the same metrics when only the full controllability constraint is considered (see Level 2).

FIGURE 7 . 7 :

 77 FIGURE 7.7: left panel : n D vs N clusters for different values of p in and p out = 0.1. N = 200 and curves are averaged over 100 realizations. right panel : n D against p in for systems of N = 200, p out = 0.1, and for different values of N clusters .The curves are averaged over 100 realizations.

7. 4 .FIGURE 7 . 8 :

 478 FIGURE 7.8: n D vs the relative standard deviation of the capacity distribution of the batteries σ λ µ λ . The dots are averages over 100 measurements and the curves are obtained using a Savitzky-Golay filter, each color shows the results for a given metric. The graphs are erdos-renyi with N = 100 and p = 0.3, and µ λ = 100 units.

FIGURE 7 . 9 :

 79 FIGURE 7.9: European transmission power grid[START_REF] Tue | The RE-Europe data set[END_REF]. Nodes are colored according to their county.

C. 1 .

 1 Introduction 123 a pour conséquence de fortement réduire les pertes par effet Joules lors du transport. Les réseaux très haute tension maillent généralement les pays en fonction de la répartition des populations et des ressources et constituent les squelettes des réseaux électriques. L'opération inverse est ensuite effectuée pour réduire la tension jusqu'aux niveaux d'utilisation des clients. Ce type d'architecture « top-down », où l'électricité ne circule que dans un sens, possède un certain nombre de défauts que nous évoquerons plus loin. Par ailleurs, il n'existe que très peu d'échanges d'information entre les entités opérant le réseau et les utilisateurs finaux. Au mieux, les compteurs électriques individuels ne sont relevés que tout les six mois afin d'ajuster les montants des factures.

  et couvrent la France de 2006 à 2012 avec une fréquence d'échantillonnage de 3h, et les Etats-Unis durant 2010 avec une fréquence d'une heure.

  1.1 World Energy Consumption by Source (from[START_REF]Our Finite World[END_REF]). . . . . . . 1.2 Per capita world energy consumption, calculated by dividing world energy consumption shown in Figure1.1 by population estimates (from [68]). . . . . . . . . . . . . . . . . . . 2.1 Power grid architecture. Source : Wikipedia . . . . . . . . . . 2.2 Network of medicis . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Erdös-Rényi networks of n = 50 nodes for different values of p. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Barabasi-Albert preferential attachment model. Nodes sizes are proportional to their degrees. . . . . . . . . . . . . . . . . 2.5 Small World model. . . . . . . . . . . . . . . . . . . . . . . . . 2.6 Planted partition model. . . . . . . . . . . . . . . . . . . . . . 2.7 Overlaping community structure. . . . . . . . . . . . . . . . . 2.8 Structure of the power grid. Source : Wikipedia . . . . . . . 2.9 European high voltage power grid extracted with Gridkit (13871 nodes and 17277 edges). . . . . . . . . . . . . . . . . . 2.10 Smart grid multilayer achitecture. Source: Wikipedia. . . . .

World Wide Web xxi List of Symbols Prosumer model notations :

  are colored according to their county. . . . . . . . . . . . . . . . . . . . . 7.10 Gramian rank and control energy evolution for European transmission power grid (see figure 7.9). . . . . . . . . . . . .

	xxii				xix xxiii
	error function List of Abbreviations erf (•) P CRCT S best possible contract value for coalition S control energy E W (t) Gramian matrix N (µ, σ) normal distribution with mean µ and standard deviation σ --W ρ ij pearson's correlation coefficient between P i and P j -P r[•] probability of some event -Storage model notations : Chapter 1	--
	φ	r	reliability threshold maximum charge/discharge rate	-	W
	P M IN Λ M AX	minimum production threshold Maximum capacity	W	W h
	AC BA DC DER DP DSM EDF ER EV HVDC High-Voltage Direct-Current Alternating Current Distributed Energy Resources Dynamic Pricing Demand Side Managment Electricité De France Erdös Rényi Electric Vehicle (s) OSM Open Street Map PV PhotoVoltaic panel RTE Réseau de Transport d'Electricité SM Small World UPMC Université Pierre et Marie Curie V2G Vehicle to Grid VPP Virtual Power Plant WT Wind Turbine Total production of agent i Total consumption of agent i zone of agent i Wind turbine model notations : wind speed at agent i location cut-in-speed rated output speed cut-out speed rated output power wind turbine power curve Solar array model notations : solar radiance at agent i location number of coalitions average number of agent in a coalition correlation matrix G(V, E) graph G with vertex set V and edge set E P P i (t) P D i (t) Z i ν i (t) ν in ν out ν cut P m F W T Ψ i (t) N COAL N M N i neighborhood of node i d ij distance between i and j filtering threshold optimum filtering threshold Θ k (G) set of non overlapping cliques of size k in G R S resilience of coalition S ψ fraction of failed agents Power grid dynamic notations : θ i phase angle of node i (or deviation from Ω) δ i phase angle of node i WWW P i (t) Available extra-production of agent i δ S (i) marginal contribution of agent i to coalition S Direct Current P M AX normalizing factor for utility function Barabàsi Albert α coalition size parameter U(•) utility function Λ(t) Energy stored at time t	-----------rad rad -W --	W W -m s -1 m s -1 m s -1 m s -1 W -W/m 2 W W h
	ω i	Ψ i (t)	perfect solar radiance at agent i location natural frequency of node i	Hz	W/m 2
	K	η i (t)	cloudiness at agent i location coupling strength	-	octat
	γ	ρ	array efficiency phase cohesiveness	rad	-
	L †	S	array surface moore-penrose pseudo inverse of laplacian L	-	m 2
	F P V • ∞,E worst case dissimilarity over edge set E solar array power curve Ω main frequency	-Hz	-
	K D		Consumption model notations : dissipation constant	kg.m 2 .s -1
	I		inertia		kg.m 2
	τ i (t) P M AX ij	outside temperature at agent i location maximum capacity of line (i, j)	W	K
	P S,i α	T i R i B i	desired inside temperature for agent i thermal resistance for agent i ideal power source/sink at node i surface of thermal exchanges for agent i dissipation term	W s -1	K K W -1 m 2
		Ω i	maximum consumption possible for agent i Control notations :		W
		ω i	vector of the average fraction of Ω i used for each hour		-
	u(t) u (t) F heat i i A F elec X(t)	noise term input vector of control signals heating power curve of agent i appliance power curve of agent i optimum input vector of control signals dynamic of the system state of the system	----	---
	B		control matrix	Market model notations :	-
	T		control time		s
	C I	A N	set of prosumers controllability matrix number of prosumers identity matrix	--	--
	N D n D	P S (t) P CRCT number of drivers available extra-production of coalition S S contract value for coalition S fraction of drivers in the system	--	W W

  Basically,

		Chapter 4. Forming Stable Aggregations of Prosumers for Electricity
							Markets
	Solar irradiance	Jan 2015 0 200 400 600 800 1000	Apr Jul Oct Jan 2016 hourly month average	00:00 01-Jun 1000 800 600 400 200 0 2015 00:00 01-Dec 2015 0 50 100 150 200 250 300 350	06:00 12:00 18:00 06:00 12:00 18:00	00:00 02-Jun 00:00 02-Dec	06:00 12:00 18:00 06:00 12:00 18:00

  4. Forming Stable Aggregations of Prosumers for Electricity Markets

		12
		10
	Available production	4 6 8		P CRCT S 2
		2				P CRCT S 1
		0	0	5	10 Time of the day	15	20
				FIGURE 4.8: Available production (straight lines) and con-

tract values (dashed lines) for two coalitions S 1 and S 2 . The areas filled with stars represent periods where storage should be charged, while areas filled with circles represent periods where storage should be discharged.

  .7, where the number of drivers is plotted against p in for N = 200 and N clusters ∈ {2, 4, 5, 10}. For N clusters = 2 and p in = 0.1 the number of drivers is large since the graph is poorly connected. When p in increases, n D decreases until a minimum value n D ∼ 0.6 at p in ∼ 0.25. After this point, n D augments with p in . For N clusters = 10, we do not see this behavior : n D decreases continuously as p in increases as expected from the curves of the bottom left panel of figure 7.7.

  Comme expliqué précédemment, l'agrégateur gérant S doit proposer un contrat P CRCT S sur le marché pour une période ∆t. Durant cette période, si P S (t) ≥ P CRCT C.2. Formation de coalitions stables pour les marchés de l'électricité 129 Où λ S (t) = P [P S (t) < P CRCT S

	S alors l'agrégateur respecte constamment son contrat et la coalition sera ré-∀t
	munérée t+∆t t l'électricité. A l'inverse, si P S (t) ≤ P CRCT ρ + (t)P CRCT dt, où ρ + (t) est le prix unitaire de revente de S S ∀t alors l'agrégateur est toujours en défaut de production et la coalition sera pénalisée de t+∆t t ρ -(t)P CRCT dt, S où ρ -(t) est la pénalité unitaire. Ainsi, lorsque l'agrégateur propose un con-
	trat P CRCT S	, son espérance de gain peut s'écrire comme :
	E[Gains S ] =	t	t+∆t	[1 -λ S (t)]ρ + (t)P CRCT S	S -λ S (t)ρ -(t)[P CRCT	˘PS (t)]dt (C.3)

Acknowledgements

Acknowledgements ix

Chapter 7. Optimal storage placement for prosumer networks

The next chapter first gives a short summary of the present thesis, and then addresses the ongoing works. Finally, the main ideas of some future works that are still at an early stage of development are presented. Cette thèse est consacrée à l'étude d'agents appelés prosumers parce qu'ils peuvent, par l'intermédiaire de générateurs basés sur des énergies renouvelables, à la fois produire et consommer de l'électricité. Il est concevable que, si leurs productions excèdent leurs propres besoins, les prosumers chercheront à vendre leur surplus. Bien entendu, ces excédents sont extrêmement volatiles, car ils dépendent à la fois des conditions météorologiques à un instant donné, mais aussi de la consommation des agents. Étant donné qu'il n'existe pas, pour le moment, de données réelles précises sur la dynamique de ces excédents, le début de cette thèse a été consacré à la modélisation et à la simulation de ces prosumers. Dans un souci de réalisme, nous nous sommes basés sur des données météorologiques réelles plutôt que sur des distributions aléatoires classiques. Ces simulations nous ont permis d'obtenir des séries temporelles décrivant comment les excès de productions (positifs ou négatifs) évoluent pour différents agents.

Appendix A

List of publications

L'étude de ces séries a mis en évidence des corrélations spatio-temporelles non triviales qui sont d'une grande importance pour les agrégateurs. Comme leur nom l'indique, ces agents forment des portefeuilles de générateurs, de charges électriques, et de moyens de stockage afin de vendre des services à l'opérateur du réseau. Ces services sont destinés à maintenir la stabilité du système, que ce soit par de la régulation de fréquence ou en équilibrant production et consommation. En regroupant divers prosumers, un agrégateur peut chercher à stabiliser sa production. Cela est primordial car un agrégateur, lié par un contrat avec l'opérateur, peut faire l'objet de sanctions s'il est incapable de remplir son rôle. Nous montrons dans cette thèse que la structure de corrélation entre les prosumers a un impact direct et décisif Appendix B. Thesis abstract in french sur la stabilité des agrégats, et donc sur le risque encouru par les agrégateurs. Ainsi, nous proposons un algorithme pour minimiser le risque d'un ensemble d'agrégations, tout en maximisant leur gain attendu. Cette méthode gourmande est basée sur la théorie des graphes et permet des gains significatifs par rapport à des approches plus aléatoires.

Si le marché de l'énergie et les interconnexions entre les pays sont censés aider à stabiliser le système, il est encore très probable qu'une forte augmentation de la capacité de stockage sera nécessaire. La mise en place de dispositifs de stockage dans un réseau où les générateurs et les charges sont dynamiques et stochastiques apparaît comme un véritable défi. En effet, la dynamique non linéaire du réseau électrique et la multitude de perturbations possibles rendent l'existence d'un placement globalement dominant plutôt improbable. Il semble plus approprié de rechercher une stratégie avec une bonne performance en moyenne des situations possibles. Compte tenu de la taille de l'espace d'état, une méthode non-exhaustive avec une garantie semble être nécessaire. Nous proposons de répondre à cette question avec une approche basée sur la théorie du contrôle dans les réseaux. Nous modélisons le système électrique par un réseau d'oscillateurs couplés, dont la dynamique des angles de phase est une approximation de la dynamique réelle du système. Le but est de trouver le sous-ensemble des noeuds du graphe qui, lors d'une perturbation du système, permettrait le retour à l'équilibre si les bons signaux y étaient injectés. Nous montrons que ces signaux peuvent être interprétés comme la puissance à laquelle les dispositifs de stockage doivent injecter ou absorber de l'électricité. Nous cherchons ensuite le placement qui permet de minimiser l'énergie moyenne de contrôle. Nous proposons un algorithme, basé sur l'optimisation de fonctions sous-modulaires, pour trouver un placement proche de l'optimum. Nous montrons également qu'il existe une limite qui contraint le résultat de l'algorithme, de telle sorte que nous avons une garantie d'être proche de l'optimum.

Appendix C

Modéliser et optimiser un réseau électrique distribué, une approche systèmes complexes des prosumers dans le smart grid C.1 Introduction

C.1.1 Vers un nouveau système énergétique

Au cours de ces dernières années, il semble que la modernisation des systèmes électriques soit devenue une nécessité. Les installations crées au cours du XXème siècle atteignent actuellement la fin de leur durée de vie théorique et devraient être, en toute logique, réparées et modernisées. Toutefois, depuis leur déploiement initial, de vastes progrès ont été réalisés au sein des technologies de l'information. Internet, les réseaux mobiles, ou encore les objets connectés pour ne citer qu'eux, sont le fruit d'un développement effréné du monde le l'informatique au sens large.

Parallèlement à ce boom, les systèmes électriques n'ont que peu changé depuis leur déploiement. Bien entendu, la manière dont ces systèmes sont gérés a évolué, en utilisant largement les possibilités offertes par ces nouvelles technologies. Toutefois, l'architecture de base, c'est-à-dire la philosophie initiale avec laquelle ces systèmes ont été établis est restée globalement la même. De façon simplifiée, la production d'imposantes centrales réparties sur le territoire est planifiée suivant la prévision de la consommation des utilisateurs. Cette production de base est ensuite affinée le jour J grâce à des générateurs pouvant être allumé ou éteint beaucoup plus facilement et rapidement. Durant ces dernières décennies, ce mode de fonctionnement a fait ses preuves et a l'avantage d'être relativement simple et d'apporter une stabilité satisfaisante au système. Pourquoi vouloir alors révolutionner un système qui fonctionne ?

Il existe un certain nombre de raisons plus ou moins profondes pour envisager une transition vers un nouveau type de système. Premièrement, les centrales et générateurs évoqués jusqu'à maintenant fonctionnent grâce à des sources d'énergies fossiles (nucléaire, charbon, pétrole. . . ). Ce type de générateur possède l'avantage de pouvoir être programmé à l'avance. Il est alors relativement aisé de s'adapter à la consommation des utilisateurs du réseau. Cependant, il est désormais bien connu que ces sources Appendix C. Modéliser et optimiser un réseau électrique distribué, une approche systèmes complexes des prosumers dans le smart grid La théorie du contrôle permet de répondre à ce genre de question. Plus précisément, le système (A, B) est dit contrôlable s'il est possible de le piloter de n'importe quel état initial à n'importe quel état final au moyen d'une suite finie de signaux u(t) injectés au niveau des noeuds encodés par B. Déterminer si un système est contrôlable est un objectif classique de la théorie du contrôle. Pour ce faire il existe un certain nombre de méthodes, dont l'une des plus anciennes et connues est certainement le critère de Kalman, qui consiste à vérifier que la matrice C = [B, AB, A 2 B, . . . , A N -1 B] possède un rang égal à N. Cela fonctionne très bien sur de petits systèmes mais devient rapidement problématique pour des systèmes plus complexes.