1

A Resistance Distance-Based Approach for Optimal
Leader Selection in Noisy Consensus Networks

arXiv:1708.06873v1 [math.OC] 23 Aug 2017

Stacy Patterson, Member, IEEE, Yuhao Yi, and Zhongzhi Zhang

Abstract—We study the performance of leader-follower noisy
consensus networks, and in particular, the relationship between
this performance and the locations of the leader nodes. Two types
of dynamics are considered (1) noise-free leaders, in which leaders
dictate the trajectory exactly and followers are subject to external
disturbances, and (2) noise-corrupted leaders, in which both
leaders and followers are subject to external perturbations. We
measure the performance of a network by its coherence, an H2
norm that quantifies how closely the followers track the leaders’
trajectory. For both dynamics, we show a relationship between
the coherence and resistance distances in an a electrical network.
Using this relationship, we derive closed-form expressions for
coherence as a function of the locations of the leaders. Further, we
give analytical solutions to the optimal leader selection problem
for several special classes of graphs.

I. I NTRODUCTION
Consensus problems are an important class of problems in
networked and multi-agent systems. The consensus model has
been used to study a wide range of applications, including
opinion dynamics in social networks [1], information fusion in
sensor networks [2], formation control [3], and load balancing
in distributed computing systems [4]. Over the past decades,
much research effort has been devoted to analysis of the convergence behavior and robustness of consensus networks and
to the derivation of relationships between system performance
and graph theoretic properties.
A type of consensus problem that has received attention in
recent years is leader-follower consensus [5], [6], [7], [8],
[9], [10], [11]. In leader-follower systems, a subset of nodes
are leaders that track an external signal. The leaders, in
essence, dictate the desired trajectory of the network. The
remaining nodes are followers that update their states based
on relative information exchanges with neighbors. Leaderfollower dynamics can be used to model formation control
where, due to bandwidth limitations, only a small subset
of agents can be controlled by a system operator [12]. In
addition, leader-follower systems can also be used to model
agreement dynamics in social networks in which some subset
of participants exhibit degrees of stubbornness [13]. Leaderfollower dynamics have also been applied to the problem of
distributed sensor localization [14]. In leader-follower systems,
S. Patterson∗ is with the Department of Computer Science, Rensselaer
Polytechnic Institute, Troy, NY 12180. Email: sep@cs.rpi.edu, Phone: 518276-2054 (∗ corresponding author)
Y. Yi and Z. Zhang are with the Shanghai Key Laboratory of Intelligent Information Processing, School of Computer Science, Fudan
University, Shanghai 200433, China. Email: 15110240008@fudan.edu.cn,
zhangzz@fudan.edu.cn.

the system performance depends on the network topology and
the locations of the leaders. This dependence naturally leads
to the question of how to select the leaders so as to optimize
performance for a given topology.
We study the the performance of leader-follower networks
where nodes are governed by consensus dynamics and are also
subject to stochastic external disturbances. We consider two
types of dynamics. In the first, referred to as noise-free leaders,
leaders are not subject to disturbances and thus track the
external signal exactly. In the second dynamics, called noisecorrupted leaders, all nodes are subject to the external perturbations. As in many works on noisy consensus networks [5],
[15], [11], [10], we quantify the system performance by an
H2 norm that captures the steady-state variance of the node
states. We call this the coherence of the network. Coherence is
related to the spectrum of the Laplacian matrix of the network;
however, it is not always straightforward to relate this spectrum
to the network topology and locations of leaders.
In this work, we develop relationships between the steady-state
variance for a given leader set and resistance distances in a
corresponding electrical network. A similar approach was used
to study the performance of a single noise-free leader [12];
we generalize this notion to an arbitrary number of noise-free
leaders. Further, we develop a novel resistance-distance based
approach to study coherence in networks with an arbitrary
number of noise-corrupted leaders. We use this resistance
distance-based approach to analyze the coherence for different
network topologies based on resistance distances. In special
classes of graphs, we can relate the resistance distance to graph
distance, which gives us the optimal leader locations in terms
of the graph distances between leaders. We also e derive closed
form-expressions for the optimal single noise-free and noisecorrupted leaders in weighted graphs, the optimal k noise-free
leaders in cycles and paths, the optimal two noise-free leaders
in trees, and the optimal twof noise-corrupted leaders in cycles.
The leader selection problem for noise-free leaders was first
posed in [5]. This problem can be solved by an exhaustive
search over all subsets of nodes of size k, but this proves
computationally intractable for large graphs and large k.
Several works have proposed polynomial-time approximation
algorithms for the k-leader selection problem in noise-free
leader-follower systems [14], [7], [15], [8]. In particular, we
note that the solution presented in [15] yields a leader set
whose performance is within a provable bound of optimal.
With respect to analysis for the noise-free leader selection
problem, the recent work by Lin [9] gives asymptotic scalings

2

of the steady-state variance in directed lattice graphs for a
single noise-free leader, based on the graph distance from the
leader. Our recent work [11] gives polynomial-time algorithms
for optimal k-leader selection in weighted, undirected cycles
and path graphs. The leader-selection problem for noisecorrupted leaders was first posed by Lin et al. [7], who also
gave heuristic-based bounds and algorithms for its solution.
In addition, other performance measures have been considered
for the leader selection problem including controllability [16],
[17] and convergence rate [6], [11].
The recent works by Fitch and Leonard [10], [17] study the
optimal leader selection problem for noise-free and noisecorrupted leaders. These works also relate the steady-state
variance to a graph theoretic concept, in this case, graph centrality. The authors define centrality measures that capture the
performance of a given leader set. They then use this analysis
to identify the optimal leader sets for various classes of graphs.
We note that this work identifies the optimal single leader for
noise-free and noise-corrupted graphs under slightly stronger
assumptions than we make in our approach. In addition, [10]
identifies the optimal k-noise free leaders in cycles, under
the restriction that the number of nodes in the cycle is a
multiple of k. We address cycles with an arbitrary number of
nodes and provide a closed-form expression for the resulting
steady-state variance for any leader set based on the graph
distance between leaders. We view our proposed approach as
complementary that in [10]; for some classes of networks,
analysis is more straightforward under the resistance distance
interpretation. Thus, our work expands the classes of networks
that have known analytical solutions. A preliminary version
of our work appeared in [18]. This earlier work gave analysis
for noise-free leader selection in cycle and path graphs only,
using the related concept of commute times of random walks
rather than resistance distance. Our resistance-distance based
approach greatly simplifies the analysis and presentation.
The remainder of this paper is organized as follows. Section II
describes the system model and dynamics, and it formalizes the leader selection problems. Section III describes the
relationship between the system performance and resistance
distance for both noise-free and noise corrupted leaders.
This section also presents analysis of resistance distance for
“building blocks”, i.e., components of graphs, that will be
used to analyze specific graph topologies. Section IV gives
closed-form solutions for the leader selection problem for
various classes of graphs. In Section V, we compare the
asymptotic behavior of coherence in leader-free and leaderfollower consensus networks, and in Section VI, we give an
algorithm and a numerical example for increasing the size of a
binary tree while maintaining the optimality of the two noise
free leaders. Finally, we conclude in Section VII.

II. S YSTEM M ODEL AND P ROBLEM F ORMULATION
We consider a network of n agents, modeled by an undirected,
connected graph G = (V, E, W ), where V is the set of agents,
also called nodes, and E is the set of edges. The weight of edge

