1

Submodular Optimization for Consensus Networks
with Noise-Corrupted Leaders

arXiv:1712.08212v1 [math.OC] 21 Dec 2017

Erika Mackin and Stacy Patterson

Abstract—We consider the leader selection problem in a
network with consensus dynamics where both leader and follower agents are subject to stochastic external disturbances. The
performance of the system is quantified by the total steadystate variance of the node states, and the goal is to identify the
set of leaders that minimizes this variance. We first show that
this performance measure can be expressed as a submodular
set function over the nodes in the network. We then use this
result to analyze the performance of two greedy, polynomialtime algorithms for leader selection, showing that the leader sets
produced by the greedy algorithms are within provable bounds
of optimal.
Index Terms—Greedy algorithm, leader-follower system,
stochastic system.

I. I NTRODUCTION
ONSENSUS algorithms play an important role in networked systems in applications such as sensor fusion [1],
autonomous formation control [2], clock synchronization [3],
and distributed localization [4]. Due to their importance, much
study has been done on the performance of these algorithms,
including their convergence rates and their robustness to
external disturbances.
An important class of consensus algorithms is leaderfollower consensus algorithms. In leader-follower consensus, a
subset of nodes are leaders that dictate the desired state of the
network. The remaining nodes are followers that update their
states using consensus dynamics. The performance of a leaderfollower consensus system depends both on the topology of
the network and the locations of the leader nodes. A natural
question that arises is where to locate the leaders (i.e., at what
nodes in the network?) so as to optimize some performance
measure. This problem is known as the leader selection
problem.
The optimal leader set of a given size k can be found
through an exhaustive search of all possible subsets of nodes
of size k. This approach, however, is not computationally
tractable for anything other than small networks or small
values of k. Therefore, much research has been done into
deriving efficient approximation algorithms and corresponding
bounds for leader selection. Several works have investigated
the leader selection problem using convergence rate as a
performance measure [5], [6], [7], [8], [9], [10]. Most notably, the works [11], [8] propose relaxations of the leader

C

*This work was supported in part by NSF grants CNS-1527287 and CNS1553340.
Erika Mackin and Stacy Patterson are with Department of Computer
Science, Rensselaer Polytechnic Institute, Troy, New York 12180, USA.
Phone: 518-276-2054. Fax: 518-276-4033. Email: mackie2@rpi.edu,

sep@cs.rpi.edu

selection problem that admit efficient solutions. While these
relaxed formulations perform well in evaluations, there are no
guarantees on the optimality of their solutions.
Another performance measure used for leader-follower systems is network coherence, which is quantified by the total
steady-state variance of the node states. In systems with
noise-free leaders, follower nodes are subject to stochastic
disturbances, while leader nodes are not. Heuristic approaches
have been proposed to optimize coherence in this setting for
general undirected graphs [12], [13], [14]. Further, analytic
solutions have been developed for undirected paths and cycles
for an arbitrary number of leaders [15], [16], [17], and for
regular trees when the number of leaders is restricted to
two [18]. A closed-form expression for coherence in Koch
networks with a single noise-free leader was derived in [10],
and analysis of the asymptotic scaling of coherence in 1D and
2D directed lattice graphs when leaders are on the boundary
was given in [19]. Of particular note is the work of Clark et
al. [14], which showed that the leader selection problem with
noise-free leaders can be expressed as an optimization problem
over a submodular set function. As such, a greedy polynomialtime algorithm can find a leader set with performance that is
within a provable bound of optimal [20].
Several works have also considered the leader selection
problem with noise-corrupted leaders, i.e., networks in which
both the leader and follower nodes are subject to stochastic
disturbances. The work by Fitch and Leonard [15] developed
expressions for determining the optimal two noise-corrupted
leaders in undirected cycles and paths, while [18] developed
a closed-form expression for the coherence in cycles with
two noise-corrupted leaders. The work by Lin et al. [13]
gives lower and upper bounds on network coherence for an
undirected network with noise-corrupted leaders. While this
work proposes a similar polynomial-time algorithm to [5],
[14], as well as to the one we study in this work, it does not
give any bounds on the quality of the solutions produced by
this algorithm. Finally, the recent work by Dhingra et al. [21]
presents an algorithm for noise-corrupted leader selection in
directed networks; however, no guarantee on the optimality of
the solution is provided.
In this work, we consider the leader selection problem in
undirected graphs with noise-corrupted leaders. We quantify
the performance of the system, for a given set of leaders, by
the network coherence. We first show that this performance
measure can be recast as a submodular set function over
the set of possible leader nodes. We then use this result to
prove optimality bounds for greedy leader selection algorithms
similar to those described in [13]. As far as we are aware, this

