Strategy for the Identification of Optimal Network Distribution Through Network Reconfiguration Using Graph Theory Techniques − Status and Technology Review

Konwar Pushpanjalee,Sarkar Dipu 대한전기학회 2022 Journal of Electrical Engineering & Technology Vol.17 No.6

Nowadays, power system reconfi guration has received much interest and has achieved signifi cant progress. Reconfi guration can be accomplished by modifying the status of the sectionalizing switches or tie switches. The main objective of a network reconfi guration strategy is to reduce power loss, relieve overloading and improve load end voltage profi le. This study reviews the advancement of power system reconfi guration research using graph theory including optimization-based approaches. In the context of determining the optimal radial network using graph theory-based strategies are also discussed. Network reconfi guration mechanism, which includes diff erent graph theory analysis such as Prim’s Minimal Spanning Tree, Dijkstra’s Shortest Path Algorithm, Kruskal’s Maximal Spanning Tree, Edmonds’ Maximal Spanning Tree are presented. Four diff erent code for the above graph theory techniques which already been implemented by previous researchers have been simulated and generate candidate solutions for 14 node system. The simulations demonstrate step by step procedure of the network reconfi guration mechanism. Moreover, simulation results verify that the graph theory approach can give good solution for Network reconfi guration with optimal radial network, less power loss and higher level of load voltage.

국내 정부기관 사이트에서 활용된 인포그래픽의 문제점과 개선 방안- 게슈탈트 이론을 적용한 막대그래프를 중심으로-

이현주 ( Hyun Ju Lee ),홍미희 ( Mi Hee Hong ) 한국기초조형학회 2014 기초조형학연구 Vol.15 No.5

사용자가 그래프를 볼 때 각각의 요소를 따로 보는 것이 아니라 단위로 그룹화 시켜 자연스럽게 지각적 조직화를 이루게 된다. 본고는 시지각적 측면에서 그래프가 얼마나 효율적으로 잘 활용되고 있는지를 조사 분석하고 그 결과를 바탕으로 문제점과 개선방안을 제시하는데 연구 목적이 있다. 연구 대상으로 대한민국 정부 웹사이트의 인포그래픽 콘텐츠 중 일반적으로 많이 사용되는 막대그래프를 대상으로 게슈탈트 이론의 형태를 지각하는 방법 또는 그 법칙을 막대그래프에 개별적으로 적용하여 분석하였다. 분석 결과 막대 및 그룹들 사이에 일정 거리면적이 잘 유지되고, 막대가 척도의 끝을 넘어서 확장되지 않았다. 또한, 전체 라벨이 아닌 부분을 위한 라벨은 부분의 요소와 함께 그룹화 되는 등 근접성과 연속성, 폐쇄성에서 비교적 효율적인 막대그래프의 사용이 많았다. 이와는 반대로 유사성은 막대의 음영이 일관되지 않거나 축의 라벨보다 부분을 위한 라벨이 강조되는 등 비효율적인 막대그래프의 사용이 많은 것을 알 수 있었다. 이러한 분석 결과를 토대로 개선 방안을 정리하면, 내용의 막대는 일관된 음영을 사용해야 하며, 틀의 X, Y축은 이어진 선으로 구성되어야한다. 또한, 라벨의 내용은 축보다는 막대의 부분 라벨을 사용해야 하는 점들을 게슈탈트 이론을 적용해 그래프를 지각할 수 있도록 개선한다면 사용자에게 정보를 효율적인 전달할 수 있을 것이다. When a user looks at a graph, he or she groups its elements by a unit to form a naturally perceptual organization, rather than seeing each element separately. This paper inquires into and analyzes how efficiently the graph is used in terms of visual perception and aims to suggest problems and measures for improvements based on the result. With a bar graph that is usually used among the infographic contents on the web sites of the government of the Republic of Korea, the method or rule of perceiving the form in the Gestalt theory was applied to bar graphs individually and analyzed. As a result of the analysis, a certain area of distance between the bars and the groups was well maintained, and the bars did not expand beyond the end of the scale. In addition, many bar graphs were used, which were relatively efficient in terms of proximity, continuity and closure: e.g. Labels for the parts were grouped along with the elements of the parts, rather than those for the entire area. In contrast, it was found that, in terms of similarity, many bar graphs were used inefficiently: e.g. The shading of the bars was inconsistent or labels for the parts were emphasized rather than those of the axis. To summarize the measures for improvements based on these results of the analysis, consistent shading should be used for bars of contents, and the x-axis and y-axis of the frame should be composed of continuous lines. In addition, if it is improved by applying the Gestalt theory so as to perceive the graphs regarding the fact that partial labels of bars should be used rather than those of the axis for the contents of the labels, information can efficiently be delivered to the user.

