On an Invariant of Tournament Digraphs

To date, it is unknown whether it is possible to construct a complete graph invariant in polynomial time, so fast algorithms for checking non-isomorphism are important, including heuristic algorithms, and for successful implementations of such heuristics, both the tasks of some modification of previously described graph invariants and the description of new invariants remain relevant. Many of the described invariants make it possible to distinguish a larger number of graphs in the real time of a computer program. In this paper, we propose an invariant for a special kind of directed graphs, namely, for tournaments. The last ones, from our point of view, are interesting because when fixing the order of vertices, the number of different tournaments is exactly equal to the number of undirected graphs, also with fixing the order of vertices. In the invariant we are considering, all possible tournaments consisting of a subset of vertices of a given digraph with the same set of arcs are iterated over. For such subset tournaments, the places are calculated in the usual way, which are summed up to obtain the final values of the points of the vertices;these points form the proposed invariant. As we expected, calculations of the new invariant showed that it does not coincide with the most natural invariant for tournaments, in which the number of points is calculated for each participant. So far, we have conducted a small number of computational experiments, and the minimum value of the pair correlation between the sequences representing these two invariants that we found is for dimension 15.

Directed Acyclic Graph Blockchain for Secure Spectrum Sharing and Energy Trading in Power IoT

Peer-to-peer(P2P)spectrum sharing and energy trading are promising solutions to locally satisfy spectrum and energy demands in power Internet of Things(IoT).However,implementation of largescale P2P spectrum sharing and energy trading confronts security and privacy challenges.In this paper,we exploit consortium blockchain and Directed Acyclic Graph(DAG)to propose a new secure and distributed spectrum sharing and energy trading framework in power IoT,named spectrum-energy chain,where a set of local aggregators(LAGs)cooperatively confirm the identity of the power devices by utilizing consortium blockchain,so as to form a main chain.Then,the local power devices verify spectrum and energy micro-transactions simultaneously but asynchronously to form local spectrum tangle and local energy tangle,respectively.Moreover,an iterative double auction based micro transactions scheme is designed to solve the spectrum and energy pricing and the amount of shared spectrum and energy among power devices.Security analysis and numerical results illustrate that the developed spectrum-energy chain and the designed iterative double auction based microtransactions scheme are secure and efficient for spectrum sharing and energy trading in power IoT.

A Secure Microgrid Data Storage Strategy with Directed Acyclic Graph Consensus Mechanism

The wide application of intelligent terminals in microgrids has fueled the surge of data amount in recent years.In real-world scenarios,microgrids must store large amounts of data efficiently while also being able to withstand malicious cyberattacks.To meet the high hardware resource requirements,address the vulnerability to network attacks and poor reliability in the tradi-tional centralized data storage schemes,this paper proposes a secure storage management method for microgrid data that considers node trust and directed acyclic graph(DAG)consensus mechanism.Firstly,the microgrid data storage model is designed based on the edge computing technology.The blockchain,deployed on the edge computing server and combined with cloud storage,ensures reliable data storage in the microgrid.Secondly,a blockchain consen-sus algorithm based on directed acyclic graph data structure is then proposed to effectively improve the data storage timeliness and avoid disadvantages in traditional blockchain topology such as long chain construction time and low consensus efficiency.Finally,considering the tolerance differences among the candidate chain-building nodes to network attacks,a hash value update mechanism of blockchain header with node trust identification to ensure data storage security is proposed.Experimental results from the microgrid data storage platform show that the proposed method can achieve a private key update time of less than 5 milliseconds.When the number of blockchain nodes is less than 25,the blockchain construction takes no more than 80 mins,and the data throughput is close to 300 kbps.Compared with the traditional chain-topology-based consensus methods that do not consider node trust,the proposed method has higher efficiency in data storage and better resistance to network attacks.

RESEARCH ON SEARCH AND RECOGNI-TION FOR CONSTRAINT BASED ON COMPREHENSION OF GRAPH

A promising approach on the search for geometric constraint of directionalgraph in off-line parametric design has been put forward. The method for representation of thedirectional graph is given firstly, then the constraint model for every geometry element is putforward. By the search of geometric constraint, it sets up the topology constraint relation on thedifferent element objects, which are not related in geometry data base, and achieves the identifyfor the directional graph. The algorithm of recognizing geometric constraint is described in detail,in the meantime, the application example in off-line parametric design on dimension-driven isgiven.

Energy Economic Dispatch for Photovoltaic-Storage via Distributed Event-Triggered Surplus Algorithm

