Mathematics Colloquium: Detecting Low-Diameter Clusters in Graphs
4:10 pm - Neill Hall
Foad Mahdavi Pajouh
Detecting clusters in graph-models of data is a key approach in graph-based data mining of social and biological networks. Cliques, defined as a set of pairwise adjacent vertices, were the earliest graph-theoretic models used to formalize the concept of a cluster. Clique definition however, was found to be overly restrictive and impractical while dealing with real-life data leading to several approaches to generalize the clique definition, resulting in several parameterized graph-theoretic clique relaxations. The focus of this talk is a distance-based clique relaxation called a k-club. In this talk, we will discuss complexity and polyhedral results, and exact algorithms for the maximum k-club problem– that is to find a largest order subgraph of diameter at most k. Additionally, this talk will address the maximum 2-club problem under risk in which, given a random graph subject to probabilistic edge failures, we are interested in finding a large “risk-averse” 2-club. Here, risk-aversion is achieved via modeling the loss in 2-club property due to the edge failures as a random loss function, and using Conditional Value-at-Risk (CVaR) as a quantitative measure of risk that is bounded in the model. This presentation is based on joint work with my Ph.D. advisor Dr. Baski Balasundaram and Dr. Illya V. Hicks.