Controllability of Deterministic Networks with the Identical Degree Sequence

Xiujuan Ma; Haixing Zhao; Binghong Wang

doi:10.1371/journal.pone.0127545

Abstract

Controlling complex network is an essential problem in network science and engineering. Recent advances indicate that the controllability of complex network is dependent on the network's topology. Liu and Barabási, et.al speculated that the degree distribution was one of the most important factors affecting controllability for arbitrary complex directed network with random link weights. In this paper, we analysed the effect of degree distribution to the controllability for the deterministic networks with unweighted and undirected. We introduce a class of deterministic networks with identical degree sequence, called (x,y)-flower. We analysed controllability of the two deterministic networks ((1, 3)-flower and (2, 2)-flower) by exact controllability theory in detail and give accurate results of the minimum number of driver nodes for the two networks. In simulation, we compare the controllability of (x,y)-flower networks. Our results show that the family of (x,y)-flower networks have the same degree sequence, but their controllability is totally different. So the degree distribution itself is not sufficient to characterize the controllability of deterministic networks with unweighted and undirected.

Citation: Ma X, Zhao H, Wang B (2015) Controllability of Deterministic Networks with the Identical Degree Sequence. PLoS ONE 10(5): e0127545. https://doi.org/10.1371/journal.pone.0127545

Academic Editor: Yongtang Shi, Nankai University, CHINA

Received: March 10, 2015; Accepted: April 16, 2015; Published: May 28, 2015

Copyright: © 2015 Ma et al. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited

Data Availability: All relevant data are within the paper and its Supporting Information files.

