Review on Energy Resilience

Physica A 453 (2016) 84–98

Contents lists available at ScienceDirect

Physica A

journal homepage: www.elsevier.com/locate/physa

Characterizing the topological and controllability features of U.S. power transmission networks Jian Li a,b,∗, Leonardo Dueñas-Osorio b, Changkun Chen a, Benjamin Berryhill c, Alireza Yazdani d a Institute of Disaster Prevention Science and Safety Technology, Central South University, Changsha, Hunan 410075, China b Department of Civil and Environmental Engineering, Rice University, Houston, TX 77005, USA c OneSubsea, Houston, TX 77041, USA d Quantitative Risk Consultant, Boston, MA 02459, USA

h i g h l i g h t s

• This paper studies the structural controllability of 58 power transmission networks. • A small proportion of driver nodes are enough to control power networks topologically. • Intermittent nodes tend to have low degree, triangular sub-graphs and betweenness. • High degree and high betweenness nodes act infrequently as driver nodes.

a r t i c l e i n f o

Article history: Received 13 January 2015 Received in revised form 16 May 2015 Available online 8 February 2016

Keywords: Power transmission networks ensembles Structural controllability Driver nodes Redundant nodes Intermittent nodes Smart infrastructure systems

a b s t r a c t

Understanding the controllability of complex networks continues to gain traction across disciplinary fields, including the exploration of infrastructure systems such as power grids. Through topological principles, this paper investigates the controllability features of an ensemble of 58 U.S. city-level power transmission networks in seven U.S. states. To per- form structural controllability analyses, the topological characteristics of the ensemble of networks are first quantified, including degree, shortest path length, clustering co- efficient, meshedness and betweenness centrality, as well as the uncertainty associated with these and related properties. Then, the paper focuses on the controllability features of complex networks so as to detect the minimal sets of driver nodes to possibly con- trol the networks given system linearity assumptions. Accordingly, a node is critical, in- termittent or redundant if it acts as a driver node in all, some, or none of the poten- tially controllable system configurations. Moreover, this paper constructs a new method- ology to quantify the probability of being a driver node among the intermittent nodes, and reveals the controllability importance of system components. Results show that a small proportion of driver nodes can provide the conditions for controlling the slow dy- namics of entire power transmission networks from a topological perspective, despite variations in network sizes and configurations. This paper also reveals that the driver nodes tend to avoid high degree nodes and high triangulation sub-graph nodes as well as high betweenness centrality nodes. The identification of topological differences for different categories of nodes (critical, intermittent or redundant) could help researchers and utilities understand the conditions for future functional controllability of power

∗ Corresponding author at: Institute of Disaster Prevention Science and Safety Technology, Central South University, Changsha, Hunan 410075, China. E-mail address: [email protected] (J. Li).

http://dx.doi.org/10.1016/j.physa.2016.01.087 0378-4371/© 2016 Elsevier B.V. All rights reserved.

J. Li et al. / Physica A 453 (2016) 84–98 85

networks while improving their reliability and resilience as well as facilitating their tran- sition into smart grid systems.

© 2016 Elsevier B.V. All rights reserved.

1. Introduction

Network controllability is one of the central notions of modern control theory. It was through the work of R.E. Kalman that the notion of controllability of a linear system was shown to be of interest [1]. The controllability of linear system has a simple and appealing formulation in that the system is said to be controllable if it can be driven from any initial state to any desired final state within finite time with a suitable choice of inputs—note that by extension, this notion includes maintaining a system within a certain state despite disruptions. Since the early 1970s, research has also been directed towards nonlinear system controllability [2]. For nonlinear systems, the notion of controllability refers to the case where the control can act on the system state, but may be insufficient to transfer it to a specified terminal state. Often, nonlinear system controllability is defined in terms of system state equations and tested by means of Lie distributions or their dual form [3]—typically for fast dynamics systems. Although both linear and nonlinear system controllability have been well studied to date, they are only starting to be examined for networked systems; thus, understanding the effects of systems’ internal topological connectivity and directionality is critical to support future controllability studies [4].

Structural controllability1 of complex networks has garnered traction by integrating classical control theory and network science [5–11]. Lombardi and Hörnquist [12] first showed how linear controllability theory could be applied to networks. Later, Liu et al. [13] developed analytical tools to study the controllability of an arbitrary complex directed network, and identified the set of driver nodes (by finding a maximum matching of an associated bipartite graph), which can in prin- ciple guide the system’s entire linear dynamics. They found that the number of driver nodes is mainly determined by the network’s degree distribution owing to linearity assumptions. Based on Liu et al.’s method, Wang et al. [14] proposed a gen- eral approach to optimize the controllability of complex networks by perturbing the network structure, while the optimal control is referred to as the situation where such a network can be fully controlled using only one driving signal. However, Cowan et al. [15] proposed that it is nodal dynamics, not degree distributions, which determines the structural controlla- bility of complex networks. Also, according to the role that an individual node plays in controlling a network, namely, the likelihood of being included in minimum driver node sets, nodes are classified into three categories by Jia et al. [16]: critical, intermittent and redundant. Jia et al. also developed an analytical framework to identify the category of each node, finding two distinct control modes in complex networks related to centralized and distributed control.

Clearly, the research on network controllability is far from settled. Also, most of the reviewed work has dealt with ideal networks (e.g., E–R random networks [17], Scale-Free networks [18], Small World networks [19]), or combinations of different kinds of practical networks (e.g., food web networks, social communication networks). Some research involves power networks [14], which are one of the most important networked infrastructure systems. However, as an spatial networked system, power networks have to meet engineering design principles and custom demand patterns. There are many restrictions on the topology of power networks. For example, there is a cost associated with the length of edges and the location of demand centers, which in turn have tangible effects on the topological structure of these networks. As a result, the controllability features of the class of power networks may differ from other ideal or practical networks, in part due to their topological differences. Hence, a structural controllability exploration is presented in this paper, in which we determine how the topological properties of an ensemble of power systems affect their linear controllability features, including the topological differences between critical nodes, intermittent nodes and redundant nodes [16]—the topological metrics that affect the likelihood to be a driver node. Note that linear dynamics could be associated with slow dynamics, such as those related to commodity supply/demand balance, and not to fast dynamics related to network stability.

Before performing structural controllability analyses, it is necessary to quantify the topological characteristics of the power networks, as well as to reveal topological commonalities, differences and trends across different systems in the ensemble. Previous investigations provide a foundation to assess the topological features of power networks, such as Barabási and Albert [18], Albert et al. [20], Amaral et al. [21] and Newman et al. [22]; however, these studies may be insufficient to evaluate system controllability conditions as they focus on the evaluation of network topology by using only one or a small number of cases. To this end, a unique ensemble-based topological characterization of power transmission networks and controllability conditions of different sizes and topological specifications is carried out in this paper by exploring 58 city-level power transmission networks across seven U.S. states. Through detailed measurements at both local (nodes and links) and global (network) levels, this paper identifies topological properties of the ensemble of real power networks, particularly properties that possibly relate to controllability features, including the characteristics of driver nodes.

