当前位置:首页 >> 理学 >>

On Maximizing the Second Smallest Eigenvalue of a



On Maximizing the Second Smallest Eigenvalue of a State-Dependent Graph Laplacian
Yoonsoo Kim and Mehran Mesbahi
Abstract—We consider the set consisting of graphs of ?xed order and will correspond to point weighted edges. The vertex set of graphs in masses and the weight for an edge between two vertices is a functional of the distance between them. We pose the problem of ?nding the best vertex positional con?guration in the presence of an additional proximity constraint, in the sense that, the second smallest eigenvalue of the corresponding graph Laplacian is maximized. In many recent applications of algebraic graph theory in systems and control, the second smallest eigenvalue of Laplacian has emerged as a critical parameter that in?uences the stability and robustness properties of dynamic systems that operate over an information network. Our motivation in the present work is to “assign” this Laplacian eigenvalue when relative positions of various elements dictate the interconnection of the underlying weighted graph. In this venue, one would then be able to “synthesize” information graphs that have desirable system theoretic properties. Index Terms—Euclidean distance matrix, graph Laplacian, networked dynamic systems, semide?nite programming.

and 2 (LG (x)) denotes the second smallest eigenvalue of the statedependent Laplacian matrix LG (x) with its spectrum ordered as

1 (LG )  2 (LG )  1 1 1  n (LG ):

Furthermore, we restrict the feasible set of (2) by imposing the proximity constraint


:= kxi 0 xj k2  1 ;

for all i 6= j


I. INTRODUCTION Consider the set of n mobile elements as vertices of a graph, with the edge set determined by the relative positions between the respective elements. Speci?cally, we let G denote the set of graphs of order n with vertex set V = f1; 2; . . . ; ng and edge set E = feij ; i = 1; 2; . . . ; n0 1; j = 2; . . . ; n; i < j g with the weight function

w : R3 2 R3 ! R+

assigning to each edge eij , a function of the distance between the two nodes i and j . Thus, we have for some f : R+ ! R+ , with xi 2 R3 denoting the position of element i. In our setup the function f in (1) will be required to exhibit a distinct behavior as it traverses the positive real line. For example, we will require that this function assume a constant value of one when the distance between i and j is less than some threshold and then rapidly drop to zero (or some small value) as the distance between these elements increases. Such a requirement parallels the behavior of an information link in a wireless network where the signal power at the receiver side is inversely proportional to the some power of the distance between transmitting and receiving elements [18]. Using this framework, we now consider the con?guration problem where x := [x1 ; x2 ; . . . ; xn ]T 2 3n is the vector of positions for the distributed system, the matrix LG (x) is a weighted graph Laplacian de?ned element-wise as 0wij ; if i 6= j [LG (x)]ij := (3) wis ; if i = j


:= w(xi ; xj ) = f (kxi 0 xj k)


3 : max 2 (LG (x)) x




preventing the elements from getting arbitrary close to each other in their desire to maximize 2 (LG ) in (2). The second smallest eigenvalue of the graph Laplacian LG , also known as the algebraic connectivity of G [4], [8], [14], has emerged as an important parameter in many systems problems de?ned over networks [7], [12], [15], [17], [20]. In fact, in several recent works [7], [17], [19], it has been observed that 2 (LG ) is a measure of stability and robustness of the networked dynamic system. This observation implies, for example, that small perturbations in the con?guration of the networked system will be attenuated back to its equilibrium state(s) with a rate that is proportional to 2 (LG ). When this important graph parameter is considered in a state-dependent setting as proposed in [15], the characterization of a distributed system states that maximize 2 (LG ) emerges as a natural optimization problem. In this venue however, there are only a handful of studies in the literature that are related to such a graph eigenvalue assignment problem (2). In particular we mention the work of Fallat and Kirkland [6] where a graph-theoretical approach has been proposed to extremize 2 (LG ) over the set of trees of ?xed diameter. Also related to the present work are those by Chung and Oden [5] pertaining to bounding the gap between the ?rst two eigenvalues of graph Laplacians, and Berman and Zhang [2] and Guattery and Miller [11], where, respectively, isoperimetric numbers of weighted graphs and graph embeddings are employed for lower bounding the second smallest Laplacian eigenvalue. We note that maximizing the second smallest eigenvalue of state dependent graph Laplacians over arbitrary graph constraints is a dif?cult computational problem [16]. The contribution of this note is to propose an iterative greedy-type algorithm for problem (2) with a guaranteed local convergence behavior. Although the convergence of this algorithm is provably local in nature, extensive simulations suggest that it often converges to the global maximum when the initial graph is taken to be a path. The outline of the note is as follows. In Section II-A we delineate on the various possible choices for the edge weights for our state-dependent weighted Laplacians. Sections II-B and C are devoted to the main result of the note where an iterative semide?nite programming-based approach is proposed for the solution of problem 3 (2). A numerical example is then presented in Section III followed by a few concluding remarks. A few words on the notation. The 2-norm of vector x will be denoted by kxk. The spaces of n 2 n real matrices and n 2 n real symmetric matrices are designated by n2n and n , respectively; In will be the n 2 n identity matrix. The inequalities between symmetric matrices are interpreted in the sense of L?wner ordering, i.e., A > B and A  B indicate, respectively, the positive de?niteness and positive semide?niteness of the matrix difference A 0 B .



