CS&E Seminar: Aristides Gionis - 11 June 2010 - 12.00 @ Aula Magna

Speaker: Aris Gionis (Yahoo! Research, Barcelona)

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

Abstract: A lot of research in graph mining has been devoted in the discovery of communities. Most of the work has focused in the scenario where communities need to be discovered with only reference to the input graph. However, for many interesting applications such as in social-network analysis, query-log analysis, biology, and others, one is interested in finding the community formed by a given set of nodes. In this paper we study a query-dependent variant of the community-detection problem, which we call the community-search problem: given a graph G, and a set of query nodes in the graph, we seek to find a subgraph of G that contains the query nodes and it is densely connected.
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.