1 In engineering disciplines (particularly structural and infrastructure engineering), ‘‘topological controllability’’ would be preferable as ‘‘structural’’ typically refers to buildings and physical components of networks.

86 J. Li et al. / Physica A 453 (2016) 84–98

This paper is structured as follows: In Section 2, we present various relevant network metrics that are used to characterize the topology of power transmission network ensembles. Then, we discuss a methodology to identify the minimum number of driver nodes that can control the systems, as well as to identify the critical, intermittent and redundant node sets. In particular, we propose a method to quantify the frequency of driver nodes from those that are intermittent nodes. Then, Section 3 offers a basic introduction of the 58 U.S. power transmission networks. Then, in Section 4, this paper discusses notable trends from the quantified metrics, particularly the ones related to controllability features by computing the fraction of different categories of nodes, the chance of being a driver node among intermittent nodes, and their dependence on different factors, ranging from degree, clustering coefficient, and triangular sub-graph number to the betweenness centrality of nodes. Finally, Section 5 presents general conclusions and ideas for future work.

2. Power transmission network measurements and controllability

To describe the underlying network characteristics and controllability conditions of power networks, information on the attributes (e.g. power plants) and their patterns of connectivity (i.e. topology) are required [23]. The topology of a network is described by an abstract graph G = G(N, K) which is a collection of N nodes (vertices) connected by K edges (links). Each vertex represents a power plant or substation, while each edge denotes the transmission line connecting two vertices [24]. The graph is represented as an N × N adjacency matrix A, where A = (aij) in which the aij terms determine whether there is a link from node i to j, and i, j ∈ {1, . . . , N}.

Once the structure of a power network is available, analysts can compute a variety of topological metrics. This paper explores some of the most relevant properties that may potentially influence the controllability conditions of power transmission network topologies.

2.1. Fundamental networks metrics

The clustering coefficient measures the likelihood that two of a node’s neighbors are themselves neighbors [19,25]. The local clustering coefficient of node i is defined by

ci = 2ti

ki(ki − 1) , (1)

where ti is the number of edges among node i’s neighbors and ki is the degree of node i [26]. In power networks, the degree of a generator or substation is the number of transmission lines that connect to other generators or substations. The clustering coefficient may be viewed as a purely topological indicator of local redundancy via triangular loops in energy network infrastructures.

The shortest path length dij defines the smallest number of edges between nodes i and j. If node i and node j are connected, dij = 1, otherwise, dij > 1. Note that the investigated networks are strongly connected (which means every vertex is reachable from every other vertex) and their electrical distances are not employed as the current emphasis is on topology and not function. By finding the shortest path between any two nodes, we can calculate the betweenness centrality bi of node i, which is defined as the sum of the ratio between the number of shortest paths between two nodes passing through node i [27] over the count of shortest paths between the two nodes. It is given by

bi = 1

(N − 1)(N − 2)

N h≠j≠i

σhj(i) σhj

, (2)

where σhj is the total number of shortest paths from nodes h to j and σhj(i) is the number of those shortest paths that pass through node i. The betweenness centrality of a node is a measure of centrality of that node. Higher betweenness nodes are typically bridges and articulation points that enable a greater level connectivity or passage of flow in the network as compared to lower betweenness nodes. Losing high betweenness elements may disconnect and break the original network into multiple clusters of nodes during failures or accidents [27]. Hence, monitoring such elements is an important part of topology-based controllability analysis.

The local metrics discussed so far could be aggregated for network-level characterizations. Through averaging the above metrics, the average degree k̄, mean clustering coefficient c, average shortest path length d and average betweenness centrality b can be computed.

Other global metrics include the meshedness coefficient, which is the ratio between the total number of loops in a planar graph and the total possible number of such loops [28,29], and is defined as:

M = K − N + 1 2N − 5

. (3)

High meshedness typically implies high redundancy and the presence of alternative transmission paths in a network. These paths may increase the chances of controllability even in the presence of local failures.

J. Li et al. / Physica A 453 (2016) 84–98 87

a b c

d e f

g h

Fig. 1. A simple network for structural controllability assessment.

Other important topological features may be studied through quantifying network spectra and the analysis of eigenvalues of adjacency or Laplacian matrices. Here we use the largest eigenvalue (λmax) of the adjacency matrix A = (aij), which has been linked to system dynamics and controllability of networks [30]. Overall, the noted metrics in this paper are but a sample of many, which focus on topological characteristics that may have impacts on the structural controllability features of networks.

2.2. Network controllability

Along with urbanization, power grids are becoming more equipped with telecommunication systems and more amenable to control within the paradigm of smart systems [31], particularly for demand-driven contingencies or other slow dynamics events. There are models to capture the controllability of a system that is driven by linear and time-invariant processes [12,32], as assumed in this study, such as:

dx(t) dt

= Ax(t) + Bu(t), (4)

where x(t) = (x1(t), . . . , xN (t))T denotes the state of a system with N nodes at time t. The matrix A (N × N) describes the system’s wiring diagram. Matrix B (N ×M) is the input that identifies the nodes controlled by an outside controller (M 6 N). The system is controlled using the time-dependent input vector u(t) = (u1(t), . . . , uM (t))T .

It is proved that the above linear dynamical system can be driven from any initial state to any desired state in finite time, if and only if the N × NM controllability matrix C has full rank [12,13], i.e.,

Rank(C) ≡ Rank[B, AB, A2B, . . . , AN−1B] = N. (5)

