Graph Network Centralization via Asymmetric Edge Weight Allocation: Laplacian Conditioning and Multi-UAV System Application
Hye Jin Lee, Hyeon-Woo Na, PooGyeon Park · IEEE Transactions on Network Science and Engineering · 2025
Centrality measurement and network centralization are crucial for understanding and managing graph networks. This paper introduces a novel method for network centralization, termed the Laplacian conditioning method, which is applicable to both directed and undirected graphs. The proposed method allocates asymmetric edge weights emphasizing critical nodes and edges with minimal computational effort. To achieve this, an improved Laplacian matrix representation is developed that distinguishes between connection status and directional edge weights, enabling direct manipulation of each directional edge weight. An iterative algorithm is proposed to condition the Laplacian matrix spectrum by minimizing the ratio of the largest eigenvalue to the second-smallest eigenvalue in the sense of magnitude. This method offered enhanced design flexibility and improved conditioning capability by eliminating restrictions on edge weight configurations. Numerical examples demonstrate the effectiveness of the proposed method in multi-UAV systems, enhancing information dissemination in time-delay, sampled-data, and event-triggered environments.