Minimum Control Cost of Weighted Linear Dynamic Networks

Abstract

Controlling a weighted linear dynamic network is important to various real world applications such as influencing political elections through a social network. Extant works mainly focus on minimizing the number of controllers that control the nodes in a network, but ignore the cost of controlling an individual node. Apparently, controlling a journalist or a mayor in a city has largely different costs, and we show that the aggregated control cost in extant works is often prohibitive. In this paper, we formulate the minimum control cost (MCC) problem in a weighted linear dynamic network, which is to find the set of controlled nodes with minimum sum of control costs. We show that the MCC problem is NP-hard by reducing the set cover problem to it. We also derive the lower/upper bounds and propose two approximation algorithms. Extensive evaluation results also show that the proposed algorithms have good performance compared to the derived lower bound of the problem.