{'fraction_non_alphanumeric': 0.05494602335316149, 'fraction_numerical': 0.0170522141440846, 'mean_word_length': 3.732276897414512, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Minimum leader selection for Structural Controllability of Undirected Graphs with Leader-follower Framework

The optimization problem of the minimum set of leaders for the controllability of undirected graphs are addressed. It is difficult to find not only its optimal solution but also its approximate algorithm. We propose a new concept, namely minimal perfect critical set (MPCS), to obtain an optimal solution. Some properties are presented, and on the basis of these theorems, the problem of the minimum set of leaders of two typical self-similar bipartite networks, namely deterministic scale-free networks (DSFN) and Cayley trees, is solved completely.


Introduction
In recent years, the controllability of undirected networks has attracted considerable attention. In contrast to the various insights and results on the controllability of directed networks, there remain many basic problems that need to be investigated with regard to the controllability of undirected networks. For example, to ensure the controllability of an undirected network, it is necessary to determine how to select the leader (leaders), what is the minimum number of leaders, how to get the minimum set of leaders, and how large is the minimum set of leaders. These problems are interesting because of their potential application to various fields such as complex networks, multi-agent systems, and biology.

Literature Review
Our goal is to address the problem of how to select leaders and how to obtain the minimum number and minimum set of leaders of Laplacian-based leader-follower undirected systems. Therefore, we review only the related studies. The networks mentioned throughout this paper are undirected networks, unless stated otherwise.
Research on the controllability of undirected network began with the work of Tanner [1], where both a leader-follower framework and a Laplacian matrix were considered to understand how the network structure and leader's location affect the controllability of a network. Many studies have been conducted since then. The methods used in this field mainly include spectral analysis, equitable partitions, zero forcing sets, balancing sets (see [17]), and constraint matching.
The necessary or sufficient algebraic conditions of the leader set in view of eigenvectors were presented for the controllability of a general network in [2]- [6]. Owing to the existence of multiple eigenvalues and the need to examine eigenvectors with zero components, it is computationally difficult to directly use the algebraic conditions to find the set of leaders. Therefore, network controllability based on the leader's graphical structure has attracted widespread attention.
In [7], the authors applied the concept of equitable partitions to the study of controllability and pointed out that some vertex sets with a symmetric character should not be selected as leaders. The necessary graph-theoretic conditions for controllability involving equitable partitions or almost equitable partitions were subsequently reported; see, for instance, [8]- [11].
The necessary/sufficient conditions for controllability based on (generalized) zero forcing sets have been established in the literature [12]- [18]. In these studies, a one-to-one correspondence was established between the set of leaders rendering the network controllable and the zero forcing sets.
Some studies, such as [16], [19]- [20], have focused on constraint matching to investigate controllability. A single leader and multiple leaders have been considered in [19] and [20], respectively. The relationship between zero forcing sets and constraint matching was discussed in [16].
The above-mentioned studies constitute the profound literature on the theoretical research of controllability. Some other studies are devoted to algorithm design. As pointed out in several studies, finding a minimal zero forcing set (see [16] ) or finding a minimum leader set (see [20]) for a general network is an NP-hard problem, as is finding an approximate solution (see [18]). Moreover, there are several different concepts of controllability in the field of network controllability, such as controllability as defined by Kalman in [21], structural controllability (defined by Lin in [22]), and strong structural controllability (defined by Mayeda and Yamada in [23]). The matrix can be defined as the adjacency matrix or Laplacian matrix with variable or fixed parameters. Thus, research on the controllability of networks is extensive.
Different from the existing studies, this paper proposes the concept of a minimal perfect critical set (MPCS) in section 2. In addition, it presents the necessary and sufficient conditions for S to be a minimal perfect critical 2 set and proves an interesting result that a minimal perfect critical 3 set does not exist. Section 3 constitutes the main part of this paper. It presents some special MPCS of tree graphs. Section 4 presents three examples to illustrate how to use the theories proposed to find MPCS . Finally, Section 5 concludes the paper.

Notations and Preliminary Results
Let G = (V, E) be an undirected and unweighted simple graph, where V = {v 1 , v 2 , · · · , v n } is a vertex set and E = {v i v j |v i and v j ∈ V } is an edge set, where an edge v i v j is an unordered pair of distinct vertices in V . If v i v j ∈ E, then v i and v j are said to be adjacent or neighbors.
The valency matrix ∆(G) of graph G is a diagonal matrix with rows and columns indexed by V , in which the (i, i)-entry is the degree of vertex v i , e.g., |N V (v i )|. Any undirected simple graph can be represented by its adjacency matrix, D(G), which is a symmetric matrix with 0-1 elements. The element in position (i, j) in D(G) is 1 if vertices v i and v j are adjacent and 0 otherwise. The symmetric matrix defined as is the Laplacian of G. Throughout this paper, it is assumed without loss of generality that F denotes a follower set; its vertices play the role of followers and the vertices in F are leaders(driver nodes), where F = V \F denotes the complement set of F . Let y be a vector and y S denote the vector obtained from y after deleting the elements in S. Let L S→T denote the matrix obtained from L after deleting the rows in S and columns in T . If the followers' dynamics is (see (4) in [1] where x is the vector of all x i corresponding to follower v i ∈ F and u is the external control input vector that is injected to only leaders, then, the system is controllable if and only if the N × N M controllability matrix has full row rank, where B = L F →F and A = L F →F . This mathematical condition for controllability is well known as Kalman's controllability rank condition [21,24,26]. In terms of eigenvalues and eigenvectors of Laplacian submatrices, a necessary and sufficient algebraic condition on controllability was presented in [2] and [6](see Proposition 2,1(2) in [2] and Proposition 1 in [6] ).
Proposition 1. [2,6] The undirected graph G is controllable under the leader set F if and only if y| F = 0 ( ∀ y is an eigenvector of L).
According to Proposition 1, for any S ⊂ V and S = ∅, if there exists an eigenvector y of Laplacian matrix L such that y S = 0, then S cannot be used as a leader set.

Minimal Perfect Critical Set
For a vertex set S, from Proposition 1, if there exist an eigenvector y such that y S = 0, then S should not be used as a leaders set. In other words, there must be a vertex v in S to be selected as a member of the leaders set. Therefore, to locate the leaders of graph G, three new concepts are proposed.
From Remark 1 , there is a close relationship between MPCS and the minimum leader set. In other words, when we find all MPCS of G, we find the minimum leader set and hence the minimum number of leader vertices. For example, by Remark 1 and the 4 MPCS stated above, graph G in Fig.1 is not controllable under any single leader because Therefore, the minimum number of leaders is 3.
Moreover, many MPCS have typical graphical characteristics. For example, all of the 4 MPCS of G in Fig.1 have the graphical structure stated in Theorem 1.

Sufficient conditions for Critical Set
For an undirected connected graph, Laplacian matrix L is symmetric and all the eigenvectors corresponding to different eigenvalues are orthogonal to each other. Hence, by knowing that 1 n is an eigenvector of L, it is immediate that all the other eigenvectors of L are orthogonal to 1 n , i.e., for all eigenvectors y, For all nontrivial graphs, if S is a CS, then In fact, suppose that |S| = 1; without loss of generality, S = {v 1 }. Let y = (y 1 , y 2 , · · · , y n ) T be the inducing eigenvector associated with eigenvalue λ. Then, Ly = λy and y S = 0. By y S = 0 and (1), y S = 0, e.g., y = 0. Further, since any subset S with |S| = 1 is not a CS, by Remark 1, G is controllable with the leader set F when |F | = 1. Now, we investigate the properties of a CS. First, a sufficient condition for S to be a CS is provided in the following Proposition 2, which describes a special case of the symmetry-based uncontrollability results.
Proposition 2. Let G be an undirected connected graph of order n, S ⊂ V , and |S| ≥ 2. If for (1), there exists an eigenvector y 0 of the Laplacian L S→S − mI |S| such that 1 T |S| y 0 = 0. Set vector y as y S = y 0 and y S = 0. It can be seen that Noting that the rows in matrix L S→S are either ones or zeros, the conclusion is proved by 1 T |S| y 0 = 0(see (1)).

Minimal Perfect Critical 2 and 3 Set
Based on the above-mentioned properties, the critical k set with k ≤ 3 can be determined directly from the graphical characterization. This is achieved via a detailed analysis of the inducing eigenvector.
Lemma 1. Let G be an undirected connected graph and S be a perfect critical k vertices set.
By (2), a critical 2 set is also a minimal perfect critical 2 set. The following Theorem 1 will follow from Lemma 1 and Proposition 2.
For example, see graph G in Fig.1. All its 4 MPCS can be recognized by the graphical characterization stated in Theorem 1.
Next, we will prove that a minimal perfect critical 3 set does not exist in the following theorem.
Noting that T ⊂ S and T = {u} S, by Proposition 2, T is a critical set. This is in contradiction with S as a MPCS.
is not a critical set

Minimal Perfect Critical Set of Trees
In this section, we first introduce a method for the simplification of G and then prove some properties of MPCS of trees.

Simplification GraphG
Let S be a proper subset of V (G). LetG denote a graph constructed in the following steps: S is a CS of a connected graph G if and only if S is a CS ofG. Further, λ is the corresponding eigenvalue of L(G) if and only if λ − 1,λ is an eigenvalue of L(G) in case 1 ○, 2 ○, respectively. Proof Let v 0 ∈S be a pendent vertex in tree G and u 0 be the vertex adjacent to v 0 . By Lemma 1, we have u 0 ∈S. Hence, S is still a PCS of tree graph

Necessities of MPCS of Trees
. Repeat these steps to obtain a tree graph G ′ with d G ′ (v) > 1(∀v ∈S). It is well known that there are at least two pendent vertices in a tree graph. Considering the tree graph G ′ , we know that the pendent vertices are all in S. This completes the proof.
By Remark 1 and Proposition 3, we have the following theorem: Theorem 3 tells us that when |S 0 | − 1 vertices in S 0 are selected as leaders, the graph will be controllable. Therefore, the minimum number of leaders is no more than |S 0 | − 1.
Next, we will study the property that the MPCS of trees should have. Proof Suppose that G[S] is a connected subgraph. Arbitrarily take a vertex v inS. By Lemma 1, there exist at least two vertices in S, say u 1 , u 2 such that vu i ∈ E(G)(i = 1, 2). Since G[S] is connected, there exists a circle C with u 1 , u 2 , v ∈ V (C) in G, and this is a contradiction to G being a tree.

Proposition 5. If S is a nontrivial MPCS of tree graph G, thenG[S] is a graph of isolated vertices.
Proof Suppose that there exists a component T ofG[S] that contains at least two vertices. See Fig.4. Then, T is a tree graph and there exist at least two pendent vertices of T , say u, v. Let P uv be the (u, v)-path in T and wv ∈ E(P uv ). Considering the disconnected graphG − wv, it is seen that u and v belong to different components. Let T 1 be the component that contains We claim that S 1 is a PCS. In fact, S u and S 1 belong to different components ofG − wv. Hence, the submatrix L S1→Su = 0. s T s s s Since S 1 is a PCS and S 1 ⊂ S, it is contradictory to the fact that S is an MPCS.

Proposition 6. If S is an MPCS of tree graph G, then dG(v) = 2(∀v ∈S).
Proof From Lemma 1, dG(v) = 1(∀v ∈S). From Proposition 5, N V (G) (v) ⊂ S(∀v ∈S). Suppose that there exists a vertex inS , say u , such that dG(u) = 2, i.e. dG(u) > 2. (see Fig.5). Considering the subgraphG − u, different vertices that are adjacent to u belong to different components ofG − u. Let T i be the component and v i ∈ V (T i )(i = 1, 2). Let S i = S ∩ V (T i )(i = 1, 2). Since G is a tree graph, we have S 1 ∩ S 2 = ∅. LetS = S 1 ∪ S 2 . From dG(u) > 2, we know thatS is a proper subset of S.
We claim thatS is a PCS. In fact, let y be the inducing eigenvector of MPCS S, where y i are its elements corresponding to v i (i = 1, 2) and y Si are its elements corresponding to S i . Let Then, we have LS →S yS = λyS and LS →S yS = 0. Therefore, [yS, 0] is a inducing eigenvector for S to be a PCS. This is a contradiction to the fact that S is an MPCS sinceS is a proper subset of S.

No Isolated MPCS with |S| ≥ 3 in Trees
In this subsection, it is proved that there is no MPCS with isolated vertex set S(|S| ≥ 3) for tree graph.  Proof Suppose that S is an MPCS and it is an isolated vertex set. Then, L S→S is a diagonal matrix. By L S→S y S = λy s , we know that d G (v) = λ(∀v ∈ S). Thus, all vertices in S have the same degree.
On the other hand, from Proposition3, there exist at least two vertices in S with degree 1. Hence, we have d G (v) = 1(∀v ∈ S).
Noting thatG[S ∪S] is a tree graph and from Proposition 6, we have Hence, |S| = 2. This is a contradiction to |S| ≥ 3. From Theorem 4 and Theorem 1, for the tree graph, the isolated vertex set S is an MPCS if and only if |S| = 2 and the two vertices in S are twin nodes.

A Type of Special MPCS of Trees
Considering the Laplacian matrix of graphG, similar to the proof of Theorem 4, it is seen that the following proposition holds. Proof By contrast, suppose that u v ∈ S. Then, by Lemma 1, we have v / ∈S. Hence, v ∈ S. From Proposition 7, we know that λ = 1. Since L v→V (G) y = λy v = y v , y v − y uv = y v and y uv = 0. This is a contradiction to u v ∈ S and S is an MPCS.
To prove the next property of MPCS, we first give the following lemma.
If n = 1, then a 11 = 0 and (a 11 + c 1 )x 1 = 0. Hence, c 1 = 0 since x 1 = 0. Assume that the lemma is true for each matrix of order lower than n(n ≥ 2). Let T be the given tree with n vertices and A be its Laplacian matrix. Let v 1 be a pendent vertex in T and v 2 be the only vertex adjacent to v 1 . Then, matrix A and matrix B have the following form: Let X 0 = (x 1 , x 2 , · · · , x n )(∀i, x i = 0) and BX 0 = 0. From the first row of BX 0 = 0, If c 1 = −1, then x 2 = 0 and this is a contradiction. Hence, c 1 = 0 and x 1 = x 2 . By elementary row transformation on matrix B, The second row of BX 0 = 0 and x 1 = x 2 implies that B ′ X ′ 0 = 0, where X ′ 0 = (x 2 , x 3 , · · · , x n ) T . Noting that matrix B ′ is of order n − 1, we have c 2 = c 3 = · · · = c n = 0. c 1 = c 2 = · · · = c n = 0 means B = A, that is B is the Laplacian matrix of tree graph. Next, we will prove the following theorem to provide a graphical characterization of a special type of MPCS. Proof (⇒) We only need to prove that dG(v) = dG [S] (v) + 1(∀v ∈ S). Since S is an MPCS,G is connected. Hence, for vertex v 0 , from |NG(v) ∩S| ≤ 1, we have dG(v 0 ) = 1. By Proposition 7, the corresponding eigenvalue λ = 1 and dG(v) = 1(∀v ∈ S : dG [S] (v) = 0). Therefor, only the vertices v ∈ S with dG [S] (v) > 0 needed to be considered.
Let Since S is an MPCS, we know that there exists an eigenvector y such that y v = 0(∀v ∈ S) and LG Si→Si · y Si = λy Si = y Si (λ = 1). Thus, (LG Si→Si − I) · y Si = 0. By Lemma 2, we have and this completes the proof of necessity.
(⇐) If v is a pendent vertex inG, then dG [S] (v) = 0. From Proposition 3 and Proposition 7, we know that the corresponding eigenvalue λ = 1 for any PCS S ′ (S ′ ⊆ S).
To prove the sufficiency, we need to prove that there exists only one linearly independent vector y (corresponding eigenvalue λ = 1) such that LG · y = y, y v = 0(∀v ∈S).
We construct a new graph H as follows. Let According to Proposition 4, u i (i ≥ 1) exists. ∀u i (i ≥ 1) ∈ V (H), there exists only one path between u 0 and u i . Let l i be the length of this path (i.e., the number of edges on this path). By Proposition 6, l i is even. Set It is easily seen that the vector y defined above satisfies (6) and (7). ∀w j ∈ V (H), by Proposition 5 and Proposition 6, we know that there exist exactly two vertices, say u i1 and u i2 , such that u i k w j ∈ E(H)(k = 1, 2). Hence, from (8), we have LG v→V (G) · y = 1 + (−1) = 0 = y v (∀v ∈S).
Si→Si is the Laplacian matrix of tree graphG i , we know that y Si (see (8)) is the only linearly independent vector such that
Hence, the vector y defined above satisfies (5). This completes the proof of sufficiency.

Simulations and Discussion
Finally, we illustrate the method for selecting leader vertices that render an undirected graph controllable by using the theories presented above.

A Synthetic Tree
See Fig.6. All MPCS of G can be found, and the process of finding MPCS is shown in Table 1.
There are a total of three MPCS of G; they are 14 , v 10 , v 12 } Hence, from Remark 1, we know that the minimum number of leaders is 2 and there are a total of 15 different minimum leader sets, i.e.,

