\section{Background and Notation}
\label{sec:defs}
We use $\mathcal{G} = \{\mathcal{V},\mathcal{E}\}$ to denote an undirected graph where $\mathcal{V}$ is the set of nodes (or vertices) and $\mathcal{E} \subset \mathcal{V}\times\mathcal{V}$ is the set of edges.  We will denote the number of vertices by $n$.  The {\it neighbors} of  node $v_i \in \mathcal{V}$ in graph $\mathcal{G}$ are given by the set $\mathcal{N}_i = \{v_j \in \mathcal{V}~|~(v_i, v_j) \in \mathcal{E}\}$.  The {\it degree} of node $v_i$ is $d_i = |\mathcal{N}_i|$, and the minimum and maximum degrees of the nodes in the graph will be denoted by $d_{min}$ and $d_{max}$, respectively.  If $d_{max} = d_{min} = d$, the graph is said to be $d$-{\it regular}.  For a given set of nodes $S \subset \mathcal{V}$, the {\it edge-boundary} (or just boundary) of the set is given by $\partial{S} = \{(v_i,v_j) \in \mathcal{E} \mid v_i \in S, v_j \in \mathcal{V}\setminus{S}\}$.  The {\it isoperimetric constant} of $\mathcal{G}$ is given by \cite{ChungSpectral}
 $$
 i(\mathcal{G})\triangleq \min_{A \subset \mathcal{V}, |A| \le \frac{n}{2}}\frac{|\partial A|}{|A|}.
 $$
 Choosing $A$ to be the vertex with the smallest degree yields the bound $i(\mathcal{G}) \le d_{min}$.
 
 \subsection{Laplacian and Grounded Laplacian Matrices}
 \label{subsec:prop_grounded_laplacian}
 The {\it adjacency matrix} for the graph is a matrix $A \in \{0,1\}^{n\times{n}}$, where entry $(i,j)$ is $1$ if $(v_i,v_j) \in \mathcal{E}$, and zero otherwise.  The {\it Laplacian matrix} for the graph is given by $L = D - A$, where $D$ is the degree matrix with $D = \hbox{diag}(d_1, d_2, \ldots, d_n)$.  For an undirected graph $\mathcal{G}$, the Laplacian $L$ is a symmetric matrix with real eigenvalues that can be ordered sequentially as $0=\lambda_1 (L)\leq \lambda_2 (L)\leq \cdots \leq \lambda_n (L)\leq 2d_{max}$.  The second smallest eigenvalue $\lambda_2(L)$ is termed the {\it algebraic connectivity} of the graph and satisfies the bound \cite{ChungSpectral} 
 \begin{equation}
\lambda_2(L) \ge \frac{i(\mathcal{G})^2}{2d_{max}}.
\label{eqn:lower_bound_lambda_2_iso}
\end{equation}

 
  We will designate a nonempty subset of  vertices $\mathcal{S} \subset \mathcal{V}$ to be {\it grounded nodes}, and assume without loss of generality that they are placed last in the ordering of the nodes. 
 We use $\alpha_i$ to denote the number of grounded nodes that node $v_i$ is connected to (i.e., $\alpha_i = \left|\mathcal{N}_i \cap \mathcal{S}\right|$).  
 Removing the rows and columns of  $L$ corresponding to the grounded nodes $S$ produces a {\it grounded Laplacian matrix} (also known as a {\it Dirichlet Laplacian matrix}) denoted by $L_{g}(S)$.  When the set $S$ is fixed and clear from the context, we will simply use $L_g$ to denote the grounded Laplacian.
For any given set $S$, we denote the smallest eigenvalue of the grounded Laplacian by $\lambda(L_{g}(S))$ or simply $\lambda$.  

When the graph $\mathcal{G}$ is connected, the grounded Laplacian matrix is a positive definite matrix and all of the elements in its inverse are nonnegative \cite{Miekkala}.  From the Perron-Frobenius (P-F) theorem \cite{Horn}, the eigenvector associated with the smallest eigenvalue of the grounded Laplacian can be chosen to be nonnegative (elementwise).  Furthermore, when the grounded nodes do not form a vertex cut, the eigenvector associated with the smallest eigenvalue is unique (up to normalization) can be chosen to have all elements positive.


