Séminaire ETIS : Olgica Milenkovic

Titre et oratrice

Community Detection via Correlation Clustering And Boolean Intersection Graph Models.

Olgica Milenkovic, University of Illinois, Urbana-Champaign.

Date et lieu

Mardi 5 avril 2016, 11h.

ENSEA Cergy, salle du conseil.


Communities in complex networks are important structural components that may be characterized by large density, shared features or coevolving behavior. Community structures guide properties of the networks such as their functional behavior, rate of information spreading and dynamics. Many approaches have been proposed for community detection for random and deterministic graph models, including correlation clustering and overlapping correlation clustering. These agnostic learning methods reduce to optimization problems on graphs that are known to be NP hard, but for which efficient approximation algorithms exist. The crux behind the clustering method is to define an integer-constrained linear objective function, and approximately optimize it by using linear programming relaxations and subsequent rounding.

We introduce two new paradigms in correlation clustering involving minimax objective functions and motif partitions, useful for a number of problems in systems biology. We also describe how this framework may be extended to work for overlapping community detection via new Boolean intersection models for graphs. The proposed algorithmic approaches are tested on cancer driver networks, outperforming existing methods based on Markov Chain Monte Carlo methods.

This is joint work with Hoang Dau, Amin Emad, Jack Hou, Jian Ma, and Gregory Puleo (listed in alphabetical order).