Community detection is a fundamental issue for understanding the structure of large and complex networks such as social, biological and informa- tion networks. In this paper, we propose a new approach to detect overlapping communities in large complex networks. We first introduce a parametrized no- tion of a community, called k-linked community, allowing us to characterize node/edge centered k-linked community with bounded diameter. Such commu- nity admits a node or an edge with a distance at most k 2 from any other node of that community. Next, we show how the problem of detecting node/edge cen- tered k-linked overlapping communities can be expressed as a Partial Max-SAT optimization problem. Then, we propose a post-processing strategy to limit the overlaps between communities. An extensive experimental evaluation on real- world networks shows that our approach outperforms several popular algorithms in detecting relevant communities.