Edge Augmentation with Controllability Constraints in Directed Laplacian Networks
In this paper, we study the maximum edge augmentation problem in directed Laplacian networks to improve their robustness while preserving lower bounds on their strong structural controllability (SSC). Since adding edges could adversely impact network controllability, the main objective is to maximally densify a given network by selectively adding missing edges while ensuring that SSC of the network does not deteriorate beyond certain levels specified by the SSC bounds. We consider two widely used bounds: first is based on the notion of zero forcing (ZF), and the second relies on the distances between nodes in a graph. We provide an edge augmentation algorithm that adds the maximum number of edges in a graph while preserving the ZF-based SSC bound, and also derive a closed-form expression for the exact number of edges added to the graph. Then, we examine the edge augmentation problem while preserving the distance-based bound and present a randomized algorithm that guarantees an approximate solution with high probability. Finally, we numerically evaluate and compare these edge augmentation solutions.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Signed Directed Graph Contrastive Learning with Laplacian Augmentation
Graph contrastive learning has become a powerful technique for several graph mining tasks. It learns discriminative representation from different perspectives of augmented graphs. Ubiquitous in our daily life, singed-dir…
Contrastive LearningGraph MiningLearning Undirected Graphs in Financial Markets
We investigate the problem of learning undirected graphical models under Laplacian structural constraints from the point of view of financial market data. We show that Laplacian constraints have meaningful physical inter…
ClusteringGraph Learning in 4D: a Quaternion-valued Laplacian to Enhance Spectral GCNs
We introduce QuaterGCN, a spectral Graph Convolutional Network (GCN) with quaternion-valued weights at whose core lies the Quaternionic Laplacian, a quaternion-valued Laplacian matrix by whose proposal we generalize two …
Graph LearningDirected Graph Contrastive Learning
Graph Contrastive Learning (GCL) has emerged to learn generalizable representations from contrastive views. However, it is still in its infancy with two concerns: 1) changing the graph structure through data augmentation…
Contrastive LearningData AugmentationNonlinear Laplacians Improve Signed-Directed Graph Learning
While signed-directed graphs have been studied using linear Laplacians in the design of graph neural networks, relatively little research has focused on developing non-linear Laplacian operators for such networks. We int…
Node ClassificationLink PredictionGraph Learning