Funding: This work was supported to National Natural Science Foundation of China (grant nos: 61164005, 11275186, 91024026, http://www.nsfc.gov.cn/Portal0/default152.htm) received by HX Zhao. The funders had a role in study design, decision to publish, and preparation of the manuscript. This work was also supported by Key Laboratory of Tibetan intelligent information processing and machine translation of Qinghai P.R.C (grant no.2013-Z-Y17), received by HX Zhao. The funders had a role in data collection, analysis and preparation of the manuscript. This work was also supported by The Open Funding Programme of Joint Laboratory of Flight Vehicle Ocean-based Measurement and Control (grant no. FOM2014OF001), received by BH Wang. The funders had a role in study design and preparation of the manuscript. This work was also supported by Research Fund for the Chunhui Program of Ministry of Education of China (grant no.Z2012101), received by XJ Ma. The funders had a role in study design, data collection and analysis, decision to publish and preparation of the manuscript.

Competing interests: The authors have declared that no competing interests exist.

Introduction

Controlling is one of the most challenging problems in modern network science and engineering of complex network. In the past decades significant efforts have been devoted to understanding the controllability of the complex network [1–21]. A networked system is controllable if imposing appropriate external signals on a subset of its nodes, the system can be driven from any initial state to any final state in finite time [22–30]. The minimal set of driver nodes required to control a network is called the minimum driver node set (MDS). The minimum number of the driver nodes denoted by N_D. Moreover, we can measure the controllability of a network by the n_D, $n_{D} = \frac{N_{D}}{N}$ . Lin proposed the structural controllability theory in 1974 [24] and gave two factors influencing the structural controllability. He proposed minimal structure that ensured the structural controllability. However, the structural controllability theory didn’t solve the problem of minimal set of driver nodes. Liu, Slotine and Barabási [7] studied the controllability of various random directed networks and proposed a method to get N_D. Recently Yuan and Zhao et.al [11] introduced the exact-controllability framework based on the maximum multiplicity to identify the N_D of arbitrary network topology. For more complicated model networks and many real-word weighted networks with distinct node-degree distributions, the exact controllability can be efficiently assessed by numerical computations. In spite of their results offered a general tool to solve the N_D, we are more interested in the influence of network topologies to controllability. To find the factors which affect the controllability of the complex network, researchers from different perspectives were in the study of controllability [1–18]. In previous research, one of the most significant conclusions was given by Liu, Slotine and Barabási [7]. Their main conclusion is that the controllability of random directed network is determined by the degree distributions of network. That means, for arbitrary random directed networks, if they had different degree distribution then had different controllability. Meanwhile, the results be obtained were base on the random directed networks. Random network has most of the characteristics of the real network, however as Barabási said [31], it is hard to gain a visual understanding for many properties, and how do different nodes relate to each other. Deterministic networks are abundant in many real systems, such as power networks, computer networks, neural network and chemical network. Therefore, it is significant to study the controllability of deterministic networks. Li and Yuan et.al [17] analysed the controllability of several deterministic networks and gained the exactly expression of N_D.

So far, we did not see relevant results in the controllability of deterministic complex networks with identical degree distributions. If two networks with same degree distribution, it is worthy of studying whether they have same controllability. On the other hand, there is an interesting problem as to whether the degree distribution is the only ingredient responsible for the controllability in the deterministic networks with unweighted and undirected.

To analyse the controllability of deterministic networks with identical degree distribution, we introduce the family of deterministic networks with fractal feature, which was called (x, y)-flower [32, 33] and has identical degree sequence. In the field of complex networks, fractal properties and self-similarities are shared by many real network systems [34–37] include World-Wide-Web, biological and social networks. In a lots of fractal networks, the (x, y)-flower networks displayed some remarkable properties such as scale-free, non-clustered and their degree distribution follows the power-law distribution. On the other hand, the (x, y)-flower has small world property for x = 1 and has large world property for x = y. Hence, it is worthwhile to investigate the dynamic processes of the (x, y)-flower networks. Zhang et.al [38] studied the percolation of two networks in (x, y)-flower networks, which were (1, 3)-flower network and (2, 2)-flower network respectively. Their results indicated that power-law degree distribution alone didn’t suffice to characterize the percolation threshold on (1, 3)-flower and (2, 2)-flower under bond percolation. Lin et.al [33] studied the spanning trees of (x, y)-flower networks, the authors found that the entropy of spanning trees on (x, y)-flower networks were different although the networks had the identical degree distribution. Thus, the degree distribution alone was not sufficient enough to describe the spanning trees of the network.

In this paper, we analysed the controllability and give accurate results of the minimum number of driver nodes for (1, 3)-flower networks and (2, 2)-flower network by exact controllability theory. Our results show that although (1, 3)-flower and (2, 2)-flower have same degree sequence, their controllability are totally different; that is, the N_D of the (1, 3)-flower is about half of the (2, 2)-flower. Furthermore, we verify the results in (x, y)-flower networks by computer simulation. Simulation results show that the (x, y)-flower networks of x = 1 have the identical degree sequence with x = y, but their controllability are entirely different. So the degree distribution itself is not sufficient to characterize the controllability of deterministic networks with unweighted and undirected.

Model

Model and properties of (x, y)-flower

In order to analyse the controllability of the (x, y)-flower networks, we first introduce the construction and structural properties of the (x, y)-flower. The (x, y)-flower are built in an iterative way. We denote the (x, y)-flower after t generations of evolution by F_t(x, y)(n ≥ 0), without loss of generality we assumed that x ≤ y and y > 1. The (x, y)-flower are constructed by the algorithm as follows [32, 33]:

At the initial time t = 0, F₀(x, y) is an edge connecting two node, called the initial nodes.
After, for t ≥ 1, F_t(x, y) is derived from the F_t−1(x, y). For x = 1, every old edge generates y − 1 new nodes, and all of these y − 1 new nodes and the old edge form a circle of length y+1. For x > 1, every old edge connecting two old nodes is removed and replaced by two parallel paths with the two old nodes as the ends of the two parallel paths: the above y − 1 nodes and the two old nodes form a path of length y, while the below x − 1 nodes and the two old nodes constitute another path of length x.

According the constructed process of (x, y)-flower, we can obtain some topological properties [32, 33] as follows:

Let E_t is the number of edges and N_v(t) is the number of total nodes in F_t(x, y), then it is easy to calculate E_t = (x + y)^t and $N_{v} (t) = \frac{x + y - 2}{x + y - 1} {(x + y)}^{t} + \frac{x + y}{x + y - 1}$ .
Since the F_t(x, y) is deterministic construction, we obtain the degree sequence of F_t(x, y). In F_t(x, y), the degree of node i at time t denoted by k_i(t). By construction, the degree k_i(t) evolves with time as k_i(t) = 2k_i(t−1) = 2^s(s = 1, 2, …, t), that is, the degree of node i increases by a factor 2 at each time step. Let N_t(s)(s = 1, 2, …, t) be the number of nodes with degeree 2^s(s = 1, 2, …, t) in F_t(x, y), we have: (1) Thus, all the class of F_t(x, y) with the same x + y have the identical degree sequence.
The degree distributions of (x, y)-flower obey a power-law distribution P(k) ∼ k^−γ, with the exponent $γ = 1 + \frac{ln (x + y)}{ln 2}$ . According the algorithm of constructing the (x, y)-flower, we obtain the (1, 3)-flower and the (2, 2)-flower after t iterations, and denoted by F_t(1, 3) and F_t(2, 2) respectively. Figs 1 and 2 respectively show the growth process of the (1, 3)-flower and the (2, 2)-flower.

Download:

Fig 1. Illustration of the growing process for the (1, 3)-flower.

Where, every old edge generates 2 new nodes. All of these 2 new nodes and the old edge form a circle of length 4.

https://doi.org/10.1371/journal.pone.0127545.g001

Download:

Fig 2. Illustration of the growing process for the (2, 2)-flower.

Where, each old edge connecting two old nodes is removed and replaced by two pathes with the two old nodes as the ends; one new node and the two old nodes form one path of length 2, while another new node and the two old nodes constitute the other path of length 2.

https://doi.org/10.1371/journal.pone.0127545.g002

For these two networks, after t iterations, we have E_t = 4^t, $N_{v} (t) = \frac{2}{3} (4^{t} + 2)$ . Let L_v(t) be the number of nodes generated at step t. Each existing edge at a given step will yield two new nodes at the next step, this leads to L_v(t) = 2E_t−1 = 2×4^t−1(t ≥ 1).

The average node degree after t iterations is $⟨ k_{t} ⟩ = \frac{2 E_{t}}{N_{v} (t)} = \frac{3 \times 4^{t}}{4^{t} + 2}$ , which approaches 3 for large t. Meanwhile, the two networks have an identical degree sequence, and they obey a power-law degree distribution P(k) ∼ k⁻³. Fig 3 show that the degree distributions of F_t(1, 3) network and F_t(2, 2) network. From this figure, we can see that the degree distributions of the F_t(1, 3) and F_t(2, 2) are identical.

Download:

Fig 3. The degree distribution of F_t(1, 3) and F_t(2, 2).

Two networks have identical degree distribution and their degree distribution obey a power-law degree distribution P(k) ∼ k⁻³.

https://doi.org/10.1371/journal.pone.0127545.g003

In this paper, we analysed the controllability of (1, 3)-flower and (2, 2)-flower by the exact controllability theory. Next, let’s start by reviewing some basic concepts of the exact controllability theory.

Exact controllability theory

One controlled complex network with N nodes, described by the following linear ordinary differential equations [7, 11] (2) where the vector x = (x₁, x₂, ⋯, x_N)^T stands for the states of N nodes, A ∈ R^{N × N} denotes the coupling matrix of a complex network, u is the vector of m controllers: u = (u₁, u₂, ⋯, u_m)^T and B is the N × m input matrix. Note that each node is captured by single state, saying one-dimensional nodal dynamics. In order to fully control the complex network, we should choose right B and u. Our purpose is to devise a matrix B, corresponding to the minimum number of input signals imposing on minimum set of driver nodes. According to the results of Liu [7] and Yuan [11], (3) According to the PBH rank condition [23, 28–30] Yuan et.al [11] proved that for arbitrary network, the minimum number N_D of controllers or drivers are determined by the maximum geometric multiplicity μ(λ_i) of the eigenvalue λ_i of A: (4) where μ(λ_i) = dimV_{λ_i} = N−rank(λ_i I_N−A) and λ_i(i = 1, ⋯, l) are the distinct eigenvalues of A. For a symmetric coupling matrix, its geometric multiplicity equals to algebraic multiplicity. For an undirected networks, N_D is determined by the maximum algebraic multiplicity δ(λ_i) of λ_i [11]: (5)

For a large sparse network with a small fraction of self-loops, in which the number of links scales with N in the limit of large N [39], N_D is simply determined by the rank of the coupling matrix A [11] (6) which means the eigenvalue 0 has a maximum multiplicity.

For a densely connected network with a small fraction of self-loop in which the zeros in A same scale with N in the limit of large N, we have [11] (7)

The measure of controllability denoted by n_D, it is defined as the ratio of N_D to the network size N [7]: (8) Using the Eqs (3)–(7) we can calculate N_D of an arbitrary network topology. For the deterministic (1, 3)-flower network and (2, 2)-flower network, we obtain the exact solutions of N_D in (1, 3)-flower network and (2, 2)-flower network by equation Eq (6). Moreover, we get the measure of controllability n_D in (x, y)-flower by equation Eq (8).

Analysis

We derive the formula of N_D and n_D of F_t(1, 3) and F_t(2, 2) from network topology by exact controllability theory. To calculate the eigenvalues of fractal scale-free networks, Zhang and Hu et.al introduced a method [36] Inspired by this method, we calculate the rank of the adjacency matrix in F_t(1, 3) and F_t(2, 2).

The controllability of (1, 3)-flower network

Let α be the set of nodes of the network at the s-step, α = N_s; β be the set of nodes that are generated at the (s + 1)-th iteration, β = N_s+1−N_s. The matrix A_s+1(1, 3) is the adjacency matrix of F_s+1(1, 3), which has the following block form: (9) The matrix A_α,α is the adjacency matrix of (1, 3)-flower at t = s, which represents the adjacency relations of old nodes. The matrix A_β,β represents the adjacency relationships of new nodes, and the matrix $A_{β, α} = A_{α, β}^{T}$ characterizes the relationships between new nodes and old nodes. By the construction of the F_s+1(1, 3) and appropriately implementing elementary transformations for the matrix A_s+1(1, 3), we get (10) where the I_β,β is an identity matrix with β rows and β columns. For details on elementary transformations, see Supporting Information(S1 File). Obviously, rank(A_s+1) = rank(I_β,β) = β = N_s+1−N_s. Thus by Eq (6), So, (11) The measure of controllability n_D of F_t(1, 3) network is obtained by Eq (8): (12) with its thermodynamic limit: (13)

The controllability of (2, 2)-flower network

The controllability of the (2, 2)−flower network can be analysed in the same way as the (1, 3)−flower network. Similarly, let α be the set of nodes that are belong to the s-step network F_t(2, 2); and β be the set of nodes that are generated at the (s + 1)-th iteration, where the value of α and β are same with F_t(1, 3). From the construction, at (s + 1)-th step, the adjacency matrix B_s+1(2, 2) of the network F_s+1(2, 2) has the following form: (14)

Then, we can obtain the rank of the adjacency matrix B_s+1 as: (15) By calculating(S1 File) we obtain rank(B_α,β) = N_s − 1. Then, by Eq (15), rank(B_s+1) = 2(N_s−1). According the Eq (6), we have: (16) Furthermore, the measure of controllability n_D of F_t(2, 2) network is obtained: (17) with its thermodynamic limit: (18)

Numerical analysis

Lots of results about controllability of the complex network show that the controllability is mainly determined by the degree distribution of the network. We numerically analysed the controllability of a class of deterministic networks with the identical degree sequence. However from our results, the family of deterministic networks with identical degree sequence have different controllability.

Numerical analysis of (1, 3)-flower network and (2, 2)-flower network As shown in Fig 4, we calculate N_D of (1, 3)-flower network and (2, 2)-flower network by computer numerical simulation, and compare with the theory results of Eqs (11) and (16). We see that the computer numerical simulations are in accordance with theory results obtained from equation. On the other hand, as discussed above, the minimum number N_D of driver nodes of the two networks increases exponentially as the iteration step t increase, as reflected in Eqs (11) and (16). Moreover, Fig 4 shows that the N_D of the two networks are totally different. The size of N_D in the (2, 2)-flower network is more than the (1, 3)-flower network. This indicates that the (1, 3)-flower network is easier to control. The Fig 5 shows both limits of the two networks’ controllability measure n_D converge to the constant lower than 1, as predicted by Eqs (12), (13), (17) and (18). The controllability measure n_D of the (1, 3)-flower network falls faster and tends to a constant $\frac{1}{4}$ , and the n_D of the (2, 2)-flower network tends to $\frac{1}{2}$ . It shows that the (1, 3)-flower network is much more easily controlled.

Download:

Fig 4. The minimum number of driver nodes N_D of the two networks increased with s.

CSR denotes the results by computer simulation. AR denotes the results predicted by Eqs (11) and (16) in two networks. Two networks are iterated to step 7. For the two networks, the CSR and AR are exactly same, respectively. But the N_D of the (2, 2)-flower network is more than the (1, 3)-flower network.

https://doi.org/10.1371/journal.pone.0127545.g004

Download:

Fig 5. Controllability measure n_D is a function of iteration step s for the (2, 2) flower network and the (1, 3)-flower network, respectively.

CSR denotes the results by computer simulation. AR denotes the results predicted by Eqs (12) and (17) for the two networks. Limit denotes the thermodynamic limit predicted by Eqs (13) and (18). The two networks are iterated to step 7. For the (2, 2)-flower network, three curves of CRS, AR and Limit are coincide. For the (1, 3) flower network, three curves of CRS, AR and Limit are almost entirely the same at s ≥ 4.

https://doi.org/10.1371/journal.pone.0127545.g005

Numerical analysis of (x, y)-flower networks In order to verify that a class of network with the identical degree sequence have different controllability, we give the simulation results of (x, y)-flower networks. We compare the controllability of (x, y)-flower networks, and obtain the same conclusions with (1, 3)-flower networks and (2, 2)-flower network. That is, for (x, y)-flower networks, the networks of x = 1 have the identical degree distribution with the networks at x = y, but their controllability are different. Fig 5 shows that the controllability measure of networks for x = 1 and x = y. In the simulation, we give the controllability measure n_D with fixed x+y = 6, 8, 10 and 12, respectively. Fig 6 shows that the n_D of each network tends a constant lower than 1, and the controllability of each other is different. Furthermore, Fig 6 shows that the ratios of n_D for the network with x = 1 and x = y, all ratios are lower than 1. According to the results of Fig 7, the networks of x = 1 is controlled easy than the networks of x = y.

Download:

Fig 6. Controllability measure n_D of the (x, y) flower networks at different iteration s.

Controllability measure n_D is a function of iteration step s for the (x, y) flower networks, where we take x+y = 6, 8, 10 and 12 respectively. These networks are iterated to step 5. The controllability measure are equal of all networks at s = 0, after start to fall at s > 0, and converges a constant lower than 1 at s > 4.

https://doi.org/10.1371/journal.pone.0127545.g006

Download:

Fig 7. The ratio of the n_D for x = 1 and x = y.

All ratios both are lower than 1.

https://doi.org/10.1371/journal.pone.0127545.g007

Conclusions and discussion

In this paper, we investigate the controllability of a class of deterministic networks with the identical degree sequence. The family of (x, y)-flower networks are deterministic networks and have the same degree sequence. They have many good properties such as scale-free, non-clustered; the networks of x = 1 are small-world, but the networks of x = y are large world. Hence, it is worthwhile to investigate the processes taking place upon the model to find the different impact on dynamic processes. The family of (x, y)-flower networks are sparse deterministic networks with fractal characteristics, according the exact controllability theory, their controllability are completely determined by the rank of their adjacency matrix of the network. Due to the self-similarity of networks, we derived an exact expression of the minimum driver nodes for the (1, 3)-flower network and the (2, 2)-flower network by exactly controllability theory. Theoretical analysis and simulation results show that though the (1, 3)-flower network and (2, 2)-flower network have the identical degree sequence, their controllability are entirely different. Meanwhile, by comparing the controllability measure of (x, y)-flower networks, we find that the degree distributions of the networks x = 1 are identical with x = y, but they have different controllability. Moreover, the networks of x = 1 are display better controllability than the networks of x = y. The results indicate that the degree distribution alone is not sufficient to characterize the controllability of deterministic scale-free networks with unweight and undirect. Then, an important question arises: For the unweighted and undirected networks, which structural property has the decisive effect on the controllability in network with identical degree sequence? In the Ref [33] the authors studied the thresholds of bond percolation in the (x, y)-flower networks, which indicated that the thresholds of bond percolation of the networks x = 1 are smaller than the x = y. In recent years, some new results about the entropy of graphs are obtained [29, 32, 38, 40–42]. In the Ref [32, 38] the authors studied the entropy of the spanning trees of two networks, and they got similar results that the entropy of the spanning trees in the networks x = 1 are smaller than x = y. Thus, it is a worthwhile to studying the relation between the controllability, the thresholds and the spanning trees.

Supporting Information

S1 File. This file includes the process how to calculate the rank of the adjacency matrix in F_t(1, 3) network and F_t(2, 2) network.

https://doi.org/10.1371/journal.pone.0127545.s001

(PDF)

Acknowledgments

This work is supported by NSFC (Grant Nos. 61164005, 11275186, 91024026), Key Laboratory of Tibetan intelligent information processing and machine translation (Qinghai normal university) of Qinghai P.R.C(Grant No.2013-Z-Y17), The Open Funding Programme of Joint Laboratory of Flight Vehicle Ocean-based Measurement and Control(Grant No. FOM2014OF001) and Research Fund for the Chunhui Program of Ministry of Education of China (Grant No.Z2012101).

Author Contributions

Conceived and designed the experiments: XM HZ. Performed the experiments: XM HZ. Analyzed the data: XM HZ. Contributed reagents/materials/analysis tools: XM HZ. Wrote the paper: XM HZ BW. Gave useful advice: BW.

References

1. Kelly FP, Maulloo AK, Tan DK. Rate control for communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research society. 1998;p. 237–252.
- View Article
- Google Scholar
2. Wang XF, Chen G. Pinning control of scale-free dynamical networks. Physica A: Statistical Mechanics and its Applications. 2002;310(3):521–531.
- View Article
- Google Scholar
3. Srikant R. The mathematics of Internet congestion control. Springer Science & Business Media; 2004.
4. Sorrentino F, di Bernardo M, Garofalo F, Chen G. Controllability of complex networks via pinning. Physical Review E. 2007;75(4):046103.
- View Article
- Google Scholar
5. Yu W, Chen G, Lü J. On pinning synchronization of complex dynamical networks. Automatica. 2009;45(2):429–435.
- View Article
- Google Scholar
6. Rahmani A, Ji M, Mesbahi M, Egerstedt M. Controllability of multi-agent systems from a graph-theoretic perspective. SIAM Journal on Control and Optimization. 2009;48(1):162–186.
- View Article
- Google Scholar
7. Liu YY, Slotine JJ, Barabási AL. Controllability of complex networks. Nature. 2011;473(7346):167–173. pmid:21562557
- View Article
- PubMed/NCBI
- Google Scholar
8. Egerstedt M, Martini S, Cao M, Camlibel K, Bicchi A. Interacting with networks: How does structure relate to controllability in single-leader, consensus networks? Control Systems, IEEE. 2012;32(4):66–73.
- View Article
- Google Scholar
9. Wang WX, Ni X, Lai YC, Grebogi C. Optimizing controllability of complex networks by minimum structural perturbations. Physical Review E. 2012;85(2):026115.
- View Article
- Google Scholar
10. Nepusz T, Vicsek T. Controlling edge dynamics in complex networks. Nature Physics. 2012;8(7):568–573.
- View Article
- Google Scholar
11. Yuan Z, Zhao C, Di Z, Wang WX, Lai YC. Exact controllability of complex networks. Nature communications. 2013;4.
- View Article
- Google Scholar
12. Jia T, Liu YY, Csóka E, Pósfai M, Slotine JJ, Barabási AL. Emergence of bimodality in controlling complex networks. Nature communications. 2013;4.
- View Article
- Google Scholar
13. Jia T, Barabási AL. Control capacity and a random sampling method in exploring controllability of complex networks. Scientific reports. 2013;3.
- View Article
- Google Scholar
14. Pósfai M, Liu YY, Slotine JJ, Barabási AL. Effect of correlations on network controllability. Scientific reports. 2013;3. pmid:23323210
- View Article
- PubMed/NCBI
- Google Scholar
15. Zhao C, Wang WX, Liu YY, Slotine JJ. Universal Symmetry in Complex Network Control. arXiv preprint arXiv:14030041. 2014;.
16. Nie S, Wang X, Zhang H, Li Q, Wang B. Robustness of controllability for networks based on edge-attack. PloS one. 2014;9(2):e89066. pmid:24586507
- View Article
- PubMed/NCBI
- Google Scholar
17. Li J, Yuan Z, Fan Y, Wang WX, Di Z. Controllability of fractal networks: An analytical approach. EPL (Europhysics Letters). 2014;105(5):58001.
- View Article
- Google Scholar
18. Yuan Z, Zhao C, Wang WX, Di Z, Lai YC. Exact controllability of multiplex networks. New Journal of Physics. 2014;16(10):103036.
- View Article
- Google Scholar
19. Kraus V, Dehmer M, Emmert-Streib F. Probabilistic inequalities for evaluating structural network measures. Information Sciences. 2014;.
- View Article
- Google Scholar
20. Li RH, Yu JX, Huang X, Cheng H, Shang Z. Measuring the impact of MVC attack in large complex networks. Information Sciences. 2014;278:685–702.
- View Article
- Google Scholar
21. Dehmer M, Emmert-Streib F, Grabner M. A computational approach to construct a multivariate complete graph invariant. Information Sciences. 2014;260:200–208.
- View Article
- Google Scholar
22. Kalman RE. Mathematical description of linear dynamical systems. Journal of the Society for Industrial & Applied Mathematics, Series A: Control. 1963;1(2):152–192.
- View Article
- Google Scholar
23. Hautus M. Controllability and observability conditions of linear autonomous systems. PROCEEDINGS OF THE KONINKLIJKE NEDERLANDSE AKADEMIE VAN WETENSCHAPPEN SERIES A-MATHEMATICAL SCIENCES. 1969;72(5):443.
- View Article
- Google Scholar
24. Lin CT. Structural controllability. Automatic Control, IEEE Transactions on. 1974;19(3):201–208.
- View Article
- Google Scholar
25. Luenberger DG. Introduction to dynamic systems. John Wiley & Sons New York; 1979.
26. Chui CK, Chen G. Linear Systems and optimal control. Springer; 1989.
27. Slotine JJE, Weiping L. Applied nonlinear control. vol. 60. Prentice-Hall Englewood Cliffs, NJ; 1991.
28. Rugh WJ. Linear system theory. vol. 2. prentice hall Upper Saddle River, NJ; 1996.
29. Antsaklis PJ, Michel AN. Linear systems. Springer Science & Business Media; 2006.
30. Sontag ED. Mathematical control theory: deterministic finite dimensional systems. vol. 6. Springer Science & Business Media; 1998.
31. Barabási AL, Ravasz E, Vicsek T. Deterministic scale-free networks. Physica A: Statistical Mechanics and its Applications. 2001;299(3):559–564.
- View Article
- Google Scholar
32. Rozenfeld HD, Ben-Avraham D. Percolation in hierarchical scale-free nets. Physical Review E. 2007;75(6):061102.
- View Article
- Google Scholar
33. Lin Y, Wu B, Zhang Z, Chen G. Counting spanning trees in self-similar networks by evaluating determinants. Journal of Mathematical Physics. 2011;52(11):113303.
- View Article
- Google Scholar
34. Song C, Havlin S, Makse HA. Self-similarity of complex networks. Nature. 2005;433(7024):392–395. pmid:15674285
- View Article
- PubMed/NCBI
- Google Scholar
35. Song C, Havlin S, Makse HA. Origins of fractality in the growth of complex networks. Nature Physics. 2006;2(4):275–281.
- View Article
- Google Scholar
36. Zhang Z, Hu Z, Sheng Y, Chen G. Exact eigenvalue spectrum of a class of fractal scale-free networks. EPL (Europhysics Letters). 2012;99(1):10007.
- View Article
- Google Scholar
37. Dehmer M, Emmert-Streib F, Shi Y. Interrelations of graph distance measures based on topological indices. PloS one. 2014;9(4):e94985. pmid:24759679
- View Article
- PubMed/NCBI
- Google Scholar
38. Zhang Z, Zhou S, Zou T, Chen L, Guan J. Different thresholds of bond percolation in scale-free networks with identical degree sequence. Physical Review E. 2009;79(3):031110.
- View Article
- Google Scholar
39. Newman ME. Fast algorithm for detecting community structure in networks. Physical review E. 2004;69(6):066133.
- View Article
- Google Scholar
40. Cao S, Dehmer M, Shi Y. Extremality of degree-based graph entropies. Information Sciences. 2014;278:22–33.
- View Article
- Google Scholar
41. Chen Z, Dehmer M, Emmert-Streib F, Shi Y. Entropy bounds for dendrimers. Applied Mathematics and Computation. 2014;242:462–472.
- View Article
- Google Scholar
42. Chen Z, Dehmer M, Shi Y. A Note on Distance-based Graph Entropies. Entropy. 2014;16(10):5416–5427.
- View Article
- Google Scholar

[ref1] 1. Kelly FP, Maulloo AK, Tan DK. Rate control for communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research society. 1998;p. 237–252.
View Article
Google Scholar

[2] View Article

[3] Google Scholar

[ref2] 2. Wang XF, Chen G. Pinning control of scale-free dynamical networks. Physica A: Statistical Mechanics and its Applications. 2002;310(3):521–531.
View Article
Google Scholar

[5] View Article

[6] Google Scholar

[ref3] 3. Srikant R. The mathematics of Internet congestion control. Springer Science & Business Media; 2004.

[ref4] 4. Sorrentino F, di Bernardo M, Garofalo F, Chen G. Controllability of complex networks via pinning. Physical Review E. 2007;75(4):046103.
View Article
Google Scholar

[9] View Article

[10] Google Scholar

[ref5] 5. Yu W, Chen G, Lü J. On pinning synchronization of complex dynamical networks. Automatica. 2009;45(2):429–435.
View Article
Google Scholar

[12] View Article

[13] Google Scholar

[ref6] 6. Rahmani A, Ji M, Mesbahi M, Egerstedt M. Controllability of multi-agent systems from a graph-theoretic perspective. SIAM Journal on Control and Optimization. 2009;48(1):162–186.
View Article
Google Scholar

[15] View Article

[16] Google Scholar

[ref7] 7. Liu YY, Slotine JJ, Barabási AL. Controllability of complex networks. Nature. 2011;473(7346):167–173. pmid:21562557
View Article
PubMed/NCBI
Google Scholar

[18] View Article

[19] PubMed/NCBI

[20] Google Scholar

[ref8] 8. Egerstedt M, Martini S, Cao M, Camlibel K, Bicchi A. Interacting with networks: How does structure relate to controllability in single-leader, consensus networks? Control Systems, IEEE. 2012;32(4):66–73.
View Article
Google Scholar

[22] View Article

[23] Google Scholar

[ref9] 9. Wang WX, Ni X, Lai YC, Grebogi C. Optimizing controllability of complex networks by minimum structural perturbations. Physical Review E. 2012;85(2):026115.
View Article
Google Scholar

[25] View Article

[26] Google Scholar

[ref10] 10. Nepusz T, Vicsek T. Controlling edge dynamics in complex networks. Nature Physics. 2012;8(7):568–573.
View Article
Google Scholar

[28] View Article

[29] Google Scholar

[ref11] 11. Yuan Z, Zhao C, Di Z, Wang WX, Lai YC. Exact controllability of complex networks. Nature communications. 2013;4.
View Article
Google Scholar

[31] View Article

[32] Google Scholar

[ref12] 12. Jia T, Liu YY, Csóka E, Pósfai M, Slotine JJ, Barabási AL. Emergence of bimodality in controlling complex networks. Nature communications. 2013;4.
View Article
Google Scholar

[34] View Article

[35] Google Scholar

[ref13] 13. Jia T, Barabási AL. Control capacity and a random sampling method in exploring controllability of complex networks. Scientific reports. 2013;3.
View Article
Google Scholar

[37] View Article

[38] Google Scholar

[ref14] 14. Pósfai M, Liu YY, Slotine JJ, Barabási AL. Effect of correlations on network controllability. Scientific reports. 2013;3. pmid:23323210
View Article
PubMed/NCBI
Google Scholar

[40] View Article

[41] PubMed/NCBI

[42] Google Scholar

[ref15] 15. Zhao C, Wang WX, Liu YY, Slotine JJ. Universal Symmetry in Complex Network Control. arXiv preprint arXiv:14030041. 2014;.

[ref16] 16. Nie S, Wang X, Zhang H, Li Q, Wang B. Robustness of controllability for networks based on edge-attack. PloS one. 2014;9(2):e89066. pmid:24586507
View Article
PubMed/NCBI
Google Scholar

[45] View Article

[46] PubMed/NCBI

[47] Google Scholar

[ref17] 17. Li J, Yuan Z, Fan Y, Wang WX, Di Z. Controllability of fractal networks: An analytical approach. EPL (Europhysics Letters). 2014;105(5):58001.
View Article
Google Scholar

[49] View Article

[50] Google Scholar

[ref18] 18. Yuan Z, Zhao C, Wang WX, Di Z, Lai YC. Exact controllability of multiplex networks. New Journal of Physics. 2014;16(10):103036.
View Article
Google Scholar

[52] View Article

[53] Google Scholar

[ref19] 19. Kraus V, Dehmer M, Emmert-Streib F. Probabilistic inequalities for evaluating structural network measures. Information Sciences. 2014;.
View Article
Google Scholar

[55] View Article

[56] Google Scholar

[ref20] 20. Li RH, Yu JX, Huang X, Cheng H, Shang Z. Measuring the impact of MVC attack in large complex networks. Information Sciences. 2014;278:685–702.
View Article
Google Scholar

[58] View Article

[59] Google Scholar

[ref21] 21. Dehmer M, Emmert-Streib F, Grabner M. A computational approach to construct a multivariate complete graph invariant. Information Sciences. 2014;260:200–208.
View Article
Google Scholar

[61] View Article

[62] Google Scholar

[ref22] 22. Kalman RE. Mathematical description of linear dynamical systems. Journal of the Society for Industrial & Applied Mathematics, Series A: Control. 1963;1(2):152–192.
View Article
Google Scholar

[64] View Article

[65] Google Scholar

[ref23] 23. Hautus M. Controllability and observability conditions of linear autonomous systems. PROCEEDINGS OF THE KONINKLIJKE NEDERLANDSE AKADEMIE VAN WETENSCHAPPEN SERIES A-MATHEMATICAL SCIENCES. 1969;72(5):443.
View Article
Google Scholar

[67] View Article

[68] Google Scholar

[ref24] 24. Lin CT. Structural controllability. Automatic Control, IEEE Transactions on. 1974;19(3):201–208.
View Article
Google Scholar

[70] View Article

[71] Google Scholar

[ref25] 25. Luenberger DG. Introduction to dynamic systems. John Wiley & Sons New York; 1979.

[ref26] 26. Chui CK, Chen G. Linear Systems and optimal control. Springer; 1989.

[ref27] 27. Slotine JJE, Weiping L. Applied nonlinear control. vol. 60. Prentice-Hall Englewood Cliffs, NJ; 1991.

[ref28] 28. Rugh WJ. Linear system theory. vol. 2. prentice hall Upper Saddle River, NJ; 1996.

[ref29] 29. Antsaklis PJ, Michel AN. Linear systems. Springer Science & Business Media; 2006.

[ref30] 30. Sontag ED. Mathematical control theory: deterministic finite dimensional systems. vol. 6. Springer Science & Business Media; 1998.

[ref31] 31. Barabási AL, Ravasz E, Vicsek T. Deterministic scale-free networks. Physica A: Statistical Mechanics and its Applications. 2001;299(3):559–564.
View Article
Google Scholar

[79] View Article

[80] Google Scholar

[ref32] 32. Rozenfeld HD, Ben-Avraham D. Percolation in hierarchical scale-free nets. Physical Review E. 2007;75(6):061102.
View Article
Google Scholar

[82] View Article

[83] Google Scholar

[ref33] 33. Lin Y, Wu B, Zhang Z, Chen G. Counting spanning trees in self-similar networks by evaluating determinants. Journal of Mathematical Physics. 2011;52(11):113303.
View Article
Google Scholar

[85] View Article

[86] Google Scholar

[ref34] 34. Song C, Havlin S, Makse HA. Self-similarity of complex networks. Nature. 2005;433(7024):392–395. pmid:15674285
View Article
PubMed/NCBI
Google Scholar

[88] View Article

[89] PubMed/NCBI

[90] Google Scholar

[ref35] 35. Song C, Havlin S, Makse HA. Origins of fractality in the growth of complex networks. Nature Physics. 2006;2(4):275–281.
View Article
Google Scholar

[92] View Article

[93] Google Scholar

[ref36] 36. Zhang Z, Hu Z, Sheng Y, Chen G. Exact eigenvalue spectrum of a class of fractal scale-free networks. EPL (Europhysics Letters). 2012;99(1):10007.
View Article
Google Scholar

[95] View Article

[96] Google Scholar

[ref37] 37. Dehmer M, Emmert-Streib F, Shi Y. Interrelations of graph distance measures based on topological indices. PloS one. 2014;9(4):e94985. pmid:24759679
View Article
PubMed/NCBI
Google Scholar

[98] View Article

[99] PubMed/NCBI

[100] Google Scholar

[ref38] 38. Zhang Z, Zhou S, Zou T, Chen L, Guan J. Different thresholds of bond percolation in scale-free networks with identical degree sequence. Physical Review E. 2009;79(3):031110.
View Article
Google Scholar

[102] View Article

[103] Google Scholar

[ref39] 39. Newman ME. Fast algorithm for detecting community structure in networks. Physical review E. 2004;69(6):066133.
View Article
Google Scholar

[105] View Article

[106] Google Scholar

[ref40] 40. Cao S, Dehmer M, Shi Y. Extremality of degree-based graph entropies. Information Sciences. 2014;278:22–33.
View Article
Google Scholar

[108] View Article

[109] Google Scholar

[ref41] 41. Chen Z, Dehmer M, Emmert-Streib F, Shi Y. Entropy bounds for dendrimers. Applied Mathematics and Computation. 2014;242:462–472.
View Article
Google Scholar

[111] View Article

[112] Google Scholar

[ref42] 42. Chen Z, Dehmer M, Shi Y. A Note on Distance-based Graph Entropies. Entropy. 2014;16(10):5416–5427.
View Article
Google Scholar

[114] View Article

[115] Google Scholar

Figures

Abstract

Introduction

Model

Model and properties of (x, y)-flower

Exact controllability theory

Analysis

The controllability of (1, 3)-flower network

The controllability of (2, 2)-flower network

Numerical analysis

Conclusions and discussion

Supporting Information

S1 File. This file includes the process how to calculate the rank of the adjacency matrix in Ft(1, 3) network and Ft(2, 2) network.

Acknowledgments

Author Contributions

References

S1 File. This file includes the process how to calculate the rank of the adjacency matrix in F_t(1, 3) network and F_t(2, 2) network.