Constructing a minimum dominating set for a complex network
by
周海军 Hai-Jun Zhou(Institute of Theoretical Physics, Chinese Academy of Sciences)
→
Europe/Stockholm
122:026
122:026
Description
The minimum dominating set (MDS) problem has wide applications in network science and related fields. It aims at constructing a node set of smallest size such that any node of the network is either in this set or is adjacent to at least one node of this set. The nodes in a MDS are very important for monitoring and controlling the dynamical processes on a network, but constructing a MDS is in general very difficult.
I demonstrate that both the directed and undirected MDS problem can be exactly solved by a generalized leaf-removal process if the network contains no core. If a core exists in the network, a near-optimal dominating set can be constructed through a belief-propagation decimation (BPD) algorithm. The spin glass model behind this BPD algorithm is also discussed.
This work shall be useful for researchers who are interested in applying the MDS concept to practical social or biological problems.