For an arbitrary network, a brute-force search to compute the rank of C for 2N −1 distinct combinations is computationally prohibitive for large networks [12]. Liu et al. [13] proved that the minimum number of driver nodes needed to maintain full control of a network is determined by the ‘maximum matching’ (MM), that is, the maximum set of links that do not share start or end nodes. A node is said to be matched if a link in the maximum matching set points at it; otherwise it is unmatched. One can gain full control over a directed network if and only if one directly controls each unmatched node and there are directed paths from the input signals to all matched nodes [33]–those controlled nodes are called driver nodes. For example, in Fig. 1, there are four nodes in the network, and a maximum matching contains three links, such as links l1, l3 and l5 in Fig. 1(a). As a result, there are three matched nodes and one unmatched node (or driver node). This means that one would have to apply at least one input signal to a certain node (such as x4 in Fig. 1(a)) to fully control the system topologically. How these nodes relate to generators in a power network will be discussed in the next section. For now, restricting the discussion to topology, it should be noted that there may be many different configurations of maximum matching for a certain network, though the number of links in the maximum matching remains the same. For the network shown in Fig. 1, ND (number of driver nodes) = 1 and NM (number of matched nodes) = 3, but the formalism indicates that control can be achieved via eight different maximum matchings: {l1, l3, l5}, {l1, l3, l7}, {l1, l5, l6}, {l1, l6, l7}, {l2, l3, l8}, {l3, l5, l8}, {l2, l6, l8} and {l5, l6, l8}, shown in Fig. 1(a)–(h). Under the eight kinds of maximum matching, there are three kinds of minimum driver node sets ({x1}, {x2} and {x4}) accompanied by three maximum matched node sets ({x2, x3, x4}, {x1, x3, x4} and {x1, x2, x3}).

The nodes in the networks can be divided into three categories according to their frequency as driver nodes [16]. Specifically, a node is critical, intermittent or redundant if it acts as a driver node in all, some or none of the control

88 J. Li et al. / Physica A 453 (2016) 84–98

a b

Fig. 2. (a) Algorithm to identify critical, intermittent and redundant nodes; (b) Algorithm to quantify the frequency of driver nodes from the set of intermittent nodes.

configurations. Here, node x3 is never a driver node, so it is a redundant node. Nodes x1, x2 and x4 sometimes act as the driver nodes; hence, they are intermittent nodes. There are no critical nodes in the graphs in Fig. 1, but Jia et al. [16] proved that a node is critical if and only if it has no incoming links.

This paper builds upon an algorithm from Jia et al. [16] to identify the critical, intermittent and redundant nodes (Fig. 2(a)). First, this paper converts the directed network into a bipartite graph with two disjoint sets of out and in nodes. As noted, a node is critical if and only if it has no incoming links [16]. For distinguishing the intermittent nodes and redundant nodes, this paper takes the following steps:

A.1. Adopt the Hopcroft–Karp (HK) algorithm [34,35] to find one maximum matching to determine the minimum number of driver nodes (ND) needed to fully control the system and obtain a set of matched nodes (Ma) in the in set. An unmatched node will be an intermittent node if there is at least one link that points at it, otherwise it is a critical node.

A.2. Pick one element (node i) in Ma and identify the node in the out set that matches i (denoted by j). A.3. Keep the current matching, and remove i and all its incident links. A.4. Judge whether there is at least one Augmenting Path (AP) [34] that starts from j and ends at an unmatched node with

a Breadth First Search (BFS). If yes, node i is an intermittent node, otherwise, it is a redundant node. A.5. Add back node i and the removed links, and repeat steps (A.2)–(A.5) until all the matched nodes in the in set have been

enumerated.

The maximum matching in directed networks can be identified numerically in at most O(N1/2K) steps [34], and each Breadth First Search (BFS) for Augmenting Path (AP) requires O(K) time. Since the number of matched nodes is equal to or less than N, the final (worst) complexity of the above algorithm will be O(KN) [16], which is still a polynomial time algorithm, and thus is computationally affordable; however, this algorithm is not capable of enumerating the possible configurations in which critical, intermittent and redundant nodes can be arranged. Similarly, an intermittent node is a node that sometimes is a driver node, but its frequency as a driver node is not revealed by the previous algorithm. As a result, Jia et al. [36] used a sampling method to quantify the likelihood that a node is a driver node. However, the exact frequency to be a driver node cannot be computed with Jia’s algorithm. For the same purpose, in this paper, we develop a new method to quantify the frequency of intermittent nodes as driver nodes, as ranking is essential for the operation and investment in critical infrastructure systems. The flowchart of the new algorithm is shown in Fig. 2(b), whose main steps are as follows:

J. Li et al. / Physica A 453 (2016) 84–98 89

Table 1 Point estimates of topological properties across the 58 studied networks. k, average degree; c, mean clustering coefficient; d, average shortest path length; b, average betweenness centrality; M, meshedness coefficient; λmax, largest eigenvalue of the adjacency matrix; nD, proportion of driver (or unmatched) nodes; nC , proportion of critical nodes; nI , proportion of intermittent nodes; nR, proportion of redundant nodes.

Measures k̄ c d b M λmax nD nC nI nR

Minimum 2.11 0 3.94 0.0072 0.032 3.29 0.075 0 0 0.613 P25 2.36 0.040 5.41 0.0292 0.096 3.82 0.117 0.029 0.124 0.712 P50 2.50 0.054 6.21 0.0448 0.133 4.28 0.146 0.045 0.182 0.758 µ 2.52 0.059 6.39 0.0431 0.138 4.26 0.144 0.053 0.188 0.759 P75 2.65 0.078 7.30 0.0526 0.171 4.64 0.167 0.075 0.248 0.815

Maximum 2.94 0.146 9.98 0.0798 0.252 6.11 0.233 0.164 0.387 0.925 γ 0.32 0.435 0.51 −0.015 0.365 0.67 0.199 1.01 0.079 −0.026 σ 0.20 0.030 1.38 0.018 0.051 0.61 0.036 0.034 0.08 0.066 CV 0.08 0.507 0.22 0.418 0.368 0.14 0.25 0.642 0.426 0.087

B.1. Find a maximum matching to achieve the minimum number of driver nodes (ND) with the previous algorithm. Distinguish the critical, intermittent and redundant nodes, and quantify their number NC , NI and NR respectively;

B.2. Label P = ND − NC nodes from the NI intermittent nodes, and remove the labeled intermittent nodes from the in set as well as their links;

B.3. Find a maximum matching with the Hopcroft–Karp (HK) algorithm and see whether the number of driver nodes equals ND, if no, turn to step (B.4), otherwise, the frequency of the P labeled intermittent nodes increases 1 and the number of maximum matchings (NN) increases 1, then turn to (B.4);

B.4. Add back the removed nodes and links, and repeat (B.2)–(B.4) until all the combinations (pick P nodes from NI nodes) have been enumerated;

B.5. Calculate the total frequency of each intermittent node and normalize them by dividing NN .

We have illustrated that the number of driver nodes, critical nodes, intermittent nodes and redundant nodes can be identified in O(KN) steps. For picking P = ND −NC nodes from the NI intermittent nodes, the worst complexity will be O(2N ), and to find one maximum matching would require at most O(N1/2K) steps [34], so in the worst case, the time complexity for ranking is exponential in N. Though this is not a time-efficient algorithm, one can still quantify in practice the frequency to be driver nodes for the intermittent nodes in power transmission networks of small or middle size cities, such as Austin, TX (with 131 nodes and 181 links). Sampling methods are needed for large N networks.

