论文标题
复杂网络的目标观察
Target observation of complex networks
论文作者
论文摘要
如何从有限数量的测量中观察网络的状态已成为复杂网络，工程，通信，流行病学等的重要问题。在某些情况下，观察整个网络既不是不可行的也不是不必要的。因此，我们研究了本文中网络的目标观察。我们提出了一个与目标观察相对应的目标最小的主导集合问题，这是经典最小主导设置问题的自然概括。提出了三种算法，以近似足以观察目标观察的最小占用节点集。计算机生成的随机网络和现实世界网络的广泛数值结果表明，所提出的算法在识别目标最小的主导集合时提供了卓越的性能。
How to observe the state of a network from a limited number of measurements has become an important issue in complex networks, engineering, communication, epidemiology, etc. Under some scenarios, it is neither unfeasible nor unnecessary to observe the entire network. Therefore, we investigate the target observation of a network in this paper. We propose a target minimal dominating set problem corresponding to target observation, which is a natural generalization of classical minimal dominating set problem. Three algorithms are proposed to approximate the minimum set of occupied nodes sufficient for target observation. Extensive numerical results on computer-generated random networks and real-world networks demonstrate that the proposed algorithms offer superior performance in identification of a target minimal dominating set.