Manuscript received April 29, 2004; revised March 18, 2005 and August 1, 2005. Recommended by Associate Editor C. D. Charalambous. This work was supported by the National Science Foundation under Grant NSF/CMS-0301753. Y. Kim is with the Department of Engineering, University of Leicester, Leiceister LE1 7RH, U.K. (e-mail: yk17@leicester.ac.uk). M. Mesbahi is with the Department of Aeronautics and Astronautics, University of Washington, Seattle, WA 98195-2400 USA (e-mail: mesbahi@aa.washington.edu). Digital Object Identi?er 10.1109/TAC.2005.861710


3 (2) does not readily hint at being tractable, in the sense of admitting an ef?cient algorithm for its solution. Generally, maximizing the second smallest eigenvalue of a symmetric matrix subject to matrix inequalities, does not yield to a standard linear matrix inequality approach [3] and, subsequently, a solution procedure that relies solely

As we mentioned in Section I, the general formulation of the problem

0018-9286/$20.00 ? 2006 IEEE



Fig. 1. Several candidates for the function f in (1) where  = 1 and  = 2.

on an interior point method [1]. The previous complication however is alleviated in case of graph Laplacians, where the smallest eigenvalue 1 (LG ) is always zero with the associated eigenvector of 1 composed of unit entries. This observation follows directly from the de?nition (3). Nevertheless, due to the nonlinear dependency of entries of LG on the relative distance dij and the presence of constraints (4), the problem 3 (2) assumes the form of a nonconvex optimization. In light of this fact, we will proceed to propose an iterative SDP-based approach for this problem. However, before we proceed, we make a few remarks on some judicious choices for the function f in (1). The choice of f in (1) is not only guided by particular applications but also by numerical considerations. A few candidate functions are shown in Fig. 1. Although there are a host of choices for f , for our analysis and numerical experimentation we have chosen to work with Type-IV functions (the lower right corner in Fig. 1), where f assumes the form

A. Maximizing 2 (LG ) We ?rst present a linear algebraic result in conjunction with the general problem of maximizing the second smallest eigenvalue of graph Laplacians. Proposition 2.1: Consider the m-dimensional subspace P  Rn spanned by the vectors pi 2 Rn , i = 1; . . . ; m. Denote P := [p1 ; . . . ; pm ] 2 Rn2m . Then, for M 2 Sn one has

xT Mx > 0
if and only if

for all nonzero x 2 P

P T MP > 0:
Proof: An arbitrary nonzero element x


P can be written as

f (dij ) = ( 0d


0 ) ;


x = 1 p1 + 2 p2 + 1 1 1 + m pm 1 ; . . . ; m 2 R, not all zeros and, thus, x = P y , where y := [ 1 ; 2 ; . . . ; m ]T . Consequently, the ?rst inequality in (6) is
for some equivalent to


given that dij  1 We note that f (1 ) = 1 and f (2 ) = . Among the advantages of working with functions (5) are their differentiability properties, as well as their ability to capture a situations that is of practical relevance. In many such situations, the strength of an information link is inversely proportional to the relative distance and decays exponentially after a given threshold is passed. Furthermore, and possibly more importantly, functions (5) lead to a stable algorithm for our numerical experimentation; a representative set of examples is discussed in Section III.
have also used functions of the form (1=d ) , where is a positive number and f ( ) = . Our simulation results in Section III turned out to be exactly the same for these functions as compared with those obtained using functions of the form (5).