2

note is the first work to give optimality bounds on algorithms
for leader selection in networks with noise-corrupted leaders.
We note our proof technique was inspired by a result in [22] on
optimizing network coherence by adding edges to the network.
The proof in this work was later found to be flawed [23], [24].
We show that, in the problem considered in this work, this
proof technique is valid. Details are given in Section III.
The remainder of this note is structured as follows. In
Section II, we describe our system model and problem formulation, as well as background on submodular functions.
Section III gives our analysis of the submodularity of the
leader selection performance measure. Section IV describes
the greedy algorithms for leader selection and presents analysis of the performance of these algorithms, followed by a
brief numerical example demonstrating their performance in
Section V. Finally, we conclude in Section VI.
II. P RELIMINARIES

It is straightforward to show that, for S 6= ∅ [13]:

1
H(S) = tr Q−1
.
S
2
The k-leader selection problem for noise-corrupted leaders
is: given a budget k, identify a set of at most k leaders that
minimizes the total steady-state variance, i.e.,

minimize H(S) = 21 tr Q−1
S
(LS)
subject to |S| ≤ k.
We denote the minimal value of H(S), over all possible leader
sets S with |S| ≤ k, by Ĥ.
A recent work [13] proposed an efficient approximation
algorithm for (LS), but did not provide bounds on the performance of solutions generated by this algorithm. In the
remainder of this work, we show that H(S) can be related
to a submodular set function and, using this relationship, we
derive bounds on the solutions produced by greedy algorithms
similar to the ones proposed in [13].

A. System Model
We consider a network of n nodes, modeled by a connected,
undirected graph G = (V, E). Each node i has a scalar-valued
state xi . Nodes are either followers or leaders. The state of a
leader is updated as,
X
(xi − xj ) − κi xi + wi ,
ẋi = −
j∈Ni

where wi is a zero-mean, white stochastic disturbance and κi
is a real, positive number. The state of a follower is updated
as,
X
ẋj = −
(xj − xk ) + wj ,
j∈Nj

where wj is again a zero-mean, white stochastic disturbance.
Let S denote the set of leaders. The dynamics of the system
can be written as,
ẋ = −(L + Dκ DS )x + w,
where L is the Laplacian matrix of the graph, Dκ is a diagonal
matrix, with diagonal entries κi , and DS is a diagonal matrix
where the (i, i)th component is 1 if node i is a leader; the
(i, i)th component is 0 otherwise. For simplicity of notation
we use QS to denote L + Dκ DS . If the set S is a singleton
consisting of the node v, we simply write Qv . Provided S 6= ∅,
the matrix QS is positive definite [6].
We note that QS can also be interpreted as a grounded
Laplacian matrix of a graph Ḡ, which is defined as follows.
Given the graph G and the leader set S, Ḡ is formed by adding
a single node s̄ to G and adding an edge from each node i ∈ S
to s, with edge weight κi . All other edges have weight 1. Let
L̄ be the corresponding Laplacian. By removing the sth row
and column from L̄, we obtain QS . .
As in [12], [13], [14], we quantify the performance of the
system, for a given set of leaders S, by the total steady-state
variance of x,
H(S) := lim

t→∞

n
X
i=1

 
E x2i .

