# Densely connected non overlapping subgraph

I'm trying to detect quasi cliques in an undirected graph. My problem is that I don't want any overlap between cluster.

I'm currently trying to detect community using Louvain algorithm, but it detects subgraphs with a low clustering coefficient (0.60) and when I detect maximal or quasi cliques they tend to overlap.

How can I compute a clique decomposition of an undirected graph with no overlap between clusters ? Is there an algorithm with an implementation of it which can deal with my problem ?

Thanks

• I'm not sure what you're looking for. The input is a graph but what's the output supposed to be? A set of non-overlapping cliques? If so, what does "maximal" mean in this context? No clique can be extended and no new cliques can be added? – David Richerby May 23 '16 at 19:32
• Sorry i misused the term clique. The output is supposed to be a set of non-overlapping densely connected subgraph. A maximal clique is a clique that cannot be extended by including one more adjacent vertex. – adp7 May 23 '16 at 20:16
• Please edit the question to clarify what problem exactly you wish to solve. – Raphael May 23 '16 at 22:14
• Generally cliques allow overlaps; there are heaps of methods for detecting communities such as modularity optimization and the codes are available. You need to do some research and find the method that suits you. – orezvani May 24 '16 at 11:10

Non-overlapping definitions - There are some definitions that do not allow any overlap between communities such as $k$-cores. Basically, the following properties prevent $k$-cores of being overlapping:
1. $k$-cores are maximal
2. Union of two $k$-cores is a $k$-core.