(P y)T M (P y) = yT P T MP y > 0
for all nonzero y 2 Rm , or in other words, having P T MP note that P T MP 2 Sm . Corollary 2.2: For a graph Laplacian LG the constraint

> 0; we

 2 (L G ) > 0
is equivalent to


P T LG P > 0




where P p1 ; p2 ; chosen such that


. . . ; pn0 ], and the unit vectors pi 2

Rn are

to rewrite (14) as

pT 1 i

= 0;
T pi pj

(i = 1; 2; . . . ; n 0 1) = 0;

(i 6= j ):
LG 1


?rst differentiating the terms wij with respect to time, and then having

2fxi (k + 1) 0 xj (k + 1)gT fxi (k) 0 xj (k)g = dij (k + 1) + dij (k): Similarly, the state dependent Laplacian LG (x) in (15) is discretized by
wij k

Proof: It is well-known that for G

( + 1) = wij (k)





0  0d




fdij (k + 1) 0 dij (k)g

and, thereby, the smallest eigenvalue of LG is always zero and rank LG  n 0 . This implies that (7) is equivalent to having


recall that we are employing functions of the form (5) in (1). The discrete version of the state dependent Laplacian, LG k , assumes the form


xT LG x > ;


for all nonzero x 2 1?


[LG(k)]ij =

0wij (k);

if i 6 wis k ; if i


=j = j.

1? := fx 2 Rn j1T x = 0g:


Putting it all together, we arrive at the iterative step of solving the optimization problem

In view of Proposition 2.1, the condition (11) is equivalent to having P T LG P > , with P denoting the matrix of vectors spanning the subspace 1? . Without loss of generality, this subspace can be identi?ed with the basis unit vectors satisfying (9). Corollary 2.3: The problem (2) is equivalent to



1? (12).

thogonal unit vectors pi s forming the columns of P span the subspace

max (13) x dij := kxi 0 xj k   (14) P T LG (x)P  In0 (15) where i = 1; 2; . . . ; n 0 1, j = 2; . . . ; n, i < j , and the pairwise or0
2 1 1

3: s: t:

Proof: The proof follows from Corollary 2.2. One of the consequences of Corollary 2.3 pertains to the following graph synthesis problem2: determine graphs satisfying an upper bound on the number of their edges with maximum smallest second Laplacian eigenvalue. Although this problem will not be further considered in this note, we point out that it can be reformulated as

3k : xmax (17) k s:t: 2fxi (k + 1) 0 xj (k + 1)gT fxi (k) 0 xj (k)g (18) = dij (k + 1) + dij (k) dij (k + 1)   (19) T P LG (k + 1)P  In0 (20) for i = 1; 2; . . . ; n 0 1, j = 2; . . . ; n, i < j , and x(k) := [x (k); x (k); . . . ; xn (k)]T 2 R n . Thereby, the algorithm is initiated at time k = 0 with an initial graph (con?guration) G , and then for k = 0; 1; 2; . . ., we proceed to iteratively ?nd a graph that maximizes  (LG (k + 1)). This greedy procedure is then iterated upon until the value of  (LG (k)) can not be improved further. We
( +1) 1 1 1 2 3 0 2 2

note that the proposed greedy algorithm converges, as the sequence generated by it is nondecreasing and bounded from above.3 C. Further Considerations

maxf j Trace LG  ; P T LG P  In0 g G2G

where P is de?ned as in Corollary 2.3 and  is twice the maximum number of edges allowed in the desired graph. In this venue, a complication that needs to be further addressed pertains to the integrality of the entries of the sought matrix LG . B. Discrete and Greedy

In previous section, we proposed an algorithm that converges to a local optimal vertex positional con?guration, in terms of maximizing the quantity 2 LG . However, by replacing the nonconvex constraint (14) with its linear approximation (18)–(19), one introduces a potential inconsistency between the position and the distance vectors. In this section, we provide two remedies to avoid such potential complications. Let us ?rst recall the notion of Euclidean distance matrix ; xn 2 R3 , the EDM (EDM). Given the position vectors x1 ; x2 ; n2n D dij 2 R is de?ned entry-wise as