B. Background
Our analysis of the leader selection problem is based on
theory related to submodular set functions, which are defined
as follows.
Definition 1 ([20]). A function f : 2V 7→ R, where V is a
finite set, is called submodular if, for all A, B ⊆ V ,
f (A) + f (B) ≥ f (A ∪ B) − f (A ∩ B).
Informally, a submodular function exhibits a “diminishing
returns” property: the incremental benefit of adding an element
to a set S is more than the incremental benefit of adding that
same element to a superset of S.
We make use of the following definition in our analysis.
Definition 2. A set function f : 2V 7→ R is called nonincreasing if for all A, B ⊆ V , if A ⊆ B, then f (A) ≥ f (B).
The function f is called non-decreasing if for all A, B ⊆ V ,
if A ⊆ B, then f (A) ≤ f (B).
We also make use of the following theorem.
Theorem 1 ([25]). A function f : 2V 7→ R is submodular
if and only if the derived set functions fa : 2V −{a} 7→ R,
defined by,
fa (X) = f (X ∪ {a}) − f (X),

(1)

are non-increasing for all a ∈ V .
We note that maximizing a submodular function is an NPhard problem [20].
III. L EADER S ELECTION AND S UBMODULARITY
We introduce a function f (S) over sets of leader nodes,
such that maximizing f (S) is equivalent to minimizing H(S).
We then prove that this set function f is non-decreasing
and submodular, properties which guarantee that leader sets
generated by polynomial-time greedy algorithms are within a
provable bound of optimal. These algorithms and bounds are
presented in Section IV.

3

The function f : 2V 7→ R is defined as follows:

0
 if S = ∅
f (S) =
(2)
C − tr Q−1
otherwise,
S

. Note that a set Ŝ that
where C = 2 maxv∈V tr Q−1
v
maximizes f also minimizes H.
Proposition 1. The function f is a non-decreasing function.
Proof: Let S1 ⊆ S2 ⊆ V . First, we consider the case
where S1 = S2 = ∅. Then, f (S1 ) = f (S2 ) = 0, which
implies f (S1 ) ≤ f (S2 ).
Next, we consider S1 = ∅ and S2 6= ∅. We now show
f (S2 ) ≥ 0, which implies f (S1 ) ≤ f (S2 ). By definition,


− tr Q−1
f (S2 ) = 2 max tr Q−1
v
S2
v∈V


− tr Q−1
≥ 2 max tr Q−1
v
S2 .
v∈S2

If |S2 | = 1, then f (S2 ) ≥
 0 holds trivially. Otherwise, let
and let Z = S2 \ {u}. It follows
u = arg maxv∈S2 tr Q−1
v
that:
Q S2 = L + D κ D S2
= L + Dκ DZ + Dκ Du .
Since L + Dκ DZ is positive definite and Dκ Du is positive
semidefinite, by Weyl’s theorem,
λi (Qu ) ≤ λi (QZ + Dκ Du ) = λi (QS2 ) ,


≥ tr Q−1
for i = 1 . . . n. This implies that tr Q−1
u
S2 , and
thus, f (S2 ) ≥ 0.
Finally, we consider the case where S1 6= ∅. Then,


−1
f (S1 ) − f (S2 ) = C − tr Q−1
S1 − C − tr QS2


−1
= tr Q−1
S2 − tr QS1 .

Let Z = S2 \ S1 and note that QS2 = QS1 + Dκ DZ . By a
similar application
of
 Weyl’s theorem as above, it holds that

−1
≤
tr
Q
tr Q−1
S1 , or equivalently, that f (S1 ) ≤ f (S2 ).
S2

Theorem 2. The set function f , defined in (2), is submodular.
Proof: To prove this theorem, we first define the set
function fa : 2V \{a} 7→ R,
fa (S) = f (S ∪ {a}) − f (S),

(3)

and show that it is monotone decreasing.
Let S1 ⊆ S2 ⊆ V \ {a}. We first consider the case where
S1 6= ∅ and S2 6= ∅. The proof of this case follows the same
structure used in [22]. In this case, (3) is equivalent to:



−1
fa (S) = C − tr Q−1
S∪{a} − C − tr QS


= −tr (QS + Dκ Da )−1 + tr QS−1 ,
where Da denotes the diagonal matrix with Da (a, a) = 1 and
all other entries equal to 0.
We define the function Q(t), for t ∈ [0, 1], as,
Q(t) = QS1 + t(QS2 − QS1 ).
Note that Q(0) = QS1 and Q(1) = QS2 . Let


