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.

In an ad hoc cognitive radio network, secondary users access channels temporarily unused by primary users, and the existence of a communication link between two secondary users depends on the transmitting and receiving activities of nearby primary users. Using theories and techniques from continuum percolation and ergodicity, we analytically characterize the connectivity of the secondary network defined in terms of the almost sure finiteness of the multihop delay, and show the occurrence of a phase transition phenomenon while studying the impact of the temporal dynamics of the primary traffic on the connectivity of the secondary network. Specifically, as long as the primary traffic has some temporal dynamics caused by either mobility and/or changes in traffic load and pattern, the connectivity of the secondary network depends solely on its own density and is independent of the primary traffic; otherwise, the connectivity of the secondary network requires putting a density-dependent cap on the primary traffic load. We show that the scaling behavior of the multihop delay depends critically on whether or not the secondary network is instantaneously connected. In particular, we establish the scaling law of the minimum multihop delay with respect to the source-destination distance when the propagation delay is negligible.

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.

We analyze the multihop delay of ad hoc cognitive radio networks, where the transmission delay of each hop consists of the propagation delay and the waiting time for the availability of the communication channel (i.e. the occurrence of a spectrum opportunity at this hop). Using theories and techniques from continuum percolation and ergodicity, we establish the scaling law of the minimum multihop delay with respect to the source-destination distance in cognitive radio networks. When the propagation delay is negligible, we show the starkly different scaling behavior of the minimum multihop delay in instantaneously connected networks as compared to networks that are only intermittently connected due to scarcity of spectrum opportunities. Specifically, if the network is instantaneously connected, the minimum multihop delay is asymptotically independent of the distance; if the network is only intermittently connected, the minimum multihop delay scales linearly with the distance. When the propagation delay is nonnegligible but small, we show that although the scaling order is always linear, the scaling rate for an instantaneously connected network can be orders of magnitude smaller than the one for an intermittently connected network.

We address the percolation-based connectivity of large-scale ad hoc heterogeneous wireless networks, where secondary users exploit channels temporarily unused by primary users and the existence of a communication link between two secondary users depends on not only the distance between them but also the transmitting and receiving activities of nearby primary users. We introduce the concept of connectivity region defined as the set of density pairs-the density of secondary users and the density of primary transmitters - under which the secondary network is connected. Using theories and techniques from continuum percolation, we analytically characterize the connectivity region of the secondary network and reveal the tradeoff between proximity (the number of neighbors) and the occurrence of spectrum opportunities. Specifically, we establish three basic properties of the connectivity region-contiguity, monotonicity of the boundary and uniqueness of the infinite connected component, where the uniqueness implies the occurrence of a phase transition phenomenon in terms of the almost sure existence of either zero or one infinite connected component; we identify and analyze two critical densities which jointly specify the profile as well as an outer bound on the connectivity region; we study the impacts of secondary users' transmission power on the connectivity region and the conditional average degree of a secondary user and demonstrate that matching the interference ranges of the primary and the secondary networks maximizes the tolerance of the secondary network to the primary traffic load. Furthermore, we establish a necessary condition and a sufficient condition for connectivity, which lead to an outer bound and an inner bound on the connectivity region.

We analyze the multihop delay of ad hoc cognitive radio networks, where the transmission delay of each hop consists of the propagation delay and the waiting time for the availability of the communication channel (i.e., the occurrence of a spectrum opportunity at that hop). Using theories and techniques from continuum percolation and ergodicity, we establish the scaling law of the minimum multihop delay with respect to the source-destination distance. We show the starkly different scaling behavior of the multihop delay in instantaneously connected networks as compared to networks that are only intermittently connected due to the scarcity of spectrum opportunities.

We consider power control in cognitive radio networks where secondary users identify and exploit instantaneous and local spectrum opportunities without causing unacceptable interference to primary users. We qualitatively characterize the impacts of the transmission power of secondary users on the occurrence of spectrum opportunities and the reliability of opportunity detection. Based on a Poisson model of the primary network, we quantify these impacts by showing that (i) the probability of spectrum opportunity decreases exponentially with the transmission power of secondary users, where the exponential decay constant is given by the traffic load of primary users; (ii) reliable opportunity detection is achieved in the two extreme regimes in terms of the ratio between the transmission power of secondary users and that of primary users. Such analytical characterizations allow us to study power control for optimal transport throughput under constraints on the interference to primary users. Furthermore, we reveal the difference between detecting primary signals and detecting spectrum opportunities, and demonstrate the complex relationship between physical layer spectrum sensing and MAC layer throughput. The dependency of this PHY-MAC interaction on the application type and the use of handshake signaling such as RTS/CTS is also illustrated.