# The Exact Controllability of the Molecular Graph Networks

Authors: Liang Wei; Faxu Li; Haixing Zhao; Bo Deng; Zhonglin Ye
Journal: Journal of Chemistry
 (2019)

---

## Abstract

In this paper, we mainly study the exact controllability of several types of extended-path molecular graph networks. Based on the construction of extended-path molecular graph networks withC3, C4, or K4, using the determinant operation of the matrix and the recursive method, the exact characteristic polynomial of these networks is deduced. According to the definition of minimum driver node number ND, the exact controllability of these networks is obtained. Moreover, we give the minimum driver node sets of partial small networks.


---

## Body

## 1. Introduction

In recent years, the research on complex network is one of the hottest research fields, and controllability of complex network is a challenging problem in modern network science, such as molecular graph networks, computer networks, social networks, biological networks, and transportation networks [1–8]. The study of network structure has always been a basic object in complex network research. The majority of core issues of research in many fields are based on the structure of the networks, such as connectivity, robustness, and controllability of networks.In chemical graph theory, the vertices represent each atom and the edges represent the bonds between them in the molecule, and the corresponding molecular graph represents different chemical structures when they represent different things. Figure1(a) shows the representation of two small molecular structures. As the molecular scale increases, the molecular graph structure gradually becomes a complex system, an example as shown in Figure 1(b). Generally, researchers investigate the related problems of complex systems with large molecular structure by using methods of studying complex networks. In addition, molecular graphs can be used to express some topological properties of molecules. The topological properties of molecules with the same connected structure should be identical. The quantity describing the topological properties of molecules is topological invariants of molecular graphs, such as number of nodes, number of edges, shortest distance, and spectrum. In order to quantify the topological properties of molecules, researchers proposed a lot of indexes, such as Wiener index, Randic index, Hosoya index, Merrifield–Simmons index, and molecular information index.Figure 1
Transformation from molecular structure to molecular graph network. Representation of (a) two small molecular structures and (b) a large molecular structure.
(a)
(b)With the development of network science, people begin to pay much attention to study how to control some nodes in the network to achieve the desirable goals, namely, making the network controllable. The structural controllability of molecular graphs is studied as a molecular topological index. Lin firstly gives the concept of structural controllability in the literature [9] and presents the structural controllability theorem. In the literature [10], the structural controllability theorem is applied to the directed and unweighted complex networks, and the maximum matching theory and the minimum input theorem of structural controllability are proposed.However, when the edges of the networks are undirected or weighted, the previous theory is not suitable for this type of networks. Then, researchers present another theory framework, which is the exact controllability analysis of the complex network. Yuan et al. [11] proves that the number of driver nodes of a network is equal to the maximum geometric multiplicity and gives a method to solve the minimum set of driver nodes. In [12], Wu et al. constructs a star-type network and gives its characteristic polynomial, which directly expresses the exact controllability of this kind of complex networks. Furthermore, research on controllability of multilayer networks and fractal networks, which is common in the chemical system, has some results [13, 14].In chemistry, hexagonal chain and polyomino chain are two kinds of classical linear systems. In order to observe different linear systems, we consider the controllability of complex networks with linear dynamics. A network withN nodes is described by the following set of ordinary differential equations [15]:(1)x˙=Ax+Bu,where x=x1,x2,x3…,xNT is the status of nodes, A∈RN×N denotes the coupling matrix of the system, in which aij represents the weight of a link i,j and u=u1,u2,u3…,uMT is the status of M controllers, and B is the control matrix with the size of N×M. In classic control theory, the system (1) can be controlled from any initial state to any final state with finite time if and only if(2)rankB,AB,A2B,…,AN−1B=N.Generally, solving the controllability problems is to construct a suitable control matrixB, which consists of a minimum set of driver nodes for satisfying the Kalman rank condition [16]. And there are many possible control matrices B for system (1), which satisfies the controllable condition. The main task of exact controllability is to find a set of B corresponding to the minimum number ND of controllers, which can control the whole network. Then, it is important to measure the exact controllability of the system (1). For undirected graphs, the system controllability can be given by the following terms:(3)ND=maxiδλi,where δλi is the algebraic multiplicity of eigenvalue of matrix A. It is well known that the theory of graph spectra is related to the chemistry through the HMO (Huckel Molecular Orbital) theory [1]. At an early stage, it was supposed that HMO theory could be reduced to the study of graph spectra of the adjacency matrix of molecular graphs.In subsequent sections, we mainly discuss the undirected graph with link unweight. Firstly, we give some construction methods of the extended-path molecular graph networks. By using the controllability theory in Sections3 and 4, we then analyze the exact controllability of these networks and characterize all minimum sets of driver nodes of partial small networks by simulation.


## 2. Construction of the Extended-Path Networks