3. Power transmission networks

This study explores an ensemble of 58 individual power transmission networks from small to large cities across seven U.S. states that are susceptible to damage from hurricanes or earthquakes (or both) with their combined coastlines on the Pacific, Atlantic, and Gulf of Mexico [24]. The states include California (CA), Florida (FL), Georgia (GA), North Carolina (NC), South Carolina (SC), Tennessee (TN), and Texas (TX). The city population ranges from tens of thousands to millions. The grids consist of 110–765 kV transmission-level power lines connecting generators and substations. The raw network data is obtained in GIS format from the ‘‘Platts’’ repository for maps and geospatial data [37]. The network sizes range from 47 nodes and 62 edges (Amarillo, TX) to 1036 nodes and 1511 edges (Los Angeles, CA). The edges are bidirectional between substations (and between generators), but are unidirectional from generators to substations. All networks are sparse (i.e. K ≈ O(Na) with 1 < a < 2 and 2K ≪ N(N − 1)) and planar (i.e. 2K ≈ 3N − 6), as shown in the Appendix (Table A.1) along with other topological features.

4. Results and discussions from topological and controllability analyses

The topological properties for the 58 U.S. city-level power transmission networks are computed, along with their minimal number of driver nodes (ND), the number of critical nodes (NC ), intermittent nodes (NI) and redundant nodes (NR). This paper uses normalized versions to remove size effects (nD = ND/N, nC = NC /N, nI = NI /N, nR = NR/N). Statistics of the measurements for the studied ensemble are presented in Table 1. Results include the minimum value, 25th percentile P25, 50th percentile P50 (median), mean value µ, 75th percentile P75, maximum value, skewness γ , standard deviation σ , and coefficient of variation σ /µ (denoted as CV below). Appendix (Table A.1) reports the obtained values of topological metrics for all 58 networks sorted by graph order N.

4.1. Topological properties of the ensemble of 58 power grids

4.1.1. Degree and degree distribution According to Table 1, the mean degree µ of the ensemble (2.52) is in agreement with other studies of technological and

infrastructure networks where connectivity (e.g. through node degree) is severely restricted due to physical constraints

90 J. Li et al. / Physica A 453 (2016) 84–98

Fig. 3. Degree distributions for the power transmission network of Amarillo, TX.

[19,24,38,39]. The distribution of k̄ values of the current sample of power grids is slightly right-skewed with γ = 0.32, illustrating that more cities have node degrees less than the average value. The CV for degree is very low (8% according to Table 1), pointing out that the average degree of power transmission networks for different cities tends to be uniform (consistent with engineering design principles).

Exploring the uncertainty in the degree distribution further, this paper probes five kinds of (continuous or discrete) probability distribution functions, including the power law, lognormal, exponential, normal and Poisson distributions, which are widely used in engineering. Fig. 3 shows the fitting curve of the degree distribution of the network of Amarillo, TX as an example (note that similar degree distributions are also found with other power transmission networks). This paper uses the chi-square test [40] to verify the goodness-of-fit of these five theoretical distributions, and the results show that for almost all the 58 cases the lognormal distribution is the best fit. The reason is that the lognormal model captures the heavy tail of the degree distribution while allowing for a mode degree that is low.

4.1.2. Shortest path length and its distribution The observed values for average shortest path lengths d are not particularly high (ranging from 3.94 to 9.98 with

µ = 6.39), with a variability across the ensemble of CV = 22%, which is considered not too high and thus pointing to a common functional form. Plots presenting shortest path length distributions p(d) for several cities, ranging from 62 edges to 1511 edges, are shown in Fig. 4. This paper uses a trial function to fit the data, which fits well to asymmetric, unimodal trends [41]:

p(d) = Ade−Bd 2 +Cd

, (6)

where A, B and C are fitting coefficients. There is a very good agreement between the values from Eq. (6) and the observed data, with a minimum R2 = 0.9597 and a maximum R2 = 0.9997 across the 58 cases.

4.1.3. Clustering coefficient and meshedness As a whole, the clustering coefficient c is small in power networks, and this illustrates that few triangular sub-graphs exist

at the transmission level. For the meshedness coefficient M, the variability in the observed values (CV = 0.368) is smaller as compared to the variability in the clustering coefficient (CV = 0.507). The distributions of both datasets of clustering and meshedness coefficients are right-skewed with γ > 0, illustrating that more cities have clustering coefficient and meshedness less than the average value as expected for sparse networks.

4.1.4. Largest eigenvalue of adjacency matrix Spectral graph theory is an important emerging branch of mathematics which offers insights about the structure and

dynamics of a graph with quantities computed from the eigenvalues of the adjacency or Laplacian representations [42]. Godsil and Severini [30] mentioned that the controllability of a closed quantum system and its dynamical Lie algebra is generated by the adjacency matrices of graphs. To this end, this paper computes the Pearson product-moment correlations [43] between the eigenvalues of the adjacency (this paper studies the maximum eigenvalue λmax) and basic topological metrics before exploring the controllability features of power transmission networks. It is found that the Pearson correlation coefficient between the largest eigenvalue λmax and the average betweenness is the largest, with a value of −0.8348. Also, the correlation between λmax and average degree (as well as meshedness coefficient) is relatively high (0.5757 and 0.5191). Such results show that topological characteristics, including betweenness, degree and meshedness, may have

J. Li et al. / Physica A 453 (2016) 84–98 91

Fig. 4. Fitted shortest path length distribution for several representative cities: Amarillo, TX, solid line; EI Centro, CA, dash line; Abilene, TX, dot line; Augusta, GA, dash dot line; Los Angeles, CA, dash dot dot line.

ba

Fig. 5. Proportion of different kinds of nodes across the 58 networks: (a) Driver nodes (or unmatched nodes); (b) Critical, intermittent and redundant nodes.

some relationship with the controllability of networks. Since meshedness is a global metric, this paper will focus on the betweenness and degree (of each node) in the next section where linear controllability features are discussed.

4.2. Controllability features of power transmission networks

In this section, we explore the structural controllability features of power transmission networks, as well as how power transmission network topology affects the system’s potential controllability.

The number of driver nodes (ND), as well as critical (NC ), intermittent (NI) and redundant nodes (NR), are listed in the Appendix (Table A.1), and their proportions are shown in Fig. 5. Note that the unmatched nodes or driver nodes have very low fractions, ranging from 7.5% to 23.4%, and about 14.4% as an average value (also shown in Table 1)—which is desirable. The figure also shows that the redundant nodes occupy a large proportion of all the nodes, while few nodes are critical nodes.

