# 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? May 23, 2016 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, 2016 at 20:16
• Please edit the question to clarify what problem exactly you wish to solve.
– Raphael
May 23, 2016 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. May 24, 2016 at 11:10

## 1 Answer

If you want to find cliques, or quasi-cliques, don't expect non-overlapping communities, as their definitions imply that there might be overlap between clusters. When it comes to community detection or clustering, you need to make a formal definition of a community or cluster (in this case it is a clique). There are two types of definitions:

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.

There are lots of different techniques such as modularity optimization, seed expansion, etc. If you are looking for stricter non-overlapping community definitions, you can dig further in this paper (and the sequence of other papers) and find the one ghat works well on coefficient clustering score:

Fortunato, Santo. "Community detection in graphs." Physics reports 486.3 (2010): 75-174.

Overlapping definitions - However, some definitions such as cliques or quasi-cliques, allow overlap between clusters, even though you consider maximality. Below, I show a simple example where few maximal cliques overlap with each other (link for image).