(i, j), denoted by wij , corresponds to the (i, j)th component
of the symmetric weighted adjacency matrix W . We let D
denote the diagonal matrix
P of weighted node degrees, with
diagonal entries dii = j∈V wij . The matrix L = D − W is
thus the weighted Laplacian matrix of the graph G.
Each node i ∈ V has a scalar-valued state xi . The objective
is for all node states to track an external signal x ∈ R. Some
subset of nodes F ⊂ V are followers that update their states
using noisy consensus dynamics, i.e.,
X
ẋi = −
wij (xi − xj ) + di ,
(1)
j∈N (i)

where Ni denotes the neighbor set of node i, and di is a
zero-mean, unit variance, white stochastic noise process. The
remaining set of nodes S = V \ F are leaders; leader nodes
have access x.
T
We write the state of the system as xT = [xT
l xf ], where xl
are the leader states and xf are the follower states. We can
then decompose the Laplacian of G as:


Lll Llf
L=
.
Lf l Lf f

A. Noise-Free Leader Dynamics
We consider two types of leader dynamics. In the first, called
noise-free leaders, leader states are dictated solely by x.
Without loss of generality, we assume x = 0 [5], so leader
nodes update their states as:
ẋi = −κi (xi − x) = −κi xi ,
where κi ∈ R+ is the weight node i gives to the external
signal, sometimes referred to as the degree of stubbornness
of node i. The dynamics of the follower nodes can then be
written as:
ẋf = −Lf f x + df ,
(2)
where Lf f is the principle submatrix of the Laplacian corresponding to the follower nodes, and df is the vector of noise
processes for the followers.
We quantify the performance of the system for a given leader
set S by its coherence, i.e., the total steady-state variance of
the follower nodes. This value is related to Lf f as follows [5],
RN F (S) = lim

t→∞

X
i∈(V \S)

 1

E xi (t)2 = tr (Lf f )−1 . (3)
2

Note that Lf f is positive definite for any S 6= 0 [5], and thus,
RN F (S) is well defined. The total variance depends on the
choice of leader nodes.
The nose-free leader selection problem is to identify the leader
set S of size at most k, such that RN F (S) is as small as
possible, i.e.,
minimize RN F (S)
(4)
subject to |S| ≤ k.

3

B. Noise-Corrupted Leader Dynamics

3

…
i

We also consider dynamics with noise-corrupted leaders. In
this case, the leader nodes update their states using both
consensus dynamics and the external signal, and the leader
states are also subject to external disturbances. We again
assume, without loss of generality, that x is 0. The dynamics
for leader node i are then:
X
ẋi = −
wij (xi − xj ) − κi xi + di ,

2

1
s
n
n-1

…

Fig. 1. Augmented cycle graph with noise-corrupted leaders nodes 1 and i.

j∈N (i)

where κi is the degree of stubbornness of node i, i.e., the
weight that it gives to its own state. The dynamics of the
entire system can be written as:
ẋ = −(L + Dκ DS )x + d,

(5)

where d is a vector of zero-mean white noise processes that
affect all nodes, Dκ is the diagonal matrix of degrees of
stubbornness, and DS is a diagonal (0,1) matrix with its (i, i)th
entry equal to 1 if node i is a leader and 0 otherwise. We note
that if S 6= ∅, then L + Dκ DS is positive semi-definite [19].
As with noise-free leaders, we define the performance of the
system for a given set of leaders S in terms of the total steadystate variance, which is given by [7],

1
(6)
RN C (S) = tr (L + Dκ DS )−1 .
2
The noise-corrupted leader selection problem is to identify the
set of at most k leaders that minimizes this variance, i.e.,
minimize RN C (S)
subject to |S| ≤ k.

(7)

This relationship can be generalized to multiple noise-free
leaders. In this case, the resistance distance r(i, S) is the
potential difference between follower node i and the leader
set S with unit current.
Proposition 1. The resistance distance r(i, S) from a node
i ∈ V \ S to a leader set S 6= ∅ is related to Lf f as:
r(u, S) = L−1
f f (i, i).
Proof: Let B ∈ R|E|×|V | be the incidence matrix of G. For
each edge e = (i, j) ∈ E, a direction is assigned arbitrarily.
B(e, i) = 1 if node i is the tail of edge e, B(e, i) = −1 if node
i is the head of edge e, and B(e, i) = 0 otherwise. A resistance
r is assigned to each edge e = (i, j) such that r(e) = w1ij . Let
K ∈ R|E|×|E| be a diagonal matrix with K(e, e) = r(e). It
is easy to verify that B > K −1 B = L. Let i ∈ R|E| represent
the current across all edges, and let v ∈ R|V | represent the
voltages at all vertices. By Kirchoff’s law, B > i = c, where
c ∈ R|V | denotes the external currents injected at all vertices,
and by Ohm’s law, Ki = Bv. It follows that,
Lv = c.

III. R ELATIONSHIP TO R ESISTANCE D ISTANCE
For a graph G = (V, E, W ), consider an electrical network
with V the set of nodes and E the set of edges, where each
edge (i, j) has resistance w1ij . The resistance distance between
two nodes i and j, denoted r(i, j), is the potential difference
between i and j when a unit current is applied between them.
Let Lj denote the Laplacian matrix of G where the row
and column of node j has been removed. It has been shown
that [20],
r(i, j) = L−1
(8)
j (i, i),
i.e., r(i, j) is given by the (i, i)th component of L−1
j .
We now show how the performance measures RN F (S) and
RN C (S) can be expressed in terms of resistance distances.
A. Noise-Free Leaders
For a single noise-free leader v, it follows directly from (8) that
the total steady-state variance is determined by the resistance
distances from all follower nodes to leader node v,
RN F ({v}) =

1
2

X
i∈V \{v}

r(i, v).

(9)

Let vj = 0 for all leaders j ∈ S, and thus vT = [0 vfT ], where
vf denotes the voltages for the follower nodes. Let ci = 1 for
follower i and ck = 0 for followers k 6= i. Expanding (9), we
obtain,


 

Lf f Llf
0
cl
=
,
Lf l Lf f
vf
ei
where ei is the canonical basis vector. Therefore, Lf f vf = ei ,
Since Lf f is positive definite, and thus, invertible, we have
r(i, S) = vi = L−1
f f (i, i).
The coherence for a set of noise-free leaders is given in the
following theorem, which follows directly from Proposition 1
and (3).
Theorem 2. Let G be a network with noise-free leader
dynamics, and let S be the set of leaders. The coherence of
G is:
1 X
r(i, S).
RN F (S) =
2
i∈V \S

B. Noise-Corrupted Leaders
For the case of noise-corrupted leaders, we obtain our expression for the coherence by constructing an augmented network.

4

Let G = (V, E, W ) be undirected weighted graph, and let
S ⊆ V be a set of noise-corrupted leaders. We form the
augmented graph G from G by adding a single node s to
G and creating an edge from each node i ∈ S to s, with edge
weight κi . An example is shown in Fig. 1 for an n-node cycle.
The noise-corrupted leaders are nodes 1 and i. We let r(u, v)
denote the resistance distance between nodes u and v in G
The relationship between resistance distances in G and the
coherence with a set S of noise-corrupted leaders is given in
the following theorem.
Theorem 3. Let G = (V, E, W ) be a network with noisecorrupted leader dynamics, and let S be the set of leaders.
Let G = (V , E, W ) be the corresponding augmented graph.
Then, the coherence of G is:
1X
r(i, s).
RN C (S) =
2

vertices i, j on the path, let dij denote their graph distance.
Then,
d2uy
d2
.
(10)
r(u, {x, y}) = dux − ux = duy −
dxy
dxy
Proof: We start by assigning 0 voltage to x and y. Then, we
impose unit external current to u, which flows out from {x, y}.
By definition, r(u, {x, y}) = vu , as defined in the proof of
Proposition 1. It follows that,
r(u, {x, y}) =

1
r(u,x)

= dux −

1
+

1
r(u,y)

=

1
dux

1
+

1
duy

d2uy
d2ux
= duy −
,
dxy
dxy

(11)
(12)

where the second equality follows from Lemma 5, and (12) is
obtained from (11) by applying the equality dux + duy = dxy .

i∈V

Proof: Let L be the weighted Laplacian of G, and let L be the
weighted Laplacian of G. We denote by Ls the matrix formed
from L by removing the row and column corresponding to
node s. We first note that, by the construction of G, Ls =
L + DS Dκ . By (8), for any node i ∈ V ,
−1

r(i, s) = (L + DS Dκ )

(i, i),

from which we obtain:
X

r(i, s) = tr (L + DS Dκ )−1 = 2RN C (S),
i∈V

where the last equality follows from (6).

C. Useful Results on Resistance Distance
We conclude this section by stating some useful results on
resistance distance.
Proposition 4. Let S ⊆ V , and for a node i ⊆ V , let Ui ⊆ S
be the set of nodes in S for which there is path from i to some
j ∈ U that does not traverse any other element in S. Then
r(i, S) = r(i, Ui ).
This proposition follows directly from the definition of resistance distance.
Lemma 5 ([20] Thm. D). Consider an undirected connected
graph G = (V, E, W ), and let duv denote the graph distance
between u, v ∈ V , i.e., the sum of the edge weights along
the shortest path between u and v. Then, r(u, v) ≤ duv , with
equality if and only if there is single path between u and v.
Lemma 6. Consider a weighted, undirected graph
G = (V, E, W ), partitioned into two components
A = (VA , EA , WA ) and B = (VB , EB , WB ) that share
only a single vertex {x}. Let S ⊆ VB . Then for any u ∈ VA ,

Theorem 8 ([21], Thm. 2.1). Let G0 = (V, E 0 , W 0 ) be
the graph formed by adding edge (i, j) to the connected,
undirected graph G = (V, E, W ), with edge weight wij . For
p, q ∈ V , let r(p, q) denote their resistance distance in G, and
let r0 (p, q) denote their resistance distance in G0 . Then,
2

r0 (p, q) = r(p, q) −

wij [r(p, i) + r(q, j) − r(p, j) − r(q, i)]
.
4 (1 + wij r(i, j))

IV. L EADER S ELECTION A NALYSIS
In this section, we use the resistance distance based formulations for coherence to provide closed-form solutions to the
leader selection problems for several classes of networks.
We first consider the case of a single leader v. For the noisefree case,
1 X
RN F ({v}) =
r(u, v).
(13)
2
u∈V \{v}

The expression (13) shows that the optimal single noise-free
leader is the node with minimal total resistance distance to all
other nodes. As shown in [17], this corresponds to the node
with maximal information centrality.
In the noise-corrupted case,
1X
RN F ({v}) =
r(u, s)
2
u∈V



X
1
= 
r(u, v) + |V |κv  .
2

(14)

u∈V \{v}

r(u, S) = r(u, x) + r(x, S)

where the last equality follows from Lemma 6. If all nodes exhibit the same degree of stubbornness, then the optimal noisefree leader and the optimal noise-corrupted leader coincide.
However, if nodes exhibit different degrees of stubbornness,
the single best leader may differ for the two dynamics.

Lemma 6 is a generalization of Lemma E from [20].
Lemma 7. Consider a weighted, undirected path graph, with
end vertices x and y. Let u be a vertex on the path. For any

We next explore the leader selections problems for k > 1
leaders. For the remainder of this section, we restrict our
study to networks where all edge weights and all degrees of
stubbornness, κi , are equal to 1.

5

A. k Noise-Free Leaders in a Cycle

B. k Noise-Free Leaders in a Path

Consider a cycle n nodes, identified by 1, 2, . . . , n in a
clockwise direction. We use the notation x ≺ y to mean that
node x precedes node y on the ring, clockwise and dxy denotes
the graph distance between nodes x and y where x ≺ y. For
example, for n = 5, where x = 4 and y = 2, x ≺ y and
dxy = 3.
Theorem 9. Let G be an n-node cycle with k noise-free
leaders, with n written n = k` + q, where ` and q are integers
with 0 ≤ q < k. Let S = {s1 , . . . , sk } be the leaders and let
c be a k-vector of graph distances between adjacent leaders,
i.e., ci is the distance between leader si and leader si+1 , for
i = 1 . . . k − 1, and ck is the distance between leader sk and
leader s1 . Then:

Consider a path graph with n nodes, identified by 1, 2, . . . , n.
Let duv denote the graph distance between nodes u and v.
Theorem 10. Let G be a path graph with n nodes, and let
S = {s1 , . . . sk } be a set of k noise-free leaders. Let c be a
(k + 1)-vector, where c1 = (s1 − 1) and ck+1 = n − sk . Let
ci = si+1 − si , for i = 2, . . . , k. Then,

1) The coherence of G is
RN F (S) =

1
T
12 (c c

− k).

