Events and Seminars : 2014 Seminars

MONTE CARLO ALGORITHMS FOR IDENTIFYING DENSELY CONNECTED SUBGRAPHS

EMMA JINGFEI ZHANG, PH.D.
Assistant Professor
Management Science Department
School of Business Administration
University of Miami
TUESDAY, SEPTEMBER 23, 2014
11:00 a.m.– 12:00 p.m, CRB 692

The problem of finding densely connected subgraphs in a network has attracted a lot of recent interest. Such subgraphs are sometimes referred to as molecular modules in protein networks or communities in social networks. In this talk, we describe two Monte Carlo optimization algorithms for identifying the densest subgraphs with a fixed size or with size in a given range. The proposed algorithms combine the idea of simulated annealing and efficient moves for the Markov chain, and both algorithms are shown to converge to the set of optimal states (densest subgraphs) with probability one. When applied to a yeast protein interaction network, the algorithms identify interesting new densely connected subgraphs.