Energy and Power E ngineering, 2013, 5, 597602 doi:10.4236/epe.2013.54B115 Published Online July 2013 (http://www.scirp .o rg/journal/epe) Copyright © 2013 SciRes. EPE An EnergyBased 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 energybased 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 currentflow betweenness on the IEEE 14bus 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; Currentflow 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 [14]. 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 socalled randomwalk 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 andomwalk betweenness is closely related to the currentflow betweenness proposed in [6]. The paper derives the metric straightforward from the electrical current and proves that the currentflow closeness is in fact identical with the information centrality [7]. Some papers proposed their measures which are actually of no difference with the currentflow 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 currentflow centrality. Besides, they pointed out the differences of the topology of power grids from that of ErdosRenyi random graphs, the “smallworld” networks or “scalefree” networks but the power networks appear to have a scalefree 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 unserved 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 easyunderstanding 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 resistancedistance 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 currentflow betweenness, that is, the local currentflow betweenness is given. Section 4 provides the comparisons with the currentflow 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. CurrentFlow Betweenness The currentflow 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 currentflow betweenness respectively by: , , 1 () (), ( 1) 1 () (). ( 1)(2) CB st st V CB st st V ce e nn cv v nn τ τ ∈ ∈ =− =−− ∑ ∑ The currentflow betweenness is reasonable for that the current is uni que by Lemma 1 of [6]. Besides, Brandes proposed also the currentflow 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 energybased 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 Kirchhoffbased cen trality. Analo gous to the defi nit ion o f verte x cur ren tflow betweenness, we can also define the vertex energybased centrality and vertex Kirchhoffbased 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 energybased 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 currentf 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 ntflow b et weenness by ,() () .    st sSt T b e LC eST σ ∈∈ =∑ The vertex local currentflow betweenness is defined similarly and denoted by v LCu. 4. Numerical Analysis In this section, the edge (vertex) energybased metric and the edge (vertex) Kirchhoffbased metric are compared with the edge (vertex) currentflow betweenness, the edge (vertex) local curr e ntflow betweenness and the closeness centrality on the IEEE 14bus. 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 14bus 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 14bus. Figure 2 . The graph representation of IEEE 14bus transmissio n network. nodes and the ellipses represent the transmission nodes. It is known that for the highvoltage 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 currentflow betweenness, edge lo cal currentflow betweenness, edge energybased meas ure a nd ed ge Kir chho ffbased measure are abbreviated as B, LocalB, Ebased and Kfbased respectively. All the four methods rank the edge 56 first, which says that the edge 56 is very possible to be the most important b ranch in this network. It shows that the edge betweenness and the edge Kirchhoffbased 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 LocalB Ebased Kf based 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 56 12 79 910 47 45 611 1011 914 613 1314 15 24 25 23 34 1213 612 49 56 613 914 12 1314 79 47 24 25 15 49 34 23 1213 612 910 1011 611 45 56 914 1314 613 12 47 79 15 49 24 25 612 1213 910 1011 611 23 34 45 56 910 914 79 611 1011 47 1314 613 12 34 1213 612 45 49 23 15 24 25 Table 2. The importanc e order of nodes f rom high to lo w. Order VB VLocalB C VEbased VKfbased 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 currentflow betweenness and our edge energybased 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 energybased ce ntralit y is lower than tha t of computing the edge local currentflo 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 {12, 15, 23, 24, 25, 34, 45, 47, 49, 56, 611, 612, 613, 79, 910, 914, 1011, 1213, 1314}, denote by and 2 X the ranking lists for energybased centrality and edge local currentflow betweenness respectively. Using linear regression to check whether and 2 X are relevant, we get that the adjusted 2 equals 0.814 and the pvalue 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 Kirchhoffbased measure with the effective resistances being replaced the Kirchhoff index. Besides, we propose the local currentflow betweenness in the most simple way more clear ly. Based on defined measures, experiments are performed on IEEE 14bus and some interesting results are discov ered. It has been found that our proposed edge energy based measure is very similar to the local currentflow 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 gybased measure is very simple and clear. Besides, from the ex periments we get that the currentflow betweenness is very different fro m the local currentflo w. Ho wever, it is difficult to j udge which are mo re accurate. Moreover, we verify that the currentflow 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 KGCX2RW329) 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. 14. 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. 12, 2004, pp. 9297. doi:10.1016/j.bbr.2011.03.031 [4] M. RosasCasals, 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. 24652475. 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. 3954. 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. 533544. doi:10.1007/9783540318569_44 [7] K. A. Stephenson and M. Zelen , “Rethinking Centrality: Methods and Examples,” Social Networks, Vol. 11, No. 1, 1989, pp . 137. doi:10.1016/03788733(89)900166 [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 , 710 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/9781461416050_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, 2224 February, 2010, pp. 5254. 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.8195. doi:10.1007/BF01164627 [12] K. C. Das, A. D. Gungor and A. S. Cevik, “ On Kirchhoff Index and ResistanceDistance Energy of a Graph,” MATCH Communications in Mathematical and in Com puter Chemistry, Vol. 67, No. 2, 2012, pp. 541556. [13] B. Zhou and N. Trinajstic, “On ResistanceDistance and Kirchhoff Index,” Journal of Mathematical Chemistry, Vol. 46, N o. 1, 20 09, pp. 283289. doi:10.1007/s1091000894593 [14] L. C. Freeman , “A Set of Measures of Centrality Based On Betweenness,” Sociometry, Vol. 40, No. 1, 1977, pp. 3541. [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. 78217826. doi:10.1073/pnas.122653799 [16] B. Bollobás, “Modern Graph Theory,”3rd Edition, Sprin gerVer 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. 910, 2003, pp . 494498. [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. 102109. doi:10.1016/j.ress.2012.02.005