In general, we see that the percentage of driver nodes (unmatched nodes) shows no significant difference with different networks sizes, which is also seen for critical nodes, intermittent nodes and redundant nodes. Visually, the size of the systems in our sample has no significant influence on the linear controllability features of power networks. However, analyses at the state and national levels are still needed in the future, as the noted trends are limited to city-sized systems for now.

In addition, the nodes with degree one have impact on controllability features of the power transmission networks, such as the proportion of driver nodes, as shown in Fig. 6. One can observe that as the percentage of k = 1 nodes increases, the node percentage needed to control the system also increases. This means that the existence of k = 1 nodes reduces the con-

92 J. Li et al. / Physica A 453 (2016) 84–98

Fig. 6. Relationship between driver node proportions and k = 1 node proportions.

Fig. 7. Average degree of intermittent and redundant nodes as a function of average degree of the networks.

trollability of the power networks, highlighting that the design of power transmission networks would benefit from reducing k = 1 nodes for slow linear dynamics regimens; this strategy will also help with traditional system reliability in practice.

Given the important role that hubs (nodes with high degree) have in maintaining the topological integrity of networks against failures and attacks [13], it is natural to expect that nodes with large degree are essential to control a network. To test this proposition, this study quantifies the average degree of redundant nodes and intermittent nodes as a function of the mean degree, as shown in Fig. 7. Note that intermittent nodes rather than critical nodes are discussed, because critical nodes are always power plants in this study. We can see that in all the 58 cases, the average degree of intermittent nodes is smaller than the average degree of redundant nodes. This study also plots the fraction of intermittent and redundant nodes in terms of different node degrees, as shown in Fig. 8. It can be seen that most intermittent nodes have degree of k = 1 or k = 2, and very few high-degree nodes are intermittent nodes. On the other hand, as the degree increases, the percentage of redundant nodes increases, and for those nodes with k > 2, they are nearly all redundant nodes. These results indicate that intermittent nodes, which are also key for future controllability, tend to be nodes with low degree and avoid the hubs. Liu et al. [13] has revealed similar results, and found that driver nodes tend to avoid hubs in two idealized complex networks: E–R and scale-free networks. However, our observations extend such results for engineered power transmission grids.

Regarding the clustering coefficient, Posfai et al. [9] observed that the clustering coefficient c (of the network) plays a negligible role in determining ND. We also find that the nodal clustering coefficients of intermittent nodes have no significant difference relative to the clustering coefficient of redundant nodes for all the 58 cases. We conjecture it is the number of triangular sub-graph (TSN) rather than the clustering coefficient that matters for the category of nodes (intermittent or redundant) in power transmission networks. Typically, (local) clustering coefficient is the normalized version of TSN. For this reason, the average TSN for intermittent nodes and redundant nodes is quantified and shown in Fig. 9. In the figure, one

J. Li et al. / Physica A 453 (2016) 84–98 93

Fig. 8. Fraction of intermittent and redundant nodes in terms of different node degrees (city names in terms of different indexes are listed in the Appendix (Table A.1); blank spots mean there is no intermittent or redundant node with that particular node degree).

Fig. 9. Average TSN of intermittent and redundant nodes.

can see that for most (actually 49 cases of the 58 cases) cases, the intermittent nodes have lower average TSN compared with redundant nodes. To be more specific, the fraction of intermittent and redundant nodes in terms of different TSN is shown in Fig. 10. We observe that almost all the intermittent nodes have TSN smaller than 2, and nodes with TSN > 2 are seldom intermittent nodes. This means the intermittent nodes tend to avoid triangular sub-graph especially high TSN, which is consistent to the finding that intermittent nodes tend to avoid hubs, because high TSN is usually accompanied with high degree in power transmission networks.

94 J. Li et al. / Physica A 453 (2016) 84–98

Fig. 10. Fraction of intermittent and redundant nodes in terms of different TSN (note: there may be no nodes with certain TSN levels, and in these circumstances the percentage of both intermittent and redundant nodes is zero).

Fig. 11. Average betweenness centrality for intermittent and redundant nodes.

In terms of potential network controllability, betweenness centrality alone could be an important factor. As shown in Fig. 11, one can find that the average betweenness centrality for redundant nodes is higher than that of intermittent nodes for almost all the power networks (54 of 58). This is counterintuitive, yet similar to the relation of controllability conditions and vertex degree. In the power transmission systems, high betweenness nodes tend to have high degree and, as shown before, intermittent nodes do not correlate with them. Hence, most high betweenness nodes are redundant.

Overall, the topological impact on the controllability features of power networks illustrates that intermittent nodes suitable for control benefit from low degree, low TSN and low betweenness. Whether these topological properties also

J. Li et al. / Physica A 453 (2016) 84–98 95

a b

dc

Fig. 12. Frequency of driver nodes among all intermittent nodes in 26 power grids in terms of different metrics: (a) degree, (b) clustering coefficient, (c) betweenness centrality, and (d) betweenness centrality of nodes in 11 similar-scale cities.

have an impact on the frequency of nodes being driver nodes from the set of intermittent nodes is still unknown (note that an intermittent node is classified as such if it is a driver node in at least one controllable system configuration). Consequently, this study quantifies the frequency of nodes being intermittent in all possible controllable configurations for the 26 smaller power networks among the set of 58 (since the algorithm for computing the frequency has exponential computational complexity as elaborated in Section 2.2). Fig. 12 shows the average frequency of nodes in terms of degree, clustering coefficient and betweenness centrality. One can observe that high degree nodes have a lower average frequency compared with low degree nodes in Fig. 12(a), reinforcing the notion that driver nodes tend to be low degree nodes [13].

Fig. 12(b) shows that as the clustering coefficient increases, the frequency of nodes as drivers increases, except for the nodes with c = 0 and k = 1. A plausible explanation is that nodes with very low clustering coefficient tend to have a high degree; for example, the nodes with 0 < c 6 0.2 have an average degree of about 5.0 while nodes with c = 1 have an average degree of about 2.0, and recall that driver nodes tend to avoid high degree nodes. The above explanation also accounts for the observation that c = 0 (and k = 1) nodes have the highest frequency (because of lowest degree).

Unlike the degree and clustering coefficient, we observe no significant impact from the betweenness centrality on the frequency of nodes as driver nodes when assessed in aggregate (see Fig. 12(c)). This is because the scale of networks also influences the average betweenness centrality of the nodes (usually for similar structure networks, larger size networks have smaller average betweenness centrality), and the scale of the networks is not uniform. Therefore, we select 11 similar-size power networks whose average betweenness centrality ranges from 0.045 to 0.055, and gather statistics of the frequency

96 J. Li et al. / Physica A 453 (2016) 84–98

of nodes as driver nodes in terms of different betweenness centrality levels as shown in Fig. 12(d). In this circumstance, we find that nodes with low betweenness have high frequency of being driver nodes.