Graph Theory를 활용한 서울도시철도 Network의 특성변화 분석

김명재(Myoung-Jae Kim),정성봉(Sung-Bong Chung),이부원(Boo-Won Lee),조문석(Moon Suk Joe) 한국철도학회 2017 한국철도학회 학술발표대회논문집 Vol.2017 No.05

과거 교통네트워크 분석은 새로운 교통수단도입 및 신규노선 계획단계에서 이용자의 Mobility와 Accessibility 향상과 경제성 및 효율성 확보를 목표로 수행되었다. 이는 대다수 경제개발도상국의 대중교통 확대가 거시적인 도심성장계획을 바탕으로 이루어진 것이 아닌 직면한 문제해결에 중점을 두고 이루어졌기 때문이며, 이러한 상황은 대한민국의 수도인 서울시에도 동일하게 적용되었다. 본 논문에서는 서울시 도시철도 Network를 건설단계별로 분류하고 각 단계별 Network의 특성변화를 Centrality개념으로 분석하였다. 이러한 연구는 Graph Theory의 개념이 실제 Network특성을 표현할 수 있는가에 대한 검증의 역할을 할 수 있을 것이며, 나아가 도시철도건설계획 수립 시 Centrality 개념을 도입한 효율적인 Network구축에도 도움이 될 것으로 기대한다. In the past, Traffic Network Analysis had the purposes to enhance Mobility and Accessibility of users when made a plan for New Transportation or Line. The major reasons were to solve facing traffic problems without a macroscopic plan for enlarged cities especially in economically developing countries. And Seoul Metropolitan was similar to them. This paper classified the Seoul Metropolitan Railway by construction steps and analyzed its Network characteristic based on Centrality concept. Theses attempts will be able to make a verification about Graph Theory in application for expression of traffic Network characteristics. Furthermore, it will help to make an efficient Network when establish plan for New Metropolitan Railway based on Centrality concept.

CAS IMPLEMENTATION OF RECURSIVE STRUCTURE IN A SPANNING TREE

Song, Kee-Hong The Youngnam Mathematical Society Korea 2005 East Asian mathematical journal Vol.21 No.2

Experimentation using computer plays an important part in education and research in graph theory. The purpose of this paper is to develop the CAS techniques for the hands-on approach in graph theory specifically on the topic of constructing the spanning tree. This paper discusses the advantages of CAS as the software system for doing graph theory and introduces the software solutions integrating multimedia user interface developed by the author, which extend the functionality of the existing CAS-based graph theory software package.

De Bruijn 그래프에 의한 다중처리기 구성

박춘명,Park, Chun-Myoung 한국정보통신학회 2006 한국정보통신학회논문지 Vol.10 No.12

