Optimizing Pinning Control of Complex Dynamical Networks Based on Spectral Properties of Grounded Laplacian Matrices

Hui Liu, Xuanhong Xu, Jun-An Lu, Guanrong Chen, Zhigang ZengIEEE Trans. SMC: Systems 2021 · DOI

TL;DR

This paper introduces a novel method for optimizing "pinning control" in complex networks by analyzing the spectral properties of a "grounded Laplacian matrix." This approach provides a theoretical framework to determine which nodes are most effective to control, leading to more efficient synchronization of network dynamics.

What Problem Does This Paper Address?

Complex systems, from power grids to social networks, are often modeled as networks of interacting nodes. In many applications, it's desirable to make all nodes in the network behave in a synchronized manner, for example, to track a specific signal. However, controlling every node in a large network is often impractical or too expensive. "Pinning control" offers a solution by controlling only a small subset of nodes to influence the entire network's behavior. The challenge lies in selecting which nodes to pin to achieve the most effective and efficient control. Existing methods often focus on if a network can be controlled, but not on how to optimally choose the pinned nodes. This paper addresses this gap by providing a systematic way to optimize node selection based on network structure.

Methods

The core of this paper's contribution lies in its use of the grounded Laplacian matrix. For a given network, the Laplacian matrix captures its structure. By removing the rows and columns corresponding to the "pinned" (controlled) nodes, a smaller matrix called the grounded Laplacian is obtained. The authors propose that the smallest eigenvalue of this grounded Laplacian matrix is a key indicator of pinning control effectiveness: a larger eigenvalue signifies more effective control.

They then delve into analyzing the spectral properties of this smallest eigenvalue, relating it to various network topology features such as:

  • The spectrum of the original network Laplacian matrix.
  • The minimum degree of uncontrolled nodes.
  • The number of connections between controlled and uncontrolled nodes.

The paper derives theoretical conditions and lemmas (e.g., using Schur complements and eigenvalue interlacing theorems) to understand how these topological features influence the smallest eigenvalue of the grounded Laplacian. This theoretical understanding is then applied to develop strategies for selecting optimal sets of nodes to pin.

Datasets

Not discussed in the paper. The paper uses simulated networks (double-star, scale-free, small-world, dolphin, email networks) to demonstrate the effectiveness of their proposed methods.

Key Insights and Ideas

  • The smallest eigenvalue of the grounded Laplacian is a direct measure of pinning control effectiveness. This provides a concrete, quantifiable metric for optimizing node selection.
  • Network topology dictates optimal pinning strategy. The paper reveals a counter-intuitive finding: for scale-free and small-world networks, it's generally better to pin nodes with high degrees when the number of pinned nodes is small, but better to pin nodes with low degrees when the number of pinned nodes is large. This is explained by the interplay between the minimal degree of uncontrolled nodes and the overall network structure.
  • Spectral properties offer predictive power. The (l+1)-th smallest eigenvalue of the full network Laplacian can estimate the minimum number of nodes needed for control, and the Laplacian spectrum can accurately predict the effectiveness of pinning schemes when only a small fraction of nodes are controlled.
  • A systematic algorithm for node selection. The paper proposes an algorithm (Algorithm 1) that aims to achieve a specific eigenvalue target (λ₁(L(S|S)) = 1) by strategically selecting nodes, particularly in networks with many leaf nodes.

Key Results

The paper demonstrates through theoretical analysis and numerical simulations that:

  • The proposed spectral criterion (largest smallest eigenvalue of the grounded Laplacian) effectively measures pinning control performance.
  • The developed theoretical insights can guide the selection of optimal pinned nodes, leading to better synchronization compared to degree-based or betweenness centrality-based methods in tested scenarios.
  • For the dolphin network, their proposed algorithm achieved a grounded Laplacian eigenvalue of 1, significantly outperforming other methods that yielded eigenvalues between 0.2699 and 0.5615.
  • Similarly, for the email network, their algorithm achieved an eigenvalue of 1, while other methods resulted in eigenvalues around 0.3-0.4.

Limitations and Future Work

  • Computational Complexity: While the spectral approach offers theoretical optimization, calculating eigenvalues for large networks can still be computationally intensive. The paper acknowledges that finding the absolute maximum of the grounded Laplacian eigenvalue is an NP-hard problem.
  • Generalizability: The paper focuses on undirected networks for some results. Extending the analysis to directed networks more broadly could be a future direction.
  • Integration with Evolutionary Algorithms: The authors suggest that future work could explore combining spectral properties with evolutionary algorithms for more sophisticated node-selection strategies.

Summary updated

BibTeX
@article{liu2021optimizing,
  author = {Hui Liu and Xuanhong Xu and Jun-An Lu and Guanrong Chen and Zhigang Zeng},
  title = {{Optimizing Pinning Control of Complex Dynamical Networks Based on Spectral Properties of Grounded Laplacian Matrices}},
  journal = {IEEE Trans. Syst. Man Cybern. Syst.},
  year = {2021},
  doi = {10.1109/tsmc.2018.2882620},
}
Figure