2) S is an optimal solution to the k-leader selection problem
if and only if c ∈ C, where
)
(
k
X
di = n .
C = d | di ∈ {`, ` + 1}, i = 1 . . . k,
i=1

Proof: We first find the total resistance distance to S for all
nodes j such that with si ≺ j ≺ si+1 ,
X
X
r(j, S) =
r(j, {si , si+1 })
(15)
si ≺j≺si+1

si ≺j≺si+1

=

cX
i −1 

=

`−

`=1
1
2
6 ci

`2
ci




−1 ,

1) The coherence of G is:
k


1 X 2
1 2
c1 + c2k+1 + c1 + ck +
(c − 1).
4
12 i=2 i
(21)

RN F (S) =

2) Let n be such that, for the optimal leader configuration,
it holds that c1 + ck+1 = a, where 2 divides a and b =
(n − 1) − a, where (k − 1) divides b. Then, the optimal
solution to the k-leader selection problem is:


2(n − 1) − 3(k − 1)
(22)
c1 = ck+1 = round
6(k − 1) + 4
1
ci =
((n − 1) − 2c1 ) , i = 2 . . . k.
(23)
k−1
Proof: We first find the total resistance distance to S for all
nodes u with 1 ≤ u < s1 :
sX
1 −1

r(u, S) =

u=1

u=1

n
X

(17)

v=sk+1

r(v, S) =

ck+1 (ck+1 + 1)
.
2

si+1 −1

k

T

subject to 1 c = n

X

ci ∈ {1, . . . , n − 1}.

r(u, S) =

u=si +1

(19)
(20)

If k divides n, then it is straightforward to verify that c? =
is a solution to the above problem. In this case, ` = nk .

n
k1

For n = kl + q, with q > 0, assume that c is a solution to
(4) but c ∈
/ C. Then there exists some component ci such that
ci = ` + 1 + x for some integer x > 0 and some component
cj such that cj = ` − y for some integer y > 0. Let c0 be
such that c0i = ci − 1 and c0j = cj + 1 and c0` = c` for all
1
1
` 6= i, ` 6= j. Clearly, 12
cT c − k > 12
(c0 )T c0 − k , which
contradicts our assumption that c is a solution to (4).

ci (ci + 1)
,
2

(24)

(25)

The total resistance distances to S for all nodes u between si
and si+1 can be obtained in a similar fashion to (15) - (17),

1X1 2
1 T
RN F (S) =
(ci − 1) =
(c c − k).
2 i=1 6
12
With this, we can express problem (4) as an integer quadratic
program:

1
minimize 12
cT c − k
(18)

u=

where the first equality follows from Proposition 4 and
Lemma 5. Similarly, the total resistance distance to S for all
nodes v > sk is:

(16)

where (15) follows from (16) by Proposition 4 and Lemma 7.
Applying Proposition 1, we obtain,

ci
X

1 2
(c
− 1).
6 i+1

(26)

Combining (24), (25), and (26) with Proposition 1, we obtain,
RN F (S) =

1 X
r(u, S)
2
u∈V \S

=

k
1 2
1 X 2
(c1 + c2K+1 + c1 + ck+1 ) +
(ci − 1).
4
12 i=2

To find the optimal leader locations, we must solve the
optimization problem,
minimize
subject to

cT P c + rT d − k−1
12
1T c = n − 1
ci ∈ {1, . . . , n − 1},

(27)

where P is the (k +1)×(k +1) diagonal matrix with diagonal
1
1
1
components [ 41 12
. . . 12
4 ], and r is a (k + 1)-vector with
1
r1 = rk+1 = 4 , and all other entries equal to 0. Let c? be a

6

solution to (27). Using a similar argument to that in the proof
of Theorem 9, we can conclude c?1 = c?k+1 = a/2 for some
even integer a, i.e., that leaders s1 and sk should each be the
same distance from their respective ends of the path. Similarly,
c?i = b/(k − 1) for i = 2 . . . k, i.e., the leaders s2 , . . . , sk−1
should be equidistant.

T rooted at x, excluding those nodes in Ty , denoted by
Tx = (Vx , Ex ), and (3) the induced subgraph of T consisting
of nodes V − (Vx ∪ Vy ) ∪ {x, y}, which is denoted by
Gxy = (Vxy , Exy ). Note that by Proposition 4, for u ∈ Vx , it
holds that r(u, S) = r(u, x). Similarly, for u ∈ Vy , we have
r(u, S) = r(u, y). We can therefore decompose RN F (S) as,

Let q = a/2, so that the optimal leader placement has c?1 =
1
c?k+1 = q and c?i = k−1
((n − 1) − 2q), for i = 2 . . . k. Then,
we can reframe (27) as minimizeq∈{1,...,n} C(q), where,
!

2
(n − 1) − 2q
1 2
(k − 1)
−1 .
C(q) = (q + q) +
2
12
k−1

RN F ({x, y}) =


X
X
X
1
r(u, x) +
r(u, y) +
r(u, {x, y})
2

Relaxing the integer constraint, the value of q that minimizes
C(q) is,
2(n − 1) − 3(k − 1)
q? =
.
6(k − 1) + 4

=

Since C(q) is quadratic, the optimal integer value for q is
round(q). The values for ci , i = 1 . . . k + 1, in (22) - (23)
follow from the definition of q above.
While the restriction that c1 = ck+1 and ci = ci+1 , i =
2 . . . k does not hold for all network sizes, it can be shown
experimentally to hold for many. An example is a path graph
with n = 40 and k = 3, where c1 = c4 = 3 and c1 = c2 =
c3 = 11.

u∈Vx

u∈Vy

u∈Vxy

(28)




X
X
1X
r(u, {x, y}) , (29)
duy +
dux +
2
u∈Vx

u∈Vy

u∈Vxy

where (29) follows from (28) by Lemma 5.
With this decomposition, we can apply the building blocks
described in Section III-C to identify the optimal 2 noise-free
leaders in M -ary trees for various values of M . We begin with
M = 2.
Theorem 12. For the noise-free 2-leader selection problem in
a perfect binary tree with height h ≥ 4, the optimal leaders are
such that dxy = 4 and dxr = 2, and the resulting coherence
is:


(n + 1)
25
7
RN F (S) =
log2 (n + 1) −
+ .
(30)
2
8
2

C. Two Noise-Free Leaders in Trees
We next consider the 2-leader selection problem in rooted,
undirected M -ary trees. An M -ary tree is a rooted tree where
each node has at most M children. A perfect M -ary tree is
an M -ary tree in which all non-leaf nodes have exactly M
children and all leaves are in the same level. Let r denote the
root node of the tree, and let h denote its height. We number
the levels of the tree starting with the root, as 0, 1, 2, . . . , h.
The root of the tree is at level 0, and the leaves of a perfect
M -ary tree of height h are at level h. We use lev(x) to denote
the level of a node.
We begin with the following lemma, which gives general
guidance for the optimal location of two leader nodes.
Lemma 11. Consider a perfect M -ary tree T = (V, E). Let
x, y ∈ V, x 6= y be such that their lowest common ancestor
is a node of level ` > 0. Then, there exists y, z ∈ V, y 6= z,
with lowest common ancestor r such that RN F ({x, y}) >
RN F ({y, z}).
The proof of this lemma is given in Appendix 11. Lemma 11
tells us that the optimal 2-leader set will not have two nodes
in the same subtree of a child of r.
We denote these two leaders by x and y, and assume there
lowest common ancestor is r. Without loss of generality,
we assume lev(x) ≤ lev(y). We denote the graph distances
between x and y, x and r, and y and r by dxy , dxr and
dyr , respectively. To study the coherence of this system, we
decompose the tree into three subgraphs, (1) the subtree of
T rooted at y, denoted Ty = (Vy , Ey ), (2) the subtree of

The proof of Theorem 12 is given in Appendix B.
It is interesting to note that the optimal leader locations are
independent of the height of the tree. This independence of
the height also holds for M > 2, as shown in the following
theorems. Proofs are given in Appendix B.
Theorem 13. For the noise-free 2-leader selection problem
in a perfect ternary tree T (3) with height h ≥ 4, the optimal
leaders are such that dxy = 2 and dxr = 1, and the resulting
coherence is:
RN F (S) =

2n + 1
(log3 (2n + 1) − 2) + 1 .
4

(31)

Theorem 14. For the noise-free 2-leader selection problem a
perfect M -ary tree T , with M ≥ 4 and h ≥ 4, the optimal
leaders are such that dxy = 1 and dxr = 0, and the resulting
coherence is:


1
1
n+
logM (nM − n + 1)
2
M −1
n(M 2 + M − 1)
1
−
+
.
2M (M − 1)
2M

RN F (S) =

(32)

D. Two Noise-Corrupted Leaders in a Cycle Graphs
Consider an n-node cycle with nodes labeled {1, 2, . . . , n}.
We use Theorem 8 to determine the coherence of the graph
as a function of the graph distance between nodes 1 and i.
Theorem 15. In an n-node cycle with two noise-corrupted
leaders, where n is even, the coherence is minimized with the

7

leaders are at distance n/2 apart, and the resulting coherence
is:
n3 + 16n2 + 44n − 16
RN C (S) =
.
(33)
24(n + 8)
Proof: Without loss of generality, we assume node 1 and node i
are noise-corrupted leaders. Let the graph G be the augmented
graph shown in Fig. 1, omitting edge (i, s). By Lemma 7, for
arbitrary nodes u, v ∈ {1, 2, ..., n}, their resistance distance in
G is:
|u − v|(n − |u − v|)
r(u, v) =
,
n
and the resistance distance from a node u ∈ {1, 2, . . . , n} is:
r(u, s) = r(u, 1) + 1 =

(u − 1)(n − (u − 1))
+ 1.
n

Let G0 be the graph formed from G by the addition of
edge (i, s). Then, for a node u ∈ {1, 2, ..., n}, the resistance
distance from u to s in G0 is:
2

[r(u, i) + r(s, s) − r(u, s) − r(i, s)]
4 (1 + r(i, s))
(u − 1)(n − (u − 1)
+ 1−
=
n
h
i2
|u−i|(n−|u−i|)
− (u−1)(n−(u−1))
− ((i−1)(n−(i−1))
−2
n
n
n



.
4 1 + (i−1)(n−(i−1))
+
1
n

r0 (u, s) = r(u, s) −

By Theorem 3, summing over all nodes u, we obtain:
n
1X 0
1 2
RN C (S) =
r (u, s) =
(n + 6n − 1)
2 u=1
12
h
1

 2i4 − 4i3 (n + 2)
−
12n 2 + (i−1)(n−(i−1))
n

i
+ i3 (2n2 + 6n + 11) + i(2n2 + n − 6) + 2n2 − 3n + 1 .
(34)
We note that this function is continuous over the interval [1, n].
We then take the derivative with respect to i:
∂
RN C (S) =
∂i
h
1
2i5 − 5i4 (n + 2))
(6(−i2 + i(n + 2) + n − 1)2 )
+ 4i3 (n2 + 3n + 5) − i2 (n3 + 6n + 20)
i
− 2i(n3 + 3n2 + n − 5) + n2 + n − 2 .
The derivative has five roots. Of these, only i = (n + 2)/2 lies
in the interval [1, n]. Further, it is a minima of ∂/∂iRN C (S).
For even n, we substitute this value of i into (34) to obtain
(33).

Algorithm 1 Algorithm to add nodes to a perfect binary tree
of height h, while maintaining optimality of the 2 leaders.
Input: Th , with optimal 2 leaders x and y
while there is a new node u to add do
if last level of left or right subtree of x is not filled then
Add node u to level h+1 of subtree of x with fewer leaves,
breaking ties arbitrarily.
else if last level of left or right subtree of y is not filled then
Add node u to level h+1 of subtree of y with fewer leaves,
breaking ties arbitrarily.
else
Add node u as leaf on level h + 1, in any remaining
location.
end if
if level h + 1 is filled then
h←h+1
end if
end while

V. C OMPARISON TO C OHERENCE IN L EADER -F REE
N ETWORKS
Network coherence has also been studied in graphs without
leaders. In this setting, every node behaves as a follower, using
the dynamics in (1). Coherence is measured as the total steadystate variance of the deviation from the average of all node
states,
2

n
n
X
X
1
E xi (t) −
xj (t) .
V = lim
t→∞
n
i=1
j=1
It has been shown that, for a network with a single noise-free
leader, i.e.,|S| = 1 [5],
RN F (S) ≥ V.
In some sense, this means that adding a single leader increases
the disorder of the network.
In a leader-free cycle graph, it has been shown that the
coherence V scales as O(n2 ) [3]. In a cycle with k noise-free
leaders, where the leaders are located optimally, by Theorem 9,


1  n 2 T
n2
k
RN F (S) =
1 1−k =
− .
12
k
12k 12
Thus for a fixed leader set size k, The coherence RN F (S)
also scales as O(n2 ). Similarly, for the optimal two noisecorrupted leaders in a cycle, RN C (S) scales as O(n2 ). This
shows that, in the limit of large n, in cycle networks, the
disorder of the network is similar for leader-free and leaderfollower consensus networks.
VI. N UMERICAL E XAMPLE
Theorem 12 applies to the noise-free leader selection problem
in a perfect binary tree. We now present an algorithm that
can be used to grow the tree by adding nodes in a way that
does not change the location of the optimal two noise-free
leaders. Pseudocode for this tree-growing process is given in
Algorithm 1. The algorithm is initialized with a perfect binary

8

r

9

...

log2(RNF)

8.5

A
P (x, y ′ )

8

B

C
P (x, y)

7.5

D

E

F

G

7

y′

y
x
6.5
60

70

80

90

100

110

120

130

n

Fig. 2. Coherence for two-noise free leaders, as a perfect binary tree of height
5 is grown into a perfect binary tree of height 6 using Algorithm 1.

tree of height h ≥ 4, with the optimal leader set {x̂, ŷ}, with
dx̂r = 2 and dŷr = 2. In each iteration, a node is added in a
location dictated by the algorithm.
The analysis of this algorithm remains an open question.
However, example executions, the algorithm is able to grow
a tree from height h to height h + 1 without impacting the
optimality of the leader nodes x and y. In Fig. 2, we show
such and execution. The algorithm is initialized with a perfect
binary tree of of height h = 5, with 63 nodes. Nodes are added
according to the algorithm, until the tree is a perfect binary
tree of height h = 6, with 127 nodes. The figure shows the
coherence for every pair of leader nodes such that dxr ≤ 3 and
dyr ≤ 3, in log scale. The coherence for the leader set {x̂, ŷ}
is shown in red, while the coherence for each other leader set
is shown in blue. As the figure shows, the coherence for {x̂, ŷ}
is the smallest throughout the execution of the algorithm.
VII. C ONCLUSION
We have investigated the performance of leader-follower consensus networks under two types of leader dynamics, noisefree leaders and noise-corrupted leaders. For both leader
dynamics, we have developed a characterization of the system
performance in terms of resistance distances in electrical
networks. With this characterization, we have derived closedform expressions for network coherence in terms of the leader
locations. We have also identified the optimal leader locations
in several special classes of networks.
In future work, we plan to extend our analysis to study
coherence in general leader-follower networks. We also plan to
develop a similar mathematical framework to study coherence
in second-order systems.
A PPENDIX A
P ROOF OF L EMMA 11
Proof: Let x and y be the optimal two noise-free leaders
in a perfect binary tree T . Without loss of generality, let

SD

SB

SE

...
...
...
...
...

SA

SF

SC

SG

Fig. 3. Arrangement of nodes in perfect binary tree with two possible leader
sets {x, y} and {x, y 0 }.

lev(x) ≤ lev(y). Assume, for contradiction, that the lowest
common ancestor of x and y is a node B that is a descendant
of the root t. Let A be the parent of B, and let D and E be
children of B. Let x be a member of the node set consisting of
node B and the nodes in the subtree rooted at D. We denote
this node set by SD . Let y be a node in the subtree rooted at
E. We denote this node set by SE . Let SB denote the node
set in the subtree rooted at B, excluding B and the nodes in
SD and SE . This arrangement is shown in Fig. 3.
Let C be another child of A, as shown in the figure, and let
F and G be children of C, with the node sets of the the trees
rooted at F and G denoted by SF and SG , respectively. Let SC
denote the node set of the subtree rooted at C, excluding C and
the nodes in SF and SG . We will prove that, for a node y 0 in
the subtree rooted at G that is in the same location with respect
to G that y is with respect to to E, RN F {x, y} > RN F {x, y 0 }.
Let P (x, y) denote the vertices along the path between x and
y, and let P (x, y 0 ) denote the vertices along the path between
x and y 0 . Consider a pair of vertices u ∈ SD and k ∈ SF ,
where k is at the same location relative to F (in the subtree
rooted at F ) that u is relative to D (in the subtree rooted at
D). Denote the vertex on P (x, y) that is the nearest to u by
p. We find the sum of the resistance distances of u and k to
the respective leader sets {x, y} and {x, y 0 }. By Lemmas 5
and 7,

Ru,k
0
Ru,k

=

r(u, {x, y}) + r(k, {x, y})

=

dup + r(p, {x, y}) + dkB + r(B, {x, y}) ,

= r(u, {x, y 0 }) + r(k, {x, y 0 })
= dup + r(p, {x, y 0 }) + dkC + r(C, {x, y 0 }) .

Noting that dBy = dCy0 and dxy0 = dxy + 2, and applying

9

Since dCy0 = dBy ,

Lemma 7, we have:
0
Ru,k − Ru,k
=(dup − dup ) + (dkB − dkC )

0
Ri,j − Ri,j
=(diB − diB ) + (djB − djC )

0

+ (r(p, {x, y} − r(p, {x, y }))

+ r(B, {x, y}) − r(B, {x, y 0 })

+ (r(B, {x, y}) − r(C, {x, y 0 }))
=0 + 2 +
+

dpx −

dBy −

d2By
dxy

d2px
d2px
− (dpx −
)
dxy
dxy0
!
d2Cy0
− (dCy0 −
)
dxy0

+ r(B, {x, y}) − r(C, {x, y 0 })


d2
d2
=0 + 2 + dBx − Bx − (dBx − Bx )
dxy
dxy0
!
2
2
dBy
dCy0
+ dBy −
− (dCy0 −
)
dxy
dxy0

!

2(d2xp + d2By )
.
=2−
dxy (dxy + 2)
Further, since dxp ≤ dxB and dxB + dBy = dxy , we obtain:
0
Ru,k − Ru,k
≥

4(dxB dBy + dxy )
> 0.
dxy (dxy + 2)

Next, consider a pair of vertices v ∈ SE and ` ∈ SG , where
` is at the same location relative to G that v is relative to E.
Denote the vertex on P (x, y) that is the nearest to v by q, and
denote the vertex on P (x, y 0 ) that is nearest to ` by m The
sum of the resistance distances from v and ` to the respective
leader sets are (again, by Lemmas 5 and 7),
Rv,`
0
Rv,`

=

r(v, {x, y}) + r(`, {x, y})

