Random Graphs and Hypergraphs for Complex Networks

This thesis addresses the design and analysis of complex networks using advanced graph theory. Specifically, power control, connectivity, and the scaling behavior of multihop delay in heterogeneous networks are analyzed using percolation and ergodic theory. The design of complex networks replete with group behaviors and hyper-relationships is tackled based on the mathematical model of hypergraph and simplicial complex.;In the first part of the thesis, we address several fundamental issues, including power control, connectivity, multihop, and multicast, in heterogeneous networks. We focus on ad hoc cognitive radio networks, a major emerging class of heterogeneous networks. In a cognitive radio network, secondary users identify and exploit instantaneous and local spectrum opportunities without causing unacceptable interference to primary users. For power control, we qualitatively and quantitatively characterize the impacts of the transmission power of secondary users on the occurrence of spectrum opportunities and the reliability of opportunity detection. Such analytical characterizations allow us to study power control for optimal transport throughput under constraints on the interference to primary users. For connectivity, 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. We also analyze the instantaneous connectivity of the secondary network defined in the percolation sense, and reveal the tradeoff between proximity (the number of neighbors) and the occurrence of spectrum opportunities. For multihop delay, we establish the scaling law of the minimum multihop delay with respect to the source-destination distance, and show the starkly different scaling behavior of the minimum multihop delay in a secondary network that is instantaneously connected with a positive probability as compared to a network that is not. For multicast, we propose a low-complexity approximation algorithm with bounded performance guarantee for constructing the minimum-energy multicast tree, and demonstrate the impact of the primary traffic on the minimum-energy multicast tree.;In the second part of this thesis, we introduce simplicial complex to model and characterize group behaviors and hyper-relationships in complex networks that are more than a simple union of pairwise relationships. We address the shortest path and minimum spanning problems in simplicial complexes. For networks with dynamically varying topologies and weights, the proposed algorithm for computing the shortest path outperforms an existing algorithm developed for hypergraphs in terms of time complexity. For the minimum spanning problem, its NPcompleteness is established, and two approximation algorithms with order-optimal performance guarantee are proposed.;The contributions of this thesis to network science are twofold. On the one hand, we solve specific engineering problems in complex networks using advanced tools in graph theory (random graph, percolation, ergodicity). On the other hand, the problems addressed enrich the applications of graph theory and lead to contributions to the basic theories of random graph and hypergraph. In particular, this thesis tackles fundamental algorithmic problems in hypergraphs and simplicial complexes that have not been addressed before.