| dc.description.abstract | Many complex systems involve entities that interact with each other through various relationships (e.g., people in social systems, neurons in the brain). These entities and interactions are commonly represented using graphs due to several advantages. This dissertation focuses on developing theory and algorithms for novel methods in graph theory and optimization, and their applications to social and brain networks.
Specifically, the major contributions of this dissertation are three fold. First, this dissertation aims not only to develop a new clique relaxation model based on a structural metric, clustering coefficient, but also to introduce a novel graph clustering algorithm using this model. Clique relaxations are used in classical models of cohesive subgroups in social network analysis. Clustering coefficient was introduced more recently as a structural feature characterizing small-world networks. Leveraging the similarities between the concepts of cohesive subgroups and small-world networks (i.e., graphs that are highly clustered with small path lengths). The first part of this dissertation introduces a new clique relaxation, α-cluster, defined by enforcing a lower bound α on the clustering coefficient in the corresponding induced subgraph. Two different definitions of the clustering coefficient are considered, namely, the local and global clustering coefficient. Certain structural properties of α-clusters are analyzed, and mathematical optimization models for determining the largest size α-clusters in a network are developed and applied to several real-life social network instances. In addition, a network clustering algorithm based on local α-cluster is introduced and successfully evaluated.
Second, this dissertation explores a novel mathematical model called the maximum independent union of cliques problem (max IUC problem), which arises as a special case of α-clusters. It is an interesting problem for which both the maximum clique and maximum independent sets are feasible solutions and individually their corresponding sizes are lower bounds for the size of the IUC solution. After presenting the structural properties as well as the complexity results of different graph types (planar, unit disk graphs and claw-free graphs), an integer programming formulation is developed, followed by a branch-and-bound algorithm and several heuristic methods to approximate the maximum independent union of cliques problem. The developed methods have been empirically evaluated on many benchmark instances.
Finally, this dissertation, in collaboration with Texas Institute of Preclinical Studies (TIPS), applies clique relaxation models to explore a new experimental data to understand the effect of concussion on animal brains. Our research involves cohesive and robust clustering analysis of animal brain networks utilizing a unique and novel experimental data. In collaboration with TIPS, we have analyzed multiple pairs of fMRI data about animal brains that are measured before and after a concussion. We utilize network analysis to first identify the similar regions in animal brains, and then compare how these regions as well as graph structural properties change before and after a concussion. To the best of our knowledge, this study is unique in the literature in that it not only explicitly examines the relation between concussion level and the functional unit interaction but also uses very detailed and fine-grained fMRI measurements of brain data. | en |
