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.

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.

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 acyclic 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 proposed 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.

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.

PACKINGS OF THE COMPLETE DIRECTED GRAPH WITH m-CIRCUITS

A packing of the complete directed symmetric graph DK v with m circuits, denoted by ( v,m) DCP, is defined to be a family of arc disjoint m circuits of DK v such that any one arc of DK v \ occurs in at most one m circuit. The packing number P(v,m) is the maximum number of m circuits in such a packing. The packing problem is to determine the value P(v,m) for every integer v≥m. In this paper, the problem is reduced to the case m+6≤v≤2m- 4m-3+12 , for any fixed even integer m≥4 . In particular, the values of P(v,m) are completely determined for m=12 , 14 and 16.

On (t, r) Broadcast Domination of Directed Graphs

A dominating set of a graph G is a set of vertices that contains at least one endpoint of every edge on the graph. The domination number of G is the order of a minimum dominating set of G. The (t, r) broadcast domination is a generalization of domination in which a set of broadcasting vertices emits signals of strength t that decrease by 1 as they traverse each edge, and we require that every vertex in the graph receives a cumulative signal of at least r from its set of broadcasting neighbors. In this paper, we extend the study of (t, r) broadcast domination to directed graphs. Our main result explores the interval of values obtained by considering the directed (t, r) broadcast domination numbers of all orientations of a graph G. In particular, we prove that in the cases r = 1 and (t, r) = (2, 2), for every integer value in this interval, there exists an orientation of G which has directed (t, r) broadcast domination number equal to that value. We also investigate directed (t, r) broadcast domination on the finite grid graph, the star graph, the infinite grid graph, and the infinite triangular lattice graph. We conclude with some directions for future study.

A new Algorithm for the Solution of under Constraint Graph in Sketch Drawing

A new algorithm for the solution of under constraint graph in sketch drawing is put forward. The directed process of constraint graph is completed by picking concealed constraints of adjacent entities in sketch of few or no dimensions. In this paper, the priority of concealed constraint is given by the different constraint types and constructing orders, and some more priority concealed constraints are forced into obvious ones by the need number of constraint for every node in constraint solution process.

A DIRECTED GRAPH ALGORITHM OF VARIATIONAL GEOMETRY BASED ON GEOMETRIC REASONING

The undirected graph to express engineering drawings is discussed .The principle to re-solve and reason the undirected graph is presented, and the algorithm finally transforms theundirected graph into the resolvable directed graph. Therefore,a rapid and simple way is suppliedfor variational design. A prototype of this algorithm has been implemented, and some examplesare given.

Robust Consensus Tracking Control of Uncertain Multi-Agent Systems With Local Disturbance Rejection

In this paper,a new distributed consensus tracking protocol incorporating local disturbance rejection is devised for a multi-agent system with heterogeneous dynamic uncertainties and disturbances over a directed graph.It is of two-degree-of-freedom nature.Specifically,a robust distributed controller is designed for consensus tracking,while a local disturbance estimator is designed for each agent without requiring the input channel information of disturbances.The condition for asymptotic disturbance rejection is derived.Moreover,even when the disturbance model is not exactly known,the developed method also provides good disturbance-rejection performance.Then,a robust stabilization condition with less conservativeness is derived for the whole multi-agent system.Further,a design algorithm is given.Finally,comparisons with the conventional one-degree-of-freedombased distributed disturbance-rejection method for mismatched disturbances and the distributed extended-state observer for matched disturbances validate the developed method.

Distributed Adaptive Resource Allocation:An Uncertain Saddle-Point Dynamics Viewpoint

This paper addresses distributed adaptive optimal resource allocation problems over weight-balanced digraphs.By leveraging state-of-the-art adaptive coupling designs for multiagent systems,two adaptive algorithms are proposed,namely a directed-spanning-tree-based algorithm and a node-based algorithm.The benefits of these algorithms are that they require neither sufficiently small or unitary step sizes,nor global knowledge of Laplacian eigenvalues,which are widely required in the literature.It is shown that both algorithms belong to a class of uncertain saddle-point dynamics,which can be tackled by repeatedly adopting the Peter-Paul inequality in the framework of Lyapunov theory.Thanks to this new viewpoint,global asymptotic convergence of both algorithms can be proven in a unified way.The effectiveness of the proposed algorithms is validated through numerical simulations and case studies in IEEE 30-bus and 118-bus power systems.

Containment-Based Multiple PCC Voltage Regulation Strategy for Communication Link and Sensor Faults

The distributed AC microgrid(MG) voltage restoration problem has been extensively studied. Still, many existing secondary voltage control strategies neglect the co-regulation of the voltage at the point of common coupling(PCC) in the AC multi-MG system(MMS). When an MMS consists of sub-MGs connected in series, power flow between the sub-MGs is not possible if the PCC voltage regulation relies on traditional consensus control objectives. In addition, communication faults and sensor faults are inevitable in the MMS. Therefore, a resilient voltage regulation strategy based on containment control is proposed.First, the feedback linearization technique allows us to deal with the nonlinear distributed generation(DG) dynamics, where the PCC regulation problem of an AC MG is transformed into an output feedback tracking problem for a linear multi-agent system(MAS) containing nonlinear dynamics. This process is an indispensable pre-processing in control algorithm design. Moreover, considering the unavailability of full-state measurements and the potential faults present in the sensors, a novel follower observer is designed to handle communication faults. Based on this, a controller based on containment control is designed to achieve voltage regulation. In regulating multiple PCC voltages to a reasonable upper and lower limit, a voltage difference exists between sub-MGs to achieve power flow. In addition, the secondary control algorithm avoids using global information of directed communication network and fault boundaries for communication link and sensor faults. Finally, the simulation results verify the performance of the proposed strategy.