The bulk synchronous parallel （BSP） model is very user friendly for coding and debugging parallel graph algorithms. However, existing BSP-based distributed graphprocessing frameworks, such as Pregel, GPS and Giraph,...The bulk synchronous parallel （BSP） model is very user friendly for coding and debugging parallel graph algorithms. However, existing BSP-based distributed graphprocessing frameworks, such as Pregel, GPS and Giraph, routinely suffer from high communication costs. These high communication costs mainly stem from the fine-grained message-passing communication model. In order to address this problem, we propose a new computation model with low communication costs, called LCC-BSE We use this model to design and implement a high-performance distributed graphprocessing framework called LCC-Graph. This framework eliminates high communication costs in existing distributed graph-processing frameworks. Moreover, LCC-Graph also balances the computation workloads among all compute nodes by optimizing graph partitioning, significantly reducing the computation time for each superstep. Evaluation of LCC-Graph on a 32-node cluster, driven by real-world graph datasets, shows that it significantly outperforms existing distributed graph-processing frameworks in terms of runtime, particularly when the system is supported by a highbandwidth network. For example, LCC-Graph achieves an order of magnitude performance improvement over GPS and GraphLab.展开更多
It is challenging to model the performance of distributed graph computation.Explicit formulation cannot easily capture the diversified factors and complex interactions in the system.Statistical learning methods requir...It is challenging to model the performance of distributed graph computation.Explicit formulation cannot easily capture the diversified factors and complex interactions in the system.Statistical learning methods require a large number of training samples to generate an accurate prediction model.However,it is time-consuming to run the required graph computation tests to obtain the training samples.In this paper,we propose TransGPerf,a transfer learning based solution that can exploit prior knowledge from a source scenario and utilize a manageable amount of training data for modeling the performance of a target graph computation scenario.Experimental results show that our proposed method is capable of generating accurate models for a wide range of graph computation tasks on PowerGraph and GraphX.It outperforms transfer learning methods proposed for other applications in the literature.展开更多
The second-order random walk has recently been shown to effectively improve the accuracy in graph analysis tasks.Existing work mainly focuses on centralized second-order random walk(SOW)algorithms.SOW algorithms rely ...The second-order random walk has recently been shown to effectively improve the accuracy in graph analysis tasks.Existing work mainly focuses on centralized second-order random walk(SOW)algorithms.SOW algorithms rely on edge-to-edge transition probabilities to generate next random steps.However,it is prohibitively costly to store all the probabilities for large-scale graphs,and restricting the number of probabilities to consider can negatively impact the accuracy of graph analysis tasks.In this paper,we propose and study an alternative approach,SOOP(second-order random walks with on-demand probability computation),that avoids the space overhead by computing the edge-to-edge transition probabilities on demand during the random walk.However,the same probabilities may be computed multiple times when the same edge appears multiple times in SOW,incurring extra cost for redundant computation and communication.We propose two optimization techniques that reduce the complexity of computing edge-to-edge transition probabilities to generate next random steps,and reduce the cost of communicating out-neighbors for the probability computation,respectively.Our experiments on real-world and synthetic graphs show that SOOP achieves orders of magnitude better performance than baseline precompute solutions,and it can efficiently computes SOW algorithms on billion-scale graphs.展开更多
Because of cloud computing's high degree of polymerization calculation mode, it can't give full play to the resources of the edge device such as computing, storage, etc. Fog computing can improve the resource ...Because of cloud computing's high degree of polymerization calculation mode, it can't give full play to the resources of the edge device such as computing, storage, etc. Fog computing can improve the resource utilization efficiency of the edge device, and solve the problem about service computing of the delay-sensitive applications. This paper researches on the framework of the fog computing, and adopts Cloud Atomization Technology to turn physical nodes in different levels into virtual machine nodes. On this basis, this paper uses the graph partitioning theory to build the fog computing's load balancing algorithm based on dynamic graph partitioning. The simulation results show that the framework of the fog computing after Cloud Atomization can build the system network flexibly, and dynamic load balancing mechanism can effectively configure system resources as well as reducing the consumption of node migration brought by system changes.展开更多
With increasingly complex website structure and continuously advancing web technologies,accurate user clicks recognition from massive HTTP data,which is critical for web usage mining,becomes more difficult.In this pap...With increasingly complex website structure and continuously advancing web technologies,accurate user clicks recognition from massive HTTP data,which is critical for web usage mining,becomes more difficult.In this paper,we propose a dependency graph model to describe the relationships between web requests.Based on this model,we design and implement a heuristic parallel algorithm to distinguish user clicks with the assistance of cloud computing technology.We evaluate the proposed algorithm with real massive data.The size of the dataset collected from a mobile core network is 228.7GB.It covers more than three million users.The experiment results demonstrate that the proposed algorithm can achieve higher accuracy than previous methods.展开更多
Integrating marketing and distribution businesses is crucial for improving the coordination of equipment and the efficient management of multi-energy systems.New energy sources are continuously being connected to dist...Integrating marketing and distribution businesses is crucial for improving the coordination of equipment and the efficient management of multi-energy systems.New energy sources are continuously being connected to distribution grids;this,however,increases the complexity of the information structure of marketing and distribution businesses.The existing unified data model and the coordinated application of marketing and distribution suffer from various drawbacks.As a solution,this paper presents a data model of"one graph of marketing and distribution"and a framework for graph computing,by analyzing the current trends of business and data in the marketing and distribution fields and using graph data theory.Specifically,this work aims to determine the correlation between distribution transformers and marketing users,which is crucial for elucidating the connection between marketing and distribution.In this manner,a novel identification algorithm is proposed based on the collected data for marketing and distribution.Lastly,a forecasting application is developed based on the proposed algorithm to realize the coordinated prediction and consumption of distributed photovoltaic power generation and distribution loads.Furthermore,an operation and maintenance(O&M)knowledge graph reasoning application is developed to improve the intelligent O&M ability of marketing and distribution equipment.展开更多
With the fast development of Internet technology,more and more payments are fulfilled by mobile Apps in an electrical way which significantly saves time and efforts for payment.Such a change has benefited a large numb...With the fast development of Internet technology,more and more payments are fulfilled by mobile Apps in an electrical way which significantly saves time and efforts for payment.Such a change has benefited a large number of individual users as well as merchants,and a few major players for payment service have emerged in China.As a result,the payment service competition becomes even fierce,and various promotion activities have been launched for attracting more users by the payment service providers.In this paper,the problem focused on is fraud payment detection,which in fact has been a major concern for the providers who spend a significant amount of money to popularize their payment tools.This paper tries the graph computing-based visualization to the behavior of transactions occuring between the individual users and merchants.Specifically,a network analysisbased pipeline has been built.It consists of the following key components:transaction network building based on daily records aggregation;transaction network filtering based on edge and node removal;transaction network decomposition by community detection;detected transaction community visualization.The proposed approach is verified on the real-world dataset collected from the major player in the payment market in Asia and the qualitative results show the efficiency of the method.展开更多
With the increasing complexity of distribution network structures originating from the high penetration of renewable energy and responsive loads,fast and accurate fault location technology for distribution networks is...With the increasing complexity of distribution network structures originating from the high penetration of renewable energy and responsive loads,fast and accurate fault location technology for distribution networks is a prerequisite for rapid isolation of faults and restoration of the power supply.In this paper,a fault location method based on community graph depth-first traversal is proposed for fast location of single-phase ground faults in distribution networks.First,this paper defines the fault graph weight of the vertices in the distribution network graph model,which can be used to reflect the topology of the vertices and fault points as well as the fluctuation of the vertices’currents.Then,the vertices on the graph model are clustered by using an improved parallel louvain method(IPLM).Finally,the community formed by IPLM is used as the smallest unit for depth-first traversal to achieve fast and accurate location of the fault section.The paper develops a distribution network graph model of IEEE 33-bus system on the graph database for testing.And three other methods are selected for comparison with IPLMDF.The test results show that IPLMDF can achieve fast and accurate fault location when half of the nodes in the distribution network are equipped with D-PMUs.When some of the D-PMUs lose time synchronization,it is still possible to locate the fault section,and at the same time,the locating results can be avoided by falling into local optimal solutions.展开更多
By leveraging the 5G enabled vehicular ad hoc network(5G-VANET), it is widely recognized that connected vehicles have the potentials to improve road safety, transportation intelligence and provide in-vehicle entertain...By leveraging the 5G enabled vehicular ad hoc network(5G-VANET), it is widely recognized that connected vehicles have the potentials to improve road safety, transportation intelligence and provide in-vehicle entertainment experience. However, many enabling applications in 5G-VANET rely on the efficient content sharing among mobile vehicles, which is a very challenging issue due to the extremely large data volume, rapid topology change, and unbalanced traffic. In this paper, we investigate content prefetching and distribution in 5G-VANET. We first introduce an edge computing based hierarchical architecture for efficient distribution of large-volume vehicular data. We then propose a multi-place multi-factor prefetching scheme to meet the rapid topology change and unbalanced traffic. The content requests of vehicles can be served by neighbors, which can improve the sharing efficiency and alleviate the burden of networks. Furthermore, we use a graph theory based approach to solve the content distribution by transforming it into a maximum weighted independent set problem. Finally, the proposed scheme is evaluated with a greedy transmission strategy to demonstrate its efficiency.展开更多
The cycle structure in a power grid may lower the stability of the network;thus,it is of great significance to accu-rately and timely detect cycles in power grid networks.However,detecting possible cycles in a large-s...The cycle structure in a power grid may lower the stability of the network;thus,it is of great significance to accu-rately and timely detect cycles in power grid networks.However,detecting possible cycles in a large-scale network can be highly time consuming and computationally intensive.In addition,since the power grid's topology changes over time,cycles can appear and disappear,and it can be difficult to monitor them in real time.In traditional computing systems,cycle detection requires considerable computational resources,making real-time cycle detection in large-scale power grids an impossible task.Graph computing has shown excellent performance in many areas and has solved many practical graph-related problems,such as power flow calculation and state estimation.In this article,a cycle detection method,the Paton method,is implemented and optimized on a graph computing platform.Two cases are used to test its performance in an actual power grid topology scenario.The results show that the graph computing-based Paton method reduces the time consumption by at least 60%compared to that of other methods.展开更多
A k coloring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colors i and j the subgraph induced by the edges whose endpoints have colors i and j is acyclic. We consider...A k coloring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colors i and j the subgraph induced by the edges whose endpoints have colors i and j is acyclic. We consider some generalized acyclic k colorings, namely, we require that each color class induces an acyclic or bounded degree graph. Mainly we focus on graphs with maximum degree 5. We prove that any such graph has an acyclic 5 coloring such that each color class induces an acyclic graph with maximum degree at most 4. We prove that the problem of deciding whether a graph G has an acyclic 2 coloring in which each color class induces a graph with maximum degree at most 3 is NP complete, even for graphs with maximum degree 5. We also give a linear time algorithm for an acyclic t improper coloring of any graph with maximum degree d assuming that the number of colors is large enough.展开更多
The sequential method is easy to integrate with existing large-scale alternating current(AC)power flow solvers and is therefore a common approach for solving the power flow of AC/direct current(DC)hybrid systems.In th...The sequential method is easy to integrate with existing large-scale alternating current(AC)power flow solvers and is therefore a common approach for solving the power flow of AC/direct current(DC)hybrid systems.In this paper,a highperformance graph computing based distributed parallel implementation of the sequential method with an improved initial estimate approach for hybrid AC/DC systems is developed.The proposed approach is capable of speeding up the entire computation process without compromising the accuracy of result.First,the AC/DC network is intuitively represented by a graph and stored in a graph database(GDB)to expedite data processing.Considering the interconnection of AC grids via high-voltage direct current(HVDC)links,the network is subsequently partitioned into independent areas which are naturally fit for distributed power flow analysis.For each area,the fast-decoupled power flow(FDPF)is employed with node-based parallel computing(NPC)and hierarchical parallel computing(HPC)to quickly identify system states.Furthermore,to reduce the alternate iterations in the sequential method,a new decoupled approach is utilized to achieve a good initial estimate for the Newton-Raphson method.With the improved initial estimate,the sequential method can converge in fewer iterations.Consequently,the proposed approach allows for significant reduction in computing time and is able to meet the requirement of the real-time analysis platform for power system.The performance is verified on standard IEEE 300-bus system,extended large-scale systems,and a practical 11119-bus system in China.展开更多
This paper proposes a graph computing based mixed integer programming(MIP)framework for solving the security constrained unit commitment(SCUC)problem in hydro-thermal power systems incorporating pumped hydro storage(P...This paper proposes a graph computing based mixed integer programming(MIP)framework for solving the security constrained unit commitment(SCUC)problem in hydro-thermal power systems incorporating pumped hydro storage(PHS).The proposed graph computing-based MIP framework considers the economic operations of thermal units,cascade hydropower stations and PHS stations,as well as their technical impacts towards the network security.First,the hydro-thermal power system data and unit information are stored in a graph structure with nodes and edges,which enables nodal and hierarchical parallel computing for the unit commitment(UC)solution calculation and network security analysis.A MIP model is then formulated to solve the SCUC problem with the mathematical models of thermal units,cascade hydropower stations and PHS stations.In addition,two optimization approaches including convex hull reformulation(CHR)and special ordered set(SOS)methods are introduced for speeding up the MIP calculation procedure.To ensure the system stability under the derived UC solution,a parallelized graph power flow(PGPF)algorithm is proposed for the hydro-thermal power system network security analysis.Finally,case studies of the IEEE 118-bus system and a practical 2749-bus hydro-thermal power system are introduced to demonstrate the feasibility and validity of the proposed graph computing-based MIP framework.展开更多
Approaches to apply graph computing to power grid analysis are systematically explained using real-world application examples.Through exploring the nature of the power grid and the characteristics of power grid analys...Approaches to apply graph computing to power grid analysis are systematically explained using real-world application examples.Through exploring the nature of the power grid and the characteristics of power grid analysis,the guidelines for selecting appropriate graph computing techniques for the application to power grid analysis are outlined.A custom graph model for representing the power grid for the analysis and simulation purpose and an in-memory computing(IMC)based graph-centric approach with a shared-everything architecture are introduced.Graph algorithms,including network topology processing and subgraph processing,and graph computing application scenarios,including in-memory computing,contingency analysis,and Common Information Model(CIM)model merge,are presented.展开更多
文摘The bulk synchronous parallel （BSP） model is very user friendly for coding and debugging parallel graph algorithms. However, existing BSP-based distributed graphprocessing frameworks, such as Pregel, GPS and Giraph, routinely suffer from high communication costs. These high communication costs mainly stem from the fine-grained message-passing communication model. In order to address this problem, we propose a new computation model with low communication costs, called LCC-BSE We use this model to design and implement a high-performance distributed graphprocessing framework called LCC-Graph. This framework eliminates high communication costs in existing distributed graph-processing frameworks. Moreover, LCC-Graph also balances the computation workloads among all compute nodes by optimizing graph partitioning, significantly reducing the computation time for each superstep. Evaluation of LCC-Graph on a 32-node cluster, driven by real-world graph datasets, shows that it significantly outperforms existing distributed graph-processing frameworks in terms of runtime, particularly when the system is supported by a highbandwidth network. For example, LCC-Graph achieves an order of magnitude performance improvement over GPS and GraphLab.
文摘It is challenging to model the performance of distributed graph computation.Explicit formulation cannot easily capture the diversified factors and complex interactions in the system.Statistical learning methods require a large number of training samples to generate an accurate prediction model.However,it is time-consuming to run the required graph computation tests to obtain the training samples.In this paper,we propose TransGPerf,a transfer learning based solution that can exploit prior knowledge from a source scenario and utilize a manageable amount of training data for modeling the performance of a target graph computation scenario.Experimental results show that our proposed method is capable of generating accurate models for a wide range of graph computation tasks on PowerGraph and GraphX.It outperforms transfer learning methods proposed for other applications in the literature.
文摘The second-order random walk has recently been shown to effectively improve the accuracy in graph analysis tasks.Existing work mainly focuses on centralized second-order random walk(SOW)algorithms.SOW algorithms rely on edge-to-edge transition probabilities to generate next random steps.However,it is prohibitively costly to store all the probabilities for large-scale graphs,and restricting the number of probabilities to consider can negatively impact the accuracy of graph analysis tasks.In this paper,we propose and study an alternative approach,SOOP(second-order random walks with on-demand probability computation),that avoids the space overhead by computing the edge-to-edge transition probabilities on demand during the random walk.However,the same probabilities may be computed multiple times when the same edge appears multiple times in SOW,incurring extra cost for redundant computation and communication.We propose two optimization techniques that reduce the complexity of computing edge-to-edge transition probabilities to generate next random steps,and reduce the cost of communicating out-neighbors for the probability computation,respectively.Our experiments on real-world and synthetic graphs show that SOOP achieves orders of magnitude better performance than baseline precompute solutions,and it can efficiently computes SOW algorithms on billion-scale graphs.
基金supported in part by the National Science and technology support program of P.R.China(No.2014BAH29F05)
文摘Because of cloud computing's high degree of polymerization calculation mode, it can't give full play to the resources of the edge device such as computing, storage, etc. Fog computing can improve the resource utilization efficiency of the edge device, and solve the problem about service computing of the delay-sensitive applications. This paper researches on the framework of the fog computing, and adopts Cloud Atomization Technology to turn physical nodes in different levels into virtual machine nodes. On this basis, this paper uses the graph partitioning theory to build the fog computing's load balancing algorithm based on dynamic graph partitioning. The simulation results show that the framework of the fog computing after Cloud Atomization can build the system network flexibly, and dynamic load balancing mechanism can effectively configure system resources as well as reducing the consumption of node migration brought by system changes.
基金supported in part by the Fundamental Research Funds for the Central Universities under Grant No.2013RC0114111 Project of China under Grant No.B08004
文摘With increasingly complex website structure and continuously advancing web technologies,accurate user clicks recognition from massive HTTP data,which is critical for web usage mining,becomes more difficult.In this paper,we propose a dependency graph model to describe the relationships between web requests.Based on this model,we design and implement a heuristic parallel algorithm to distinguish user clicks with the assistance of cloud computing technology.We evaluate the proposed algorithm with real massive data.The size of the dataset collected from a mobile core network is 228.7GB.It covers more than three million users.The experiment results demonstrate that the proposed algorithm can achieve higher accuracy than previous methods.
基金This work was supported by the National Key R&D Program of China(2020YFB0905900).
文摘Integrating marketing and distribution businesses is crucial for improving the coordination of equipment and the efficient management of multi-energy systems.New energy sources are continuously being connected to distribution grids;this,however,increases the complexity of the information structure of marketing and distribution businesses.The existing unified data model and the coordinated application of marketing and distribution suffer from various drawbacks.As a solution,this paper presents a data model of"one graph of marketing and distribution"and a framework for graph computing,by analyzing the current trends of business and data in the marketing and distribution fields and using graph data theory.Specifically,this work aims to determine the correlation between distribution transformers and marketing users,which is crucial for elucidating the connection between marketing and distribution.In this manner,a novel identification algorithm is proposed based on the collected data for marketing and distribution.Lastly,a forecasting application is developed based on the proposed algorithm to realize the coordinated prediction and consumption of distributed photovoltaic power generation and distribution loads.Furthermore,an operation and maintenance(O&M)knowledge graph reasoning application is developed to improve the intelligent O&M ability of marketing and distribution equipment.
基金Supported by the National Natural Science Foundation of China(No.61972250)National Key Research and Development Program of China(No.2018AAA0100700,2016YFB1001003)the Program of Shanghai Academic/Technology Research Leader(No.19XD1433700)。
文摘With the fast development of Internet technology,more and more payments are fulfilled by mobile Apps in an electrical way which significantly saves time and efforts for payment.Such a change has benefited a large number of individual users as well as merchants,and a few major players for payment service have emerged in China.As a result,the payment service competition becomes even fierce,and various promotion activities have been launched for attracting more users by the payment service providers.In this paper,the problem focused on is fraud payment detection,which in fact has been a major concern for the providers who spend a significant amount of money to popularize their payment tools.This paper tries the graph computing-based visualization to the behavior of transactions occuring between the individual users and merchants.Specifically,a network analysisbased pipeline has been built.It consists of the following key components:transaction network building based on daily records aggregation;transaction network filtering based on edge and node removal;transaction network decomposition by community detection;detected transaction community visualization.The proposed approach is verified on the real-world dataset collected from the major player in the payment market in Asia and the qualitative results show the efficiency of the method.
基金supported by the National Natural Science Foundation of China (Grant Nos.52009106,51779206)the National Key R&D Program of China (No.2018YFB1500800)the Natural Science Fund Youth Project of Shaanxi Province (2019J-130).
文摘With the increasing complexity of distribution network structures originating from the high penetration of renewable energy and responsive loads,fast and accurate fault location technology for distribution networks is a prerequisite for rapid isolation of faults and restoration of the power supply.In this paper,a fault location method based on community graph depth-first traversal is proposed for fast location of single-phase ground faults in distribution networks.First,this paper defines the fault graph weight of the vertices in the distribution network graph model,which can be used to reflect the topology of the vertices and fault points as well as the fluctuation of the vertices’currents.Then,the vertices on the graph model are clustered by using an improved parallel louvain method(IPLM).Finally,the community formed by IPLM is used as the smallest unit for depth-first traversal to achieve fast and accurate location of the fault section.The paper develops a distribution network graph model of IEEE 33-bus system on the graph database for testing.And three other methods are selected for comparison with IPLMDF.The test results show that IPLMDF can achieve fast and accurate fault location when half of the nodes in the distribution network are equipped with D-PMUs.When some of the D-PMUs lose time synchronization,it is still possible to locate the fault section,and at the same time,the locating results can be avoided by falling into local optimal solutions.
基金the support of National Science and Technology Major Project of the Ministry of Science and Technology of China under Grant No.2016ZX03001025003the Natural Science Foundation of Beijing under Grant No.4181002+2 种基金the Natural Science Foundation of China under Grant No.91638204BUPT Excellent Ph.D. Students Foundation under Grant No.CX2018210Natural Sciences and Engineering Research Council (NSERC),Canada
文摘By leveraging the 5G enabled vehicular ad hoc network(5G-VANET), it is widely recognized that connected vehicles have the potentials to improve road safety, transportation intelligence and provide in-vehicle entertainment experience. However, many enabling applications in 5G-VANET rely on the efficient content sharing among mobile vehicles, which is a very challenging issue due to the extremely large data volume, rapid topology change, and unbalanced traffic. In this paper, we investigate content prefetching and distribution in 5G-VANET. We first introduce an edge computing based hierarchical architecture for efficient distribution of large-volume vehicular data. We then propose a multi-place multi-factor prefetching scheme to meet the rapid topology change and unbalanced traffic. The content requests of vehicles can be served by neighbors, which can improve the sharing efficiency and alleviate the burden of networks. Furthermore, we use a graph theory based approach to solve the content distribution by transforming it into a maximum weighted independent set problem. Finally, the proposed scheme is evaluated with a greedy transmission strategy to demonstrate its efficiency.
基金National Key Research and Development Program of China(2017YFE0132100)。
文摘The cycle structure in a power grid may lower the stability of the network;thus,it is of great significance to accu-rately and timely detect cycles in power grid networks.However,detecting possible cycles in a large-scale network can be highly time consuming and computationally intensive.In addition,since the power grid's topology changes over time,cycles can appear and disappear,and it can be difficult to monitor them in real time.In traditional computing systems,cycle detection requires considerable computational resources,making real-time cycle detection in large-scale power grids an impossible task.Graph computing has shown excellent performance in many areas and has solved many practical graph-related problems,such as power flow calculation and state estimation.In this article,a cycle detection method,the Paton method,is implemented and optimized on a graph computing platform.Two cases are used to test its performance in an actual power grid topology scenario.The results show that the graph computing-based Paton method reduces the time consumption by at least 60%compared to that of other methods.
基金supported by the Minister of Science and Higher Education of Poland (Grant No. JP2010009070)
文摘A k coloring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colors i and j the subgraph induced by the edges whose endpoints have colors i and j is acyclic. We consider some generalized acyclic k colorings, namely, we require that each color class induces an acyclic or bounded degree graph. Mainly we focus on graphs with maximum degree 5. We prove that any such graph has an acyclic 5 coloring such that each color class induces an acyclic graph with maximum degree at most 4. We prove that the problem of deciding whether a graph G has an acyclic 2 coloring in which each color class induces a graph with maximum degree at most 3 is NP complete, even for graphs with maximum degree 5. We also give a linear time algorithm for an acyclic t improper coloring of any graph with maximum degree d assuming that the number of colors is large enough.
基金supported by the State Grid Corporation Technology Project(No.5455HJ180022)。
文摘The sequential method is easy to integrate with existing large-scale alternating current(AC)power flow solvers and is therefore a common approach for solving the power flow of AC/direct current(DC)hybrid systems.In this paper,a highperformance graph computing based distributed parallel implementation of the sequential method with an improved initial estimate approach for hybrid AC/DC systems is developed.The proposed approach is capable of speeding up the entire computation process without compromising the accuracy of result.First,the AC/DC network is intuitively represented by a graph and stored in a graph database(GDB)to expedite data processing.Considering the interconnection of AC grids via high-voltage direct current(HVDC)links,the network is subsequently partitioned into independent areas which are naturally fit for distributed power flow analysis.For each area,the fast-decoupled power flow(FDPF)is employed with node-based parallel computing(NPC)and hierarchical parallel computing(HPC)to quickly identify system states.Furthermore,to reduce the alternate iterations in the sequential method,a new decoupled approach is utilized to achieve a good initial estimate for the Newton-Raphson method.With the improved initial estimate,the sequential method can converge in fewer iterations.Consequently,the proposed approach allows for significant reduction in computing time and is able to meet the requirement of the real-time analysis platform for power system.The performance is verified on standard IEEE 300-bus system,extended large-scale systems,and a practical 11119-bus system in China.
文摘This paper proposes a graph computing based mixed integer programming(MIP)framework for solving the security constrained unit commitment(SCUC)problem in hydro-thermal power systems incorporating pumped hydro storage(PHS).The proposed graph computing-based MIP framework considers the economic operations of thermal units,cascade hydropower stations and PHS stations,as well as their technical impacts towards the network security.First,the hydro-thermal power system data and unit information are stored in a graph structure with nodes and edges,which enables nodal and hierarchical parallel computing for the unit commitment(UC)solution calculation and network security analysis.A MIP model is then formulated to solve the SCUC problem with the mathematical models of thermal units,cascade hydropower stations and PHS stations.In addition,two optimization approaches including convex hull reformulation(CHR)and special ordered set(SOS)methods are introduced for speeding up the MIP calculation procedure.To ensure the system stability under the derived UC solution,a parallelized graph power flow(PGPF)algorithm is proposed for the hydro-thermal power system network security analysis.Finally,case studies of the IEEE 118-bus system and a practical 2749-bus hydro-thermal power system are introduced to demonstrate the feasibility and validity of the proposed graph computing-based MIP framework.
基金supported by National Natural Science Foundation of China under the Grant U1766214.
文摘Approaches to apply graph computing to power grid analysis are systematically explained using real-world application examples.Through exploring the nature of the power grid and the characteristics of power grid analysis,the guidelines for selecting appropriate graph computing techniques for the application to power grid analysis are outlined.A custom graph model for representing the power grid for the analysis and simulation purpose and an in-memory computing(IMC)based graph-centric approach with a shared-everything architecture are introduced.Graph algorithms,including network topology processing and subgraph processing,and graph computing application scenarios,including in-memory computing,contingency analysis,and Common Information Model(CIM)model merge,are presented.