In sum, we explored controllability features for an ensemble of 58 power transmission networks, and found topological effects on the linear controllability conditions of power networks. For example, the intermittent and driver nodes, which are critical for future system operation studies, tend to avoid hubs, high betweenness nodes and high TSN nodes. Also, the selected 58 networks enabled us to investigate structural controllability attributes for the class of power transmission networks. These insights could inform reliability-based infrastructure network design, maintenance and restoration principles, particularly for future smart infrastructure systems, which are expected to exercise functional controllability strategies that depend on system topology and physical constraints.

5. Conclusions

Power transmission grids are infrastructure systems that are vital to the function of modern societies, particularly as they evolve into smart and more controllable systems. However, most ongoing research on controllability focuses on ideal networks or combinations of different kinds of networks. To guide future power system design and maintenance, it is necessary to start exploring the controllability of entire classes of networks, even if focusing on topological control properties at first, which are pertinent to linear dynamics. Hence, this study unravels structural controllability features from an ensemble of 58 power transmission networks in the United States. Topological features from the ensemble are used to study controllability features. The topological metrics cover a range of local and global quantities, including vertex degree, shortest path length, clustering coefficient, betweenness centrality, meshedness coefficient, and proportions of nodes in network- controllable configurations. In particular, this paper identifies the controllability features of power networks through how topological factors affect the fraction of intermittent (driver or controlling) nodes, and the frequency of driver nodes from the set of intermittent nodes across controllable configurations of the power systems.

Despite prominent differences in the scale and topology of the 58 U.S. power networks of this study, most topological metrics display small to moderate variability. In addition, the node degrees in power networks show a lognormal distribution, while the shortest path length distribution fits well with asymmetric unimodal functions. Also the average betweenness, average degree and meshedness are found to have correlations with the largest eigenvalue of the adjacency matrix, which is suitable to relate to system dynamics, and thus future system controllability.

Particular to the linear controllability features of power transmission networks, we find that a small proportion of driver nodes (about 14.4% as an average value) could provide the conditions for controlling the power networks in spite of power network size. However, a high proportion of k = 1 nodes (not uncommon in the studied set of networks) will increase the proportion of driver nodes needed to control the networks, which becomes disadvantageous to the power systems. It is also found that the intermittent nodes, as well as driver nodes, tend to have low degree, effectively avoiding the hubs. We observe no obvious influence on the controllability features from the clustering coefficient, but find that high TSN nodes correlate with a high fraction of redundant nodes. Furthermore, intermittent nodes have relatively low betweenness centrality, which has been revealed for most of the 58 cities.

As for the frequency of driver nodes among the intermittent nodes, it is degree that impacts the outcome. To be specific, high degree intermittent nodes tend to have low frequency of being driver nodes. Also, due to the impact from degree, low clustering coefficient and high betweenness centrality nodes tend to have low frequency of being driver nodes.

As the present selection of networks is one of the largest ensembles of real power transmission networks published to date, insights could be attributed to the class of engineered power transmission systems. In addition, this paper uses linear controllability theory to peer into power networks, where topological factors offer insights and set the stage for more sophisticated future research on practical design, nonlinear dynamics, and controllability of smart power transmission networks and other geographically distributed infrastructure systems.

We should also note that according to previous work, such as Yan et al. [44], the energy cost for controlling complex network systems can be very high. And in practice, the driver nodes set identified in this paper may not be the most economical (the lowest energy cost) for controlling various system configurations. An efficient method to choose an optimal control node set for minimizing the energy cost is lacking, which is a promising avenue for future work [44]. Also, it is promising to explore link classification and properties, as the supplementary material in Liu et al. [13] showcases. Future work will also focus on the computational complexity of the algorithms to quantify the frequency of nodes in controllable configurations, so as to inform ranking and prioritization of resources, as well as the potential relationships between controllability and practical reliability of infrastructure systems.

Acknowledgments

This work is financially supported by National Natural Science Foundation of China (NSFC) under grant 51534008 and 51576212 and the Fundamental Research Funds for Central Universities of China. This work is also funded in part by the U.S. Department of Defense through the MURI grant W911NF-13-1-0340.

J. Li et al. / Physica A 453 (2016) 84–98 97

Appendix. Topological measurements for the studied ensemble of 58 U.S. power transmission networks

Table A.1 Selected topological characteristics of the U.S. power transmission network ensemble under consideration: N, number of nodes; K , number of links; k, average degree; c, mean clustering coefficient; d, average shortest path length; b, average betweenness centrality; M, meshedness coefficient; ND, number of driver (or unmatched) nodes; NC , number of critical nodes; NI , number of intermittent nodes; NR, number of redundant nodes.

City index City names N K k̄ c d b M ND NC NI NR

1 Amarillo, TX 47 62 2.6383 0.073 4.0083 0.067 0.180 7 2 8 37 2 Lakeland, FL 50 69 2.7600 0.146 4.3845 0.071 0.211 8 4 9 37 3 El Paso, TX 52 65 2.5000 0.019 4.4623 0.069 0.141 9 4 11 37 4 San Luis Obispo, CA 57 69 2.4211 0.042 5.3872 0.080 0.119 7 4 6 47 5 Eureka, CA 61 70 2.2951 0.067 5.6388 0.079 0.085 11 10 2 49 6 Bulls Gap, TN 62 91 2.9355 0.078 4.1565 0.053 0.252 9 2 18 42 7 Plantersville, SC 66 96 2.9091 0.044 4.9012 0.061 0.142 11 3 19 44 8 Memphis, TN 66 83 2.5152 0.104 3.9375 0.046 0.244 10 2 16 48 9 Palm Bay, FL 74 98 2.6486 0.115 5.1988 0.058 0.175 7 3 7 64

