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

A lot of research in graph mining has been devoted in the dis-covery 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 interest-ing applications 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 prob-lem, 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 de-gree and distance constraints, and we develop an optimum greedy algorithm for this measure. We proceed by charac-terizing 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