\subsection{Applications in Consensus with Stubborn Agents} 
Consider a multi-agent system described by the connected and undirected graph $\mathcal{G} = \{\mathcal{V},\mathcal{E}\}$ representing the structure of the system, and a set of equations describing the interactions between each pair of agents.  In the study of consensus and opinion dynamics \cite{Olfati1}, each agent $v_i \in \mathcal{V}$ starts with an initial scalar state (or opinion) $y_i(t)$, which evolves over time as a function of the states of its neighbors.  A commonly studied version of these dynamics involves a continuous-time linear update rule of the form
\begin{equation*}
\dot{y}_i(t)= \sum_{v_j\in \mathcal{N}_i} (y_j(t)-y_i(t)).

\end{equation*}
Aggregating the state of all of the nodes into the vector $Y(t)=\left[\begin{matrix}y_1(t) & y_2(t) & \cdots & y_n(t)\end{matrix}\right]^T$,  the above equation produces the system-wide dynamical equation
\begin{equation}
\dot{Y}=-LY,
\label{eqn:dynamicmatrix}
\end{equation}
where $L$ is the graph Laplacian.   When the graph is connected, the trajectory of the above dynamical system satisfies $Y(t) \rightarrow \frac{1}{n}\mathbf{1}\mathbf{1}^TY(0)$ (i.e., all agents reach consensus on the average of the initial values), and the asymptotic convergence rate is given by $\lambda_2(L)$ \cite{Olfati1}.

Now suppose that there is a subset $S \subset \mathcal{V}$ of agents whose opinions are kept constant throughout time, i.e., $\forall v_s \in S$, $\exists y_s \in \mathbb{R}$ such that $y_s(t)=y_s$ $\forall t \in \mathbb{R}_{\ge{0}}$. Such agents are known as {\it stubborn agents} or {\it leaders} (depending on the context) \cite{Clark1, Ghaderi13}. In this case the dynamics \eqref{eqn:dynamicmatrix} can be written in the matrix form
\begin{equation*}
\begin{bmatrix}
  \dot{Y}_F(t)   \\
  \dot{Y}_S(t) \\
 \end{bmatrix}=-\begin{bmatrix}
  L_{11} & L_{12}   \\
  L_{21}  & L_{22}  \\
 \end{bmatrix}\begin{bmatrix}
  {Y}_F(t)   \\
  {Y}_S(t) \\
 \end{bmatrix},

\end{equation*}
where $Y_F$ and $Y_S$ are the states of the non-stubborn and stubborn agents, respectively. Since the stubborn agents keep their values constant, the matrices $L_{21}$ and $L_{22}$ are zero. Thus, the matrix $L_{11}$ is the grounded Laplacian for the system, i.e., $L_{11} = L_g(S)$.   It can be shown that the state of each follower asymptotically converges to a convex combination of the values of the stubborn agents, and that the rate of convergence is asymptotically given by $\lambda$, the smallest eigenvalue of the grounded Laplacian \cite{Clark1}.  

Similarly, one can consider discrete-time consensus dynamics (also known as DeGroot dynamics) with a set $S$ of stubborn nodes, given by the update equation $
Y_F(t+1)=A_gY_F(t)$, where $Y_F(t)$ is the state vector for the non-stubborn nodes at time-step $t$, and $A_g$ is an $(n-|S|)\times(n-|S|)$ nonnegative matrix given by $A_g = I - \frac{1}{k}L_g$, with constant $k \in (d_{max},\infty)$ \cite{Kingston}.
Once again, each non-stubborn node will converge asymptotically to a convex combination of the stubborn nodes' states.  The largest eigenvalue of $A_g$ is given by $\lambda_{max}(A_g)=1-\frac{1}{k}\lambda(L_g)$, and determines the asymptotic rate of convergence.  Thus, our bounds on the smallest eigenvalue of the grounded Laplacian will readily translate to bounds on the largest eigenvalue of $A_g$.

There have been various recent investigations of graph properties that impact the convergence rate for a given set of stubborn agents, leading to the development of algorithms to find approximately optimal sets of stubborn/leader agents to maximize the convergence rate \cite{Clark1, Ghaderi13, Shi13}.  
The bounds provided in this paper contribute to the understanding of consensus dynamics with fixed opinions by providing bounds on the convergence rate induced by any given set of stubborn or leader agents.
{"config": "arxiv", "file": "1406.2271/model.tex"}