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.

A hypergraph is a set V of vertices and a set of nonempty subsets of V, called hyperedges. Unlike graphs, hypergraphs can capture higher-order interactions in social and communication networks that go beyond a simple union of pairwise relationships. In this paper, we consider the shortest path problem in hypergraphs. We develop two algorithms for finding and maintaining the shortest hyperpaths in a dynamic network with both weight and topological changes. These two algorithms are the first to address the fully dynamic shortest path problem in a general hypergraph. They complement each other by partitioning the application space based on the nature of the change dynamics and the type of the hypergraph. We analyze the time complexity of the proposed algorithms and perform simulation experiments for random geometric hypergraphs, energy efficient routing in multichannel multiradio networks, and the Enron email data set. The experiment with the Enron email data set illustrates the application of the proposed algorithms in social networks for identifying the most important actor and the latent social relationship based on the closeness centrality metric.

We formulate and study the thinnest path problem for secure communication in wireless ad hoc networks. The objective is to find a path from a source to its destination that results in the minimum number of nodes overhearing the message by a judicious choice of relaying nodes and their corresponding transmission powers. We adopt a directed hypergraph model of the problem and establish the NP-completeness of the problem in 2-D networks. We then develop two polynomial-time approximation algorithms that offer √(n/2) and n/2√(n-1) approximation ratios for general directed hypergraphs (which can model nonisotropic signal propagation in space) and constant approximation ratios for ring hypergraphs (which result from isotropic signal propagation). We also consider the thinnest path problem in 1-D networks and 1-D networks embedded in a 2-D field of eavesdroppers with arbitrary unknown locations (the so-called 1.5-D networks). We propose a linear-complexity algorithm based on nested backward induction that obtains the optimal solution for both 1-D and 1.5-D networks. This algorithm does not require the knowledge of eavesdropper locations and achieves the best performance offered by any algorithm that assumes complete location information of the eavesdroppers.

We consider the broadcasting problem in multi-radio multi-channel ad hoc networks. The objective is to minimize the total broadcast cost, where the cost can be of any form that is summable over all the transmissions (e.g., the transmission and reception energy, the price for accessing a specific channel). Our technical approach is based on a simplicial complex model that allows us to capture the broadcast nature of the wireless medium and the heterogeneity across radios and channels. Specifically, we show that broadcasting in multi-radio multi-channel ad hoc networks can be formulated as a minimum spanning problem in simplicial complexes. We establish the NP-completeness of the minimum spanning problem and propose two approximation algorithms with order-optimal performance guarantee. These two algorithms offer tradeoffs between performance and time complexity. In a broader context, this work appears to be the first that studies the minimum spanning problem in simplicial complexes and weighted minimum connected set cover problem.