This paper presents a novel approach to economic dispatch in smart grids equipped with diverse energy devices.This method integrates features including photovoltaic(PV)systems,energy storage coupling,varied energy roles,and energy supply and demand dynamics.The systemmodel is developed by considering energy devices as versatile units capable of fulfilling various functionalities and playing multiple roles simultaneously.To strike a balance between optimality and feasibility,renewable energy resources are modeled with considerations for forecasting errors,Gaussian distribution,and penalty factors.Furthermore,this study introduces a distributed event-triggered surplus algorithm designed to address the economic dispatch problem by minimizing production costs.Rooted in surplus theory and finite time projection,the algorithm effectively rectifies network imbalances caused by directed graphs and addresses local inequality constraints.The algorithm greatly reduces the communication burden through event triggering mechanism.Finally,both theoretical proofs and numerical simulations verify the convergence and event-triggered nature of the algorithm.

The Path-Positive Property on the Products of Graphs

The products of graphs discussed in this paper are the following four kinds: the Cartesian product of graphs, the tensor product of graphs, the lexicographic product of graphs and the strong direct product of graphs. It is proved that:① If the graphs G 1 and G 2 are the connected graphs, then the Cartesian product, the lexicographic product and the strong direct product in the products of graphs, are the path positive graphs. ② If the tensor product is a path positive graph if and only if the graph G 1 and G 2 are the connected graphs, and the graph G 1 or G 2 has an odd cycle and max{ λ 1μ 1,λ nμ m}≥2 in which λ 1 and λ n [ or μ 1 and μ m] are maximum and minimum characteristic values of graph G 1 [ or G 2 ], respectively.

Circular L(j,k)-labeling numbers of trees and products of graphs

Let j, k and m be three positive integers, a circular m-L（j, k）-labeling of a graph G is a mapping f： V（G）→{0, 1, …, m-1}such that f（u）-f（v）m≥j if u and v are adjacent, and f（u）-f（v）m≥k if u and v are at distance two,where a-bm=min{a-b,m-a-b}. The minimum m such that there exists a circular m-L（j, k）-labeling of G is called the circular L（j, k）-labeling number of G and is denoted by σj, k（G）. For any two positive integers j and k with j≤k,the circular L（j, k）-labeling numbers of trees, the Cartesian product and the direct product of two complete graphs are determined.

Signed Directed Graph and Qualitative Trend Analysis Based Fault Diagnosis in Chemical Industry

In the past 30 years,signed directed graph(SDG) ,one of the qualitative simulation technologies,has been widely applied for chemical fault diagnosis.However,SDG based fault diagnosis,as any other qualitative method,has poor diagnostic resolution.In this paper,a new method that combines SDG with qualitative trend analysis(QTA) is presented to improve the resolution.In the method,a bidirectional inference algorithm based on assumption and verification is used to find all the possible fault causes and their corresponding consistent paths in the SDG model.Then an improved QTA algorithm is used to extract and analyze the trends of nodes on the consis-tent paths found in the previous step.New consistency rules based on qualitative trends are used to find the real causes from the candidate causes.The resolution can be improved.This method combines the completeness feature of SDG with the good diagnostic resolution feature of QTA.The implementation of SDG-QTA based fault diagno-sis is done using the integrated SDG modeling,inference and post-processing software platform.Its application is illustrated on an atmospheric distillation tower unit of a simulation platform.The result shows its good applicability and efficiency.

Sensor Configuration and Test for Fault Diagnoses of Subway Braking System Based on Signed Digraph Method

Fault diagnosis of various systems on rolling stock has drawn the attention of many researchers. However, obtaining an optimized sensor set of these systems, which is a prerequisite for fault diagnosis, remains a major challenge. Available literature suggests that the configuration of sensors in these systems is presently dependent on the knowledge and engineering experiences of designers, which may lead to insufficient or redundant development of various sensors. In this paper, the optimization of sensor sets is addressed by using the signed digraph （SDG） method. The method is modified for use in braking systems by the introduction of an effect-function method to replace the traditional quantitative methods. Two criteria are adopted to evaluate the capability of the sensor sets, namely, observability and resolution. The sensors configuration method of braking system is proposed. It consists of generating bipartite graphs from SDG models and then solving the set cover problem using a greedy algorithm. To demonstrate the improvement, the sensor configuration of the HP2008 braking system is investigated and fault diagnosis on a test bench is performed. The test results show that SDG algorithm can improve single-fault resolution from 6 faults to 10 faults, and with additional four brake cylinder pressure （BCP） sensors it can cover up to 67 double faults which were not considered by traditional fault diagnosis system. SDG methods are suitable for reducing redundant sensors and that the sensor sets thereby obtained are capable of detecting typical faults, such as the failure of a release valve. This study investigates the formal extension of the SDG method to the sensor configuration of braking system, as well as the adaptation supported by the effect-function method.

Qualitative Algebra and Graph Theory Methods for Dynamic Trend Analysis of Continuous System