=

dvq + r(q, {x, y}) + d`B + r(B, {x, y})
0

0

=

r(v, {x, y }) + r(`, {x, y })

=

dvB + r(B, {x, y 0 }) + d`m + r(m, {x, y 0 }) .

We note that dvq = d`m , dqy = dmy0 and dxy0 = dxy + 2.
Then,
0
Rv,` − Rv,`
=(dvq − dlm ) + (dlB − dvB )

+ r(q, {x, y}) − r(m, {x, y 0 })
+ r(B, {x, y}) − r(B, {x, y 0 })
!
d2my0
d2qy
− (dmy0 −
)
=0 + 2 + dqy −
dxy
dxy0


d2xB
d2xB
+ dxB −
− (dxB −
)
dxy
dxy0
2(d2xB + d2qy )
=2 −
.
dxy (dxy + 2)
0
Since dqy ≤ dBy and dxB +dBy = dxy , similar to Ru,k −Ru,k
,
0
we obtain Rv,` − Rv,` > 0.

For a pair of vertices i ∈ SB ∪ {B} and j ∈ SC ∪ {C}, where
` is at the same location relative to G that v is relative to E,
define
Ri,j = r(i, {x, y}) + r(j, {x, y})
= diB + r(B, {x, y}) + djB + r(B, {x, y})
0
Ri,j
= r(i, {x, y 0 }) + r(j, {x, y 0 })

= diB + r(B, {x, y 0 }) + djC + r(C, {x, y 0 }).

=2 −

2(d2xB + d2By )
.
dxy (dxy + 2)

Since dxB + dBy = dxy , it follows that
0
Ri,j − Ri,j
=

4(dxB dBy + dxy )
> 0.
dxy (dxy + 2)

Finally, we consider a vertex t that is not in the subtree rooted
at B nor the subtree rooted at C. In this case,
Rt = r(t, {x, y}) = dtB + r(B, {x, y})
Rt0 = r(t, {x, y 0 }) = dtA + r(A, {x, y 0 }).
It follows that
Rt − Rt0 = 2 −

(dxB + 1)2
d2xB
.
+
dxy
dxy + 2

Recall that dxy = dxB + dBy . Thus, Rt − Rt0 > 0.
Since |SD | = |SE | = |SF | = |SG | and |SB ∪ {B}| =
|SC ∪ {C}|, by grouping vertices into pairs, we have shown
that,
n
n
1X
1X
r(i, {x, y}) >
r(i, {x, y 0 }).
2 i=1
2 i=1
This contradicts our assumption that {x, y} is the optimal
leader set.

A PPENDIX B
P ROOF OF T HEOREMS 12, 13, AND 14
We first define a quantity Ω(S) as:
Ω(S) =

X

r(i, S) = 2RN F (S) .

i∈V \S

and note that a set S that is a minimizer of Ω(·) is also a
minimizer of RN F (·).
We next present a lemma that gives Ω(·) of a perfect M -ary
tree with two noise free leaders .

10

Lemma 16. Let T be a perfect M -ary tree with height h. Let
x and y be its two noise-free leaders, and assume that the
lowest common ancestor of x and y is the root of T . Then,


M h+1 + 1
d2
Ω({x, y}) =
dxr − xr
M −1
dxy


2
M +1
h+1
+M
+
(M dxr −dxy + M −dxr )
(M − 1)2
(M − 1)3 dy


2(M + 1)
3
h
−
−
+ M h+1
M −1
(M − 1)2
(M − 1)3 dxy
dxy
M
+
+
.
(35)
M −1
(M − 1)2

Proof: Recall that in (29), we decomposed the coherence into
three terms: the coherence in the subtree rooted at x, the
coherence in the subtree rooted at y, and the coherence at
the remaining nodes. We can also devide Ω into three part as
X
X
X
Ω({x, y}) =
dux +
duy +
r(u, {x, y}).
u∈Vx

u∈Vy

u∈Vxy

To simplify the first sum in (36), we first consider the subtrees
rooted at nodes on the path from x to r, denoted by P (x, r)
(excluding r):
X

R(Tj ) =

j∈P (x,r)
j6=x,r

((M − 1)h − M − 1) · M h
dxr − 1
+
M −1
(M − 1)2
+

((M − 1)dxr − (M − 1)h + 2) · M h−dxr +1
.
(M − 1)2
(37)

A similar expression can be obtained for the subtrees rooted
at nodes on the path from r to y, substituting dxr with dyr .
To simplify the second sum in (36), we also first consider the
subtrees rooted on nodes on the path P (x, r), which is:
X

|Tj |rj ({x, y}) = M h+1

j∈P (x,r)
j6=x,y



M +1
1
+
(M − 1)2
(M − 1)3 dxy

((M − 1)dxr − M )((M − 1)(dxy − dxr ) + M )
(M − 1)3 dxy
h+1
M
.
−
(M − 1)3 dxy



+ Mh

We let Ty denote the subtree rooted at y, Tx denote the subtree
rooted at x, excluding those nodes in Ty . The remaining
subgraph is denoted by Gxy .
We consider two cases: (1) x is not the root of T , and (2) x
is the root of T .
By Lemma 5, the resistance distance of a node i in Tx (or Ty )
to the leader set depends
P only on the resistance distance to x
(or y). Let R(Tx ) = i∈Tx r(i, x). The height of the subtree
rooted at x is hx = h − dxr , where dxr is the graph distance
between x and r. At each level i in Tx there are M i nodes,
each at distance i from x. Thus,

Phx
hx
R(Tx ) = i=1
M i · i = (MM
+1 .
−1)2 (M hx − hx − 1)M
A similar expression can be obtained for R(Ty ).
We next consider Gxy . We can think of this subgraph as a
path graph connecting nodes x and y, denoted by P (x, y),
with each node in the path the root of its own subtree. For
any node j on the path between x and y, r(j, {x, y}) is given
by Lemma 7. For any node v in the subtree Tj , its resistance
distance to {x, y} is
r(v, {x, y}) = dvj + r(j, {x, y}).

(38)

As before, a similar expression can be obtained for the
subtrees rooted at nodes on the path from r to y, substituting
dxr with dyr .
The above sums (37) and (38), and their corresponding sums
for P (r, y) account for the subtrees rooted at two children of
r, one containing leader x and one containing leader y. For
each of the remaining M − 2 children of r, the total resistance
distance to x and y from the subtree rooted at child v is
R(Tv ) =

((h − 1)M − h)M h + M M h − 1
+
(M − 1)2
M −1


dxr −


d2xr
+1 .
dxy

Combining all of these sums and including r(r, {x, y}),
we obtain R(Gxy ). Substituting the expressions for R(Tx ),
R(Ty ), R(Gxy ), and the equality dyr = dxy − dxr into (29)
leads to (35).
Case 2: x is the root. In this case, R(Ty ) is the same as in
Case 1, but R(Tx ) is now
R(Tx ) =

h
X
M h (M h − h − 1) + 1
(M − 1)M i−1 · i =
. (39)
M −1
i=1

From this, we obtain,
R(Gxy ) = 16 (dxy 2 − 1) +

P

j∈P (x,y)
j6=x,y

(R(Tj ) + (|Tj | − 1)r(j, {x, y})) .

The first term is the total resistance distance for nodes on the
path from x to y. For the summation terms, first we compute
the total resistance distance from nodes in the subtree rooted
at j to j. Then, for each node in the subtree, excluding j, we
add the resistance distance from j to {x, y}. An equivalent
expression is:
R(Gxy ) =

X

(R(Tj ) + |Tj |r(j, {x, y}))

X
j∈P (x,y)
j6=x,y

R(Tj ) +

X
j∈P (x,y)
j6=x,y

|Tj |r(j, {x, y}).

dxy
M
Ω({r, y}) =
+
M −1
(M − 1)2


2
M +1
+ M h+1
+
(M −dxy + 1)
(M − 1)2
(M − 1)3 dy


2(M + 1)
3
h
+ M h+1
−
−
,
M −1
(M − 1)2
(M − 1)3 dxy

(40)

which is equal to (35) given dxr = 0.

j∈P (x,y)
j6=x,y

=

For R(Gxy ), we only need to consider the path from root to y by
using (38). Combining (39) and (38), we obtain

(36)

Thus, we conclude that in a perfect M -ary tree, (35) holds for
any leader set {x, y} where their lowest common ancestor is
the root.

11

A. Proof of Theorem 12

B. Proof of Theorem 13

Proof: We first simplify (35) in Lemma 16 for M = 2,
6
Ω({x, y}) = 2 + 2h (2h − 6) + dxy − 2h+1 · dxy




d2
+ 2h+1 + 1
dxr − xr
dxy


 3
h+1
−dxr
−(dxy −dxr )
+2
2
+2
+2 .
dxy

Proof: Based on Lemma 16, we derive Ω({x, y}) for a perfect
ternary with height h, where x and y have the root as their
lowest common ancestor,
(41)

For a given dxy and h, we treat Ω as a continuous function with
argument dxr . We derive expressions for its first and second
derivative:



∂Ω
2dxr
= 2h+1 + 1
1−
∂dxr
dxy


 3
+ 2h+1 2dxr −dxy − 2−dxr
+ 2 · ln 2 ,
(42)
dxy




∂2Ω
2
= 2h+1 + 1
−
2
∂ dxr
dxy


 3
+ 2h+1 2−dxr + 2dxr −dxy
+ 2 · (ln 2)2
dxy
(43)



 2 
dxy
3
≥ 2h+1 + 1
−
+ 2h+2− 2
+ 2 (ln 2)2 .
dxy
dxy
(44)

From (42), we observe that Ω has an extremum at dxr =
dxy /2. For dxy ≤ 5 and h ≥ 4, (44) is strictly positive, thus
Ω is convex with respect to dxr . This means that dxr = dxy /2
is a minimizer for the given dxy .
For h ≥ 4, and dxy ≤ 5, we examine the potential integer
minimizers dxy = 5, dxr = 2; dxy = 4, dxr = 2; dxy = 3,
dxr = 1; dxy = 2, dxr = 1; and dxy = 1, dxr = 1. By
comparing them in Ω({x, y}) in (41), we find the minimum
is always attained at dxy = 4, dxy = 2.
2

∂Ω
For dxy ≥ 6 and h ≥ 4, by checking ∂d
and ∂∂2 dΩxr , we
xr
observe that Ω has two minima. Because of the symmetry
of the function, these two minima must have the same value,
and so we only need to study the solution where dxr ≤ dxy /2.
Since dxy ≥ 6 and h ≥ 4, we have:

∂Ω
∂dxr

dxr =0



= 2h+1 + 1
 3



+ 2h+1
+ 2 ln 2 2−dxy − 1 < 0 ,
dxy

and
∂Ω
∂dxr

dxr =2




4
= 2h+1 + 1
1−
dxy




3
1
+ 2h+1
+ 2 ln 2 22−dxy −
> 0.
dxy
4

Therefore, an integer minimizer of Ω is attained in the set
dxr ∈ {0, 1, 2}. It is readily verified that for h ≥ 4 and
dxy ≥ 6,
Ω|dxy ≥6,dxr =k ≥ Ω|dxy =4,dxr =2 ,
for k ∈ {0, 1, 2}. This implies that dxy = 4, dxr = 2 is the
integer solution that minimizes Ω for all h ≥ 4. We obtain the
expression for RN F in (30) by substituting dxy = 4, dxr = 2
and n = 2h+1 − 1 into (41) and applying Ω = 2RN F .



d2
3h+1 + 1
dxr − xr
2
dxy


3h+1
1
(3dxr −dxy + 3−dxr )
+
1+
2
dxy


3h+1
dxy
3
2
3
+
+
h− −
+ .
2
2
dxy
2
4

Ω({x, y}) =

(45)

For a given dxy , we find its first and second derivative,


∂Ω
3h+1 + 1
2dxr
=
1−
∂dxr
2
dxy

 1
h+1 
3
+
· 3dxr −dxy − 3−dxr
(46)
+ 1 · ln 3
2
dxy


∂2Ω
1
= (3h+1 + 1) −
∂ 2 dxr
dxy

 1
3h+1  dxr +dxy
+ 3−dxr
3
+
+ 1 · (ln 3)2
2
dxy




dxy
1
1
+ 3h+1− 2
+ 1 · (ln 3)2 . (47)
≥ (3h+1 + 1) −
dxy
dxy

Similar to the proof of Theorem 12, we obtain that dxy = 2,
dxr = 1 is the optimal integer solution for any h ≥ 4 and
dxy ≤ 2. By enumerating all dxy , dxr , given dxy ≤ 4, we
can verify that dxy = 2, dxr=1 is the optimal solution for any
h ≥ 4 and dxy ≤ 4.
2

∂Ω
As shown by ∂d
and ∂∂2 dΩxr , for a given dxy , Ω has two
xr
minima. Because of the symmetry of (45), we only need to
study the minimum that satisfies dxr ≤ dxy . For any given
dxy ≥ 5, h ≥ 4,

∂Ω
=
∂dxr dxr =0

 1
3h+1 + 1
3h+1  −dxy
+
3
−1
+ 1 (ln 3) < 0
2
2
dxy
∂Ω
=
∂dxr dxr =2


h+1
3
+1
4
3h+1  2−dxy
1 1
1−
+
3
−
(
+ 1)(ln 3) > 0.
2
dxy
2
9 dxy

Thus, the optimal real-valued dxr lies in (0, 2). By evaluating
(45) for k ∈ {0, 1, 2}, it can be verified that,
Ω|dxy ≥5,dxr =k ≥ Ω|dxy =2,dxr =1 .
Thus, we have shown that dxy = 2, dxr = 1 is the global
integer minimizer for all h ≥ 4 in perfect ternary trees. We
obtain (31) by substituting dxr = 1, dxy = 2 into (41) and
applying n = (3h+1 − 1)/2 and Ω = 2RN F .

12

R EFERENCES

C. Proof of Theorem 14
Proof: We start by calculating

∂Ω
∂dxr

and

∂2Ω
∂ 2 dxr .,




∂Ω
M h+1 + 1
2dxr
+ (ln M )M h+1
=
1−
∂dxr
M −1
dxy
(M
M +1 
dxr −dxy
−dxr
(M
−M
)
+
(M − 1)3 dy



∂2Ω
M h+1 + 1
2
=
+ (ln M )2 M h+1
1−
2
∂ dxr
M −1
dxy
(M
M +1 
dxr −dxy
−dxr
(M
+M
).
+
(M − 1)3 dy

[1] M. H. DeGroot, “Reaching a consensus,” J. Amer. Statist. Assoc., vol. 69,
no. 345, pp. 118–121, 1974.

2
− 1)2
(48)
2
− 1)2
(49)

From (48) and (49), we observe that Ω has a minimum that
d
dxy
satisfies dxr ≤ xy
2 . Since Ω is symmetric about dxr = 2 ,
d
we only consider potential integer minimizers with dxr ≤ xy
2 .
Further,
∂Ω
∂dxr



Mh
1
2
M
+
)(M − 1)2 (1 −
)
(M − 1)3
Mh
dxy
dxr =1



M +1
+ 2(M − 1) +
(50)
)(M 2−dxy − 1 ln(M ) ,
dxy
=

∂Ω
and observe that ∂d
|dxy =2,dxr =1 = 0. For dxy ≥ 3, we can
xr
lower bound (50) by

∂Ω
∂dxr


Mh
2
>
M (M − 1)2 (1 −
)
(M − 1)3
dxy
dxr =1

M +1
) ln(M ) .
− (2(M − 1) +
dxy

(51)

For dxy ≥ 3, the bound (51) is positive for M = 4 and h ≥ 4,
and it is increasing in M , dxy and h. Thus, for all dxy ≥ 2,
the integer minimizer of dxr will be either 0 or 1. Further, for
dxy = 1, the only potential solution that satisfies dxr ≤ dxy /2
is dxr = 0.
We propose that the optimal integer solution is dxy = 1,
dxr = 0, and we validate its optimality by comparing with
dxy ≥ 2 and dxr ∈ {0, 1}. For dxy ≥ 2,
Ω|dxr =0 − Ω|dxy =1,dxr =0 =

1
(M − 1)2 dxy (dxy − 1)
(M − 1)3 dxy
h+1−dxy

((2dxy + 1)M − 2dxy + 1)

+ M (dxy (M − 1)2 − M (M + 1)) ,

+M

h

which is positive for M ≥ 4. In addtion,
Ω|dxr =1 − Ω|dxy =1,dxr =0 =

1
(M − 1)2 (d2xy − 1)
3
(M − 1) dxy
+ M h+2−dxy ((2dxy + 1)M − 2dxy + 1)

+ M h (dxy (M − 1)3 − M (M 2 + 2)) ,

is also positive for dxy ≥ 2 and M ≥ 4. Therefore, the
optimal leader set {x, y} is such that dxy = 1, dxr = 0 when
M ≥ 4 and h ≥ 4. Then, (32) is obtained by substituting
dxr = 0, dxy = 1, n = (M h+1 − 1)/(M − 1) into (35) and
using the fact that Ω = 2RN F .

[2] L. Xiao, S. Boyd, and S. Lall, “A scheme for robust distributed sensor
fusion based on average consensus,” in Proc. 4th Int. Sym. Information
processing in sensor networks, 2005, p. 9.
[3] B. Bamieh, M. Jovanovic, P. Mitra, and S. Patterson, “Coherence in
large-scale networks: Dimension-dependent limitations of local feedback,” IEEE Trans. Autom. Control, vol. 57, no. 9, pp. 2235–2249, Sep
2012.
[4] G. Cybenko, “Dynamic load balancing for distributed memory multiprocessors,” J. Parallel Distrib. Comput., vol. 7, no. 2, pp. 279–301, Oct.
1989.
[5] S. Patterson and B. Bamieh, “Leader selection for optimal network
coherence,” in Proc. 49th IEEE Conf. Decision and Control, 2010, pp.
2692–2697.
[6] 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. Control, vol. 59,
no. 6, pp. 1480–1494, Jun 2014.
[7] F. Lin, M. Fardad, and M. Jovanovic, “Algorithms for leader selection in
stochastically forced consensus networks,” IEEE Trans. Autom. Control,
vol. 59, no. 7, pp. 1789–1802, Jul 2014.
[8] S. Patterson, “In-network leader selection for acyclic graphs,” in Proc.
American Control Conference, 2015, pp. 329–334.
[9] F. Lin, “Performance of leader-follower multi-agent systems in
directed networks,” arXiv:1606.02269, 2016. [Online]. Available:
https://arxiv.org/abs/1606.02269
[10] K. Fitch and N. Leonard, “Joint centrality distinguishes optimal leaders
in noisy networks,” IEEE Trans. Control Netw. Syst., vol. 3, no. 4, pp.
366–378, 2016.
[11] 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. PP, no. 99, pp. 1–1, 2016.
[12] P. Barooah and J. Hespanha, “Graph effective resistance and distributed
control: Spectral properties and applications,” in Proc. 45th IEEE Conf.
Decision and Control, Dec 2006, pp. 3479–3485.
[13] L. Vassio, F. Fagnani, P. Frasca, and A. Ozdaglar, “Message passing
optimization of harmonic influence centrality,” IEEE Trans. Control
Netw. Syst., vol. 1, no. 1, pp. 109–120, March 2014.
[14] 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.
[15] 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. Control, vol. 59, no. 2, pp. 283–296, Feb
2014.
[16] A. Olshevsky, “Minimum input selection for structural controllability,”
in Proc. American Control Conference, 2015, pp. 2218–2223.
[17] K. Fitch and N. Leonard, “Optimal leader selection for controllability
and robustness in multi-agent networks,” in Proc. European Control
Conference, 2016.
[18] S. Patterson, “Optimizing coherence in 1-d noisy consensus networks
with noise-free leaders,” in Proc. American Control Conference, 2017.
[19] 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.
[20] D. Klein and M. Randic, “Resistance distance,” J. Math. Chem., no. 1,
pp. 81–95, 1993.
[21] Y. Yang and D. J. Klein, “A recursion formula for resistance distances
and its applications,” Discrete Appl. Math., vol. 161, no. 16-17, pp.
2702–2715, Nov. 2013.