In real world, we can find a class of regular networks [17–19], which is constructed like a path network, and each component looks like a star, circle, or clique. In order to carry out our research, we must construct some networks with such characteristics.Firstly, we give the construction method of theH-extended-path networks (H-EPN), which is composed of several subgraphs pasted together by one common node. As shown in Figure 2(b), H-EPN is composed of subgraph H, the number of H is N, and it satisfies that every two subgraph are connected by one common node. In other words, each edge of the path (Figure 2(a)) can be extended by a subgraph H, which can be connected to each other at a common node. We likewise construct several types of H-EPNs as shown in Figures 3(a)–3(d).Figure 2
Construction of extended-path networks. (a) Path networks. (b) Extended-path networks.
(a)
(b)Figure 3
H-EPN extended by C3,C4,andK4. (a) C3-EPN. (b) C4-EPN1. (c) C4-EPN2. (d) K4-EPN.
(a)
(b)
(c)
(d)


## 3. Main Results

In this section, we will study the exact controllability of several extended-path networks, which are extended byC3, C4, and K4.The adjacent matrix ofC3-EPN can be formalized as follows:(4)A=01110111011101110….Therefore, we can obtain the characteristic polynomial of the coupling matrixA of C3-EPN with 2N+1 nodes. For convenience, we use B2N+1 to represent the determinant of matrix λI−A as follows:(5)λI−A=B2N+1=λ−1−1−1λ−1−1−1λ−1−1−1λ−1−1−1λ…=λ2−1B2N−1−2λ+1C2N−2,where(6)C2N−2=λ−1−1λ−1−1−1λ−1−1−1λ….Thus, it follows that(7)B2N+1=λ2−1B2N−1−2λ+1C2N−2,(8)C2N−2=λB2N−3+λC2N−4.According to the equations (7) and (8), we have(9)B2N+1−λ2+λ−1B2N−1+λ3+2λ2+λB2N−3=0.For convenience of calculation, takeSN=B2N+1. Then,(10)SN−1=B2N−1,SN−2=B2N−3.So we have(11)SN−λ2+λ−1SN−1+λ3+2λ2+λSN−2=0.According to the recursive method in the theory of the determinant, the characteristic equation of recursive relations [11] is given by(12)m2−λ2+λ−1m+λ3+2λ2+λ=0.It is easy to get(13)m1=λ2+λ−1+p2,m2=λ2+λ−1−p2,where p=λ4−2λ3−9λ2−6λ+1.Thus, we give the form of solution ofSN in the following expression:(14)SN=k1m1N+k2m2N.ForS0=B1=λ and S1=B3=λ3−3λ−2, we have k1+k2=λ and k1m1+k2m2=λ3−3λ−2.So we get(15)k1=λ3−3λ−2−λm2m1−m2=1pλ3−3λ−2−λm2,k2=λ3−3λ−2−λm1m1−m2=1pλ3−3λ−2−λm1.After an arrangement of equations (13)–(15), we have(16)SN=k1m1N+k2m2N=12pλ+12λ−2m1N−m2N−λ2m1N−1−m2N−1.According to equations (5) and (10), the characteristic polynomial of matrix A is as follows:(17)λI−A=B2N+1=SN=12pλ+12λ−2m1N−m2N−λ2m1N−1−m2N−1.Letgλ=λ−2m1N−m2N−λ2m1N−1−m2N−1, then it is easy to get that g−1≠0, g1≠0, and g0≠0. So the multiplicity of eigenvalue −1 is 2. Now, we discuss the multiplicity of the remaining eigenvalues. We all know from equations (7) and (9) that if there is an eigenvalue λ0 making B2N+1=0 and suppose that C2N−2=0, then it must be B2N−1=0 and B2N−3=0 (note that 1 and 0 are not roots of the B2N+1=0), which is a contradiction with λ0 being the root of all B2i+1λ0=0,i=1,2,…,N.Now, we show that there is a principal minor determinant of order2N for B2N+1 such that the value is not 0 as follows:(18)A′=λ−1−1λλ−1−1λ−1−1−1λ−1−1−1λ…=λ−1−1λC2N−2,which is constructed by deleting the 3th row and the 3th volume of B2N+1. For C2N−2≠0 and λ−1−1λ≠0 when λ≠−1, we have A′≠0. By B2N+1=0 and A′≠0 in the case of λ≠−1, we see that the rank of the corresponding matrix of B2N+1 is 2N. Then, for all the eigenvalues λ≠−1, its multiplicity is 1. So we know that all roots of B2N+1=0 are distinct except −1.According to the above analysis, it can be known that the maximum multiplicity of the solution of the equation (17) is 2. Therefore, we get the minimum number of driver nodes in the C3-EPN as follows:(19)ND=2.Using the same way, we investigate the exact controllability of theC4-EPN1. The adjacent matrix A of the C4-EPN1 can be formalized as follows:(20)A=0101101001011010101101001011010….We obtain the characteristic polynomial of the matrixA as follows:(21)λI−A=λ−10−1−1λ−100−1λ−1−10−1λ−10−1−1λ−100−1λ−1−10−1λ….LetB3N+1=λI−A, and taking a series of determinant operations, one gets the form as follows:(22)B3N+1=λI−A=λ2C3N−1−2λB3N−2,(23)C3N−1=λB3N−2−2D3N−3,(24)D3N−3=λ2−1B3N−5−λD3N−6,where C3N−1 and D3N−3 are determinants with the size of 3N−1×3N−1 and 3N−3×3N−3, respectively. We can formalise them as follows:(25)C3N−1=λ−1−2λ−10−1−1λ−100−1λ−1−10−1λ…,D3N−3=λ−10−1λ−10−1λ−10−1−1λ−100−1λ−1−10−1λ….Through the equations (22)–(24), we get the following form of recurrence relationship:(26)B3N+1=λ3−3λB3N−2−λ4B3N−5.Now, let us defineSN=B3N+1,SN−1=B3N−2,andSN−2=B3N−5, then the equation (26) can be formalized as(27)SN=λ3−3λSN−1−λ4SN−2.According to the above definitions and equation (27), we have S0=B1=λ and S1=B4=λ2λ2−4, so(28)S2=λ3−3λS1−λ4S0=λ3λ4−8λ2+12=λ3f2λ,where fix represents the i-th polynomial about x, for which the lowest order is 0. Fox example, f0λ=1, f1λ=λ2−4, and f2λ=λ4−8λ2+12. Obviously, we can get remaining items formalized as(29)S3=λ3−3λS2−λ4S1=λ4f3λ,S4=λ3−3λS3−λ4S2=λ5f4λ,…SN=λ3−3λSN−1−λ4SN−2=λN+1fNλ.Using a simple induction and computation, we can easily get (29). That is to say, the lowest orders of polynomials S0, S1, S2, …, and SN are 1,2,3,…, and N+1, respectively, and the multiplicity of the eigenvalue 0 of SN is N+1. Since a connected graph with diameter D has at least D+1 distinct eigenvalues, noticing that the network C4-EPN1 with N cells has 3N+1 nodes and the diameter is N+2, we have that C4-EPN1 has at least N+3 distinct eigenvalues. However, the eigenvalue 0 has a multiplicity of N+1, and the remaining 2N eigenvalues have at least N+2 distinct, namely, the maximum multiplicity of these eigenvalues shall not exceed N−1. Therefore, the maximum multiplicity of C4-EPN1’s eigenvalues is N+1 (the eigenvalue is 0). Thus, the minimum number of driver nodes of the system corresponding to the graph C4-EPN1 is as follows:(30)ND=N+1.By the analytical method of the preceding part, we can obtain the recursive relations of characteristic polynomial ofC4-EPN2 and K4-EPN (see (31) and (32)) as follows:(31)SN=λ3−4λSN−1−λ4SN−2=λN+1fNλ,(32)SN=λ+1λ2−λ−4SN−1−λ+14SN−2=λ+1N+2fNλ+1.Using a method similar to that of theC3-EPN and C4-EPN1, it is easy to get that the minimum number of driver nodes of C4-EPN2 and K4-EPN, shown in Table 1.Table 1
N
D of extended-path networks.
Networks
Number of cells
n
N
D
C
3-EPN
N
2
N
+
1
2
C
4-EPN1
N
3
N
+
1
N
+
1
C
4-EPN2
N
3
N
+
1
N
+
1
K
4-EPN
N
3
N
+
1
N
+
2