Qualitative algebraic equations are the basis of qualitative simulation,which are used to express the dynamic behavior of steady-state continuous processes.When the values and operation of qualitative variables are redefined,qualitative algebraic equations can be transformed into signed direct graphs,which are frequently used to predict the trend of dynamic changes.However,it is difficult to use traditional qualitative algebra methods based on artificial trial and error to solve a complex problem for dynamic trends.An important aspect of modern qualitative algebra is to model and characterize complex systems with the corresponding computer-aided automatic reasoning.In this study,a qualitative affection equation based on multiple conditions is proposed,which enables the signed di-rect graphs to describe complex systems better and improves the fault diagnosis resolution.The application to an industrial case shows that the method performs well.

Applications of Graph Theory to Gross Error Detection for GPS Geodetic Control Networks

This paper describes a broad perspective of the application of graph theory to establishment of GPS control networks whereby the GPS network is considered as a connected and directed graph with three components.In this algorithm the gross error detection is undertaken through loops of different spanning trees using the "Loop Law" in which the individual components Δ X, Δ Y and Δ Z sum up to zero.If the sum of the respective vector components ∑X,∑Y and ∑Z in a loop is not zero and if the error is beyond the tolerable limit (ε>w),it indicates the existence of gross errors in one of the baselines in the loop and therefore the baseline must be removed or re_observed.After successful screening of errors by graph theory,network adjustment can be carried out.In this paper,the GPS data from the control network established as reference system for the HP Dam at Baishan county in Liaoning province is presented to illustrate the algorithm.

Drawing Weighted Directed Graph from It's Adjacency Matrix

This paper proposes an algorithm for building weighted directed graph, defmes the weighted directed relationship matrix of the graph, and describes algorithm implementation using this matrix. Based on this algorithm, an effective way for building and drawing weighted directed graphs is presented, forming a foundation for visual implementation of the algorithm in the graph theory.

Multi-Class Support Vector Machine Classifier Based on Jeffries-Matusita Distance and Directed Acyclic Graph

Based on the framework of support vector machines （SVM） using one-against-one （OAO） strategy, a new multi-class kernel method based on directed aeyclie graph （DAG） and probabilistic distance is proposed to raise the multi-class classification accuracies. The topology structure of DAG is constructed by rearranging the nodes＇ sequence in the graph. DAG is equivalent to guided operating SVM on a list, and the classification performance depends on the nodes＇ sequence in the graph. Jeffries-Matusita distance （JMD） is introduced to estimate the separability of each class, and the implementation list is initialized with all classes organized according to certain sequence in the list. To testify the effectiveness of the proposed method, numerical analysis is conducted on UCI data and hyperspectral data. Meanwhile, comparative studies using standard OAO and DAG classification methods are also conducted and the results illustrate better performance and higher accuracy of the orooosed JMD-DAG method.

Colouring of COVID-19 Affected Region Based on Fuzzy Directed Graphs

Graph colouring is the system of assigning a colour to each vertex of a graph.It is done in such a way that adjacent vertices do not have equal colour.It is fundamental in graph theory.It is often used to solve real-world problems like traffic light signalling,map colouring,scheduling,etc.Nowadays,social networks are prevalent systems in our life.Here,the users are considered as vertices,and their connections/interactions are taken as edges.Some users follow other popular users’profiles in these networks,and some don’t,but those non-followers are connected directly to the popular profiles.That means,along with traditional relationship(information flowing),there is another relation among them.It depends on the domination of the relationship between the nodes.This type of situation can be modelled as a directed fuzzy graph.In the colouring of fuzzy graph theory,edge membership plays a vital role.Edge membership is a representation of flowing information between end nodes of the edge.Apart from the communication relationship,there may be some other factors like domination in relation.This influence of power is captured here.In this article,the colouring of directed fuzzy graphs is defined based on the influence of relationship.Along with this,the chromatic number and strong chromatic number are provided,and related properties are investigated.An application regarding COVID-19 infection is presented using the colouring of directed fuzzy graphs.

Calculate Joint Probability Distribution of Steady Directed Cyclic Graph with Local Data and Domain Casual Knowledge

It is desired to obtain the joint probability distribution(JPD) over a set of random variables with local data, so as to avoid the hard work to collect statistical data in the scale of all variables. A lot of work has been done when all variables are in a known directed acyclic graph(DAG). However, steady directed cyclic graphs(DCGs) may be involved when we simply combine modules containing local data together, where a module is composed of a child variable and its parent variables. So far, the physical and statistical meaning of steady DCGs remain unclear and unsolved. This paper illustrates the physical and statistical meaning of steady DCGs, and presents a method to calculate the JPD with local data, given that all variables are in a known single-valued Dynamic Uncertain Causality Graph(S-DUCG), and thus defines a new Bayesian Network with steady DCGs. The so-called single-valued means that only the causes of the true state of a variable are specified, while the false state is the complement of the true state.