fˆa (Q(t)) = −tr (Q(t) + Dκ Da )−1 + tr Q(t)−1 .

We next take the derivative of fˆa with respect to t,
d ˆ
fa (Q(t))
dt


d
(5)
−tr (Q(t) + Dκ Da )−1 + tr Q(t)−1
=
dt

= tr (Q(t) + Dκ Da )−1 (QS2 − QS1 )(Q(t) + Dκ Da )−1

(6)
− tr Q(t)−1 (QS2 − QS1 )Q(t)−1



−2
−2
= tr (Q(t) + Dκ Da ) − Q(t)
(QS2 − QS1 ) , (7)

where (6) is obtained from (5) by applying the matrix derivative formula:



d
−1
−1 d
−1
tr Q(t)
= −tr Q(t)
(Q(t))Q(t)
,
dt
dt

and (7) is obtained from (6) by the cyclic property of the trace.
We now show that (7) is non-positive. We define da as the
vector of all zeros except the ath component, which has value
√
κa . Let
Q(t)−1 Dκ Da Q(t)−1
X=
.
1 + dTa Q(t)−1 da

Using the Sherman-Morrison formula, we rewrite the first
factor in (7) as:
2

2 
(Q(t) + Dκ Da )−2 − Q(t)−2 = Q(t)−1 − X − Q(t)−1
= −Q(t)−1 X − XQ(t)−1 + X 2

= −Q(t)−1 X − X(Q(t)−1 − X)

= −Q(t)−1 X − X(Q(t) + Dκ Da )−1 .

(8)

Note that Q(t) and (Q(t) + Dκ Da ) are both grounded
Laplacians, and therefore their inverses Q(t)−1 and
(Q(t) + Dκ Da )−1 are element-wise positive for all t
and a [26]. From this, we can conclude that X is also
element-wise positive, since the numerator is clearly
element-wise positive and the denominator is the positive
scalar 1 + Q(t)−1
(a,a) . We can then see that −Q(t)X and
(−X)(Q(t) + Dκ Da )−1 ) are both element-wise negative
matrices, and therefore, (Q(t) + Dκ Da )−2 − Q(t)−2 is also
element-wise negative.
We also note that
Q S2 − Q S1 = D κ D S2 − D κ D S1 ,
is a diagonal matrix where the (i, i)th component is 1 if
i ∈ S2 \ S1 and 0 otherwise. Therefore,


(9)
(Q(t) + Dκ Da )−2 − Q(t)−2 (QS2 − QS1 )

is a matrix with columns that are either all zeros or correspond
to the columns of (Q(t) + Dκ Da )−2 − Q(t)−2 with indices
in S2 \ S1 . The matrix (9) is therefore non-positive, as is its
d ˆ
fa (Q(t)) is non-positive.
trace. It follows that dt
Consider the following equality,
Z 1
d ˆ
fˆa (Q(1)) = fˆa (Q(0)) +
dt fa (Q(t))dt.
0

(4)

Since fˆa (Q(1)) = fa (S2 ) and fˆa (Q(0)) = fa (S1 ), and
d ˆ
since, as shown above, dt
fa (Q(t))dt is non-positive, we have

4

fa (S1 ) ≥ fa (S2 ). Therefore fa is non-increasing over S ⊆ V ,
S 6= ∅.
If S1 = S2 = ∅, then fa (S1 ) = fa (S2 ), and so it also holds
that fa is non-increasing over S = ∅.
Finally, we consider S1 = ∅ and S2 6= ∅. Then,

In the proof in [22], the authors argue that because (Q(t) + La )−1 − Q(t)−1 is negative semidefinite,
(Q(t) + La )−2 − Q(t)−2 is negative semidefinite as well.
They use this assumption to show that the inequality (10)
holds. As shown in [24], this relationship does not hold in
general, nor does it hold in the problems in [9], [22], [27].
fa (S1 ) − fa (S2 ) = f ({a}) − (f (S2 ∪ {a}) − f (S2 )))
In fact, this relationship does not necessarily hold in (7). Our


 