10 Greenville, NC 75 82 2.1867 0.016 5.6995 0.064 0.083 15 0 29 46 11 Wilmington, NC 75 86 2.2933 0.018 5.5604 0.062 0.055 14 6 18 51 12 Lubbock, TX 85 106 2.4941 0.070 5.3305 0.052 0.133 13 6 15 64 13 Midland, TX 88 98 2.2273 0.015 6.2649 0.061 0.064 14 6 17 65 14 Wichita Falls, TX 88 106 2.4091 0.030 6.9005 0.069 0.088 10 4 13 71 15 El Centro, CA 88 102 2.3182 0.000 5.4778 0.052 0.111 20 9 21 58 16 Palm Springs, CA 88 110 2.5000 0.084 5.3597 0.051 0.135 11 8 6 74 17 Charleston, SC 91 106 2.3297 0.055 5.3221 0.049 0.090 14 5 17 69 18 Cape Coral, FL 91 118 2.5934 0.083 5.0686 0.046 0.158 9 1 18 72 19 Fayetteville, NC 92 107 2.3261 0.049 5.5977 0.051 0.089 12 4 16 72 20 Ridgeland, SC 97 122 2.5155 0.072 5.8643 0.051 0.138 18 6 25 66 21 McAllen, TX 98 130 2.6531 0.035 5.0741 0.042 0.173 13 8 13 77 22 Athens, GA 103 116 2.2524 0.059 8.3335 0.073 0.070 9 2 14 87 23 Winston, NC 104 121 2.3269 0.044 6.3206 0.052 0.089 17 4 26 74 24 Salinas, CA 107 140 2.6168 0.038 6.0333 0.048 0.163 8 8 0 99 25 Jacksonville, FL 107 137 2.5607 0.117 5.7018 0.045 0.148 18 3 27 77 26 Daytona Beach, FL 111 145 2.6126 0.082 6.5586 0.051 0.161 17 5 27 79 27 Sumter, SC 112 139 2.4821 0.000 8.7013 0.070 0.032 18 0 34 78 28 Santa Rosa, CA 112 118 2.1071 0.053 6.0732 0.046 0.128 18 10 18 84 29 Oak Ridge, TN 116 164 2.8276 0.079 4.7043 0.032 0.216 23 5 36 75 30 Abilene, TX 117 138 2.3590 0.042 7.3103 0.055 0.096 15 5 22 90 31 Pensacola, FL 120 147 2.4500 0.073 6.5499 0.047 0.119 17 3 28 89 32 Redding, CA 126 150 2.3810 0.043 6.6993 0.046 0.101 24 19 9 98 33 Corpus Christi, TX 129 171 2.6512 0.117 6.2137 0.041 0.170 14 5 16 108 34 Austin, TX 131 181 2.7634 0.087 5.4328 0.034 0.198 12 7 12 112 35 Columbia, SC 137 167 2.4380 0.044 6.6649 0.042 0.074 21 4 33 100 36 Beaumont, TX 137 156 2.2774 0.024 6.3298 0.039 0.115 20 8 25 104 37 Spartanburg, SC 143 168 2.3497 0.041 7.1003 0.043 0.093 25 0 51 92 38 Tampa, FL 149 198 2.6577 0.094 5.927 0.034 0.171 29 7 37 105 39 Columbia, TN 163 240 2.9448 0.090 5.4067 0.027 0.243 16 5 24 134 40 Tifton, GA 171 207 2.4211 0.030 7.4634 0.038 0.110 23 2 46 123 41 Durham, NC 172 197 2.2907 0.033 7.6196 0.039 0.077 27 3 49 120 42 Eastman, GA 186 231 2.4839 0.054 6.3683 0.029 0.125 21 5 35 146 43 Augusta, GA 194 243 2.5052 0.073 7.2793 0.033 0.131 28 4 50 140 44 San Diego, CA 194 278 2.8660 0.076 5.817 0.025 0.222 23 10 24 160 45 Modesto, CA 199 263 2.6432 0.092 7.2969 0.032 0.165 29 22 13 164 46 San Francisco, CA 242 322 2.6612 0.075 6.4639 0.023 0.169 33 8 48 186 47 Stockton, CA 258 312 2.4186 0.045 7.3835 0.025 0.108 32 17 37 204 48 Bakersfield, CA 266 326 2.4511 0.052 7.566 0.025 0.116 46 27 39 200 49 Hanford, CA 271 346 2.5535 0.062 8.4597 0.028 0.142 47 25 48 198 50 Gastonia, NC 275 324 2.3564 0.053 7.1897 0.023 0.092 45 8 76 191 51 Miami, FL 276 377 2.7319 0.066 5.9924 0.018 0.186 29 12 33 231 52 San Antonio, TX 278 362 2.6043 0.051 6.6953 0.021 0.154 65 16 80 182 53 Chatsworth, GA 280 339 2.4214 0.029 9.224 0.030 0.108 23 4 44 232 54 Houston, TX 518 706 2.7259 0.057 7.8601 0.013 0.183 69 46 50 422 55 Dallas–Fort Worth, TX 621 843 2.7150 0.065 8.7713 0.013 0.180 75 49 58 514 56 Atlanta, GA 738 952 2.5799 0.040 9.9785 0.012 0.146 77 14 138 586 57 Sacramento, CA 931 1137 2.4425 0.038 9.1489 0.009 0.111 109 51 144 736 58 Los Angeles, CA 1036 1511 2.9170 0.084 8.4467 0.007 0.230 94 40 117 879

References

[1] R. Kalman, Controllability and Observability, 1960, pp. 1–27. [2] R. Hermann, A.J. Krener, Nonlinear controllability and observability, IEEE Trans. Automat. Control 22 (1977) 728–740.

98 J. Li et al. / Physica A 453 (2016) 84–98

[3] Y. Zheng, J.C. Willems, C. Zhang, A polynomial approach to nonlinear system controllability, IEEE Trans. Automat. Control 46 (2001) 1782–1788. [4] G.-R. Chen, Problems and challenges in control theory under complex dynamical network environments, Acta Automat. Sinica 39 (2014) 312–321.

http://dx.doi.org/10.3724/SP.J.1004.2013.00312. [5] Z. Yuan, C. Zhao, Z. Di, W.-X. Wang, Y.-C. Lai, Exact controllability of complex networks, Nature Commun. 4 (2013) 2447.

http://dx.doi.org/10.1038/ncomms3447. [6] H. Lvlin, L. Songyang, B. Jiang, B. Liang, Enhancing complex network controllability by rewiring links, 2013 Third Int. Conf. Intell. Syst. Des. Eng. Appl.,

2013, pp. 709–711, http://dx.doi.org/10.1109/ISDEA.2012.168. [7] J. Sun, A.E. Motter, Controllability transition and nonlocality in network control, Phys. Rev. Lett. 110 (2013) 208701.

http://dx.doi.org/10.1103/PhysRevLett.110.208701. [8] M. Nabi-Abdolyousefi, M. Mesbahi, On the controllability properties of circulant Networks, 58, 2013, pp. 3179–3184.

http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6507614. [9] M. Pósfai, Y.-Y. Liu, J.-J. Slotine, A.-L. Barabási, Effect of correlations on network controllability, Sci. Rep. 3 (2013) 1067.

http://dx.doi.org/10.1038/srep01067. [10] C.-L. Pu, W.-J. Pei, A. Michaelson, Robustness analysis of network controllability, Phys. A 391 (2012) 4420–4425.

