Date/Time
Date(s) - April 22, 2019
11:45 am - 12:35 pm
Location
CSE 112
Categories
Yajun Lu
Ph.D. Candidate
Oklahoma State University
Abstract: Finding Second-Order Clubs in Graphs
Modeling data entities and their pairwise relationships as a graph is a popular approach to visualizing and mining information from datasets in a variety of fields such as social networks, biological networks, web graphs and document networks. A powerful approach in this setting involves the detection of clusters. Clique, a subset of pairwise adjacent vertices, is often viewed as an idealized representation of a cluster. However, in the presence of errors in the data on which the graph is based, clique requirement may be too restrictive, resulting in small clusters or clusters that miss key members. Consequently, graph-theoretic clique generalizations based on the principle of relaxing elementary structural properties of a clique have been proposed in diverse fields to describe clusters of interest. In this study, we consider low-diameter clusters that require another property like robustness (parameterized by r) or heredity (parameterized by h) to hold, in addition to the diameter. Specifically, we study s-clubs with side-constraints to make them less “fragile”, i.e., less susceptible to disconnection if vertices or edges are deleted. The overall goal of the research is to develop effective exact algorithms with emphasis on s = 2, 3, 4 and low values of r and h to solve maximum r-robust s-club (MRC) and h-hereditary s-club (MHC) problems on moderately large instances (around 104 vertices and less than 5% density).