Accession Number : ADA617371


Title :   Minimum Information Dominating Set for Critical Sampling over Graphs


Descriptive Note : Conference paper


Corporate Author : CALIFORNIA UNIV DAVIS DEPT OF ELECTRICAL AND COMPUTER ENGINEERING


Personal Author(s) : Gao, Jianhang ; Zhao, Qing ; Swami, Ananthram


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a617371.pdf


Report Date : Apr 2015


Pagination or Media Count : 6


Abstract : We consider the problem of sampling a node-weighted 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 value of these nodes is sufficient to infer the information state of the entire graph. We focus on two fundamental algorithmic problems: (i) how to determine whether a given subset of vertices is an IDS (ii) how to construct a minimum IDS. Assuming binary node values and the local majority rule, we show that the first problem is co-NP-complete and the second problem is NP-hard in a general network. We then show that in acyclic graphs, both problems admit linear-complexity solutions by establishing a connection between the IDS problems and the vertex cover problem. For general graphs, we develop algorithms for solving both problems based on the concept of essential differential set. These results find applications in opinion sampling such as political polling and market survey in social-economic networks, and inferring epidemics and cascading failures in communication and infrastructure networks.


Descriptors :   *COMPUTERIZED SIMULATION , *GRAPHS , *SAMPLING , CORRELATION , DATA MINING , DIFFERENTIAL TOPOLOGY , MONTE CARLO METHOD , NETWORK ARCHITECTURE , NODES , ONLINE COMMUNITIES , PROBABILITY , PUBLIC OPINION , RANDOM VARIABLES , STATISTICAL INFERENCE , VECTOR ANALYSIS


Subject Categories : Information Science
      Statistics and Probability
      Computer Systems


Distribution Statement : APPROVED FOR PUBLIC RELEASE