DSFN
A classical self-similar hierarchical network model called a deterministic scale-free network (DSFN) was proposed in [32]. It is built in an iterative manner; see Fig.7. Subsequently, in [33], the authors studied the nature of the maximum eigenvalue in the spectrum of DSFN and showed that most of the important quantities in network theory can be obtained analytically. By using the graphical characterization of MPCS provided in this paper, we will determine both its minimum number and minimum sets of leaders in a more concise manner.
Let D(g), n l , and n s denote the g-th generation of the DSFN , the minimum number of leaders, and the number of minimum sets of leaders, respectively.
These MPCS of D(g) are pairwise disjoint; hence, n l = 3 g−1 , n s = 2 n l . The total number of vertices of D(g) is n = 3 g .
According to [34], the index N 1 , defined as the ratio of n l to the network size n, can be used to describe the level of network controllability. For DSFN, the ratio is a constant, N 1 = n l n = 1 3 . This indicates that it is necessary to independently control at least one-third of the vertices to control the DSFN fully.  Since we have obtained all the MPCS of D(g), we introduce another index N 2 , which indicates the possibility of finding the minimum sets of leaders. It is defined as the ratio of n s to the number of subsets of V with n l elements. For D(g), Here, (9) suggests that it is extremely difficult to find the minimum set without theoretical analysis, even if we know the minimum number, and the probability rapidly decreases to 0.