−1
proof does not rely on this assumption, but rather we base our
−
C
−
tr
Q
− C − tr Q−1
= C − tr Q−1
a
S2
S2 ∪{a}



argument on the element-wise positivity and negativity of the


−1
.
− tr Q−1
= C − tr Q−1
two factors in (7).
a
S2 − tr QS2 ∪{a}

, we have,
With C = 2 maxv∈V tr Q−1
v
IV. A LGORITHMS



−1
−1
≥
max
tr
Q
2 max tr Qv − tr Q−1
In
this
section,
we
describe and analyze two greedy algov
a
v∈V
v∈V

rithms
for
the
k-leader
selection problem with noise-corrupted
.
≥ max tr Q−1
u
leaders.
These
algorithms
are problem-specific variations of
u∈S2


algorithms
presented
in
[20]
for maximizing a general sub≥ tr Q−1
By Proposition 1, maxu∈S2 tr Q−1
u
S2 . Therefore,
modular function.
fa (S1 ) − fa (S2 ) ≥ 0.
Thus, fa is monotone decreasing over all subsets of V , and
A. Algorithm Descriptions
by Theorem 1, f is submodular.
The first algorithm, the Greedy Algorithm, is given in
Algorithm 1. The algorithm is initialized with an empty leader
A note on the correctness of the proof method.
set. It first selects the single node v that minimizes tr Q−1
v
A similar method to the above proof was first presented and adds that to the leader set S. Then, in each iteration,
it


in [22] to show that coherence, as a function of the set of selects the node v that gives the smallest value of tr Q−1
S∪{v}
edges that can be added to a noisy consensus network, can and adds that node to S. This continues until either |S| = k
be captured by a submodular function. This same technique
or no node whose addition would further decrease H(S) is
was later used to show the submodularity of functions in found.
other network design problems such as: adding edges in
The second algorithm, the Swap Algorithm, is given in
networks with noisy consensus dynamics [22], adding edges Algorithm 2. The Swap Algorithm takes an arbitrarily-selected
in networks with noisy consensus dynamics with stubborn leader set S of size k as input. To improve the performance
agents [9], and sensor and actuator placement for optimal of the leader set, a possible swap is looked for by repeatedly
controllability [27]. Unfortunately, the proofs in these works exchanging a single leader with a single follower. Call this
relied on a faulty assumption about the relationship between potential leader set S ′ . If tr Q−1  < tr Q−1 , then S ′
′
S
negative semidefinite matrices and their squares [23]. And, in becomes the new leader set. This Sprocess is repeated
until no
fact, it has since been shown that many of these set functions possible swap is found that decreases the value of tr Q−1 .
S
are not submodular [24].
Algorithm 1 is equivalent to the One-Leader-at-a-Time
As an illustration, we consider the problem of selecting Algorithm in [13]. Algorithm 2 is similar to the Swap Aledges to add to a noisy consensus network to optimize its gorithm in [13], with one difference. In [13], the input to the
coherence [22]. The system dynamics are:
Swap Algorithm is the output from the One-Leader-at-a-Time
Algorithm rather than an arbitrary leader set as in Algorithm 2.
ẋ = −(L + LE )x + w,
As shown in [13], the Greedy Algorithm requires O(n3 )
where w is a vector of zero-mean, white noise processes, E is operations. Further, [13] shows that, in the Swap Algorithm,
the set of edges added, and LE is the corresponding Laplacian. to evaluate the benefit of a potential swap requires O(n)
The coherence of the network is:
operations, and, once a beneficial swap has been identified,

1
O(n2 ) operations are required to compute the new Q−1
S . It has
H(E) = tr (L + LE )† ,
been shown that, for some submodular functions, such a swap
2
where L† denotes the pseudo-inverse of the Laplacian, and the algorithm may take an exponential number of iterations [20].
It is an open question whether this worst-case time complexity
set function of interest is:
holds for Algorithm 2.


