  The grounded Laplacian matrix $\LL_{-S}$ of a graph $\calG=(V,E)$ with
$n=|V|$ nodes and $m=|E|$ edges is a $(n-s)\times (n-s)$ submatrix of its
Laplacian matrix $\LL$, obtained from $\LL$ by deleting rows and columns
corresponding to $s=|S| \ll n $ ground nodes forming set $S\subset V$. The
smallest eigenvalue of $\LL_{-S}$ plays an important role in various practical
scenarios, such as characterizing the convergence rate of leader-follower
opinion dynamics, with a larger eigenvalue indicating faster convergence of
opinion. In this paper, we study the problem of adding $k \ll n$ edges among
all the nonexistent edges forming the candidate edge set $Q = (V\times
V)\backslash E$, in order to maximize the smallest eigenvalue of the grounded
Laplacian matrix. We show that the objective function of the combinatorial
optimization problem is monotone but non-submodular. To solve the problem, we
first simplify the problem by restricting the candidate edge set $Q$ to be
$(S\times (V\backslash S))\backslash E$, and prove that it has the same optimal
solution as the original problem, although the size of set $Q$ is reduced from
$O(n^2)$ to $O(n)$. Then, we propose two greedy approximation algorithms. One
is a simple greedy algorithm with an approximation ratio
$(1-e^{-\alpha\gamma})/\alpha$ and time complexity $O(kn^4)$, where $\gamma$
and $\alpha$ are, respectively, submodularity ratio and curvature, whose bounds
are provided for some particular cases. The other is a fast greedy algorithm
without approximation guarantee, which has a running time $\tilde{O}(km)$,
where $\tilde{O}(\cdot)$ suppresses the ${\rm poly} (\log n)$ factors. Numerous
experiments on various real networks are performed to validate the superiority
of our algorithms, in terms of effectiveness and efficiency.