( )

We now proceed to view the problem (2) in an iterative setting, where the goal is shifted toward ?nding an algorithm that attempts to maximize the second smallest eigenvalue of the graph Laplacian at each step. Toward this aim, we ?rst differentiate (14) with respect to time as


=[ ] [D]ij = dij = kxi 0 xj k ;


for i; j

= 1; 2; . . . ; n:

2fxi (t) 0 xj (t)gT fxi (t) 0 xj (t)g = d_ij (t) _ _
and then employ Euler’s ?rst discretization method, with sampling time


The EDM matrices are nicely characterized in terms of linear matrix inequalities [10]. dij 2 Rn2n is an EDM if and only Theorem 2.4: A matrix D if

=[ ]
for i

1t as the
where J

JDJ dii

= 0;


= 1; 2; . . . ; n
for a graph of order

(21) (22)


( ) ! x(k); x(t) ! x(k + 1)t0 x(k) _ 1

:= In 0 11T =n.
L n is bounded

connection was pointed to us by one of the referees.

3The second smallest eigenvalue of from above by n 1 [9].



Fig. 2. Trajectory generated by the proposed algorithm for six nodes in

R : the con?guration evolves from a path (circles) to a truss (squares).

Fig. 3. Trajectory generated by the proposed algorithm for six nodes in 1 ; . . . ; 6 ).