본 논문에서는 De Bruijn그래프에 기초한 다중처리기 구성 방법에 대해 논의하였다. 유한체 상의 수학적 성질과 그래프의 성질을 사용하여 변환연산자에 대해 논의하였으며, 이들 변환연산자를 이용하여 De Buijn그래프의 변환표를 도출하였다. 그리고, 이 변환표로부터 유한체 상의 De Bruijn 그래프를 도출하였다. 제안한 다중처리기는 유한체 상에서의 임의 소수와 양의 정수에 대해 구성할 수 있으며 고장허용컴퓨팅 시스템, 파이프라인 시스템, 병렬처리 네트워크, 스위칭 함수와 이의 회로, 차세대 디지털논리 시스템 및 컴퓨터 구조 등에 적 용할 수 있다. This paper presents a method of constructing the universal multiple processing element unit(UMPEU) by De Bruijn Graph. The second method is as following. First, we propose transformation operators in order to construct the De Bruijn UMPEU using properties of graph. Second, we construct the transformation table of De Bruijn graph using above transformation operators. Finally we construct the De Bruijn graph using transformation table. The proposed UMPEU be able to construct the De Bruijn graph for any prime number and integer value of finite fields. Also the UMPEU is applied to fault-tolerant computing system, pipeline class. parallel processing network, switching function and its circuits.

Fixation probability on clique-based graphs

Choi, Jeong-Ok,Yu, Unjong Elsevier 2018 PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIO Vol.492 No.-

<P><B>Abstract</B></P> <P>The fixation probability of a mutant in the evolutionary dynamics of Moran process is calculated by the Monte-Carlo method on a few families of clique-based graphs. It is shown that the complete suppression of fixation can be realized with the generalized clique–wheel graph in the limit of small wheel–clique ratio and infinite size. The family of clique–star is an amplifier, and clique-arms graph changes from amplifier to suppressor as the fitness of the mutant increases. We demonstrate that the overall structure of a graph can be more important to determine the fixation probability than the degree or the heat heterogeneity. The dependence of the fixation probability on the position of the first mutant is discussed.</P> <P><B>Highlights</B></P> <P> <UL> <LI> Undirected graph can have zero fixation probability in the Moran process. </LI> <LI> Clique-arms graph changes from an amplifier to suppressor with mutant fitness. </LI> <LI> The overall structure of a graph can be determining in the fixation probability. </LI> </UL> </P>

그래프 이론을 이용한 가변 기구의 형태 합성

임필혁(Peelhyuk Lim),심재경(Jaekyung Shim),권진욱(Jinwook Kwon),임득재(Deukjae Im) 한국자동차공학회 2009 한국자동차공학회 학술대회 및 전시회 Vol.2009 No.11

In this paper, the method of type synthesis about variable 2 DOF mechanisms is developed by using kinematical graph theory. The method is applied to Continuously Variable Valve Lift mechanisms used in vehicle. Most of the Variable mechanisms that are able to control a relation between input and output under operating conditions have two degree of freedom. On the average, mechanisms with 2 DOF have more links and joints than mechanisms with 1 DOF and the number of graphs that are considered increases, so a type synthesis of 2 DOF mechanisms is difficult. To overcome these difficulties, the type synthesis is operated as follows in this study. Before anything else, graphs of 1 DOF mechanisms with up to 6 links and 2 or 3 independent loops are enumerated. After, by adding links and joints or changing the lower pair to the higher pair, we enumerate graphs of 2 DOF mechanisms which have up to 7 links and 2 or 3 independent loops and satisfy the condition of mechanisms for synthesis. Using formulated graphs, we are easily able to synthesize the CVVL mechanisms which are presently on a commercial scale. Moreover, it is possible to synthesize the new variable mechanisms.

상수도관망 수원-절점 최소거리와 에너지 지표 상관성 분석

이승엽,정동휘 한국수자원학회 2018 한국수자원학회논문집 Vol.51 No.11

