The Minimum Information Dominating Set for Opinion Sampling in Social Networks

摘要

We consider the problem of sampling a node-valued graph. The objective is to infer the values of all nodes from that of a minimum subset of nodes by exploiting correlations in node values. We first introduce the concept of information dominating set (IDS). A subset of nodes in a given graph is an IDS if the values of these nodes are sufficient to infer the values of all nodes. We focus on two fundamental algorithmic problems: (i) how to determine whether a given subset of nodes is an IDS; (ii) how to construct a minimum IDS. Assuming binary node values and the local majority rule for information correlation, we first show that in acyclic graphs, both problems admit linear-complexity solutions by establishing a connection between the IDS problems and the vertex cover problem. We then show that in a general graph, the first problem is co-NP-complete and the second problem is NP-hard. We develop two approaches to solve the IDS problems: one reduces the problems to a hitting set problem based on the concept of essential difference set, the other a gradient-based approach with a tunable parameter that trades off performance with time complexity. The concept of IDS finds applications in opinion sampling such as political polling and market survey, identifying critical nodes in information networks, and inferring epidemics and cascading failures in communication and infrastructure networks.