R : the con?guration evolves from a path (circles, 1 ; . . . ; 6 ) to an octahedron (squares,
planar con?guration that locally maximizes 2 (LG ). The constants and 2 in (5) are chosen to be 0.1, 1, and 1.5, respectively. The algorithm was initialized with a con?guration that corresponds to a path. The sequence of con?gurations thereafter converges to the truss-shape graph with the 2 (LG ) of 1.6974. For these set of parameters, the truss-shape graph as suggested by the algorithm is the global maximum over the set of graphs on six vertices that can be con?gured in 2 .4 Using the same simulation scenario, but this time, in search of an optimal positional con?guration in 3 , the algorithm leads to the trajectories shown in Fig. 3. In this case, the graph sequence converges to an octahedron-shape con?guration with 2 (LG ) = 4:02. Increasing the number of nodes to eight, the algorithm was initialized as the unit cube; the resulting trajectories are shown in Fig. 4.
 , 1 ,

Theorem 2.4 allows us to guarantee that by adding the two convex constraints (21)–(22) to problem 3k (17)–(20), we always obtain consistency among the position and distance variables at each iteration step. Moreover, by updating the values of dij (k)’s and [L(k)]ij ’s in (18) and (20) after calculating the values of x(k), we can further reduce the effect of linearization in the proposed procedure. To further expand on this last point, suppose that x1 (k); x2 (k); . . . ; xn (k), dij (k )’s and [L(k )]ij , i = 1; 2; . . . ; n 0 1, j = 2; . . . ; n, i < j , have been obtained after solving the problem 3k (17)–(20). Our proposed modi?cation to the original algorithm thus amounts to updating the values of dij (k) and [L(k)]ij , based on the computed values of x1 (k ); x2 (k ); . . . ; xn (k ), before initiating the next iteration. III. SIMULATION RESULTS For our simulations we used SeDuMi [1] to solve the required semide?nite programs. Fig. 2 depicts the behavior of six mobile elements under the guidance of the proposed algorithm, leading to a



4A global maximum may be found in the following exhaustive manner: First, de?ne a space large enough guaranteed to contain the optimal con?guration. Then grid this region and search over the set of all n grid points for the con?guration that leads to maximum  (L ).



Fig. 4. Evolution of the proposed algorithm for eight nodes in

R : the con?guration evolves from 3-cube (circles) to octahedron (squares).


SeDuMi. McMaster Univ.. [Online]. Available: http://sedumi.mcmaster.ca A. Berman and X.-D. Zhang, “Lower bounds for the eigenvalues of Laplacian matrices,” Linear Alg. Appl., vol. 316, pp. 13–20, 2000. S. Boyd and L. Vandenberghe, Convex Programming. Cambridge, U.K.: Cambridge Univ. Press, 2003. F. R. K. Chung, Spectral Graph Theory. Providence, RI: AMS, 1997. F. R. K. Chung and K. Oden, “Weighted graph Laplacians and isoperimetric inequalities,” Paci?c J. Math., vol. 192, no. 2, pp. 257–273, 2000. S. Fallat and S. Kirkland, “Extremizing algebraic connectivity subject to graph theoretic constraints,” Elect. J. Linear Alg., vol. 1, no. 3, pp. 48–74, 1998. J. A. Fax and R. M. Murray, “Information ?ow and cooperative control of vehicle formations,” IEEE Trans. Autom. Control, vol. 49, no. 9, pp. 1465–1476, Sep. 2004. M. Fiedler, “A property of eigenvectors of nonnegative symmetric matrices and its applications in graph theory,” Czech. Math. J., vol. 100, no. 26, pp. 619–633, 1975. C. Godsil and G. Royle, Algebraic Graph Theory. New York: Springer-Verlag, 2001. J. Gower, “Properties of Euclidean and non-Euclidean distance matrices,” Linear Alg. Appl., vol. 1, no. 67, pp. 81–97, 1985. S. Guattery and G. L. Miller, “On the quality of spectral separators,” SIAM J. Matrix Anal. Appl., vol. 19, no. 3, pp. 701–719, 1998. A. Jadbabaie, J. Lin, and A. S. Morse, “Coordination of groups of mobile autonomous agents using nearest neighbor rules,” IEEE Trans. Autom. Control, vol. 48, no. 9, pp. 988–1001, Sep. 2003. Y. Kim and M. Mesbahi, “Quadratically constrained attitude control via semide?nite programming,” IEEE Trans. Autom. Control, vol. 49, no. 5, pp. 731–735, May 2004. R. Merris, “Laplacian matrices of graphs: A survey,” Linear Alg. Appl., vol. 197, no. 1, pp. 143–176, 1994. M. Mesbahi, “On state-dependent dynamic graphs and their controllability properties,” IEEE Trans. Autom. Control, vol. 50, no. 3, pp. 387–392, Mar. 2005. H. Q. Ngo and D.-Z Du, “Notes on the complexity of switching networks,” in Advances in Switching Networks, H. Q. Ngo and D.-Z. Du, Eds. Norwell, MA: Kluwer, 2000, pp. 307–357. R. Olfati-Saber and R. M. Murray, “Consensus problems in networks of agents with switching topology and time-delays,” IEEE Trans. Autom. Control, vol. 49, no. 9, pp. 1520–1533, Sep. 2004. K. Pahlavan and A. H. Levesque, Wireless Information Networks. New York: Wiley, 1995. H. Tanner, A. Jadbabaie, and G. Pappas, “Flocking in ?xed and switching networks,” Automatica, submitted for publication. L. Xiao and S. Boyd, “Fast linear iterations for distributed averaging,” Syst. Control Lett., vol. 53, pp. 65–78, 2004.

In this ?gure, the edges between vertices i and j indicate that dij  2 = 1:5. The solid lines in Fig. 4 represent the ?nal con?guration with 2 (LG ) = 2:7658. Once again, an exhaustive search procedure indicates that the proposed algorithm does lead to the global optimal con?guration (see Table I). We like to remark however that the choice for the function f in (5) and the initial con?guration, are critical to the performance of the proposed algorithm. For example, when this function is chosen to be of Type-I in Fig. 1 and the initial graph as a disconnected graph, the algorithm terminates right after initialization, as any small perturbation on the initial graph does not lead to an improvement in the value of 2 (LG ). Choosing a Type-IV function in Fig. 1 on the other hand, always lead to a connected con?guration with a positive 2 (LG ), even when the algorithm is initialized via a disconnected graph. IV. CONCLUDING REMARKS We considered the problem of maximizing the second smallest eigenvalues of a state-dependent graph Laplacian. This problem is of importance, for example, when the positions of a set of dynamic elements-operating over an information network- can be chosen for robust system performance. We proposed an iterative algorithm for this problem that employs a semide?nite programming solver at each recursive step. Although the algorithm has a local convergence behavior, extensive simulations suggest that it often leads to a globally optimal state con?guration. ACKNOWLEDGMENT The authors gratefully acknowledge suggestions and comments by the anonymous reviewers.

[6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20]