Papers › Optimization on the smallest eigenvalue of grounded Laplacian matrix via edge addition
Optimization on the smallest eigenvalue of grounded Laplacian matrix via edge addition
Xiaotian Zhou, Haoxin Sun, Wei Li, Zhongzhi Zhang
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
The grounded Laplacian matrix _(-S) of a graph =(V,E) with n=|V| nodes and m=|E| edges is a (n-s)×(n-s) submatrix of its Laplacian matrix $\LL$, obtained from $\LL$ by deleting rows and columns corresponding to s=|S| ≪n ground nodes forming set S⊂V. The smallest eigenvalue of _(-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 ≪n edges among all the nonexistent edges forming the candidate edge set Q = (V×V)\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×(V\S))\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²) to O(n). Then, we propose two greedy approximation algorithms. One is a simple greedy algorithm with an approximation ratio (1-e^(-αγ))/α and time complexity O(kn⁴), where γ and α 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 Õ(km), where Õ(·) suppresses the poly (logn) factors. Numerous experiments on various real networks are performed to validate the superiority of our algorithms, in terms of effectiveness and efficiency.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections