Algorithmic Studies of Graphs and Hypergraphs for Complex Networks.

摘要

A graph is a mathematical abstraction for modeling networks, in which nodes are represented by vertices and pairwise relationships by edges between vertices. A hypergraph is a natural extension of a graph obtained by removing the constraint on the cardinality of an edge. It thus captures group behaviors and higher-dimensional relationships in complex networks that are more than a simple union of pairwise relationships. Examples include communities and collaboration teams in social networks, document clusters in information networks, and cliques, neighborhoods, and multicast groups in communication networks.;While the concept of hypergraph has been around since the 1920's, theoretical development on hypergraph has not received sufficient attention until recently due to the prevalence of complex networks such as social networks. Many well-solved algorithmic problems in graphs remain largely open under this more general model. This thesis addresses a number of algorithmic problems in hypergraphs as well as graphs with applications ranging from discovering latent relationship in social networks, identifying critical hubs in information networks, to secure communications in wireless networks.;The first algorithmic problem studied in this thesis is the dynamic 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 complexities 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 relationships based on the closeness centrality metric.;The second problem considered is 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.;The third problem studied in this thesis is the information dominating set (IDS) problem concerning sampling node-valued graphs and hypergraphs. 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 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 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 and 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.;This thesis contributes the literature on network science and (hyper-)graph theory by addressing several fundamental algorithmic problems in hypergraphs and introducing new networking applications of graph and hypergraph theory.