Graphs, Networks and Power Systems

A simple introduction to graphs and graph theory

In 1736, the great mathematician Leonard Euler wanted to cross all seven bridges of Königsberg exactly once. The methods he used to proof that this is indeed not possible, he invented a totally new mathematical field, today called graph theory. Graph theory investigated the relations of objects, which are encoded in the eponymous graphs. While graph theory is still an active research field in fundamental mathematics today, it's very fundamental questions allow graph theory to be applied to countless research fields. It is not just used in biology, physics and computer science, but also in fields like social science and even linguistics. And, graph theory can be applied to the power system as well.

 

Fig. 1 - Drawing of the seven bridges of Königsberg, from https://commons.wikimedia.org/wiki/File:Konigsberg_bridges.png

Fig. 1 - Drawing of the seven bridges of Königsberg, from https://commons.wikimedia.org/wiki/File:Konigsberg_bridges.png

 

Graphs consists of objects, usually called vertices, and the relations, which are called edges. An example of a real-world network is shown in the next figure. This graph shows 200 famous actors as the nodes (The actors where chosen from a list of the 1000 best actors ever. How accurate this list is was not discussed). The connections between the actors are movies to which both actors contributed. As can be seen, all actors are connected over some other actors to each other. In graph theory, this is called a connected graph. The graph also shows how different actors are connected. Some prolific actors are placed very central, with many connections to each other. Other actors, located on the outside, only played in very few movies or shared little movies with the other actors in the list. In the example, two nodes are highlighted: The node shown in violet is the actor with the most shared movies in the list, which also acts as the most central node in the graph. Movie enthusiasts might be able to guess that this actor is Robert De Niro. The other highlighted actor is one of six actors which only share a single movie, here chosen as the legendary Charlie Chaplin.

 

Fig. 2 - Graph showing 200 famous actors and their connections

 

The probably most interesting property of many real world network is the so called small-world effect, which has probably been observed by most people in the world at some point. Often, a short connection between two seemingly unrelated people can be found. For example, your plane neighbour might have gone to high school with your great-aunt. While this is a particular example, it is shown that in many real-world network, ALL nodes are connected by a "small" number of edges. The famous six degrees of separation stem from this idea: All human beings might be connected by just six nodes. In networks, this effect can be investigated with the average shortest path length. This number gives an average about how many edges separate all vertices in the network.  In the examples of the actors, the average shortest path length is less than 2.4. This means that the average pair of actors is connected over less than three connections. While some actor pairs will be connected with a larger distance, the analysis shows that the maximum distance in this graph is just five. The assumption of the six degrees of separation is also obviously valid in the actor network.

Another typical occurrence in some real world networks is clustering. A typical example can be imagined in social circles in different smaller cities. While the inhabitants of each city might be closely connected to each other (as neighbours, colleagues, family or friends), the connections to the inhabitants of the next city might be much sparser. The inhabitants of each city form a cluster. Both circles might still be connected, but the connections inside each cluster are generally denser. In the following artificial graph, two clusters are indicated by the coloured circles. Not every graph shows clustering behaviour. Especially many random graphs, which are used in mathematical analysis, might not exhibit clustering behaviour. The example real world actor network does, for example, not directly reveal any clustering. A way to quantify the clustering behaviour is the average clustering coefficient of the graph. This value indicated how easy it is to find clusters in the network. The simple example graph has a value of 70%, which indicated that the graph has some clustering properties. In contrast, the actors network has only a clustering coefficient of 21%.

 

Fig. 3 - A simple example graph with two different clusters

Fig. 3 - A simple example graph with two different clusters

 

Power systems and graphs

One can ask how this, arguably interesting, phenomenon is connected to power systems? As it turns out, the underlying structure of the power system can in fact be described by a graph. The nodes in the graphs are all the buses, connected to generators or loads, while the edges are the transmission lines between these buses. As discussed in a previous blog article [3], the topology of the network will influence the stability of the power system.

Due to the transition to renewable energies, the structure of the power system will change. Large generators in power plants will be replaced by smaller feeders like wind turbines, offshore wind parks have to be included and new lines, including HVDC connections with related problems, will be included in the power system. While the system is changing, the question of how the structure of the new network is supposed to look like is still relevant. For example, in [1] it was shown that networks which show a small-world behaviour might be more robust to small load and generation changes. This effect is probably due to the shorter difference between generator and loads. At the same time, this small-world networks might be more susceptible to cascading failures. The clustering coefficient is usually larger in small world networks, which means that failures can spread very wide. The role of key buses in the power system, such as large power plants which connect a lot of transmission lines, have to be taken into the account for topological analysis.

Understanding the topological and graph theoretical properties can be a great help in designing and controlling the power system. The challenges in designing an efficient, robust and economically viable power system are still great. And it is fascinating how a mathematical theory invented to find a perfect path for a Sunday stroll can describe human interactions and the behaviour of neurons in the brain, but is also used to design the perfect power system.

 

[1] S. Mei, X. Zhang, and M. Cao, Power grid complexity. Beijing: Tsinghua Univ. Press, 2011.

[2] F. Dorfler, M. Chertkov, and F. Bullo, “Synchronization in complex oscillator networks and smart grids,” Proceedings of the National Academy of Sciences, vol. 110, no. 6, pp. 2005–2010, Feb. 2013.

[3] http://www.incite-itn.eu/blog/synchronization-in-dynamical-systems-and-power-systems/

No Comments Yet.

Leave a comment