Mitigation of malicious attacks on network observation

摘要

In the modeling, controlling, and monitoring of complex networks, a fundamental problem concerns the determination and observation of the system's states by using measurements or sensors as few as possible, defined as network observation. This work aims to investigate the robustness of network observation when an approach of minimum dominating set is considered in observing a network. We first investigate the structural properties of the minimum dominating sets, e.g. how the size depends on the degree-degree correlations and how to assess the nodes' importance in the malicious attacks. Then, we introduce a new measurement of robustness for network observation, and implement a hill-climbing algorithm to improve its robustness by edge rewiring. Furthermore, we propose a novel rewiring strategy, called smart rewiring, which could speed up the increment of robustness index. In comparison with previous strategy of edge rewiring, the smart rewiring has been found to be successfully useful on real-world and synthetic networks.