Distributed Cooperative Learning for Discrete-Time Strict-Feedback Multi Agent Systems Over Directed Graphs

This paper focuses on the distributed cooperative learning(DCL)problem for a class of discrete-time strict-feedback multi-agent systems under directed graphs.Compared with the previous DCL works based on undirected graphs,two main challenges lie in that the Laplacian matrix of directed graphs is nonsymmetric,and the derived weight error systems exist n-step delays.Two novel lemmas are developed in this paper to show the exponential convergence for two kinds of linear time-varying(LTV)systems with different phenomena including the nonsymmetric Laplacian matrix and time delays.Subsequently,an adaptive neural network(NN)control scheme is proposed by establishing a directed communication graph along with n-step delays weight updating law.Then,by using two novel lemmas on the extended exponential convergence of LTV systems,estimated NN weights of all agents are verified to exponentially converge to small neighbourhoods of their common optimal values if directed communication graphs are strongly connected and balanced.The stored NN weights are reused to structure learning controllers for the improved control performance of similar control tasks by the“mod”function and proper time series.A simulation comparison is shown to demonstrate the validity of the proposed DCL method.

A Fuzzy Directed Graph-Based QoS Model for Service Composition

Web service composition lets developers create applications on top of service-oriented computing and its native description, discovery, and communication capabilities. This paper mainly focuses on the QoS when the concrete composition structure is unknown. A QoS model of service composition is presented based on the fuzzy directed graph theory. According to the model, a recursive algorithm is also described for calculating such kind of QoS. And, the feasibility of this QoS model and the recursive algorithm is verified by a case study. The proposed approach enables customers to get a possible value of the QoS before they achieve the service.

An Improved Iterative Reconstruction Algorithm for Traveltime Tomography

Traveltime tomography is a technique to reconstruct acoustic, seismic, or electromagnetic wave-speed distributions from first arrival traveltime data. The ray paths that should be used for tomographic techniques strongly depend on the wave-speed distribution. In this paper, a new method is proposed for finding out the ray paths from Fermat's principle, that means the traveltime of the ray path should be a minimum value. The problem of finding out the ray path is actually an optimum problem. Our new method uses the idea to find out the shortest path in a weighted directed graph to solve the problem. The ray paths found out by this method are used in the iterative reconstruction algorithm. Computer simulation result produced by this reconstruction algorithm is better than that by the conventional ones. It also shows that the new algorithm is effective with good convergency and stability.

Average Convergence for Directed&Undirected Graphs in Distributed Systems

Consensus control of multi-agent systems is an innovative paradigm for the development of intelligent distributed systems.This has fascinated numerous scientific groups for their promising applications as they have the freedom to achieve their local and global goals and make their own decisions.Network communication topologies based on graph and matrix theory are widely used in a various real-time applications ranging from software agents to robotics.Therefore,while sustaining the significance of both directed and undirected graphs,this research emphases on the demonstration of a distributed average consensus algorithm.It uses the harmonic mean in the domain of multi-agent systems with directed and undirected graphs under static topologies based on a control input scheme.The proposed agreement protocol focuses on achieving a constant consensus on directional and undirected graphs using the exchange of information between neighbors to update their status values and to be able to calculate the total number of agents that contribute to the communication network at the same time.The proposed method is implemented for the identical networks that are considered under the directional and non-directional communication links.Two different scenarios are simulated and it is concluded that the undirected approach has an advantage over directed graph communication in terms of processing time and the total number of iterations required to achieve convergence.The same network parameters are introduced for both orientations of the communication graphs.In addition,the results of the simulation and the calculation of various matrices are provided at the end to validate the effectiveness of the proposed algorithm to achieve consensus.

Sample-Efficient Deep Reinforcement Learning with Directed Associative Graph

Reinforcement learning can be modeled as markov decision process mathematically.In consequence,the interaction samples as well as the connection relation between them are two main types of information for learning.However,most of recent works on deep reinforcement learning treat samples independently either in their own episode or between episodes.In this paper,in order to utilize more sample information,we propose another learning system based on directed associative graph(DAG).The DAG is built on all trajectories in real time,which includes the whole connection relation of all samples among all episodes.Through planning with directed edges on DAG,we offer another perspective to estimate stateaction pair,especially for the unknowns to deep neural network(DNN)as well as episodic memory(EM).Mixed loss function is generated by the three learning systems(DNN,EM and DAG)to improve the efficiency of the parameter update in the proposed algorithm.We show that our algorithm is significantly better than the state-of-the-art algorithm in performance and sample efficiency on testing environments.Furthermore,the convergence of our algorithm is proved in the appendix and its long-term performance as well as the effects of DAG are verified.