Grainger College of Engineering, All Events

View Full Calendar

Identifying outlier groups using combinatorial optimization

Event Type
Seminar/Symposium
Sponsor
ISE
Location
303 Transportation Building
Date
May 14, 2019   10:00 am  
Speaker
Chrys Vogiatzis
Views
19
Originating Calendar
ISE Seminar Calendar

In this talk, we present a variant of the graph bipartitioning problem, in which struc-
tural requirements are imposed. In the traditional graph bipartitioning problem, we are
interested in dividing a graph into two disjoint subgtraphs such that nodes in the same
subgraph are highly similar, while being dissimilar to nodes in the other subgraph. This
problem has attracted signicant attention in social network analysis, image segmenta-
tion, and data classication. In addition to the homogeneity criterion of traditional graph
bipartitioning, we also impose that one of the subgraphs satises a predened structural
property, i.e., the subgraph induces a given motif. This extension has applications in
identifying fringe, outlier groups in online social networks. We rst present some com-
plexity results about this new problem, and then proceed to provide a general fractional
programming formulation for when the subgraphs are required to induce cliques, stars,
and clique relaxations. We also present a series of solution approaches for tackling the
problem exactly. Due to the size of online social networks, though, exact algorithms
prove computationally expensive; hence, two greedy algorithms are presented for the case
of stars and cliques, with an approximation guarantee for stars. Finally, we present a
decomposition scheme based on the notion of graph degeneracy. We conclude the talk
with our computational results in a series of real-life and randomly generated instances.

link for robots only