Minimum Number of Information Gatherers to Ensure Full Observability of a Dynamic Social Network: A Structural Systems Approach

• Type: Article in International Conference Proceedings Book
• Date: 2014

Authors

Pequito, S (Author) Other; Kar, S (Author) Other; Aguiar, AP (Author) FEUP

Conference proceedings International

Title: 2014 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2014

Pages: 750-753

2014 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2014

3 December 2014 through 5 December 2014

Indexing

ISI Web of Knowledge - 5 Citations

Scopus - 6 Citations

Other information

Authenticus ID: P-00G-DHV

DOI: 10.1109/globalsip.2014.7032219

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 4