Connectivity between water source and demand node can be served as a critical system performance indicator of the degree of water distribution network (WDN)’ failure severity under abnormal conditions. Graph theory-based approaches have been widely applied to quantify the connectivity due to WDN’s graph-like topological feature. However, most previous studies used undirected-unweighted graph theory which is not proper to WDN. In this study, the directed-weighted graph theory was applied for WDN connectivity analyses. We also proposed novel connectivity indicators, Source-to-Node Shortest Pathway (SNSP) and SNSP-Degree (SNSP-D) which is an inverse of the SNSP value, that does not require complicate hydraulic simulation of a WDN of interest. The proposed SNSP-D index was demonstrated in total 42 networks in J City, South Korea in which Pearson Correlation Coefficient (PCC) between the proposed SNSP-D and four other system performance indicators was computed: three resilience indexes and an energy efficiency metric. It was confirmed that a system representative value of the SNSP-D has strong correlation with all resilience and energy efficiency indexes (PCC = 0.87 on average). Especially, PCC was higher than 0.93 with modified resilience index (MRI) and energy efficiency indicator. In addition, a multiple linear regression analysis was performed to identify the system hydraulic characteristic factors that affect the correlation between SNSP-D and other system performance indicators. The proposed SNSP is expected to be served as a useful surrogate measure of resilience and/or energy efficiency indexes in practice. 수원과 수용가 간 연결성은 비정상상황 시 상수도관망의 기능 유지 정도를 나타내는 시스템 특성 중 하나이다. 상수도관망은 점과 선으로 구성된 그래프로 간략화 될 수 있기 때문에, 연결성 평가를 위해 주로 그래프 이론이 적용되었다. 하지만, 대부분의 연구는 상수도관망에 적합하지 않은 무향-비가중 그래프 이론을 적용하였다. 본 연구에서는 유향-가중 그래프 이론을 상수도관망에 적용하였으며, 이를 기반으로 복잡한 수리해석 없이 상수도관망 연결성을 평가할 수 있는 지표인 SNSP (Source to Node Shortest Pathway)와 이의 역수인 SNSP-Degree (SNSP-D)를 제안하였다. 국내 J시 42개의 상수도관망을 이용하여 개발된 SNSP와 기존 상수도관망 성능평가지표 사이의 상관성 분석을 수행 및 검증하였다. 기존 상수도관망 성능평가지표는 수리해석 결과를 지표 계산에 이용하는 3개의 회복력(Resilience) 지표와 에너지 효율 지표이다. 분석 결과, SNSP의 역수인 SNSP-D의 합과 기존 상수도관망 성능지표 사이에 평균적으로 0.87 이상의 높은 피어슨 상관계수(Pearson Correlation Coefficient, PCC) 값이 도출되었다. 특히, 회복력 지표 중 하나인 Modified Resilience Index (MRI)와 에너지 효율 지표의 경우 PCC 0.93 이상의 높은 상관관계를 가지는 것으로 나타났다. 또한 다중 회귀 분석을 통해 SNSP-D와 회복력 및 에너지 효율 간의 상관성에 영향을 미치는 수리학적 변인을 확인하였다. 본 연구에서 제안한 SNSP 지표가 상수도관망의 대략적인 회복력 및 에너지 효율 수준을 알려줄 수 있는 지표로 실무에서 널리 활용될 것으로 기대된다.

Correlation analysis between energy indices and source-to-node shortest pathway of water distribution network

Lee Seungyub,Jung, Donghwi 한국수자원학회 2018 한국수자원학회논문집 Vol.51 No.11

