Minimum number of information gatherers to ensure full observability of a dynamic social network: A structural systems approach

This paper studies the problem of identifying the minimum number of entities (agents), referred to as information gatherers, that are able to infer all the states in a dynamical social network. The information gatherers can be, for instance, service providers and the remaining agents the clients, each comprising several dynamic states associated with the services and personal information. The problem of identifying the minimum number of information gatherers can constitute a way to create coalitions to oversee the entire state of the system, and consequently the behavior of the agents in the social network. The dynamical social network is assumed to be modelled as a linear time-invariant system, and we will make use of the structural systems concept, i.e., by considering only the sparsity pattern (location of zeroes/non-zeroes) of the system coupling matrix. As a consequence, the design guarantees derived hold for almost all numerical parametric realizations of the system. In this paper, we show that this problem is NP-hard: in addition, we provide a reduction of the coalition problem to a minimum set covering problem that, in practice, leads to efficient (polynomial complexity) approximation schemes for solving the coalition problem with guaranteed optimality gaps. Finally, an example is provided which illustrates the analytical findings.