Cayley Tree
A Cayley tree is a classical model for dendrimers [35], which can be constructed in an iterative manner; see Fig.8. Let C(g) denote the Cayley trees after g generations. For any g ≥ 2, C(g) is built from C(g − 1). For each pendent vertex of C(g − 1), two new vertices are created and linked to the pendent.
The total number of vertices of C(g) is n = 3 · 2 g − 2. Next, we will determine all MPCS of C(g). Some MPCS can be determined by Theorem 1. They are the sets composed of two pendents that are adjacent to the same vertex. In addition to these MPCS, there may be other MPCS. See Fig.9. Without loss of generality, let S be an MPCS with 1 ∈ S and 2 / ∈ S. Then, by Theorem 1(see vertex 2), we have 6 / ∈ S. From Proposition 6, 7 ∈ S. Further, λ = 1 can be derived by Proposition 7. We claim that 9 ∈ S. Otherwise, the vertex 7 will be an isolated vertex in G[S] and recall the proof of Theorem 4; vertex 7 should have the same degree as vertex 1 in From L 7→V y S = λy 7 , we have 3y 7 − y 9 = y 7 , i.e., y 9 = 2y 7 . Similarly, y 9 = 2y 8 . From L 9→V y S = λy 9 , we have y 9 = y 11 , i.e., 11 ∈ S. Therefore, 10 ∈ S and y 11 = y 10 . From L 11→V y S = λy 11 , we have 12 / ∈ S. Then, one of {13, 14} will belong to S. Thus far, we have obtained another MPCS S of Cayley tree C(g)(g ≥ 5), where S is composed of the vertices filled. Table 2 lists three important parameters n l , N 1 , N 2 of Cayley trees. From the last column of Table 2, we can see that N 2 decrease to 0 rapidly, to the extent that the probability of finding the optimal solution is less than one in ten million after only 4 iterations.