f (E) = tr L† − tr (L + LE )† ,
corresponding to (2) in our problem setting. The functions fa
and fˆa are defined similarly to those in equations (3) and (4).
The corresponding statement to (7) is



tr (Q(t) + La )−2 − Q(t)−2 (LE2 − LE1 ) ≤ 0, (10)

where Q(t) = L + LE1 + t(LE2 − LE1 ).

B. Performance Bounds

We now present analysis of the performance of the leader
selection algorithms.
Theorem 3. For a graph G = (V, E) and number of leaders
k, let Sg be the leader set returned by Algorithm 1, and let
Ĥ = minS,|S|≤k H(S). Then:

5

Algorithm 1: Greedy Algorithm for k-leader selection.
Input : G = (V, E), κ, maximum number of leaders k
Output: Set of leader nodes S
Initialize: S ← ∅, i ← 0 
v ← argminu∈V tr Q−1
v
S ← S ∪ {v} ;
for i = 2 . . . k do


v ← argminu∈V \S tr Q−1
S∪{u}



−1
−1
if tr QS∪{v} < tr QS then
S ← S ∪ {v}
else
return S
end
end
return S

Algorithm 2: Swap Algorithm for k-leader selection.
Input : G = (V, E), κ, arbitrary leader set S, |S| = k
Output: Set of leader nodes S
Initialize: T ← V \ S, n ← |V |, decreased ← true
while decreased do
label: for
 i ∈ S, j ∈ T do

−1
then
if tr Q−1
S∪{j}\{i} < tr QS
S ← S ∪ {j} \ {i}
T ← T ∪ {i} \ {j}
break label
end
end
decreased = f alse
end
return S

1) If |Sg | < k, then H(Sg ) = Ĥ, and Sg is an optimal
leader set.
2) If |Sg | = k, then


1
B
H(Sg ) ≤ 1 −
Ĥ + ,
(11)
e
e

.
where B = maxv∈V tr Q−1
v

Proof. In Algorithm 1, the first
 leader that is selected is the
node v that minimizes tr Q−1
. This is equivalent to selecting
v
the node v = arg maxu∈V f ({u}). In each iteration of the
algorithm, an additional leader is added to the set Sg such
that H(Sg ) is minimized, or equivalently, such that f (Sg )
is maximized. Algorithm 1 is thus equivalent to a greedy
algorithm that maximizes f . By Proposition 1 and Theorem 2,
the function f is non-decreasing and submodular, respectively.
Thus, by Proposition 4.2 in [20], if the greedy algorithm
terminates with |Sg | < k, the set S is optimal for f and,
therefore, also for H, which proves property 1. By Theorem
4.2 in [20], if the greedy algorithm terminates with |Sg | = k,
then
k !



1
k−1
f (Ŝ) ≥ 1 −
f (Ŝ), (12)
f (Sg ) ≥ 1 −
k
e



where Ŝ is any leader set such that 12 tr Q−1
= Ĥ. By
Ŝ
applying the relationship between f and H to (12), we obtain
the bound (11) in property 2.
It has been shown that the bound (12) is tight, meaning there
is some submodular set function that achieves the worst case
bound. Futher, for a general submodular set function, this is
the best achievable bound for any polynomial-time algorithm,
unless P = N P [14]. It remains an open question whether
this bound is tight for the specific function f in (2).
Theorem 4. For a graph G = (V, E) and number of leaders
k, let Ss be the leader set returned by Algorithm 2, and let
Ĥ = minS,|S|≤k H(S). Then,




k−1
k−1
H(Ss ) ≤ 1 −
,
(13)
Ĥ + B
2k − 1
2k − 1

.
where B = maxv∈V tr Q−1
v

Proof. Following a similar argument to that in the proof of
Theorem 3, it holds that the set Ss produced by Algorithm 2
is equivalent to what would be produced by a swap algorithm
that seeks to maximize f . Since f is submodular and nondecreasing, by Theorem 5.1 in [20], we have


k−1
f (Ŝ),
(14)
f (Ss ) ≥ 1 −
2k − 1


where Ŝ is any leader set such that 12 tr Q−1
= Ĥ. By
Ŝ
applying the relationship between f and H to (14), we obtain
the bound (13).

