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.

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.

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.

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.

Cooperative Output Regulation of Heterogeneous Systems over Directed Graphs:A Dynamic Adaptive Event-Triggered Strategy

This paper investigates the cooperative output regulation problem of heterogeneous linear multi-agent systems over directed graphs with the constraint of communication bandwidth.Given that there exists an exosystem whose state information is not available to all agents,the authors develop distributed adaptive event-triggered observers for the followers based on relative information between neighboring agents.It should be pointed out that,two kinds of time-varying gains are introduced to avoid relying on any global information associated with the network,and dynamic triggering conditions are designed to get rid of continuous communications.On the basis of the designed observers,the authors devise a local controller for each agent.Compared with the existing related works,the main contribution of the current paper is that the cooperative output regulation problem for general directed graphs is solved requiring neither global information nor continuous communications.

A new multi-level algorithm for balanced partition problem on large scale directed graphs

Graph partition is a classical combinatorial optimization and graph theory problem,and it has a lot of applications,such as scientific computing,VLSI design and clustering etc.In this paper,we study the partition problem on large scale directed graphs under a new objective function,a new instance of graph partition problem.We firstly propose the modeling of this problem,then design an algorithm based on multi-level strategy and recursive partition method,and finally do a lot of simulation experiments.The experimental results verify the stability of our algorithm and show that our algorithm has the same good performance as METIS.In addition,our algorithm is better than METIS on unbalanced ratio.

The Cycle Structure for Directed Graphs on Surfaces

In this paper, the cycle structures for directed graphs on surfaces are studied. If G is a strongly connected graph, C is a ∏-contractible directed cycle of G, then both of Int（C,∏） and Ext（C,∏） are strongly connected graph; the dimension of cycles space of G is identified. If G is a strongly connected graph, then the structure of MCB in G is unique. Let G be a strongly connected graph, if G has been embedded in orientable surface Sg with fw（G） ≥ 2（fw（G） is the face-width of G）, then any cycle base of G must contain at least 2g noncontractible directed cycles; if G has been embedded in non-orientable surface Ng, then any cycle base of G must contain at least g noncontractible directed cycles.

Continuous-time Distributed Heavy-ball Algorithm for Distributed Convex Optimization over Undirected and Directed Graphs

This paper proposes second-order distributed algorithms over multi-agent networks to solve the convex optimization problem by utilizing the gradient tracking strategy, with convergence acceleration being achieved. Both the undirected and unbalanced directed graphs are considered, extending existing algorithms that primarily focus on undirected or balanced directed graphs. Our algorithms also have the advantage of abandoning the diminishing step-size strategy so that slow convergence can be avoided. Furthermore, the exact convergence to the optimal solution can be realized even under the constant step size adopted in this paper. Finally, two numerical examples are presented to show the convergence performance of our algorithms.

A bound on judicious bipartitions of directed graphs

Judicious partitioning problems on graphs ask for partitions that bound several quantities simultaneously,which have received much attention lately.Scott(2005)asked the following natural question:What is the maximum constant cdsuch that every directed graph D with m arcs and minimum outdegree d admits a bipartition V(D)=V_1∪V_2 satisfying min{e(V_1,V_2),e(V_2,V_1)}cdm?Here,for i=1,2,e(V_i,V_(3-i))denotes the number of arcs in D from V_i to V_(3-i).Lee et al.(2016)conjectured that every directed graph D with m arcs and minimum outdegree at least d 2 admits a bipartition V(D)=V_1∪V_2 such that min{e(V_1,V_2),e(V_2,V_1)}≥((d-1)/(2(2 d-1))+o(1))m.In this paper,we show that this conjecture holds under the additional natural condition that the minimum indegree is also at least d.

The Game of Cops and Robbers on Directed Graphs with Forbidden Subgraphs

The traditional game of cops and robbers is played on undirected graph. Recently, the same game played on directed graph is getting attention by more and more people. We knew that if we forbid some subgraph we can bound the cop number of the corresponding class of graphs. In this paper, we analyze the game of cops and robbers on H^(-)-free digraphs. However, it is not the same as the case of undirected graph. So we give a new concept(H^(-)^(*)-free digraph) to get a similar conclusion about the case of undirected graph.

From undirected graphs to directed graphs:a new technique makes it possible for multi-agent systems

This communique introduces a simple technique,which enables the Laplacian-like matrix of a directed graph to be diagonalisable.Thus many results on multi-agent systems over undirected graphs can be extended to directed graphs.As an example,we show how to make this extension of a popular Automatica paper.

Nash equilibrium seeking over directed graphs

In this paper,we aim to develop distributed continuous-time algorithms over directed graphs to seek the Nash equilibrium in a noncooperative game.Motivated by the recent consensus-based designs,we present a distributed algorithm with a proportional gain for weight-balanced directed graphs.By further embedding a distributed estimator of the left eigenvector associated with zero eigenvalue of the graph Laplacian,we extend it to the case with arbitrary strongly connected directed graphs having possible unbalanced weights.In both cases,the Nash equilibrium is proven to be exactly reached with an exponential convergence rate.An example is given to illustrate the validity of the theoretical results.

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.

Fixed-Time Output Consensus Tracking for High-Order Multi-Agent Systems With Directed Network Topology and Packet Dropout

This paper studies the problem of fixed-time output consensus tracking for high-order multi-agent systems(MASs)with directed network topology with consideration of data packet dropout.First,a predictive compensation based distributed observer is presented to compensate for packet dropout and estimate the leader’s states.Next,stability analysis is conducted to prove fixed time convergence of the developed distributed observer.Then,adaptive fixed-time dynamic surface control is designed to counteract mismatched disturbances introduced by observation error,and stabilize the tracking error system within a fixed time,which overcomes explosion of complexity problem and singularity problem.Finally,simulation results are provided to verify the effectiveness and superiority of the consensus tracking strategy proposed.The contribution of this paper is to provide a fixed-time distributed observer design method for high-order MAS under directed graph subject to packet dropout,and a novel fixed-time control strategy which can handle mismatched disturbances and overcome explosion of complexity and singularity problem.

Global behavior of dynamical agents in directed network

This paper investigates the global behavior of controlled dynamical agents in directed networks. The agents are Lyapunov stable, are distributed in a line, and communicate through a directed network. The communication topology of the network is characterized by a directed graph and the control protocol is designed in simple linear decentralized feedback law. We study the different conditions under which agents will achieve aggregation, and critical and divergent trajectories, respectively. Our investigation on the dynamical agent system under network is extended to the time-delay network case. Furthermore, we study the case with two pre-specified virtual leaders in the system. Numerical simulations are given and demonstrate that our theoretical results are effective.

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.

Feedback arcs and node hierarchy in directed networks

Directed networks such as gene regulation networks and neural networks are connected by arcs（directed links）. The nodes in a directed network are often strongly interwound by a huge number of directed cycles, which leads to complex information-processing dynamics in the network and makes it highly challenging to infer the intrinsic direction of information flow. In this theoretical paper, based on the principle of minimum-feedback, we explore the node hierarchy of directed networks and distinguish feedforward and feedback arcs. Nearly optimal node hierarchy solutions, which minimize the number of feedback arcs from lower-level nodes to higher-level nodes, are constructed by belief-propagation and simulated-annealing methods. For real-world networks, we quantify the extent of feedback scarcity by comparison with the ensemble of direction-randomized networks and identify the most important feedback arcs. Our methods are also useful for visualizing directed networks.

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.