Energy and Power E ngineering, 2013, 5, 597-602 doi:10.4236/epe.2013.54B115 Published Online July 2013 (http://www.scirp .o rg/journal/epe) Copyright © 2013 SciRes. EPE An Energy-Based Centrality for Electric al Net works Ruiyuan Kong1, Congying Han2, Tiande Guo1, Wei Pei3 1Scho ol of Mathematical S ciences, U niversity o f Chinese Acade my of Sciences , Beijin g, China 2College of Humanities and Social Sciences , Universit y of Ch i nese Academy of Sciences, Beijing, China 3Insti tute of Electri cal Engin eer ing, Chin es e Academy of Sciences, Beij ing, Chin a Email: xyzkong@126.com Received December, 2012 ABSTRACT We present an energy-based method to estimate centrality in electrical networks. Here the energy between a pair of ver- tices denotes by the effective resistance between them. If there is only one generation and one load, then the centrality of an edge in our method is the difference between the energy of network after deleting the edge and that of the original network. Compared with the local current-flow betweenness on the IEEE 14-bus system, we have an interesting dis- covery that our proposed centrality is closely related to it in the sense of that the significance of edges under the two measures are very si milar. Keywords: Centra lity; Energy; Effective Re si stance; Current-flow Betweenness 1. Introduction The electrical network is one of the most critical and complex infrastructure networks in modern society. There are some important issues which are keys to the performance of the network. Reliable electric power supply, for example, is crucial for many devices and its disturbances may disrupt the devices or even paralyze the network. This brings the concern about reliability and resilience to disturbances and failures of various types of infrastructure systems, and a corresponding demand for methods of analyzing the vulnerabilities of the electrical network [1]. Moreover, the blackouts of the North American and Italian electric power grids in 2003 ex- posed the weaknesses of the electrical network. The weakness and vulnerable analysis about the electrical network have been widely stud ied in the past years [1-4]. With recent advances in network and graph theory, many researchers have applied centrality measures to complex networks in order to study network properties. Various centrality measures have been defined. They draw links between the structure of networks and the vulnerability to certain types of failures, and are used to identify the most vulnerable ele ments of a network. Tra- ditionally, there are four centrality measures within net- work analysis, i.e., degree centrality, betweenness, closeness, and eigenvector centrality. The degree metric utilizes the local i nformation. Close ness and betweenness utilize the shortest pa th information. And the eigenvecto r metric rely on the Laplacian matrix of the group. All of them consider only the topological properties but not the actual physical flow through the power system. Moreo- ver, the betweenness and closeness centrality postulate that the information or flow transfer along the shortest path, but this is not true for the current in the electrical network. A series of centrality measures considering the physical flow are proposed. [5] proposed a so-called random-walk betweenness, counting how often a node is traversed by a random walk between two other nodes. This centrality is known to be useful for finding vertices of high centralit y that d o not lie on the shortest p ath. Ac- tuall y, the r andom-walk betweenness is closely related to the current-flow betweenness proposed in [6]. The paper derives the metric straightforward from the electrical current and proves that the current-flow closeness is in fact identical with the information centrality [7]. Some papers proposed their measures which are actually of no difference with the current-flow betweenness though they didn’t point t hat directly. For example, [8] proposed an electrical centrality measure based on the impedance matrix which is similar to the current-flow centrality. Besides, they pointed out the differences of the topology of power grids from that of Erdos-Renyi random graphs, the “small-world” networks or “scale-free” networks but the power networks appear to have a scale-free network structure under their proposed measure. However, as the indication of [9], the proposed electrical centrality meas- ure in [8] was defined incorrectly. But a simple analysis shows that the revised measure was the right current- flow betweenness. The betweenness above needs to take into account all pairs of nodes in the networks. [10] considered only the
R. Y. KONG ET AL. Copyright © 2013 SciRes. EPE pairs of generations and load nodes. Besides, they consi- dered some other features of power systems such as power transfer distribution and line flow limits, and got that according to the un-served energy after the network being attacked the nodes ranked highly is more vulnera- ble. The centralities defined before are not so easy to un- derstand. This paper will propose an easy-understanding method which is based on the effective resistance. The effective resistance between a pair of vertices s and t is the potential difference between them ensuring a current of size 1 from s to t, and can be seen as the total energy in the system. The effective resistance is local in some sense. Its global form is the Kirchhoff index, which is based on the resistance-distance matrix introduced in 1993 by Klein and Randic and defined as the effective resistance between pairs of vertices [11]. The Kirchhoff index is often used to quantify the str uctural attr ibutes of the graph. See [12,13] for more information. This paper is organized as follows. In Section 2, we introduce some preliminary concepts about centrality measures, the effective resistance and so on. In section 3, the definition of our measure based on energy and the variation of current-flow betweenness, that is, the local current-flow betweenness is given. Section 4 provides the comparisons with the current-flow betweenness cen- trality and other centrality measures. Conclusions are drawn in Section 5. 2. Preliminaries 2.1. Betweenness Vertex betweenness, first introduced by Freeman in 1977 [14], is one of the most used centrality measure. It re- flects the occurrence degree of a node on the shortest path between any pair of nodes. Given a undirected graph GV E, whe r e V is the set of vertices and E is the set of edges, the betweenness of a node v is defined by: ( )/ () , (1)(2)/ 2 st st svtV b v Cv nn σσ ≠ ≠∈ =−− ∑ where st σ and st v σ are the number of shortest paths from s to t and the number of shortest paths from s to t through v. Girva n and Newm an [15] generalized the ver- tex betweenness to edges and proposed edge between- ness which is defined as the number of shortest paths between pairs of vertices that run along it and used to find which edges are most important. If there is more than one shortest path between a pair of vertices, then take t hem as one path. The edge betwee nnes s is given b y: ( )/ () . (1) / 2 st st stV b e Cv nn σσ ≠∈ =− ∑ It is found that the removal of the nodes or edges with large bet weenness will put th e network at high risk to b e disconnected. 2.2. Current-Flow Betweenness The current-flow betweenness here is based on the defi- nition of [6]. An electrical network is a graph VEc Gc=together with a function , where (e) e cc= is the reciprocal of the resistance of the edge e. Given a supply of size 1 from a source s to a sink t, the throughput of an edge e and an inner vertex v is defined by: : ()|() |, 1 ()|() |. 2 st st ev e e we v we τ τ ∈ = =∑ Define the edge and vertex current-flow betweenness respectively by: , , 1 () (), ( 1) 1 () (). ( 1)(2) CB st st V CB st st V ce e nn cv v nn τ τ ∈ ∈ =− =−− ∑ ∑ The current-flow betweenness is reasonable for that the current is uni que by Lemma 1 of [6]. Besides, Brandes proposed also the current-flow closeness centrality which is a variation of closeness centrality. It is defined by: () () () C CC st st ts n cs ps pt ≠ =− ∑ for all s in V, where refers to the voltage in the vertex s. Moreover, Brandes proved that the current- flow closeness centrality equals informatio n centrality. 2.3. Effective Res istan ces , E nergy and Ki rchh o ff Index Now we give the definition of effective resistances. The effective resistance is the potential difference between s and t ensur ing a c urrent of siz e 1 fr om s to t a nd denoted by st . The total energy in a network is defined as: 22 () (), xyx yxyx yxy xy Exy Exy E w VVcVVw ∈∈ ∈ =−=− ∑∑ ∑ where x V is absolute potential and is the energy in the edge between x and y. By Lemma 2 of [6], there are unique potentials. So the definition of the total energy is reasonable. Kirchhoff index is the sum of the effective resistances over all pairs of vertices: where is the effective resistance between i and j. It is
R. Y. KONG ET AL. Copyright © 2013 SciRes. EPE proved that Kirchhoff index satisfies where are the nonzero eigenvalues of the Laplacian matrix of G. 3. Centrality Metric Based on Energy It is known that the total energy in an electric current with size 1 from s to t is the effective resistance [16]. If there is o nl y one so urce s and one s in k t, t hen t he c ha nge in the energy is the change in the effective resistance between s and t. Therefore to measure the influence of removing one edge we can define a ‘metric’ based on the variant of energy by: ( )(\)(), st st EeRGe RG∆= − where is the graph deleted by the edge e. Though is not a strict definition of a metric, we regard it as a metric since we only focus on the results under the metric but not their values. The larger , the greater the risk for the network to be damaged when dele ti ng t he edge e. If there is no connection between s and t after deleting the edge e, t hen . In other words, the edge e with is very important to the network. By the monotonicity principle, Corollary 7 of [16], is nonnega tive for all edges. For the network with sources S and sinks T where , the metric based on energy is defined by , ( \)() () , | || | st st sSt T RGe RG Ee ST ∈∈ − ∆= ∑ where denotes the cardinality of the set S. The energy-based centrality can be seen as a local metric to measure the importance of an edge. Analogous to the definition of betweenness, we consider the whole impor- tance of an edge, that is, ( \)() '( ). (1) / 2 st st st RGe RG Ee nn ≠ − ∆= − ∑ (1) If we define ( \)() () , (1) / 2 Kf GeKf G Kf enn − ∆= − then it is easy to check that by the definition of the Kirchhoff index. So we call the case defined by Equation (1) the edge Kirchhoff-based cen- trality. Analo gous to the defi nit ion o f verte x cur ren t-flow betweenness, we can also define the vertex energy-based centrality and vertex Kirchhoff-based centrality by () () () , |( )| eu v Ee Eu u ∈Γ ∆ ∆= Γ () () () , |( )| eu v Kf e Kf uu ∈Γ ∆ ∆= Γ where denotes by the adjacent edge s of the vertex u. Next we take Theorem 1 of [17] as a lemma which will be used to compute the energy-based centrality. Lemma 1. Let G be a connected graph on ver- tices and . Let Li be the submatrix ob- tained from the Laplacian matrix L of the graph G by deleting its ith row and ith column and be the submatrix obtained from the Laplacian matrix L by de- leting its ith and jth rows and the ith and jth columns. Then the effective resistance between i and j satisfies det(( ,)). det(( )) ij Li j rLi = (2) Note that the gra ph G in the lemma above can be seen as a graph with one unit resistance on each edge of the network. Following the steps of its proof, we can easily check t hat the result holds for the graph G with different resistances on the edges and the Laplacian matrix L being replaced by the admittance matrix of the network. Though in general the complexity of computing the ef- fective resistance using equation (2) is3 On , the re- markably simple expression is still very valuable. Recall the argument of the reference [10] in the intro- duction. The authors utilized a local idea considering the electrical betweeness only between the pairs of genera- tions and loads with some other restriction, but they didn’t point out that clearly and didn’t give the corres- ponding simulation results. Thus this paper gives the definition and simulation clearly, and calls it the local current-f low betwe enness. Analogo us to the current -flow betweenness, for the network with so urces S and sinks T we define the edge local curre nt-flow b et weenness by ,() () . | || | st sSt T b e LC eST σ ∈∈ =∑ The vertex local current-flow betweenness is defined similarly and denoted by v LCu. 4. Numerical Analysis In this section, the edge (vertex) energy-based metric and the edge (vertex) Kirchhoff-based metric are compared with the edge (vertex) current-flow betweenness, the edge (vertex) local curr e nt-flow betweenness and the closeness centrality on the IEEE 14-bus. The IEEE 14- bus consists of 20 lines and 14 buses including 2 genera- tors and 2 loads, as shown in Figure 1. And Figure 2 is the graph representation of IEEE 14-bus transmission network. The circles with labeled G represent the gene- rator nodes, the circles with labeled L represent the load
R. Y. KONG ET AL. Copyright © 2013 SciRes. EPE Figure 1 . Transmissio n netw ork IEEE 14-bus. Figure 2 . The graph representation of IEEE 14-bus transmissio n network. nodes and the ellipses represent the transmission nodes. It is known that for the high-voltage transmission net- work in a power grid the reactance is usually the domi- nant component of a line impedance. Thus for the pur- pose of simplicity, we take the reactance as the edge weights. And the bus 8 will not affect the effective resis- tance between the generations and loads, thus we don’t consider it. To keep in accord, we compute other central- ity metrics based on the case above. Besides, the bus 8 is of low betweenness centrality by [18]. Table 1 ranks the edges according to the four edge centralities. The edge current-flow betweenness, edge lo- cal current-flow betweenness, edge energy-based meas- ure a nd ed ge Kir chho ff-based measure are abbreviated as B, Local-B, E-based and Kf-based respectively. All the four methods rank the edge 5-6 first, which says that the edge 5-6 is very possible to be the most important b ranch in this network. It shows that the edge betweenness and the edge Kirchhoff-based centrality are quite different with each other and with the other two measures.
R. Y. KONG ET AL. Copyright © 2013 SciRes. EPE Table 1. The importance order of edges from high to low. Order B Local-B E-based Kf -based 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 5-6 1-2 7-9 9-10 4-7 4-5 6-11 10-11 9-14 6-13 13-14 1-5 2-4 2-5 2-3 3-4 12-13 6-12 4-9 5-6 6-13 9-14 1-2 13-14 7-9 4-7 2-4 2-5 1-5 4-9 3-4 2-3 12-13 6-12 9-10 10-11 6-11 4-5 5-6 9-14 13-14 6-13 1-2 4-7 7-9 1-5 4-9 2-4 2-5 6-12 12-13 9-10 10-11 6-11 2-3 3-4 4-5 5-6 9-10 9-14 7-9 6-11 10-11 4-7 13-14 6-13 1-2 3-4 12-13 6-12 4-5 4-9 2-3 1-5 2-4 2-5 Table 2. The importanc e order of nodes f rom high to lo w. Order V-B VLocal-B C VE-based VKf-based 1 2 3 4 5 6 7 8 9 10 11 12 13 4 5 6 9 2 7 1 13 10 11 14 3 12 2 13 14 1 6 5 4 9 7 3 12 10 11 12 14 3 11 13 1 10 7 2 6 9 5 4 14 6 9 13 5 7 1 2 4 12 10 11 3 10 9 7 14 11 6 5 13 12 4 3 1 2 But there is a strong correlation between the edge local current-flow betweenness and our edge energy-based centrality. The first 5 important edges are the same and their orders are of little difference. Moreover, the edges ranking from 5 to 11 are also consistent with their or ders being little differe nt. I n fact, f or a ny edge e in the f irst 11 edges, the difference between the ranking of e in t he t wo cases is at most 2. However, the complexity of compu- ting the edge energy-based ce ntralit y is lower than tha t of computing the edge local current-flo w b et weenne ss. And the complexities for computing the two centrality are both . But the latter has a much more clear ex- pression. In practice, we can use both to measure the importance of two edges from different perspectives. If we give the edge ranking first the score 19, the edge ranki n g se co nd the score 18, …, the e d ge r an ki ng la st the score 1, and denote by the edge bet ween the ver- tex i and j. Then given the ordered sequence {1-2, 1-5, 2-3, 2-4, 2-5, 3-4, 4-5, 4-7, 4-9, 5-6, 6-11, 6-12, 6-13, 7-9, 9-10, 9-14, 10-11, 12-13, 13-14}, denote by and 2 X the ranking lists for energy-based centrality and edge local current-flow betweenness respectively. Using linear regression to check whether and 2 X are relevant, we get that the adjusted 2 equals 0.814 and the p-value is very close to 0. This shows that they are strongly correlated. 5. Conclusions This paper considers measures of centrality that are used to rank the importance of the nodes or edges in an elec- trical network. New methods of centrality are defined from the perspective of the energy of a network. More specifically, we use the variant of the effective resis- tances between the generations and loads after deleting an edge or a node to measure its importance, similar to whi ch we a lso define a Kirchhoff-based measure with the effective resistances being replaced the Kirchhoff index. Besides, we propose the local current-flow betweenness in the most simple way more clear ly. Based on defined measures, experiments are performed on IEEE 14-bus and some interesting results are discov- ered. It has been found that our proposed edge energy- based measure is very similar to the local current-flow bet wee nne s s, i n the sen se t ha t the i mpo r ta nce r a nki n gs of the edges in the two measures are of little difference. While the expression of computing the ener gy-based measure is very simple and clear. Besides, from the ex- periments we get that the current-flow betweenness is very different fro m the local current-flo w. Ho wever, it is difficult to j udge which are mo re accurate. Moreover, we verify that the current-flow betweenness is closely re- lated to the closeness centrality in our experimen ts. H ow - ever, more tests and analysis need to be done in order to validate the proposed measure, to find the most effective measure and to dig deep to see which nodes or edges are the real most important nodes or edges. 6. Acknowled gements This work is supported by CAS Knowledge Innovation Program (grant number KGCX2-RW-329) and National Natural Science Foundation of P.R. China (grant nu mber 10831006, 71271204). REFERENCES [1] R. Albert, I. Albert and G. L. Nakarado, “Structural Vu l- nerability of the North American Power Grid,” Physical Review E, Vol. 69, No. 2, 2004, pp. 1-4. doi:10.1103/PhysRevE.69.025103 [2] B. A. Carreras, V. E. Lynch, I. Dob son and D. E. New-
R. Y. KONG ET AL. Copyright © 2013 SciRes. EPE man, “Critical Points and Transitions in an Electric Power Transmission Model for Cascading Failure Blackouts,” Chaos, Vol. 12, No. 4, 2002, pp. 985 -994. doi: 10.1063/1.1505810 [3] P. Crucittia, V. Lator ab and M. Marchior ic, “A Top olog- ical Analysis of the Italian Electric Power Grid,” Physica A: Statistical Mechanics and its Applications, Vol. 338, No. 1-2, 2004, pp. 92-97. doi:10.1016/j.bbr.2011.03.031 [4] M. Rosas-Casals, S. Valverde and R. V. Solé, “Topolog- ical Vulnerability of the European Power Grid Under Er- rors and Attacks,” International Journal of Bifurcation and Chaos in Applied Sciences and Engineering, Vol. 17, No. 7, 2007 , pp. 2465-2475. doi: 10.1142/S0218127407018531 [5] M. E. J. Newman, “A Measure o f Betweenn ess Centr ality Based on Random Walks,” Social Networks, Vol. 27, No. 1, 2005, pp. 39-54. doi:10.1016/j.socnet.2004.11.009 [6] U. Brandes and D . Fleischer, “Centrality Measu res Based on Current Flow,” Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Springer, Berlin, Vol. 3404, 2005, pp. 533-544. doi:10.1007/978-3-540-31856-9_44 [7] K. A. Stephenson and M. Zelen , “Rethinking Centrality: Methods and Examples,” Social Networks, Vol. 11, No. 1, 1989, pp . 1-37. doi:10.1016/0378-8733(89)90016-6 [8] P. Hines and S. B l ums ac k, “A Centrality Measure for Electrical Networks,” Proceedings of the 41st Hawaii In- ternational Conference on System S ciences, Ha waii , 7-10 Janua r y 2008, p.185. doi:10.1109/HICSS.2008.5 [9] Z. H. Wang, A. Scaglione and R. J. Thomas, “Electrical Centrality Measures for Power Grids,” Control and Op- timization Methods for Electric Smart Grids, Po wer El ec- tronics and Power System, Springer, New York, Vol.3, 2012, pp. 239 -255. doi:10.1007/978-1-4614-1605-0_12 [10] E. Bompard, D. Wu and F. Xue, “The Concept of Bet- weenness in the Analysis of Power Grid Vulnerability,” Complexity in Engineering, Rome, 22-24 February, 2010, pp. 52-54. doi:10.1109/COMPENG.2010.10 [11] D. J. Klein and M. Randic, “Resistance Distance,” Jour- nal of Mathematical Chemistry, Vol. 12, No. 1, 1993, pp.81-95. doi:10.1007/BF01164627 [12] K. C. Das, A. D. Gungor and A. S. Cevik, “ On Kirchhoff Index and Resistance-Distance Energy of a Graph,” MATCH Communications in Mathematical and in Com- puter Chemistry, Vol. 67, No. 2, 2012, pp. 541-556. [13] B. Zhou and N. Trinajstic, “On Resistance-Distance and Kirchhoff Index,” Journal of Mathematical Chemistry, Vol. 46, N o. 1, 20 09, pp. 283-289. doi:10.1007/s10910-008-9459-3 [14] L. C. Freeman , “A Set of Measures of Centrality Based On Betweenness,” Sociometry, Vol. 40, No. 1, 1977, pp. 35-41. [15] M. Girvan and M. E. J. Newman, “Community Structure in Social and Biological Networks,” Proceedings of the Nation al Academy o f Sciences, Vo l . 9 9, N o. 12 , 20 02 , p p. 7821-7826. doi:10.1073/pnas.122653799 [16] B. Bollobás, “Modern Graph Theory,”3rd Edition, Sprin- ger-Ver lag, New York, 2003. [17] R. Bapat, I. Gu tman and W. Xiao, “A Simple Method for Computing Resistance Distance,” Zeitschrift für Natur- forschung, Vol. 58a , No. 9-10, 2003, pp . 494-498. [18] E. Zio , R. Piccinelli and M. Delfanti , “Application of the Load Flow and Random Flow Models for the Analy- sis of Power Transmission Networks,” Reliability Engi- neering and System Safety, Vol. 103, 2012, pp. 102-109. doi:10.1016/j.ress.2012.02.005
|