http://dx.doi.org/10.1016/j.physa.2012.04.019. [11] J. Ding, Y.-Z. Lu, J. Chu, Studies on controllability of directed networks with extremal optimization, Phys. A 392 (2013) 6603–6615.

http://dx.doi.org/10.1016/j.physa.2013.09.004. [12] A. Lombardi, M. Hörnquist, Controllability analysis of networks, Phys. Rev. E 75 (2007) 056110. http://dx.doi.org/10.1103/PhysRevE.75.056110. [13] Y.-Y. Liu, J.-J. Slotine, A.-L. Barabási, Controllability of complex networks, Nature 473 (2011) 167–173. http://dx.doi.org/10.1038/nature10011. [14] W.-X. Wang, X. Ni, Y.-C. Lai, C. Grebogi, Optimizing controllability of complex networks by minimum structural perturbations, Phys. Rev. E 85 (2012)

026115. http://dx.doi.org/10.1103/PhysRevE.85.026115. [15] N.J. Cowan, E.J. Chastain, D.A. Vilhena, J.S. Freudenberg, C.T. Bergstrom, Nodal dynamics, not degree distributions, determine the structural

controllability of complex networks, PLoS One 7 (2012) e38398. http://dx.doi.org/10.1371/journal.pone.0038398. [16] T. Jia, Y.-Y. Liu, E. Csóka, M. Pósfai, J.-J. Slotine, A.-L. Barabási, Emergence of bimodality in controlling complex networks, Nature Commun. 4 (2013)

1–6. http://dx.doi.org/10.1038/ncomms3002. [17] P. Erdős, A. Rényi, On the evolution of random graphs, Publ. Math. Inst. Hung. Acad. Sci. 5 (1960) 343–347. [18] A.L. Barabási, R. Albert, Emergence of scaling in random networks, Science 286 (5439) (1999) 509–512. http://dx.doi.org/10.1126/science.286.5439.509. [19] D.J. Watts, S.H. Strogatz, Collective dynamics of small-world networks, Nature 393 (1998) 440–442. http://dx.doi.org/10.1038/30918. [20] R. Albert, I. Albert, G. Nakarado, Structural vulnerability of the North American power grid, Phys. Rev. E 69 (2004) 025103.

http://dx.doi.org/10.1103/PhysRevE.69.025103. [21] L.A.N. Amaral, A. Scala, M. Barthelemy, H.E. Stanley, Classes of small-world networks, Proc. Natl. Acad. Sci. USA 97 (2000) 11149–11152.

http://dx.doi.org/10.1073/pnas.200327197. [22] M.E.J. Newman, S.H. Strogatz, D.J. Watts, Random graphs with arbitrary degree distributions and their applications, Phys. Rev. E 64 (2001) 026118.

http://dx.doi.org/10.1103/PhysRevE.64.026118. [23] R. Ahuja, T. Magnanti, J. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993, citeulike-article-id:486019. [24] J. Winkler, L. Dueñas-Osorio, R. Stein, D. Subramanian, Performance assessment of topologically diverse power systems subjected to hurricane events,

Reliab. Eng. Syst. Saf. 95 (2010) 323–336. http://dx.doi.org/10.1016/j.ress.2009.11.002. [25] M.E.J. Newman, Structure and function of complex brain networks, SIAM Rev. 45 (2003) 167–256. [26] L.D.F. Costa, F.A. Rodrigues, G. Travieso, P.R. Villas Boas, Characterization of complex networks: A survey of measurements, Adv. Phys. 56 (2007)

167–242. http://dx.doi.org/10.1080/00018730601170527. [27] A. Barrat, M. Barthelemy, A. Vespignani, Dynamical Processes on Complex Networks, Cambridge University Press, Cambridge, 2008

http://dx.doi.org/10.1017/CBO9780511791383. [28] J. Buhl, J. Gautrais, N. Reeves, R.V. Solé, S. Valverde, P. Kuntz, et al., Topological patterns in street networks of self-organized urban settlements, Eur.

Phys. J. B 49 (2006) 513–522. http://dx.doi.org/10.1140/epjb/e2006-00085-1. [29] A. Cardillo, S. Scellato, V. Latora, S. Porta, Structural properties of planar graphs of urban street patterns, Phys. Rev. E 73 (2006) 066107.

http://dx.doi.org/10.1103/PhysRevE.73.066107. [30] C. Godsil, S. Severini, Control by quantum dynamics on graphs, Phys. Rev. A 81 (2010) 52316. http://dx.doi.org/10.1103/PhysRevA.81.052316. [31] S.M. Amin, B.F. Wollenberg, Toward a smart grid: power delivery for the 21st century, IEEE Power Energ. Mag. 3 (2005) 34–41. [32] C. Lin, Structural Controllability, IEEE Trans. Automat. Control 19 (1974) 201–208. [33] W. Yu, G. Chen, M. Cao, J. Kurths, Second-order consensus for multiagent systems with directed topologies and nonlinear dynamics, IEEE Trans. Syst.

Man Cybern. Part B Cybern. 40 (2010) 881–891. http://dx.doi.org/10.1109/TSMCB.2009.2031624. [34] J.E. Hopcroft, R.M. Karp, An n5/2 algorighm for maximum matchings in bipartite graphs, SIAM J. Comput. 2 (1973) 225–231. [35] M.D. Plummer, L. Lovász, Matching theory, Access Online via Elsevier, 1986. [36] T. Jia, A.-L. Barabási, Control capacity and a random sampling method in exploring controllability of complex networks, Sci. Rep. 3 (2013) 2354.

http://dx.doi.org/10.1038/srep02354. [37] Platts, 2013. http://www.platts.com/products/gis-data. [38] A. Yazdani, P. Jeffrey, Complex network analysis of water distribution systems, Chaos 21 (2011) 016111. http://dx.doi.org/10.1063/1.3540339. [39] M.E.J. Newman, The structure and function of complex networks, SIAM Rev. 45 (2003) 167–256. [40] A.H.S. Ang, W.H. Tang, Probability concepts in engineering, 2004. [41] J. Sienkiewicz, J.A. Hołyst, Statistical analysis of 22 public transport networks in Poland, Phys. Rev. E 72 (2005) 046127.

http://dx.doi.org/10.1103/PhysRevE.72.046127. [42] F.R.K. Chung, Spectral Graph Theory, American Mathematical Soc., 1997. [43] A. Onwuegbuzie, L. Daniel, N. Leech, Pearson product-moment correlation coefficient, Encycl. Meas. Stat. (2007) 751–756. [44] G. Yan, J. Ren, Y.-C. Lai, C.-H. Lai, B. Li, Controlling complex networks: How much energy is needed? Phys. Rev. Lett. 108 (2012) 218703.

http://dx.doi.org/10.1103/PhysRevLett.108.218703.