As with the greedy algorithm, the bound (14) is tight [20].
The question of whether this bound is tight for Algorithm 2
remains open.
We note that, for general submodular functions, the bound
(14) is worse than the bound (12). In other words, if one were
to take the output of the greedy algorithm and use it as the
input to the swap algorithm, as is done in [13], there is no guarantee that the swap algorithm would improve upon the greedy
solution. In fact, there are submodular functions for which it
has been shown that this approach yields no improvement over
the greedy algorithm alone [20]. However, [13] demonstrated
that, in practice, the swap algorithm can lead to improvements
on the greedy solution.
V. N UMERICAL E XAMPLE
For the graph G, shown in Fig. 1, the greedy algorithm
chooses as leaders, in order, nodes 5, 4, 7, and 1. The
coherence of the network is then H(S) = 3.0910. For the
swap algorithm, given the same G and a randomly chosen
starting leader set, S = {1, 2, 4, 5}, the algorithm performs
three rounds of swaps, terminates, and outputs the leader set
S = {2, 4, 6, 8}, with resulting network coherence H(S) =
3.0576. The optimal leader set is Ŝ = {1, 3, 6, 8}, which is
distinct from the output of both algorithms. The coherence of
the network with optimal leaders is Ĥ = 3.
When the output of the greedy algorithm is used as the
initial set in the swap algorithm, then the algorithm terminates
after two rounds of swaps and outputs S = {1, 3, 5, 7}, with

6

1

2

5

6

4

3

8

7

9
(a) Optimal Leader Set.

1

2

5

6

4

3

8

7

9
(b) Leaders selected by Greedy Algorithm.

1

2

5

6

4

3

8

7

9
(c) Leaders selected by Swap Algorithm, with input S = {1, 2, 4, 5}.

Fig. 1: Leaders chosen for a graph G by Algorithms 1 and 2,
with k = 4. Leaders are shown in gray.
coherence H(S) = 3.0546. In this case, the swap algorithm
does improve upon the performance of the greedy algorithm,
although the result is still sub-optimal.
VI. C ONCLUSION
We have studied the k-leader selection problem in leaderfollower consensus networks with noise-corrupted leaders.
System performance is quantified by the network coherence,
which is the total steady-state variance of the nodes. We first
showed that the network coherence can be expressed as a
submodular set function. Using this result, we then derived
bounds on the performance of two greedy leader selection
algorithms. In future work, we plan to extend our analysis to
leader-follower consensus in directed graphs.
R EFERENCES
[1] L. Xiao, S. Boyd, and S. Lall, “A scheme for robust distributed sensor
fusion based on average consensus,” in Proc. Information Processing in
Sensor Networks, 2005, p. 9.
[2] P. Barooah and J. Hespanha, “Graph effective resistance and distributed
control: Spectral properties and applications,” in Proc. American Control
Conf., Dec 2006, pp. 3479–3485.
[3] J. Elson, R. M. Karp, C. H. Papadimitriou, and S. Shenker, “Global synchronization in sensornets,” in Latin American Theoretical Informatics,
2004, pp. 609–624.
[4] P. Barooah and J. Hespanha, “Error scaling laws for linear optimal estimation from relative measurements,” IEEE Trans. Inf. Theory, vol. 55,
no. 12, pp. 5661–5673, Dec 2009.