Conclusion
The controllability of undirected graphs has attracted considerable attention in recent years. However, the roles of leaders, the minimum number of leaders, and the leader location in a undirected graph are yet to be fully understood. A major contribution of this paper was to provide a method to determine the leaders directly from the topology structures of undirected graphs. These contributions can enhance our understanding of the leader's role in the controllability of undirected graphs. To this end, we introduced the concepts of a critical set, perfect critical set, and minimal perfect critical set. These concepts indicate that some vertices with special graphical characterization should be selected as leaders. Necessary and sufficient conditions were proposed to uncover some special minimal perfect critical set. We described the graphical characterizations of minimal perfect critical 2 set. Further, we proved that minimal perfect critical 3 set does not exist. In addition, we pointed out that every tree graph is controllable when the leader set contains at least |S 0 | − 1 pendent vertices, where S 0 is the pendent vertex set. Moreover, we studied an isolated vertex set and found that if S is isolated and |S| ≥ 3, then S is not an MPCS. Finally, we completely described the MPCS of a tree graph with |NG(v) ∩S| ≤ 1(∀v ∈ S) and showed that it can be used to discover some special MPCS of tree graphs.
All these results, which clearly indicate where the leaders are located, reveal the effect of the topology structure on controllability, and they could promote further investigation of the