A network science-based k-means++ clustering method for power systems network equivalence
Tóm tắt
Network equivalence is a technique useful for many areas including power systems. In many power system analyses, generation shift factor (GSF)-based bus clustering methods have been widely used to reduce the complexity of the equivalencing problem. GSF captures power flow on a line when power is injected at a node using bus to bus electrical distance. A more appropriate measure is the one which captures what may be called the electrical line distance with respect to a bus termed as relative bus to line distance. With increase in power transactions across different regions, the use of relative bus to line distance becomes appropriate for many analyses. Inspired by the recent trends in network science on the study of network dynamics based on the topological characteristics of a network, in this paper, we present a bus clustering method based on average electrical distance (AED). AED is independent of changes in location of slack bus and is based on the concept of electrical distance introduced in the context of molecular chemistry and pursued later for applications in social and complex networks. AED represents the AED from a bus to buses of the transmission line of interest. We first propose an AED-based method to group the buses into clusters for power systems network equivalence using k-means clustering algorithm integrated with silhouette analysis. One limitation of this method is that despite its speed, sometimes it may yield clusters of inferior quality compared to the optimal solution. To overcome this limitation, we next present our improved clustering method which incorporates a seeding technique that initializes centroids probabilistically. We also incorporate a technique in our method to find the number of clusters, k, to be given as input to our clustering algorithm. The resulting algorithm called AED-based k-means++ clustering method yields a clustering that is O(logk) competitive. Our network equivalence technique is next described. Finally, the efficacy of our new equivalencing technique is demonstrated by evaluating its performance on the IEEE 300-bus system and comparing that to the performance of our AED-based method (Sharma et al. in Power network equivalents: a network science-based k-means clustering method integrated with silhouette analysis. In: Complex networks and their application VI, Lyon, France. p. 78–89, 2017) and the existing GSF-based method.
Tài liệu tham khảo
U.S. Energy information administration: energy explained. http://www.eia.gov/energy_in_brief/article/power_grid.cfm.
Wang H, Sanchez CEM, Zimmerman RD, Thomas RJ. On computational issues of market-based optimal power flow. IEEE Trans Power Syst. 2007;22(3):1185–93.
Hogan W. A market power model with strategic interaction in electricity networks. Energy J. 1997;18:107–41.
Duran H, Arvanitidis N. Simplification for area security analysis: a new look at equivalencing. IEEE Trans Power App Syst. 1972;91(2):670–9.
Cheng X, Overbye TJ. PTDF-based power system equivalents. IEEE Trans Power App Syst. 2005;20(4):1868–76.
Shi D, Tylavsky DJ. A novel bus-aggregation-based structure preserving power system equivalent. IEEE Trans Power App Syst. 2015;30:4.
Dimo P. Nodal analysis of power systems. London: Kent; 1975.
Ward JB. Equivalent circuits for power flow studies. AIEE Trans Power App Syst. 1949;68:373–82.
Srinivasan S, Sujeer VN, Thulasiraman K. A new equivalence technique in linear graph theory. J Inst Eng. 1964;44(12):496.
Srinivasan S, Sujeer VN, Thulasiraman K. Application of equivalence technique in linear graph theory to reduction process in a power system. J Inst Eng. 1966;46:12.
Housos EC, Irisarri G, Porter RM, Sasson AM. Steady state network equivalents for power system planning applications. IEEE Trans Power App Syst. 1980;99(6):2113–20.
Tinney WF, Bright JM. Adaptive reductions for power flow equivalents. IEEE Trans Power App Syst. 1987;2(2):351–60.
Swamy MNS, Thulasiraman K. Graphs, networks and algorithms. New York: Wiley; 1981.
Klein DJ, Randic M. Resistance distance. J Math Chem. 1993;12:81–95.
Newman MJ. A measure of betweenness centrality based on random walks. Soc Netw. 2005;27(1):39–54.
Tizghadam A, Leon-Garcia A. Autonomic traffic engineering for network robustness. IEEE J Select Area Commun. 2010;28(1):39–50.
Chellappan V, Sivalingam KM, Krithivasan K. A centrality entropy maximization problem in shortest path routing networks. Comput Netw. 2016;104:1–15.
Doyle PG, Snell JL. Random walks and electrical networks. Washington, D.C.: The Mathematical Association of America; 1984.
Coppersmith D, Doyle P, Raghavan P, Snir M. Random walks on a 129 weighted graphs and applications to online algorithms. In: 22nd symposium on the theory of computing. 1990. p. 369–78.
Blumsack S, et al. Defining power network zones from measures of electrical distance. In: 2009 IEEE power energy society feneral meeting. 2009. p. 1–8.
Oh H. A new network reduction methodology for power system planning studies. IEEE Trans Power App Syst. 2010;25(2):677–84.
Shi D, Shawhan DL, Li N, Tylavsky DJ. Optimal generation investment planning: pt. 1: network equivalents. In: 44th North American power symposium, Champaign, IL, USA. 2012. p. 1–6.
Sharma D, Thulasiraman K, Wu D, Jiang JN. Power network equivalents: a network science-based k-means clustering method integrated with silhouette analysis. In: Complex networks and their application VI, Lyon, France. 2017. p. 78–89.
Arthur D, Vassilvitskii S. k-means++: the advantages of careful seeding. In: 18th annual ACM-SIAM symposium on discrete algorithms. 2007. p. 1027–35.
Gutman J, Xiao W. Generalized inverse of the Laplacian matrix and some applications. Bull Acad Serbe Sci Arts. 2004;129(29):15–23.
Molitierno JJ. Aplications of combinatorial matrix theory to Laplacian matrices of graphs. Boca Raton: Chapman and Hall–CRC; 2012.
Cetinay H, Kuipers FA, Mieghem PV. A topological investigation of power flow. IEEE Syst J. 2018;12(3):2524–32.
Brin S, Page L. The anatomy of a large-scale hypertextual web search engine. In: Seventh international world-wide web conference (WWW 1998). 1998.
Newman MEJ. Networks: an introduction. Oxford: Oxford Univ. Press; 2010.
Merton R. Social theory and social structure. New York: Simon and Schuster; 1968.
Lorrain F, White H. Structural equivalence of individuals in social networks. J Math Soc. 1971;1(1):49–80.
Rossi RA, Ahmed NK. Role discovery in networks. IEEE Trans Knowl Data Eng. 2015;27(4):1112–31.
Faber V. Clustering and the continuous k-means algorithm. Los Alamos Sci. 1994;22:138–44.
Lloyd SP. Least squares quantization in PCM. IEEE Trans Inf Theory. 1982;28:129–37.
Preparata FP, Shamos MI. Computational geometry: an introduction. Berlin: Springer; 1990.
Sicotte XB. k-means vs k-means++. Cross validated. https://stats.stackexchange.com/q/357606.
Tibshirani R, Walther G, Hastie T. Estimating the number of clusters in a data set via the gap statistic. J R Stat Soc B. 2001;63(2):411–23.
Milligan GW, Cooper MC. An examination of procedures for determining the number of clusters in a data set. Psychometrika. 1985;50:159–79.
Gordon A. Classification. London: Chapman and Hall–CRC; 1999.
Kaufman L, Rousseeuw PJ. Finding groups in data: an introduction to cluster analysis. New York: Wiley; 1990.
Rousseeuw PJ. Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. J Comput Appl Math. 1987;20(1):53–65.
Athay T, Podmore R, Virmani S. A practical method for the direct analysis of transient stability. IEEE Trans Power App Syst. 1979;2:573–84.
Pai MA. Energy function analysis for power system stability. Boston: Kluwer Academic Publishers; 1989.
300 bus Power Flow Test Case Dataset. http://www2.ee.washington.edu/research/pstca/pf300/pg_tca300bus.html.
Thulasiraman K, Yadav M. Weighted kirchhoff index of a resistance network and generalization of foster’s theorem. In: IEEE International symposium on circuits and systems, Baltimore, USA. 2017. p. 1027–35.
Thulasiraman K, Yadav M. Network science meets circuit theory: resistance distance, Kirchhoff index and foster’s theorems with generalizations and unifications. IEEE Trans Circuits Syst. 2017;66:1027–35.
Yadav M, Thulasiraman K. Network science meets circuit theory: Kirchhoff index of a graph and the power of node-to-datum resistance matrix. In: 2015 IEEE international symposium on circuits and systems (ISCAS). 2015. p. 854–7.