수원과 수용가 간 연결성은 비정상상황 시 상수도관망의 기능 유지 정도를 나타내는 시스템 특성 중 하나이다. 상수도관망은 점과 선으로 구성된 그래프로 간략화 될 수 있기 때문에, 연결성 평가를 위해 주로 그래프 이론이 적용되었다. 하지만, 대부분의 연구는 상수도관망에 적합하지 않은 무 향-비가중 그래프 이론을 적용하였다. 본 연구에서는 유향-가중 그래프 이론을 상수도관망에 적용하였으며, 이를 기반으로 복잡한 수리해석 없이 상수도관망 연결성을 평가할 수 있는 지표인 SNSP (Source to Node Shortest Pathway)와 이의 역수인 SNSP-Degree (SNSP-D)를 제안하였다. 국내 J시 42개의 상수도관망을 이용하여 개발된 SNSP와 기존 상수도관망 성능평가지표 사이의 상관성 분석을 수행 및 검증하였다. 기존 상수도관 망 성능평가지표는 수리해석 결과를 지표 계산에 이용하는 3개의 회복력(Resilience) 지표와 에너지 효율 지표이다. 분석 결과, SNSP의 역수인 SNSP-D의 합과 기존 상수도관망 성능지표 사이에 평균적으로 0.87 이상의 높은 피어슨 상관계수(Pearson Correlation Coefficient, PCC) 값이 도출되었다. 특히, 회복력 지표 중 하나인 Modified Resilience Index (MRI)와 에너지 효율 지표의 경우 PCC 0.93 이상의 높은 상관관계를 가지는 것으로 나타났다. 또한 다중 회귀 분석을 통해 SNSP-D와 회복력 및 에너지 효율 간의 상관성에 영향을 미치는 수리학적 변인을 확인하였다. 본 연구에서 제안한 SNSP 지표가 상수도관망의 대략적인 회복력 및 에너지 효율 수준을 알려줄 수 있는 지표로 실무에서 널리 활용될 것으로 기대된다. Connectivity between water source and demand node can be served as a critical system performance indicator of the degree of water distribution network (WDN)’ failure severity under abnormal conditions. Graph theory-based approaches have been widely applied to quantify the connectivity due to WDN’s graph-like topological feature. However, most previous studies used undirected-unweighted graph theory which is not proper to WDN. In this study, the directed-weighted graph theory was applied for WDN connectivity analyses. We also proposed novel connectivity indicators, Source-to-Node Shortest Pathway (SNSP) and SNSP-Degree (SNSP-D) which is an inverse of the SNSP value, that does not require complicate hydraulic simulation of a WDN of interest. The proposed SNSP-D index was demonstrated in total 42 networks in J City, South Korea in which Pearson Correlation Coefficient (PCC) between the proposed SNSP-D and four other system performance indicators was computed: three resilience indexes and an energy efficiency metric. It was confirmed that a system representative value of the SNSP-D has strong correlation with all resilience and energy efficiency indexes (PCC = 0.87 on average). Especially, PCC was higher than 0.93 with modified resilience index (MRI) and energy efficiency indicator. In addition, a multiple linear regression analysis was performed to identify the system hydraulic characteristic factors that affect the correlation between SNSP-D and other system performance indicators. The proposed SNSP is expected to be served as a useful surrogate measure of resilience and/or energy efficiency indexes in practice.

VAR와 그래프이론을 이용한 시계열의 인과성 분석 : 미국 대두 가격 사례분석 The Case of U.S. Soybean Markets

박호정,윤원철 한국환경경제학회 한국자원경제학회 2003 자원·환경경제연구 Vol.12 No.4

VAR(벡터자기회귀)에서 모형의 식별가정에 관한 주된 비판은 변수의 나열순서에 따라 결과가 달라진다는 것이다. 본 논문은 Swanson and Granger (1997) 이후 시계열 분석에 활발히 적용되기 시작한 그래프이론이 이와 같은 임의식별 문제를 해결함으로써, 자원가격의 가격발현과정을 이해하는데 유용한 수단임을 보여준다. 모형이 이론적 방법론을 소개한 후, 미국 대두의 지역 베이시스를 이용한 실증추정 결과를 제시한다. The purpose of this paper is to introduce time-series causality analysis by combining time-series technique with graph theory. Vector autoregressive (VAR) models can provide reasonable interpretation only when the contemporaneous variables stand in a well-defined causal order. We show that how graph theory can be applied to search for the causal structure In VAR analysis. Using Maryland crop cash prices and CBOT futures price data, we estimate a VAR model with directed acyclic graph analysis. This expands our understanding the degree of interconnectivity between the employed time- series variables.