**Speaker:** Aris Gionis (*Yahoo! Research, Barcelona*)

**Title:** *The community-search problem and how to plan a successful cocktail party *

We motivate a measure of density based on minimum degree and distance constraints, and we develop an optimum greedy algorithm for this measure. We proceed by characterizing a class of monotone constraints and we generalize our algorithm to compute optimum solutions satisfying any set of monotone constraints. Finally we modify the greedy algorithm and we present two heuristic algorithms that find communities of size no greater than a specified upper bound. Our experimental evaluation on real datasets demonstrates the efficiency of the proposed algorithms and the quality of the solutions we obtain.

This is joint work with Mauro Sozio.

**Aris Gionis** *is a research scientist in Yahoo! Research, Barcelona. He received his Ph.D from the Computer Science department of Stanford University in 2003, and between 2003 and 2006 he has been a senior researcher at the Basic Research Unit of Helsinki Institute of Information Technology, Finland. His research interests include data mining, web mining, and algorithmic data analysis. *