Optimization and Machine Learning Frameworks for Complex Network Analysis

Thesis (Ph.D.)--University of Washington, 2016-06

Networks are all around us, and they may be connections of tangible objects in the Euclidean space such as electric power grids, the Internet, highways systems, etc. Among the wide range of areas in the network analysis, finding critical component in the large scale complex networks is one of the most challenging but fascinating problem in the network analysis. Analytical approaches of finding critical components have been widely studied and extensively used to investigate and provide meaningful characterizations of the intrinsic dynamics and properties of complex structures in networked systems. The objective of this thesis is to build novel mathematical models for finding critical components and connectivity patterns in complex networks that may reveal hidden, yet insightful, information for the investigation of underlying dynamics of the networks. In particular: -I propose mixed integer programming (MIP) models to seek k-Cardinality Tree (KCT) ,which address the finding critical components problem. I proposed seven variations of MIP models that are based on connected component constraints and subtour elimination constraints. Through the investigation of polyhedral structures and test results, the best performance model has been chosen and then we compared it with state of the art algorithm in the literature. -I expand our scope to find critical components in the labeled networks. I design two mathematical programming model to determine $k$-sized critical component including the most informative edges to classify the networks. As a first step, we develop mixed integer programming (MIP) model for finding critical components in the networked data classification. Due to the computationally intractability on the large scaled data, I built a branch-and-cut algorithm based on the Benders decomposition. -I also build a mixed integer nonlinear programming (MINLP) model based on the support vector machine (SVM) formulation. Rather than solving this MINLP directly, an efficient iterative algorithm combining with multiple kernel learning is proposed. To demonstrate the utility of the proposed models and solution approaches, synthetic networks and brain functional connectivity networks are used as case points in this thesis. Through the extensive experiments on both data sets, proposed approaches achieve impressive scalability and comparable or even better performance rather than the state-of-the-art methods. On human brain networks, the approaches are used to detect informative regions of interests (ROIs) and their connectivity patterns that may be useful in detecting people who are risk of developing neurological diseases.