## 4. Characterization of Driver Nodes

The topology of the complex network determines the controllability, and the minimum driver nodes can quantitatively reflect the controllability of the network structures. Therefore, the minimum driver nodes are the key factors in the structural controllability analysis. In fact, evaluating the exact controllability of complex networks is to obtain the minimum driver nodes of networks.Using the method based on the PBH rank criterion [11, 20], we can characterize the minimum driver node set in detail. The condition of the full rank of the matrix λI−AB is(1)
MatrixλI−A avoids zero vector(2)
MatrixλI−A avoids repetitive vector(3)
MatrixλI−A avoids correlation vectorBecause of the symmetry of graph structures, the minimum driver nodes set is not unique and its number is mainly determined by three factors such as zero row vector, repetitive row vector, and correlation row vector ofλI−A.Let zero vector havex rows, repetitive row vector have y groups, in which each group has r1,r2,…,ry rows, and the correlation row vectors have z groups, in which each group has c1,c2,…,cz rows; then, the number of the minimum driver nodes ND and the number of groups obtained NC are shown in Table 2.Table 2
N
D and NC of three kinds of situations.
Case
N
D
N
C
Zero row vector
x
1
Repetitive row vector
∑
i
=
1
y
r
i
−
1
∏
i
=
1
y
C
r
i
r
i
−
1
Correlation row vector
z
∏
j
=
1
z
C
c
j
1Based on the above conditions, we design a corresponding algorithm to obtain the minimum driver nodes set. Through simulation analysis of Matlab platform, we compute the controllability, and describe all sets of minimal driver nodes ofC3-EPN, C4-EPN, and K4-EPN(N = 4, 5), respectively; they are shown in Tables 3, 4 and 5; H-EPNs of N=4 are shown in Figure 4.Table 3
Controllability ofC3-EPN, C4-EPN, and K4-EPN (N = 4, 5).
Networks
Number of cell (N)
Number of nodes (n)
Minimum driver node (ND)
Controllability (ND/n)
C
3-EPN
4
9
2
0.2222
C
4-EPN1
4
13
5
0.3846
C
4-EPN2
4
13
5
0.3846
K
4-EPN
4
13
6
0.4615
C
3-EPN
5
11
2
0.1818
C
4-EPN1
5
16
6
0.3750
C
4-EPN2
5
16
6
0.3750
K
4-EPN
5
16
7
0.4375Table 4
Minimum driver nodes set ofC3-EPN, C4-EPN, and K4-EPN (N = 4).
Networks
Minimum driver node set
C
3-EPN
n
1
,
n
2
n
1
∈
1,2
,
n
2
∈
8,9
C
4-EPN1
1
,
n
1
,
n
2
,
n
3
,
n
4
n
1
∈
2,3
,
n
2
∈
5,6
,
n
3
∈
8,9
,
n
4
∈
11,12
,
or
n
1
,
n
2
,
n
3
,
n
4,13
n
1
∈
2,3
,
n
2
∈
5,6
,
n
3
∈
8,9
,
n
4
∈
11,12
C
4-EPN2
n
1,10,11,12,13
n
1
∈
1,3
,
or
1,2,3,4
,
n
1
n
1
∈
11,13
K
4-EPN
n
1
,
n
2
,
n
3
,
n
4
,
n
5
,
n
6
n
1
∈
1,2,3
,
n
2
∈
1,2,3
,
n
1
≠
n
2
,
n
3
∈
5,6
,
n
4
∈
8,9
,
n
5
∈
11,12,13
,
n
6
∈
11,12,13
,
n
5
≠
n
6Table 5
Minimum driver node set ofC3-EPN, C4-EPN, and K4-EPN (N = 5).
Networks
Minimum driver node set
C
3-EPN
n
1
,
n
2
n
1
∈
1,2
,
n
2
∈
10,11
C
4-EPN1
1
,
n
1
,
n
2
,
n
3
,
n
4
,
n
5
n
1
∈
2,3
,
n
2
∈
5,6
,
n
3
∈
8,9
,
n
4
∈
11,12
,
n
5
∈
14,15
,
n
3
∈
8,9
,
n
4
∈
11,12
,
n
5
∈
14,15
C
4-EPN2
n
1,12,13,14,15,16
n
1
∈
1,3
,
or
1,2,3,4,5
,
n
1
n
2
∈
14,16
K
4-EPN
n
1
,
n
2
,
n
3
,
n
4
,
n
5
,
n
6
,
n
7
n
1
∈
1,2,3
,
n
2
∈
1,2,3
,
n
1
≠
n
2
,
n
3
∈
5,6
,
n
4
∈
8,9
,
n
5
∈
11,12
,
n
6
∈
14,15,16
,
n
7
∈
14,15,16
,
n
6
≠
n
7Figure 4
C
3-EPN, C4-EPN, and K4-EPN (N=4).
(a)
(b)
(c)
(d)The simulation results show that, in order to fully control these extended-path networks, the driver nodes selected are usually nodes with small degree, rather than the maximum degree nodes. The point is consistent with the conclusion in the literature [11]. And we can obtain from Table 3 that the C3-EPN has a fixed number of minimum driver node set, which can be fully controlled by minimal cost. Namely, the C3-EPN has higher controllability. In addition, although the structures of the C4-EPN1 and C4-EPN2 are different, we find that the controllability of the two networks is exactly the same in different network scales.


## 5. Conclusion

To summarize, we mainly study the controllability of several types of the extended-path molecular graph networks. The structural characteristics of these networks are linearly connected by a cycle or complete graph. For these special network structures, we derive the general formula of the characteristic polynomial of the network’s adjacent matrix. Furthermore, the exact controllability of these kinds of networks is analyzed, and some results are obtained. In addition, in order to directly reflect the concrete minimum driver node set of each network, we determine the distribution of the nodes by simulation.



---

*Source: 6073905-2019-11-30.xml*