  Community detection aims to reveal the community structure in a social
network, which is one of the fundamental problems. In this paper we investigate
the community detection problem based on the concept of terminal set. A
terminal set is a group of users within which any two users belong to different
communities. Although the community detection is hard in general, the terminal
set can be very helpful in designing effective community detection algorithms.
We first present a 2-approximation algorithm running in polynomial time for the
original community detection problem. In the other issue, in order to better
support real applications we further consider the case when extra restrictions
are imposed on feasible partitions. For such customized community detection
problems, we provide two randomized algorithms which are able to find the
optimal partition with a high probability. Demonstrated by the experiments
performed on benchmark networks the proposed algorithms are able to produce
high-quality communities.
