A general view on computing communities

We define a community structure of a graph as a partition of the vertices into at least two sets with the property that each vertex has connections to relatively many vertices in its own set compared to any other set in the partition and refer to the sets in such a partition as communities  . We show that it is NP-hard to compute a community containing a given set of vertices. On the other hand, we show how to compute a community structure in polynomial time for any connected graph containing at least four vertices except the star graph _Sn$S_n$. Finally, we generalize our results and formally show that counterintuitive aspects are unavoidable for any definition of a community structure with a polynomial time algorithm for computing communities containing specific vertices.