Abstract
ABSTRACT
INTRODUCTION
In large scale systems, resources are distributed over a wide geographical area and it is important not only to maintain network safe performance in the face of disasters, but also to make some decisions to optimize its performance. In such circumstance, each local decision maker (which is represented by nodes in graph theory context and by agents in a multi-agent setting) requires both local and appropriate global information to make optimal decisions. Naturally, units with large mass transportation capability and/or with extra information links have leadership ability and create several clusters. In particular, communications between leaders of clusters may create a scale-free network topology.
INTRODUCTION
From social network perspective, it is important to detect the role and the relative importance of individual decision makers within networks. It helps decision makers to process, re-transmit and direct appropriate information to optimal and robust paths in the network. In fact, performance of distributed algorithms largely relies on structures that are used to share the information within the network. In distributed systems, finding optimal yet robust information sharing structures (and related protocols) is a challenging problem.
INTRODUCTION
In graph theory, the relative importance of a vertex or edge within a graph is determined using Centrality Measures. The node degree and the shortest path between nodes are the most informative values available to determine advantage of a node with respect to its neighbors. Degree, betweeness, closeness (as local measures) and eigenvector (as global or spectral measure) are the most commonly used centrality measures [3] . Eigenvector and similar centrality measures have advantages over graph-theoretic measures like degree, betweeness, and closeness; they can be used in signed and valued graphs [4] . Extension of local measure to also include these types of graphs is in progress. However, the calculation of these measures often requires global knowledge of the network properties and network topology. This problem limits the applicability of these measures to distributed systems which necessitate scalability and make extensive use of local information.
INTRODUCTION
In graph theory, the relative importance of a vertex or edge within a graph is determined using Centrality Measures. The node degree and the shortest path between nodes are the most informative values available to determine advantage of a node with respect to its neighbors. Degree, betweeness, closeness (as local measures) and eigenvector (as global or spectral measure) are the most commonly used centrality measures [3] . Eigenvector and similar centrality measures have advantages over graph-theoretic measures like degree, betweeness, and closeness; they can be used in signed and valued graphs [4] . Extension of local measure to also include these types of graphs is in progress. However, the calculation of these measures often requires global knowledge of the network properties and network topology. This problem limits the applicability of these measures to distributed systems which necessitate scalability and make extensive use of local information.
INTRODUCTION
Some centrality measures make implicit assumptions about the manner in which traffic flows through a network and most commonly used centrality measures are not appropriate for most of the flows we are routinely interested in [1] . In [2] , it is explained how betweeness centrality measure implicitly assumes that information spreads only along shortest paths and then propose a betweeness measure that relaxes this assumption while include contributions from essentially all paths between nodes, not just the shortest, although it still gives more weight to short paths.
INTRODUCTION
In this paper, we introduce a novel eigenvector-like centrality measure, called Cumulative Degree (CD) and Distributed Cumulative Degree (DCD) measure. The idea is simple; this measure works on degree distribution of nodes within network where considers the effect of all other reachable nodes in the network graph that are accessible through spanning tree with (or without) a weighting or directing mechanism. It can be shown that the recursive computation of this measure is possible. In large problems and for computational tractability, we show that this measure can be approximated by truncated spanning trees with desired accuracy. Further, we show that the proposed measure have several desired properties like standard measures; eigenvector and betweeness measure and so on. In particular, through several simulations and applications, we analyze its performance. To this end, we show that the proposed measure can provide good estimate of the corresponding optimal flow. We also investigate different network flow with respect to network Optimality and Robustness issues. In every transportation network, nodes in shortest paths should be strengthen to achieve optimal flow, while for robustness and fault tolerance issues other links should be taken into account. Using this measure every decision maker may exploit its estimate of power of its neighbors or routing paths. In addition, we introduce Directed Consensus (DC) algorithm which is a kind of consensus seeking algorithms in which its weight selection mechanism is performed based on Cumulative Degree measure. Through simulations we show that the proposed measure has more flexibility and scalability than eigenvector centrality measure. In particular, it works based on the well-known scoring principle that connections to high-scoring nodes contribute more to the score of the node in question than equal connections to low-scoring nodes that resemble importance and popularity.
INTRODUCTION
The remainder of the work is organized as follows; the following section presents some preliminaries as well as notational conventions from graph theory and centrality measures. In the section three, distributed centrality measures, performance analysis and related consensus algorithms are discussed. Section four is devoted to presents application of the measure to the optimization and crisis management in Gas Transmission Network. Section six concludes the paper.
PRELIMINARIES
The framework presented in this paper relies on some basic concepts in graph theory and centrality measures and consensus algorithms that are discussed in the following.
Graph Theory and Centrality Measures
In distributed systems, many problems of practical interests can be represented by graphs. A graph is an ordered pair G = (V,E) , consists of a set V of vertices or nodes and a set E (V ×V) ⊆ of edges or lines. Neighbors of node m is defined as
Graph Theory and Centrality Measures
From a graph theoretic perspective, the relative importance of a vertex or edge within a graph is determined using centrality measures. At a more substantive level, measures of centrality summarize a node's involvement in or contribution to the cohesiveness of the network [5] . Centrality measures have many applications in social networks [6] . Cook et al [7] have shown that power is not same as centrality in exchange networks. However, this example necessitates careful considerations according to related domain of interest as well as type of network flow (as cited in previous section). A formal definition of the most widely used centrality measures in network analysis are adopted from [5] [6] [8] , which include degree, betweeness, closeness and eigenvector centrality measure. Definition Let x i denote the score of the i th node and A ij be the adjacency matrix of the network. Then, the Eigenvector centrality for a node i is defined as follow 
¦ ¦
In general, the A's entries can be real numbers that represent the related connection strength, as in a signed or valued graph. Eigenvector centrality is a measure of the importance of a node in a network. It assigns relative scores to all nodes in the network based on the wellknown principle that connections to high-scoring nodes contribute more to the score of the node in question than equal connections to low-scoring nodes.
¦ ¦
In the next section, we will show that the proposed centrality measure inherits several desired properties of both node and spectral centrality measures and it is adjustable according to the selected discounting series and its parameters. 
Distributed Consensus Algorithms
Information sharing plays a crucial role in every distributed system. In recent years, with the aim of growing public communication systems, it is possible to connect every subsystem of a large scale distributed system. This framework provides prerequisites for acquiring information and applying required control actions. Yet, the key questions about effective communication structure and information distribution not answered completely, especially when switching is allowed in communication structure and agents' dynamic changes.
Distributed Consensus Algorithms
(Or may be some other nodes) and also find some simple aggregation rules like Equation (1-1) puts emphasis on average aggregation by parties over initial conditions. From different theoretical development issues of this problem, design of efficient weight factors has received more attention. The effect of weights are crucial on the aggregated value, convergence rate and robustness especially in the situations which changes on topology occurs (e.g., link failure, controlled switching or etc.). In [9] , the following rule for weight selection is proposed , it is shown that the graphs with small-world property have more faster mixing time than similar regular or random graphs, so are more optimal. In the next section, we propose a bio-inspired information sharing architecture that provides a trade-off between robustness and optimality issues for related consensus algorithm.
DISTRIBUTED CENTRALITY MEASURES
In network analysis, the power of individual units is not an individual attribute, but arises from their interactions with others. In a more abstract level and only based on the connection between units, these network-wide relations may represent different forms of powers; higher connections or closer to other units, more central unit within network. In section II, we have summarized some corresponding measures which in graph theoretic context respectively called; degree, closeness and betweeness centrality measures. There are several graph theoretic attributes like degree and path to score a specific network flow or degree importance.
DISTRIBUTED CENTRALITY MEASURES
Another important class of centrality measures can be defined based on the corresponding adjacent matrix of the underlying network using Algebraic Graph Theory [13] , which usually called spectral measures like eigenvector centrality measure. These measures reveal some unique properties of nodes in the cost of requirement of network global knowledge. This problem limits the applicability of these measures in distributed algorithms. Here, we start from the well-known node degree measure and generalize it to a broader sense.
Distributed Centrality Measures: Definitions
In this section, we propose a new class of eigenvector-like centrality measures that are computationally tractable and scalable in large-scale problems. First, let's provide some basics and notational conventions. 
¦ ¦
Where n ∈ℜ is length of the spanning tree.
Performance Analysis
This section investigates the performance of the proposed measure. We have considered two datasets Iranian Railways (Figure 2. ) and Bucky ball (Figure 3. ) and then compare the result with other standard measures; Closeness, Betweeness and Eigenvector measure. These measures have several desired attributes, and our aim is to determine how well the proposed measures behaves under different network flow or how it scores nodes based on degree distribution using Railways sparse graph and the Bucky ball graph with strong connections. Figure 3 shows that the higher order cumulative degree measures are able to represent desired properties like that of the eigenvector centrality in a distributed form while node degree measure fails in some nodes to provide effective information. In Figure 4 , comparison represents a meaningful relation between cumulative degree measure and eigenvector centrality. As shown in Figure 5 , by expanding computation of the measure to higher order layer along spanning tree, the approximation error decreases below one percent. 
Directed Consensus Algorithm
In this section, we introduce Directed Consensus algorithms that provide fastest mixing time by means of its directed and weighted information sharing mechanism. In a weighted directed consensus algorithm ( 1) ( 
APPLICATIONS
Management and optimization of Large-scale systems such as power systems, oil and gas transmission networks require efficient distributed algorithms to share information within network in an optimal and robust way. In a multi-agent setting, consensus algorithms used to share information between agents to reach a consensus and then plan independently. This information sharing scheme provides an average aggregation between multiple agents to coordinate their behavior with respect to neighbors.
APPLICATIONS
Performance optimization and crisis management in Gas transmission networks has been recognized as a challenging problem and this problem have investigated from different disciplines. In this section, we present the application of the proposed measure augmented with a consensus scheme to share information and then coordinate compressor station activities and operation of remote control valves. This problem involves minimization of supply and demand gap as well as fuel consumption, and determining fault tolerance set points for safe operation of compressor station in the face of a disaster.
Figure 7. A Part of Gas Transmission Network
In this section, our approach is based on the consensusseeking technique except to the aggregation quantities and the way information directed between agents. Figure 7 shows a part of the Iranian Gas Transmission Network with three refineries that produces natural gas, and then transmitted by pipe-lines. Six compressor stations are used to maintain required pressures and flows for seven major consumers (e.g. cities and so on). Control valves are controlled by nearest station and are used to direct the network flow. Simulink-Stateflow® is used for hybrid system modeling in which each pipe segment has three operating modes; operating, break and leak. For operating mode, transient flow in pipe ducts is represented by transfer function models (see Figure 8 ). In the same way, compressor stations may take advantage of three different modes; operation, recycling and shut-down (see Figure 9 ). Control valves are also modeled by the following modes; open, close and fail (no control). The main objectives of the control system are safety (fault-tolerant), optimization and crisis management. In the optimization case, a trade-off problem between different agents is solved based on the biased consensus algorithm. To maintain a safe and fault-tolerant operation and to recover network from major failures (like when a pipe-segment or compressor station break), directed consensus algorithm is used to provide new operating points for stations just in a few iterations.
Figure 7. A Part of Gas Transmission Network
In a typical robust optimization scenario (according to Table. 1), we would like to reach desired consumers' pressures (first column). whereas in a non-coordinated case, each station tries to achieve their desired output pressure independently just based on the pressures received at its inlets, while distributed consensus algorithm based on Distributed Cumulative Degree strategy that uses weighted and directed flow of information, optimization commands receive recursively from power and information -rich stations (i.e., leaders). This type of flows provides an implicit hierarchical organization. Some results of optimization algorithm are presented in Table 1 and Figure 11 and 12. In optimization, we assume sum of the local objectives (achieve desired pressure) provides common objective and local agents only have access to its local objective and exchange information with its neighbor based on the proposed measure in this paper. 
CONCLUSION
In this paper, a new class of distributed centrality measures is introduced. These measures can be served as routing or scheduling tools in distributed algorithms. In recent years, consensus algorithms have shown their applicability and efficiency in distributed decision and control problems. We have shown that the proposed measure can be used to provide faster and more robust consensus between agents while provides an implicit hierarchical structure that route information between agents within network. However, the convergence and performance analysis of the proposed measure require further considerations where addressed in our extended report [14] . 

{'paper_id': '15856452', 'title': 'On the relation between centrality measures and consensus algorithms', 's2_url': 'https://api.semanticscholar.org/CorpusID:15856452', 'source': 'S2ORC'}