[5] F. Pasqualetti, S. Martini, and A. Bicchi, “Steering a leader-follower
team via linear consensus,” Hybrid Systems: Computation and Control,
vol. 4981, pp. 642–645, 2008.
[6] A. Rahmani, M. Ji, M. Mesbahi, and M. Egerstedt, “Controllability
of multi-agent systems from a graph-theoretic perspective,” SIAM J.
Control Optim., vol. 48, no. 1, pp. 162–186, 2009.
[7] M. Pirani and S. Sundaram, “Spectral properties of the grounded
laplacian matrix with applications to consensus in the presence of
stubborn agents,” in Proc. ACC, 2014, pp. 2160–2165.
[8] A. Clark, B. Alomair, L. Bushnell, and R. Poovendran, “Minimizing
convergence error in multi-agent systems via leader selection: A supermodular optimization approach,” IEEE Trans. Autom. Contr., vol. 59,
no. 6, pp. 1480–1494, Jun 2014.
[9] E. Mackin and S. Patterson, “Optimizing the coherence of composite
networks,” Proc. American Control Conf., pp. 4334–4340, 2017.
[10] Y. Yi, Z. Zhang, L. Shan, and G. Chen, “Robustness of first-and secondorder consensus algorithms for a noisy scale-free small-world koch
network,” IEEE Trans. Control Syst. Technol., vol. 25, no. 1, pp. 342–
350, 2017.
[11] A. Clark, B. Alomair, L. Bushnell, and R. Poovendran, “Leader selection
in multi-agent systems for smooth convergence via fast mixing,” in Proc.
IEEE Conf. Decision and Control, 2012, pp. 818–824.
[12] S. Patterson and B. Bamieh, “Leader selection for optimal network
coherence,” in Proc. IEEE Conf. Decision and Control, 2010, pp. 2692–
2697.
[13] F. Lin, M. Fardad, and M. Jovanovic, “Algorithms for leader selection in
stochastically forced consensus networks,” IEEE Trans. Autom. Contr.,
vol. 59, no. 7, pp. 1789–1802, Jul 2014.
[14] A. Clark, L. Bushnell, and R. Poovendran, “A supermodular optimization
framework for leader selection under link noise in linear multi-agent
systems,” IEEE Trans. Autom. Contr., vol. 59, no. 2, pp. 283–296, 2014.
[15] K. Fitch and N. E. Leonard, “Joint centrality distinguishes optimal
leaders in noisy networks,” IEEE Trans. Control Netw. Syst., vol. 3,
no. 4, pp. 366–378, Dec 2016.
[16] S. Patterson, N. McGlohon, and K. Dyagilev, “Optimal k-leader selection
for coherence and convergence rate in one-dimensional networks,” IEEE
Trans. Control Netw. Syst., vol. 4, no. 3, pp. 523–532, Sep 2017.
[17] S. Patterson, “Optimizing coherence in 1-d noisy consensus networks
with noise-free leaders,” in Proc. American Control Conf., 2017, pp.
3011–3016.
[18] S. Patterson, Y. Yi, and Z. Zhang, “A resistance distance-based approach
for optimal leader selection in noisy consensus networks,” arXiv preprint
arXiv:1708.06873, 2017.
[19] F. Lin, M. Fardad, and M. R. Jovanović, “Performance of leader-follower
networks in directed trees and lattices,” in Proc. IEEE Conf. Decision
and Control, 2012, pp. 734–739.
[20] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher, “An analysis of
approximations for maximizing submodular set functions—i,” Math.
Program., vol. 14, no. 1, pp. 265–294, 1978.
[21] N. K. Dhingra, M. Colombino, and M. R. Jovanović, “Leader selection
in directed networks,” in Proc. IEEE Conf. Decision and Control, 2016,
pp. 2715–2720.
[22] T. Summers, I. Shames, J. Lygeros, and F. Dörfler, “Topology design
for optimal network coherence,” in Proc. European Control Conf., 2015,
pp. 575–580.
[23] T. H. Summers, F. L. Cortesi, and J. Lygeros, “Correction to on
submodularity and controllability in complex dynamical networks.”
[24] A. Olshevsky, “On (non) supermodularity of average control energy,”
IEEE Trans. Control Netw. Syst., 2017.
[25] L. Lovász, Submodular functions and convexity.
Springer Berlin
Heidelberg, 1983, pp. 235–257.
[26] U. Miekkala, “Graph properties for splitting with grounded laplacian
matrices,” BIT Numerical Mathematics, vol. 33, no. 3, pp. 485–495,
1993.
[27] T. H. Summers, F. L. Cortesi, and J. Lygeros, “On submodularity and
controllability in complex dynamical networks,” IEEE Trans. Control
Netw. Syst., vol. 3, no. 1, pp. 91–101, 2016.

