ISE Lecturer Candidate Search

Date/Time

04/22/2019
11:45 am-12:35 pm
Add to Outlook/iCal
Add to Google Calendar

Location

CSE 112
CSE Building
Gainesville, FL 32611

Details

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).

Categories

Hosted by

Department of Industrial and Systems Engineering at the University of Florida